Lambda calculus

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


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s