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
Attention à la priorité des opérateurs
a.b.c

est équivalent à

a.(b.c)
a b c

est équivalent à

(a b) c
a = f x

est équivalent à

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

Input

Reformulation

Output