What is the Lambda Calculus?

Turing Machine

Turing Machines

Lambda-Calculus

Lambda-Calculus

Abstraction

Application

Application Example

Application

Abstraction Again

Goal

Values

Church-Rosser theorem

Undefined Values

Currying

Currying

Boolean Values

Boolean Value Example

Boolean Value Example

Data Structures

Ordered Pairs

Ordered Pair Example

Ordered Pair Example

Numbers

Number Example

Arithmetic

Recursion

Fixed Points

``I think you should be more explicit here in step two...''

Return from Digression

OK, We're Done

Building an Interpreter

There's a Catch

Applicative Order Solution

Applicative Order Solution

IMG:lambda-4.gif:-Calculus in Perl