Du Lambda Calcul à OCaml

1. Introduction

Imaginez un monde où tout est fonction. Les moutons sont des fonctions, les nuages sont des fonctions, et même le camembert est une fonction. Bienvenue dans le lambda-calcul !

Inventé par Alonzo Church dans les années 1930 (oui, avant votre grand-mère), le λ-calcul est le plus petit langage de programmation universel. Il ne contient strictement que :

• des variables,
• des abstractions (créer une fonction),
• des applications (appeler une fonction).

Et pourtant, avec ces trois briques, on peut TOUT calculer. Littéralement tout. Turing-complet, comme disent les gens sérieux.

OCaml, de son côté, est un langage de la famille ML (Meta-Language). Son ancêtre, le MétaLangage, a été conçu dans les années 70 pour servir de langage de programmation au système de preuve LCF. Aujourd'hui, OCaml est le fruit du travail de l'Inria (Xavier Leroy, Damien Doligez, et bien d'autres). C'est un peu comme si le lambda-calcul avait eu un enfant surdoué qui a fait des études de maths et d'informatique.

2. Fonctions & Application

Tout commence ici. La brique élémentaire du lambda-calcul, c'est l'abstraction : fun x -> ... (les puristes écrivent λx. ... mais on va laisser les grecs tranquilles).

(* La fonction la plus simple : celle qui ne fait rien *)
fun x -> x

(* Appliquée à 1 : *)
(fun x -> x) 1

On appelle fun x -> x la fonction identité. Tellement simple qu'elle en est philosophique : "rends-moi ce que je t'ai donné".

Maintenant, observons la beauté du lambda-calcul : puisque les fonctions sont juste des valeurs, on peut les passer en paramètre, les retourner, les stocker… On appelle ça des citoyens de première classe (first-class citizens). En Java, les fonctions n'ont eu le droit de vote qu'en 2014 avec les lambdas. En OCaml, elles votent depuis 1996.

(* Fonction qui prend une fonction et l'applique à 1 *)
fun f -> f 1

(* Fonction qui retourne une fonction *)
fun x -> fun y -> x

(* Composition de deux fonctions *)
fun f -> fun g -> fun x -> f (g x)

2.1 Fonctions anonymes

Regardez bien l'exemple précédent : on n'a aucun nom. Pas de def, pas de function nom. Juste fun. On appelle ça des fonctions anonymes (ou "lambda"). C'est le cœur du lambda-calcul : des fonctions sans nom qui se suffisent à elles-mêmes.

Un interlude philosophique : en lambda-calcul, les variables ne sont que des "trous" qu'on remplit par substitution. Quand on écrit (fun x -> x) 1, on substitue x par 1 dans le corps x, ce qui donne 1. C'est tout. C'est tellement simple que ça en devient beau.

2.2 Curryfication

Vous remarquerez que fun x -> fun y -> x est une fonction qui prend x et retourne… une fonction qui attend y et retourne x. C'est comme ça qu'on simule les fonctions à plusieurs paramètres dans le lambda-calcul : une fonction de deux arguments, c'est une fonction du premier argument qui retourne une fonction du second argument.

Cette technique s'appelle la curryfication (currying) et elle doit son nom à Haskell Curry, un autre logicien célèbre. (Oui, le langage Haskell porte aussi son nom. Ce type était partout.)

OCaml supporte un sucre pour ça :

(* Ces deux écritures sont rigoureusement équivalentes : *)
fun x -> fun y -> x
fun x y -> x

3. Le sucre let

Écrire (fun x -> x) 1, c'est un peu spartiate. Dans la vraie vie, on aime donner des noms aux choses. C'est là qu'intervient la construction let … in ….

En fait, let x = e1 in e2 n'est que du sucre syntaxique pour (fun x -> e2) e1. Littéralement. C'est exactement la même chose.

(* Ces trois paires sont rigoureusement équivalentes : *)

(* 1. La version lambda pure *)
(fun x -> x) 1

(* 2. Avec let *)
let x = 1 in x

(* 3. Avec let pour une fonction *)
let f = fun x -> x in f 1

(* 4. Double sucre : on "curryfie" le let *)
let f x = x in f 1

Les cas 3 et 4 montrent une évolution intéressante :

• Cas 3 : let f = fun x -> x — on donne un nom à une fonction anonyme.
• Cas 4 : let f x = x — du sucre sur du sucre ! OCaml nous permet de définir directement f comme une fonction qui prend x et retourne x.

Si on déroule complètement le sucre :

(* let f x = x in f 1 *)
(* = let f = fun x -> x in f 1 *)
(* = (fun f -> f 1) (fun x -> x) *)
(* = (fun x -> x) 1 *)
(* = 1 *)

C'est beau, non ? Tout n'est que fun déguisé.

4. Booléens de Church & if

Bon, on a des fonctions. On peut les appliquer. Mais comment on fait pour prendre des décisions ? Dans le lambda-calcul pur, il n'y a pas de true, pas de false, pas de if. Mais Church (encore lui !) a eu une idée géniale : coder les booléens avec des fonctions.

L'idée est simple :

• true est une fonction qui prend deux arguments et retourne le premier.
• false est une fonction qui prend deux arguments et retourne le second.

Et if devient alors une fonction qui applique le booléen à deux branches :

(* L'encodage de Church ! *)
let true_c  = fun t f -> t
let false_c = fun t f -> f

(* Le if de Church *)
let if_c b t f = b t f

(* Pour le plaisir, convertissons en vrais booléens : *)
let to_bool b = b true false

Testons :

if_c true_c "gagné" "perdu"
(* = true_c "gagné" "perdu" = "gagné" *)

to_bool true_c
(* = true_c true false = true *)

4.1 Opérateurs logiques

Avec nos booléens de Church, on peut aussi définir les opérateurs logiques :

* ET logique : b1 && b2 *)
let and_c b1 b2 = b1 b2 false_c
(* Si b1 est vrai, on retourne b2 ; sinon, faux *)

(* OU logique *)
let or_c  b1 b2 = b1 true_c b2
(* Si b1 est vrai, on retourne vrai ; sinon, b2 *)

(* NON logique *)
let not_c b     = b false_c true_c
(* On inverse les branches ! *)

Magnifique, non ? Et si on vérifie :

to_bool (and_c true_c false_c)  (* = false *)
to_bool (or_c  true_c false_c)  (* = true *)
to_bool (not_c true_c)           (* = false *)

À ce stade, on a des booléens qui marchent. Mais dans OCaml, on utilise les vrais booléens (true, false) et l'instruction if … then … else qui est intégrée au langage. Notez que même if pourrait être défini comme une fonction, mais OCaml en fait une construction syntaxique pour des raisons de typage et d'évaluation paresseuse.

5. Sucre infixe

Écrire and_c true_c false_c, c'est clair. Mais si on devait faire de grosses expressions logiques, ça deviendrait vite le bazar. Heureusement, OCaml permet un sucre rigolo : les opérateurs infixes.

En OCaml, on peut définir des opérateurs avec des symboles comme +, -, *, &, |, etc. Il suffit de les mettre entre parenthèses dans la définition :

(* On redéfinit nos opérateurs Church en version infixe *)
let (&) b1 b2 = b1 b2 false_c
let (|) b1 b2 = b1 true_c b2

(* Maintenant on peut écrire : *)
true_c & (false_c | true_c)
(* Au lieu de : and_c true_c (or_c false_c true_c) *)

OCaml a même des règles de précédence et d'associativité pour les opérateurs (les symboles commençant par * ou / sont prioritaires, etc.). Mais ça, c'est une autre histoire.

6. Nombres prédéfinis

À ce stade, on pourrait coder les entiers à la Church. Mais on va faire une entorse à la pureté du lambda-calcul : on va supposer qu'on a des entiers natifs et des opérateurs arithmétiques prédéfinis.

En OCaml (et dans la plupart des langages sérieux), on a donc :

42                  (* un entier *)
3 + 4               (* addition *)
10 - 3               (* soustraction *)
7 * 6                (* multiplication *)
42 / 6               (* division entière *)
5 mod 2              (* modulo *)

(* Comparaisons *)
3 = 4                (* false *)
3 <> 4               (* true (différent) *)
3 < 4                 (* true *)
3 <= 4                (* true *)

C'est pratique. Mais retenez que tout ça pourrait être encodé avec des fonctions. C'est juste… pas très efficace.

7. Récursion avec fix

On a des fonctions, des booléens, des entiers. On peut faire des calculs. Mais comment on fait une boucle ? En lambda-calcul pur, on n'a pas de while, pas de for, pas même de goto (Dieu merci). On n'a que des fonctions sans nom…

Mais alors, comment on écrit une fonction récursive sans nom ? C'est le paradoxe du lambda-calcul : pour s'appeler soi-même, il faut avoir un nom. Mais on n'a pas de noms (on a juste fun).

La solution, c'est le combinateur de point fixe, aussi appelé opérateur de récursion, aussi appelé "combinateur Y", aussi appelé "ce truc qui fait pleurer les étudiants en info".

Le combinateur Y, c'est ça :

let fix f = (fun x -> f (x x)) (fun x -> f (x x))

… et si vous avez compris du premier coup, bravo, vous êtes soit Church, soit Curry, soit vous mentez.

Voici comment ça marche (promis, c'est pas si méchant) :

• On veut une fonction récursive fact qui s'appelle elle-même.
• Plutôt que d'écrire fact directement, on écrit une fonction f qui prend fact en argument et retourne la « vraie » fonction.
• Ensuite, fix f calcule le point fixe de f, c'est-à-dire la fonction fact telle que fact = f fact.
• Et miracle… ça marche !

Regardez plutôt :

(* On définit fix une bonne fois pour toutes *)
let fix f = (fun x -> f (x x)) (fun x -> f (x x))

(* Notre "presque" factorielle : elle prend sa propre version en paramètre *)
let fact_step fact n =
  if n = 0 then 1
  else n * fact (n - 1)

(* Et fix fait le reste ! *)
let fact = fix fact_step

Testons :

fact 5

Ça marche ! 🎉

7.1 Mais comment ça marche, fix ?

Détaillons la magie :

fix f calcule f (fix f). En effet :

(* fix f = f (fix f) — le point fixe ! *)

(* Déroulons pour fact 3 : *)
(* fact 3 = fix fact_step 3 *)
(*        = fact_step (fix fact_step) 3 *)
(*        = fact_step fact 3 *)
(*        = if 3 = 0 then 1 else 3 * fact (3 - 1) *)
(*        = 3 * fact 2 *)
(*        = 3 * (fix fact_step) 2 *)
(*        = 3 * (fact_step (fix fact_step) 2) *)
(*        = 3 * (if 2 = 0 then 1 else 2 * fact 1) *)
(*        = 3 * 2 * fact 1 *)
(*        = … *)
(*        = 3 * 2 * 1 * 1 = 6 *)

8. Le mot-clé rec

Bon, fix c'est beau, c'est pur, c'est mathématique. Mais avouons-le : c'est pas super lisible. On doit écrire fact_step puis fix fact_step à chaque fois… c'est lourd.

Heureusement, OCaml nous offre du sucre syntaxique pour la récursion : let rec.

Au lieu d'écrire :

let fact_step fact n = if n = 0 then 1 else n * fact (n-1)
let fact = fix fact_step

On écrit tout simplement :

let rec fact n =
  if n = 0 then 1
  else n * fact (n - 1)

Et voilà ! let rec f x = ... est un sucre syntaxique qui permet à f de se référer à elle-même dans sa propre définition. C'est exactement comme si on écrivait let f = fix (fun f x -> ...).

On peut aussi définir des fonctions mutuellement récursives (plusieurs fonctions qui s'appellent les unes les autres) avec let rec … and … :

let rec pair n =
  if n = 0 then true
  else impair (n - 1)
and impair n =
  if n = 0 then false
  else pair (n - 1)

On peut aussi s'amuser à écrire let rec en termes de fix (cerveau qui explose) :

(* Ces deux définitions sont équivalentes : *)

(* Version sucre *)
let rec fact n = if n = 0 then 1 else n * fact (n - 1)

(* Version désucrée avec fix *)
let fact = fix (fun fact n -> if n = 0 then 1 else n * fact (n - 1))

9. Paires (Church)

On a des fonctions, des booléens, des entiers, de la récursion. Que nous manque-t-il ? Des structures de données ! Et comme on est en lambda-calcul pur (enfin, on fait semblant), on va encoder les paires… avec des fonctions, évidemment.

L'idée de Church pour les paires :

• Une paire (a, b) est une fonction qui attend une fonction de projection f et lui applique a et b.
• Le premier élément s'obtient en passant fun a b -> a (qui choisit le premier).
• Le second élément s'obtient en passant fun a b -> b (qui choisit le second).

(* L'encodage de Church pour les paires *)
let pair a b = fun f -> f a b

(* Première projection : fst *)
let fst p = p (fun a b -> a)

(* Seconde projection : snd *)
let snd p = p (fun a b -> b)

(* Testons ! *)
let p = pair 3 "hello"
let _ = fst p  (* = 3 *)
let _ = snd p  (* = "hello" *)

Regardez comme c'est élégant : pair a b = fun f -> f a b. Une paire, c'est une fonction qui "retient" ses deux éléments et attend qu'on lui dise quoi en faire. Les projections fst et snd sont juste des "instructions" qu'on donne à la paire pour extraire telle ou telle composante.

En OCaml "vrai", on utilise les n-uplets (tuples) : (3, "hello") et fst/snd n'existent pas en OCaml standard (on utilise le pattern matching). Mais conceptuellement, c'est la même idée.

On peut même définir des triplets, quadruplets, etc. :

(* Pour les courageux : un triplet Church *)
let triple a b c = fun f -> f a b c
let proj1 t = t (fun a b c -> a)
let proj2 t = t (fun a b c -> b)
let proj3 t = t (fun a b c -> c)

10. Listes (Church) & match

On a des paires. Maintenant, on veut des listes (chainées). Une liste, c'est soit :

• la liste vide (nil), soit
• un élément suivi d'une autre liste (cons h t).

Church encode les listes comme des fonctions qui attendent deux arguments :

• un cas de base n (pour nil),
• un cas récursif c (pour cons).

C'est exactement le principe du fold (ou réduction). Une liste de Church, c'est une fonction qui "sait se plier".

(* Liste vide : retourne le cas de base "n" *)
let nil = fun n c -> n

(* Cons : construit une liste avec tête h et queue t *)
(* On appelle c h (t n c) pour "plier" la tête puis la queue *)
let cons h t = fun n c -> c h (t n c)

(* Exemple : liste [1; 2; 3] *)
let lst = cons 1 (cons 2 (cons 3 nil))

Pour visualiser ce qu'on a construit, on peut écrire une fonction to_list qui convertit une liste Church en liste OCaml :

(* fold_right sur une liste Church *)
let fold lst n c = lst n c

(* Convertir une liste Church en liste OCaml *)
let to_list lst = lst [] (fun h t -> h :: t)

(* Testons ! *)
to_list lst  (* = [1; 2; 3] *)

(* Longueur d'une liste Church *)
let length lst = lst 0 (fun _ n -> n + 1)

(* Concaténer deux listes Church *)
let append l1 l2 = l1 l2 cons

On peut aussi extraire la tête et la queue, mais attention :

(* Attention : head et tail ne marchent pas sur liste vide ! *)
let head lst = lst (failwith "empty") (fun h _ -> h)
let tail lst = lst (failwith "empty") (fun _ t -> t)

10.1 Enfin match !

Bon, manipuler les listes avec lst n c, c'est puissant, mais c'est pas ce qu'on peut appeler "intuitif". Heureusement, OCaml a des types algébriques de données (Algebraic Data Types, ADT) — mais c'est un autre cours — et l'instruction match pour faire du pattern matching.

Le match est le sucre syntaxique ultime pour déstructurer des données. Au lieu d'écrire lst n c, on écrit :

(* OCaml a des listes natives avec [] et :: *)
let ma_liste = [1; 2; 3]

(* Pattern matching avec match *)
let sum lst =
  match lst with
  | [] -> 0
  | h :: t -> h + sum t

C'est tellement plus clair ! On voit immédiatement les deux cas : liste vide ou liste non vide.

En fait, le pattern matching est tellement pratique qu'on l'utilise partout en OCaml :

(-- Avec des tuples (n-uplets) --)
let fst p = match p with (a, _) -> a
let snd p = match p with (_, b) -> b

(* Avec des types personnalisés *)
type 'a mylist =
  | Nil
  | Cons of 'a * 'a mylist

let sum2 lst =
  match lst with
  | Nil -> 0
  | Cons (h, t) -> h + sum2 t

Vous remarquerez la correspondance parfaite avec notre encodage de Church :

• Nil correspond à nil = fun n c -> n (on rend le cas de base)
• Cons (h, t) correspond à cons h t = fun n c -> c h (t n c) (on combine la tête et la queue)

10.2 Exemples concrets

Un petit florilège de pattern matching sur les listes :

(* Fibonacci récursive *)
let rec fib n =
  match n with
  | 0 -> 0
  | 1 -> 1
  | _ -> fib (n - 1) + fib (n - 2)

(* Map sur une liste *)
let rec map f lst =
  match lst with
  | [] -> []
  | h :: t -> f h :: map f t

(* Filtrer une liste *)
let rec filter p lst =
  match lst with
  | [] -> []
  | h :: t -> if p h then h :: filter p t else filter p t

Tous ces exemples pourraient être réécrits en utilisant l'encodage de Church des listes. Mais franchement, pourquoi se priver du match ?

11. Conclusion

Vous venez de faire un voyage du lambda-calcul le plus pur (juste fun) jusqu'aux constructions élégantes d'OCaml (let, let rec, match).

Récapitulons le chemin parcouru :

Ce qu'il faut retenir :

1. Tout n'est que fonction. Le lambda-calcul le prouve : avec juste fun et l'application, on peut coder l'intégralité de l'informatique.
2. Le sucre syntaxique, c'est la classe. OCaml n'ajoute pas de nouveaux pouvoirs magiques — il rend juste les choses plus lisibles. let, if, match, let rec sont des habillages élégants du lambda-calcul.
3. Church et Curry étaient des génies. Leurs encodages sont encore étudiés aujourd'hui, et leur influence se ressent dans tous les langages fonctionnels modernes (Haskell, OCaml, Scala, F#, Elixir…).

"Le lambda-calcul est à la programmation fonctionnelle ce que la roue est au transport : simple, élégant, et personne n'aurait dû mettre autant de temps à l'inventer."

Fait avec ❤️ et beaucoup de λ