# Functional Programming

Overview of the lambda calculus and Scheme.

Lecture slide: click here

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

## λ-Calculus

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

### Syntax

ç-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))`

)

### Free and bound variables

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*.

### α-conversion

Renaming bound variables. Usually used to avoid name collision.

### β-reduction

Applying the argument and calling the function.

`[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`

.

### Normal form

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.

### Evaluation strategies

Slide page 7

For example, `(λx.λy.yxx)((λx.x)(λy.z))`

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

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

**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.

### η-reduction

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

### Computational power

The untyped λ-calculus is Turing complete.

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

**Booleans**:

**Arithmetic**:

Some numerals

Some operations

Iteration

## Scheme overview

Yet Another Scheme Tutorial (Chinese)

`symbol?`

`number?`

`pair?`

`list?`

`null?`

`zero?`

### List

`(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.

#### List decomposition

`(cadr xs)`

is `(car (cdr xs))`

`(cdddr xs)`

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

#### List building

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

### Quoting data (`'...`

)

`'...`

)`quote`

or `'`

to describe data.

### Booleans

`#t`

: true.
`#f`

: false.

Any value not equal to `#f`

is considered to be true.

### Simple control structures

#### Conditional

#### Generalized form

### Global definitions

`define`

is a special function that only can be used at the top level to create global variables.

### Locals: `let`

, `let*`

and `letrec`

`let`

, `let*`

and `letrec`

Basic `let`

skeleton:

Last updated