Y-Combinator en PHP

le 25 avril 2023

La présentation liée à l'article :

Présentation du Y-Combinator

Pour faire un peu d'auto-promotion, j'avais présenté un talk sur le Railway-Flow-Based-Programming récemment renommé en Flow. C'est un système de pipeline qui fait s'emboiter les processus les uns après les autres. Sans rentrer trop dans les détails, je vous invite à revoir le talk que j'avais donné à l'AFUP Rennes. Il me manquait quelque chose dans cette conception qu'il manquait à ce modèle. C'est ce qu'on l'on retrouve dans tous les langage de programmation objet et ici c'est de savoir comment introduire de la récursivité. C'est ce que propose le Y-Combinator, c'est à dire comment introduire de la récursivité dans un langage qui n'a pas de mécanisme de recursion.

Alors pourquoi se poser une telle question alors qu'on a déjà des notions de récursivité en PHP. Ici on a un exemple itératif et fonctionnel de cette récursivité si je prends pour exemple la fonction de factorial.

Et bien dans cet exemple, si je prend un système de pipe schématisé sous cette forme et encodée en PHP, je n'ai pas cette notion de récursivité. En effet, sur ce simple schéma, je vais aller de haut en bas mais jamais je pourrais avoir une manière de revenir en arrière grâce à une forme de récursivité. C'est cette notion qui manque dans cette notation afin de pouvoir écrire n'importe quel type de programme.

Avant de parler de ce concept, nous allons devoir introduire le concept sous-jacent qu'est le Lambda Calculus. On va alors parler de trois choses : qu'est ce que c'est, pourquoi c'est utile et d'où est ce que ce concept viens. On va d'abord s'intéresser aux origines du Lambda Calculus.

Voici Alozon Church qui était un mathématicien dans l'université de Princeton aux États Unis. Il est la personne qui a inventé le lambda-calculus. Ce qui l'intéressait était de savoir quelle est la notion de fonction dans le domaine du calcul informatique.

Ce qui est interessant c'est qu'il a été le superviseur de Alan Turing, vous connaissez sans doute, c'est la personne qui a inventé la machine de Turing qui est la base de toute l'informatique. Ce qui est remarquable c'est que La machine de Turing est un modèle à état et le concept fonctionnel Lambda-Calculus sont tous les deux des modèles équivalents. C'est ce qu'on appelle la thèse Church-Turing.

Pour Church, une fonction est une boite noire qui ne permet pas de regarder à l'intérieur. Ce qu'elle fait c'est de prendre des inputs puis d'en sortir des output. Dans notre cas, nous avons X en entrée et la boite noire va produire X+1. Aussi on introduit la notation lambda qui représente ce fonctionnement. Ici on a la représentation λ x . x + 1 traduit sous la forme lambda de X produit X + 1. Et on peut substituer avec des variables, si je prends 5, alors 5 appliqué à (λ x . x + 1) devient (λ x . x + 1) (5) = 5 + 1 = 6.

Maintenant on peut aussi prendre l'exemple avancé avec deux entrée X et Y. Et a travers la boite noire, on va produire X+Y par exemple. Deux points important ici :

  • nous avons des fonctions dite boite noire pour lesquels nous ne pouvons pas savoir comment elles fonctionnent à l'intérieur. Dit d'une autre manière on peut mettre quelque chose en entrée et voir quel sera le résultat en sortie.
  • nous avons des fonction pures, c'est à dire qu'elle n'ont pas d'état interne, tout se produit lorsque l'on introduit des paramètres en entrée qui ressortent les mêmes résultats.

Dans le lambda-calcul, on retrouve des éléments concernant les déclarations de variables, une manière de construire des fonctions et finalement un écosystème qui reste inclus dans lui même. Tout ce qui sera dérivé du lambda-calcul sera construit à partir de ce propre language.

Quels sont les cas simple appliqués au lambda calculus. Ici, comment je code true ? Comment je code false ?

En PHP classique, on aurait une implémentation tel qu'on la connait habituellement avec un if. Alors comment va-t-on représenter cette forme dans la notation lambda ? Une idée ? Dans la notation lambda, c'est pas exactement cela, comme on se place dans un environnement fonctionnel, il faut traduire qu'un élément est transformé en vrai ou faux selon l'application de la fonction lambda.

Ce qui nous donne sans rien inventer, en lambda, true et false est représenté de la sorte :

True = λ x . λ y . x et False = λ x . λ y . y

Pour traduire, si l'on a deux elements x et y en entrée, alors pour true, on ne produit que x. De même pour false, avec deux elements x et y en entrée, alors on ne produit que y.

On pourrait avoir une représentation traduite de la sorte en PHP. Je vais décrire une fonction true et false qui prennent en argument deux éléments que l'on assimile à x et y et l'on retourne respectivement x et y en résultat.

De même comment implémente-t-on la la négation à savoir not ?

En PHP classique, nous aurions une variable booléenne et on applique l'opérateur "point d'exclamation" devant la variable qui applique la négation de la valeur et est affectée à la variable $not.

En lambda-calculus, on va avoir la représentation suivante :

Not = λ b . b False True

Cette représentation je ne l'ai pas inventée et n'est pas intuitive à comprendre au premier abord, nous allons la décomposer et voir ensemble comment elle s'applique.

Lorsqu'on applique une valeur True à la représentation, alors on va l'appliquer cette valeur en interpretant b en True ce qui nous donne True False True. Cependant, nous avons vu plus haut que True était λ x . λ y . x En appliquant cette représentation à False et True en paramètre, on obtient alors x qui se substitue à False et y qui se substitue à True. Or le résultat est x, donc on obtient tout simplement False.

Si on devait représenter not en PHP, alors on obtiendrait $not une fonction de paramètre attendant un boolean $true ou $false et prend en argument $true et $false. Ici on a les fonction $true et $false que nous avons énuméré dans les définitions précédentes.

Maintenant que l'on a défini des éléments du langage Lambda, revenons à cette notion de récursivité et prenons un exemple de la fonction récursive Factorielle. La récession est l'idée de définir des éléments en terme d'eux même. La manière dont fonctionne Factorial est de donner un nombre comme par exemple 3. Et il y aura un décompte de 3 à 1 en multipliant tous les nombres entre eux. Par définition, si je prends la factorielle de 3, on aura Factorielle de 3 est 3 * 2 * 1 = 6 On peut alors se demander comment définir cette fonction. Il se trouve que la fonction Factorial a une définition simple et naturelle grâce à la recursion, c'est à dire définir une fonction en terme d'elle même.

Autrement dit, on peut écrire la factorielle de n'importe quel nombre n étant :

  • 1 si n est 1
  • n * fac(n - 1) si n est plus grand que 1

C'est la multiplication du nombre n par le factoriel de son prédécesseur.Nous venons de définir une fonction récursive, car Factorial est alors définie en terme d'elle même.

Voici un exemple simple de son execution, afin de mieux comprendre comment cela fonctionne. Ce qui nous donne en décomposant la factorielle en executant de manière récursive.

Fac(3) = 3 * Fac(2) = 3 * 2 * Fac(1) = 3 * 2 * 1 = 6

Nous venons de voir que la clef de la recursion est de définir une fonction qui se définie à travers elle même. La question est maintenant de savoir comment on défini la recursion dans un langage qui n'a pas d'éléments de langage sur la recursion. Pour cela on va se placer dans la plus simple des définitions que l'on pourrait penser, ce serait d'écrire une représentation de la fonction Loop, un fonction qui s'appelle elle même.

On peut partir du principe en lambda que Loop va s'appliquer à elle même et donc Loop = Loop. Si l'on essaye d'executer cette fonction, quelle serait la valeur de Loop, en se référent à sa c'est simplement Loop, donc l'application de Loop, nous mêne à Loop et c'est de cette manière que l'on construit la récursivité. Comment peut-on alors encoder cette définition en représentation dans le langage lambda calculus?

Pour donner la solution, on calcule

Loop = ( λ x . x . x ) ( λ x . x . x )

La clef derrière cette formule est "self-application". C'est l'idée d'appliquer quelque chose à elle même, et dans notre cas, appliquer une fonction à elle même. Encore une fois cette formule qui sort un peu du chapeau peut s'expliquer pas à pas. La première chose à observer est que l'on a deux fonctions ici et dans notre cas, deux copies de la même fonction. Si nous regardons la fonction à gauche et celle à droite, ce sont exactement les deux mêmes fonctions.

Ce que l'on va faire ici est d'appliquer la fonction al elle même. C'est l'idée du "self-application" que l'on vient de mentionner et c'est la clef pour faire de la récession dans un langage qui n'a pas de recursion. Que donne l'execution ? Si l'on se place en tant que fonction, la première fonction prend un input, comme x et dit ce qu'elle va produire comme résultat avec x. Dans notre cas, la fonction prend un x et en produit deux copies côtes à côtes. Dans le cas présent, x est représenté par ( λ x . x . x ) en tant qu'argument de la fonction ( λ x . x . x ). Si on applique ( λ x . x . x ) en argument à elle même, alors on va substituer deux fois les x dans la formule à la valeur ( λ x . x . x ).

Ainsi la formule devient

Loop = ( λ x . ( λ x . x . x ) . ( λ x . x . x ) ) = ( λ x . x . x ) ( λ x . x . x )

Et Loop est égale à la valeur précédente, on a bien cette notion de récursivité. Nous venons de vois que l'on retombe sur exactement la même représentation vu plus haut. Et à nouveau, on peut executer le processus à l'infini, si on ré-applique la fonction avec elle même, on retombe de manière infinie sur le même résultat. De cette manière nous venons de définir cette idée de boucle.

De manière plus générale, nous allons chercher une représentation de la fonction qui s'appelle récursivement elle même ? Dans notre cas, nous souhaitons trouver une formule de la forme

Y ( f ) = f ( Y ( f ) ) = f ( f ( f ( f ( ... ) ) ) )

Que fait cette définition, nous pouvons voir dans un premier temps que Y ( f ) est récursive, car Y ( f ) est définie dans les terme de sa propre définition Y ( f ). Mais, ce n'est pas seulement une boucle à travers Y ( f ), mais une boucle à travers f. Donc si on étend son execution on aura l'appel infini f ( f ( f ( f ( ... ) ) ) ). C'est ce qu'on appelle la récession général, c'est le pattern le plus général que vous pouvez trouver. Et toute fonction peut être encodée en terme de celle ci. Donc, si nous pouvons définir Y dans le lambda calculus, alors nous pouvons définir n'importe quelle fonction récursive.

Quelle valeur on va trouver dans Y pour la fonction Loop ?

Pour cela on va reprendre un peu ce qu'on a mentionné plus haut avec Loop. On va chercher Loop = Y ( λ x . x ) qui en s'executant devient ( λ x . x ) ( Y ( λ x . x ) ) et boucle sur elle même en devenant elle même et garde la même forme à savoir ( λ x . x ) ( Y ( λ x . x ) )

Qu'en est-il pour la fonction factoriel Fac en fonction de Y ?

Si je reprends la fonction factorielle, on aura un résultat qui ne s'invente pas, c'est Fac = Y ( λ f . λ n . ? ) et ce qu'on trouve dans "?" c'est max(n , 1) * fac( n - 1 ). Alors on écrira la factorielle dans sa représentation récursive Fac = Y ( λ f . λ n . max(n , 1) * fac( n - 1 ) )

De manière générale, toute fonction récursive s'écrit sous la forme

Y = λ f ( λ x . f ( x x ) ) ( λ x . f ( x x ) )

C'est une définition possible parmi toutes les définitions de Rec dans le langage du lambda calculus. Et c'est quelque chose que l'on appelle Y-Combinator. Ce qui est remarquable, c'est que l'on retrouve dans sa définition des éléments de Loop en terme de structure, c'est l'idée que l'on retrouve avec le principe de "self-application". Rec n'est pas récursive, mais encode la récursion.

Maintenant revenons en PHP. voici le code PHP de la fonction Y-combinator qui prend une fonction $F en paramètre, et $Y est la fonction Y-Combinator en PHP qui aura la définition suivante

$Y = fn(Closure $f) => $U(fn(Closure $x) => $f(fn(Closure $y) => $U($x)($y)));

Mais ce n'est qu'une des représentation en PHP que l'on peut en faire, il existe aussi un autre dépôt loophp qui décrit le Y-combinator d'une manière tout aussi élégante en programmation orientée objet. A noter que dans ce dépôt, on va retrouver d'autres types de lambda-calculus, je vous invite à regarder le dépôt : https://github.com/loophp/combinator

Un autre dépôt qui est interessant est celui de igorw. Lui va définir le langage lambda en PHP et on peut écrire directement les fonctions comme $true, $false, $not, $fact ou $Y que l'on a vu précédemment.

Fun fact. Savez vous d'où vient la société Y-Combinator ? C'est une société qui aide à entreprendre, car elle itère la création de société.

Ressources liées à l'article