La lambda calcul est un langage où tout est fonction. En effet, il n'y a rien d'autre, pas de nombres, booleens, conditions, comparaisons, boucles... Etonnament tout reste possible, le langage et tout aussi expressif.

En informatique, tout est question de représentation, disons par exemple qu'on représente un nombre "n" comme la fonction qui applique "n" fois une seconde fonction à une troisième. Le tour est joué. Voyons comment reconstruire tout ce qu'il nous faut.

Le Lambda calcul est aux languages "fonctionnels", ce que la machine de Turing est aux languages impératifs.

1. Définition de fonction

   "variable"."resultat"

   exemple : l'identité

   x.x

2. Application d'argument

   "fonction" "argument"

   exemple : f(x)

   f x

3. affectation

   "identifiant" = "valeur" "reste"

   exemple : x = a dans x

   x = a x

a.b.c

a.(b.c)

a b c

(a b) c

a = f x

(a = f)
x

On définit un nombre n comme la fonction qui à "f" et "x" applique n fois f à x.

0 = f.x.x
1 = f.x.(f x)
2 = f.x.(f (f x))
next = n.f.x.(f (n f x))
3 = (next 2)
3

1 = f.x.(f x)
2 = f.x.(f (f x))
addition = a.b.f.x.(a f (b f x))
4 = (addition 2 2)
addition 4 4

0 = f.x.x
1 = f.x.(f x)
2 = f.x.(f (f x))
multiplication = a.b.f.(a (b f))
4 = (multiplication 2 2)
multiplication 4 4

0 = f.x.x
1 = f.x.(f x)
2 = f.x.(f (f x))
exponential = a.b.(b a)
4 = (exponential 2 2)
exponential 4 4

true = x.y.x
false = x.y.y
pair = x.y.f.(f x y)
first = p.(p true)
second = p.(p false)
0 = f.x.x
1 = f.x.(f x)
2 = f.x.(f (f x))
next = n.f.x.(f (n f x))
3 = (next 2)
itere = n.u.v.(n u v)
nn = p.(pair (second p) (next (second p)))
pred = n.(first (itere n nn (pair 0 0)))
pred 3

true = x.y.x
false = x.y.y
pair = x.y.f.(f x y)
first = p.(p true)
second = p.(p false)
0 = f.x.x
1 = f.x.(f x)
2 = f.x.(f (f x))
next = n.f.x.(f (n f x))
3 = (next 2)
itere = n.u.v.(n u v)
nn = p.(pair (second p) (next (second p)))
pred = n.(first (itere n nn (pair 0 0)))
minus = a.b.(itere b pred a)
minus 3 2

false = x.y.y
true = x.y.x
false

true = x.y.x
false = x.y.y
ifthenelse = c.a.b.(c a b)
and = a.b.(ifthenelse a b false)
or = a.b.(ifthenelse a true b)
or true ( and true false)

true = x.y.x
false = x.y.y
ifthenelse = c.a.b.(c a b)
ifthenelse false valueTrue valueFalse

true = x.y.x
false = x.y.y
pair = x.y.f.(f x y)
first = p.(p true)
second = p.(p false)
first (pair a b)