La maïeutique du lambda-calcul

Pensez-vous que les humains ont découvert ou bien inventé l'informatique ?

Je penche pour la découverte, car la Machine de Turing et le Lambda-Calcul de Church ont été formalisés indépendamment l'un de l'autre en 1936, et pourtant tous deux sont aussi universellement expressifs (permettant de tout calculer). Fort différents, mais 100% équivalents.

Je ne parle pas de l'invention de l'ordinateur matériel, qui peut prendre toutes les formes et implémenter généralement ces concepts grâce à des circuits électroniques et leurs transistors. Je parle ici de la logique calculatoire et de la pensée computationnelle qui l'accompagne : celle-là flottait dans l'air en attendant d'être attrapée et mise en cage.

Comme au lycée

Rappelons-nous nos cours de maths, en particulier les fonctions :
Soit f(x) = 2*x, une fonction qui multiplie par 2 la valeur qu'on lui passe. Nommons-la Double.

Donc Double(3) = 2*3 = 6
Et Double(4) = 2*4 = 8.
Facile.

Idem pour f(x) = x 1, ou Increment.

Increment(3) = 3 1 = 4
Increment(4) = 4 1 = 5
Très facile.

Le lambda-calcul

Le lambda-calcul peut s'écrire de la même manière :
f(x) = x est par exemple une fonction qui retourne la valeur qu'on lui passe.
Cette fonction s'appelle I, ou Idiot ou encore Identity, et est une des fondations du lambda-calcul.

Donc Identity(3) = 3
Et Identity(4) = 4.
Trop facile.

Il y en a d'autres, moins évidentes, mais dont le lambda-calcul a découvert l'utilité :
f(x, y) = x est K, Kestrel, ou Constant : une fonction qui retourne son premier argument.

Constant(3, toto) = 3
Constant(toto, 5) = toto

En voici une autre :
f(x) = x(x) est M, Mockingbird ou Self-Apply.

Mais elle est trop tordue pour qu'on puisse l'utiliser avec un nombre :
f(3) = 3(3) = 3 n'a aucun sens, l'argument 3 devrait être une fonction pour pouvoir être utilisé à son tour avec un argument.

g(x) = toto voici une fonction qui retourne toto à tous les coups ! Chouette, appelons-la Dummy.

Donc si Self-Apply est f(x) = x(x)
Et Dummy est g(x) = toto

Alors Self-Apply(Dummy) = Dummy(Dummy) = toto
Bah oui, Dummy s'applique à lui-même, et comme Dummy retourne toujours toto, on obtient toto in fine.

La magie commence

La nature combinatoire du lambda-calcul le rend très simple à comprendre et à manipuler, mais aussi à redécouvrir.
Il suffit de tester toutes les associations et combinaisons possibles, avec un certain nombre de termes, pour trouver toutes les fonctions vraiment différentes et utiles.

Par exemple, on a découvert que f(x, y, z) = x(y(z)) était une fonction très utile, et on l'a appelée B, Bluebird ou Compose.
Il suffit de lui passer 2 fonctions et une valeur pour obtenir le résultat de cette chaîne d'opérations faite sur ce 3ème argument.

Compose(Increment, Increment, 3) = Increment(Increment(3)) = Increment(4) = 5
Compose(Double, Double, 10) = Double(Double(10)) = Double(20) = 40
Compose(Compose(Increment, Increment), Double, 10) = (Compose(Increment, Increment))(Double(10)) = Increment(Increment(20)) = Increment(21) = 22

Un projet un peu fou

Je me lance dans le projet de redécouvrir toutes les fonctions utiles du lambda-calcul et de les implémenter en JavaScript.
Je vais me faire aider par un ami, Claude, pour avancer plus vite en générant toutes les possibilités de combinaisons et en les testant.

Va-t-il réussir ? Et nous, allons-nous revivre et ressentir ce qu'a traversé Alonzo Church en 1936 ?

Espoir plus fou encore: peut-on découvrir des nouveautés en recherchant l’exhaustivité de ces combinaisons ?

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!