# Functional Programming

Overview of the lambda calculus and Scheme.

Readings: Scott, ch. 10 (including 10.6.1 on the CD), Dybvig ch. 1,2 (optional)

A Turing complete model of computation that has its syntax and reduction rules. It is the basis for functional languages.

ç-calculus has variables, abstraction and application.

**Variables**: lower-case letters. Such as

`x`

.
**Abstraction**: (definition of function)

`λx.M`

, `x`

being the function parameter, `M`

being the function body.
**Application**: (invocation of function)

`M N`

. Call function `M`

with the argument `N`

.Abstraction is

*right-associative*, application is*left-associative*. And application has precedence over abstraction. (For example,`λx. y λx. z`

means `λx.(y (λx.z))`

)In term

`λx.M`

, the scope of `x`

is `M`

. So, we call `x`

bound in `M`

. The variables that are not bound are *free*.Renaming bound variables. Usually used to avoid name collision.

λy.(...y...) → λw.(...w...)

Applying the argument and calling the function.

(λx.M) N → [x→N]M

`[x→N]M`

means `M`

with all bound occurences of `x`

replaced by `N`

.
**Restriction**:

`N`

should not have any free variables which are bound in `N`

.An expression that cannot be β-reduced any further is a normal form.

Not everything has a normal form. For example,

`(λz.z z)(λz.z z)`

reduces to itself which will result in infinite application.Slide page 7

For example,

`(λx.λy.yxx)((λx.x)(λy.z))`

- 1.normal-order: reduct the outermost "redex" first.

[x→(λx.x)(λy.z)](λy.yxx) → λy.y((λx.x)(λy.z))((λx.x)(λy.z)

2.applicative-order: arguments to a function evaluated first, from left to right.

(λx.λy.yxx)([x→(λy.z)]x) → (λx.λy.yxx)((λy.z))

**Some observations:**

- If a lambda reduction terminates, it terminates to the same reduced expression regardless of reduction order.
- If a terminating lambda reduction exists, normal order evaluation will terminate.

η(eta)-reduction is used to eliminate useless variables.

(λx.M x) → M

The untyped λ-calculus is Turing complete.

**Numbers and numerals**: number is an abstract idea, numeral is the representation of a number.

**Booleans**:

TRUE ≡ λa.λb.a

FALSE ≡ λa.λb.b

IF ≡ λc.λt.λe.(cte)

AND ≡ λm.λn.λa.λb.m(nab)b

OR ≡ λm.λn.λa.λb.ma(nab)

NOT ≡ λm.λa.λb.mba

**Arithmetic**:

Some numerals

⌜0⌝ ≡ λfx.x

⌜1⌝ ≡ λfx.fx

⌜2⌝ ≡ λfx.f(fx)

⌜3⌝ ≡ λfx.f(f(fx))

Some operations

ISZERO ≡ λn.n(λx.FALSE)TRUE

SUCC ≡ λnfx.f(nfx) // n+1

PRED ≡ λn.n(λgk.(g⌜1⌝)(λu.PLUS(gk)⌜1⌝)k)(λv.⌜0⌝)⌜0⌝ // n-1

PLUS ≡ λmnfx.mf(nfx) // m+n

MULT ≡ λmnf.m(nf) // m*n

EXP ≡ λmn.nm // n^m

Iteration

MUL = λmn.m (ADD n) 0

EXP = λmn.m (MUL n) 1

`symbol?`

`number?`

`pair?`

`list?`

`null?`

`zero?`

`(cons 'a '(b))`

=> list `(a b)`

`(cons 'a 'b)`

=> dotted pair `(a . b)`

`car`

: get head of list.
`cdr`

: get rest of list.
`cons`

: perpend an element to a list.
`'()`

: null list.(car '(this is a list of symbols))

=> this

(cdr '(this is a list of symbols))

=> (is a list of symbols)

(cdr '(this that))

=> (that) ; a list

(cdr '(singleton))

=> () ; the empty list

(car '())

=> Error: car expects argument of type<pair>; given()

`(cadr xs)`

is `(car (cdr xs))`

`(cdddr xs)`

is `(cdr (cdr (cdr xs)))`

(cons 'this '(that and the other))

=> (this that and the other)

(cons 'a '())

=> (a)

shortcut:

`(list 'a 'b 'c 'd 'e)`

`quote`

or `'`

to describe data.(quote (1 2 3 4))

(quote (Baby needs a new pair of shoes))

'(this also works)

`#t`

: true.
`#f`

: false.Any value not equal to

`#f`

is considered to be true.(if condition expr1 expr2)

(cond

(pred1 expr1)

(pred2 expr2)

...

(else exprn))

`define`

is a special function that only can be used at the top level to create global variables.; (define name value)

(define x 15)

(define sqr (lambda (n) (* n n))

; (define (name ...parameters) body)

(define (sqr n) (* n n))

Basic

`let`

skeleton:(let

((v1 init1) (v2 init2) ... (vn initn))

body)

Last modified 4mo ago