Lecture Notes 2: Introduction to Lambda Calculus

Turing machine

Lambda calculus, alonzo church (1930), is a universal computational method, similar to the turing machine.

Lambda caluclus is important as theorotical fondation of many functional programming including haskell, lisp, rust iterators, etc.

The Syntax

• variable: x, y, z
• abstraction: \(\lambda x. M\) which is a function with a body M
• application: (M N), function M applied to argument N

Example:

\[f(x) = x + 10\] \[\lambda x. x+10\]

Identity function

\[\lambda x. x\]

Betha-reduction

operation that allows us to simplify or evaluate lambda expression. It is applying a function to its arguments.

\[(\lambda x. x+10) \: 5\] \[(x+10) \: [x:=5]\] \[5 + 10 = 15\]

Alpha-conversion

The problem in lamdba calculus (y is free variable):

\[(λx.λy.x)y\]

with the \(\alpha-conversion\), the dependent variable \(\lambda y\) is converted into \(z\) which becomes:

\[(λx.λz.x)y\]

Currying

Functions with multiple arguments are treated as a series of single-argument function.

\[\lambda x y . x + y\] \[(\lambda x. (\lambda y. x + y))\] \[(\lambda x. (\lambda y. x + y))\: 5 \: 10\] \[(\lambda y. 5+y) \: 10\] \[5+10=15\]

Defining TRUE and FALSE

Turing Machine: single bit

Below are the lambda expression for TRUE (T) anda FALSE (F)

\[T:= \lambda xy.x := (\lambda x. (\lambda y. x))\] \[F:= \lambda xy.y := (\lambda x. (\lambda y. y))\] \[NOT:= \lambda z. z F T\] \[NOT \: TRUE := (\lambda z. z F T)\] \[z F T [z:=T]\] \[TFT\] \[\lambda xy. x F T\] \[(\lambda x. (\lambda y. x)) F T\] \[\lambda y. x [x:=F] T\] \[x [x:=F; y:=T]\] \[F\]

how about NOT TRUE?

AND operator

\[AND:=\lambda xy. (x y F)\]

how if AND operator receive TRUE and FALSE?

Exercise

Try to create lambda expression for OR and XOR