lambdaway

6 | list | login |load

| |

{uncover data/simplet.jpg 300 1000 As simple as that!}

_h1 The why of Y | ([[english version|?view=Y_en]])

_p Je lis [[The Why of Y|https://www.dreamsongs.com/Files/WhyOfY.pdf]] un article dans lequel, utilisant le langage Scheme, Richard P.Gabriel tente de m'expliquer les beautés du {b Y-combinateur} et je n'y comprends rien.

_p En revanche quand je résume ses quatre pages ainsi :

{pre 
_h2 1) global version
'{def F            
 {lambda {:f :n}
  {if {< :n 1} 
   then 1 
   else {* :n {:f :f {- :n 1}}}}}}
-> {def F
 {lambda {:f :n}
  {if {< :n 1} then 1 else {* :n {:f :f {- :n 1}}}}}}

'{def Y {lambda {:f :n} {:f :f :n}}}
-> {def Y {lambda {:f} {:f :f}}}

'{{Y F} 10}
-> {{Y F} 10}
_h2 2) local version
'{let { {:f {lambda {:f :n} 
             {if {< :n 2} 
              then 1 
              else {* :n {:f :f {- :n 1}}}}}}
       {:y {lambda {:f} {:f :f}}}
     } {{:y :f} 10} 
}
-> {let { {:f {lambda {:f :n} 
             {if {< :n 2} 
              then 1 
              else {* :n {:f :f {- :n 1}}}}}}
       {:y {lambda {:f} {:f :f}}}
     } {{:y :f} 10} 
}
_h2 3) IIFE version
'{{lambda {:y :f} {{:y :f} 10} }
 {lambda {:f :n} {:f :f :n}} 
 {lambda {:f :n} {if {< :n 2} then 1 else {* :n {:f :f {- :n 1}}}}} }
-> {{lambda {:y :f}
  {{:y :f} 10} 
 } {lambda {:f} {:f :f}} 
   {lambda {:f :n} {if {< :n 2} then 1 else {* :n {:f :f {- :n 1}}}}} }
}

_p ... j'écris sous plusieurs formes un code (inter)actif, il fonctionne dans la page wiki, je peux le tester ... et {b je comprends} ce que fait le Y-combinateur.

_p Je comprends qu'on a simplement ajouté à la forme récursive de la fonction factorielle un nouvel argument {b :f}, agissant comme un {b point fixe} qui sera appelé par un {b combinateur} agissant comme un {b pont}.

_p Concernant le langage lambdatalk il me suffit de savoir :

_ul 1) qu'en lambdatalk la forme spéciale {b '{lambda {var ...} expression}} n'accepte pas de variables libres. Les lambdas sont des {b combinateurs}, ce sont des fonctions vraiment pures sans effet de bord, en entrée comme en sortie.

_ul 2) et que la forme spéciale {b '{let { {var val} ...} expression}} est un sucre syntaxique pour l'expression {b '{{lambda {var ...} expression} val ...}}, qui n'est rien d'autre que le processus de remplacement de texte « {b remplace var ... dans expression par val ...} » auquel tout langage se réduit.

_p On reste tout le temps dans un processus basique de substitution de texte. Le fonctionnement d'une fonction se comprend à la lecture de la liste des arguments. Inutile de chercher en dehors. L'Indépendance contextuelle est totale.

_p Dans l'exemple écrit en lambdatalk il est inutile d'introduire une variant de la forme {b let} qui autorise la définition de variables et fonctions locales, ici deux fonctions non récursives, la seconde étant le Y-combinateur.

_p Dans son papier de quatre pages Richard P.Gabriel me parle de la forme spéciale {b letrec} à utiliser en lieu et place de la forme spéciale {b let} quand on veut jouer avec la récursion. Et bien sûr il part du principe que je sais qu'en Scheme les lambdas sont des fermetures, elles acceptent les variables libres prenant automatiquement leurs valeurs du contexte lexical. Tant de choses magiques dont le fonctionnement est caché.

_p Et Richard P.Gabriel veut m'expliquer le Y-combinateur ?

_p Suis-je un cas pathologique ?

_p Alain Marty | 2021/03/05

{style 
pre { box-shadow:0 0 8px #000; padding:10px; }
}