Lambda calculus is a theoretical programming language (with same expressive power as a Turing Machine). It is interesting because there is no state, and it consists only of two operators: . and λ.

If you want to learn more, visit the Wikipedia article http://en.wikipedia.org/wiki/Lambda_calculus as this will be only a short introduction.

So, since we have no state, we have no variables. We only have constants. Numbers are defined like:

1 := λf x. f x

2 := λf x. f (f x)

In other words, we can define 1 as f(x), and 2 as f(f(x)) (we get to define f and x ourselves).

Functions in lambda fall in two categories: abstraction and application.

Abstraction is when we define a function and apply no arguments to it.

Application is when we apply arguments to some abstraction (already defined function).

SUCC (successor) example:

SUCC is defined as

SUCC := λnfx. f (n f x)

So, doing SUCC 1 we get

(λnfx. f (n f x))(λf x. f x) =

λfx = f ((λf x. f x) f x) = f (f x) = 2

### Like this:

Like Loading...

## One thought on “Lambda calculus”