lambdaway :: words

6 | list | login |load

| |

_img http://lambdaway.free.fr/workshop/data/cpu_intel.jpg

{center words_numbers | [[words_numbers2]] | [[words_numbers3]]}
_h1 jeux de mots

_h2 introduction

_p Nous nous proposons de construire les bases d'un langage de programmation minimaliste en utilisant les deux formes spéciales fondamentales de lambdatalk, {b lambda & def}, {u et rien d'autre}. Le dictionnaire de ce langage est supposé vide et nous allons le remplir petit à petit.

_p En préambule on rappelle que tout part de la commande suivante

{pre
{b remplace les mots} :a & :b
   {b dans la phrase} "bla bla bla :b :a bli bli bli"
     {b par ces mots}  hello & world
}

_p dont on attend qu'elle produise ce résultat {b bla bla bla world hello bli bli bli} où les mots {b hello} et {b world} ont été inversés. Il s'agit là d'un simple processus de {b remplacement de texte} et il ne s'agira que de cela dans toute la suite.

_p Réécrivant la commande en oubliant les {b bla bla bla} et autres {b bli bli bli} on conviendra d'écrire une commande inversant deux mots

{pre
{b remplace} :a & :b
    {b dans} :b :a
     {b par}  hello & world
}

_p sous la forme parenthésée suivante

{pre
'{{lambda {:a :b} 
          :b :a} 
           a  b}
-> {{lambda {:a :b} :b :a} a b}
}

_p où , pour des raisons historiques dont on pourra reparler plus loin, le mot {b lambda} est écrit en lieu et place du verbe {b remplace} et les conjonctions {b dans, par, &} ont été remplacées par un jeu balancé d'accolades. Un tel {b code} a le mérite d'être plus compact et surtout {i compris par mon ordinateur} qui {b l'évalue et le remplace} par les deux mots {b a & b} inversés. Rien de magique. En lambda-calcul on appelle ça une {b redex} et en javascript une IIFE, Immediately Invoked Function Expression. Oublions.

_p Techniquement lambdatalk capture en premier l'expression interne {b '{lambda {:a :b} :b :a}} et la remplace par la référence à une {b fonction} gardée temporairement en mémoire. Cette référence, disons {b #123}, est inconnue de l'utilisateur. On dit que la fonction est {b anonyme}. Pour rendre le code plus lisible nous choisissons de construire l'expression en deux étapes :

_ul 1) Nous donnons un nom à la fonction anonyme, {b SWAP}, signifiant {i échanger} en anglais.

{pre
'{def SWAP {lambda {:a :b} :b :a}}
-> {def SWAP {lambda {:a :b} :b :a}}
}

_ul 2) et nous réécrivons l'expression initiale en utilisant ce nom

{pre
'{SWAP a b}
-> {SWAP a b}
}

_p Nous avons caché le mécanisme de la fonction anonyme sous un nom facile à retenir, on dit qu'on a créé une {b abstraction}. Ce faisant nous venons d'ajouter le nom {b SWAP} au dictionnaire, nous l'avons appliqué à deux mots, {b a & b},  et nous pourrons l'appliquer à bien d'autres

{pre
'{SWAP james bond}
-> {SWAP james bond}
'{SWAP ward cunningham}
-> {SWAP ward cunningham}
...
}

_p Dans ce premier exemple nous avons rappelé le principe, {i un simple jeu de {b remplacement de texte}}, et nous allons l'utiliser systématiquement pour construire et utiliser de nouvelles fonctions autant que de besoin.

_h2 booléens

_p Commençons par les {b booléens}, deux mots présents dans tout langage de programmation et signifiant le {b vrai} et le {b faux}. En les définissant comme fonctions nous donnons vie à deux noms, ils deviennent des "opérateurs" permettant d'effectuer des {b choix}, des redirections

{pre
'{def TRUE {lambda {:a :b} :a}}
-> {def TRUE {lambda {:a :b} :a}}
'{def FALSE {lambda {:a :b} :b}}
-> {def FALSE {lambda {:a :b} :b}}

'{TRUE a b}
-> {TRUE a b}
'{FALSE a b}
-> {FALSE a b}

{{trace}
0: '{TRUE a b}
1: '{{lambda {:a :b} :a} a b}
                    |<--|
2: a
}
}

_p En cliquant sur le mot {b TRACE} nous voyons apparaître le processus de remplacement de texte qui est encore plus simple à suivre que celui de la fonction {b SWAP}. Il est absolument nécessaire de l'avoir bien compris avant d'aller plus loin.

_p Définissons une fonction {b IF bool? one two} retournant {b one} si le "prédicat" {b bool} vaut {b TRUE} et {b two} s'il vaut {b FALSE}.

{pre
'{def IF {lambda {:a :b :c} {:a :b :c}}}
-> {def IF {lambda {:a :b :c} {:a :b :c}}}

'{IF TRUE a b}
-> {IF TRUE a b}
'{IF FALSE a b}
-> {IF FALSE a b}

{{trace}
0: '{IF TRUE a b}
1: '{{lambda {:a :b :c} {:a :b :c}} {lambda {:a :b} :a} a b}
                         |<-|--|---|_________________| | |
                            |<-|-----------------------| |
                               |<------------------------|
2: '{{lambda {:a :b} :a} a b}
                     |<-|
3: a
}
}

_p Ça se complique un peu et {b TRACE} décompose le mécanisme interne en remplaçant les mots {b IF} et {b TRUE} par leurs {i lambda expressions} et en appliquant systématiquement les remplacements de mots jusqu'au résultat final.

_p Voici comment on peut définir les principales "portes logiques", {b NOT, AND, OR, XOR}

{pre
'{def NOT
 {lambda {:a}
  {IF :a FALSE TRUE}}}
-> {def NOT {lambda {:a} {IF :a FALSE TRUE}}}
'{def AND
 {lambda {:a :b}
  {IF :a :b FALSE}}}   
-> {def AND {lambda {:a :b} {IF :a :b FALSE}}}
'{def OR
 {lambda {:a :b}
  {IF :a TRUE :b}}}     
-> {def OR {lambda {:a :b} {IF :a TRUE :b}}}
'{def XOR
 {lambda {:a :b} 
  {OR {AND :a {NOT :b}}
      {AND :b {NOT :a}}}}}
-> {def XOR
 {lambda {:a :b} 
  {OR {AND :a {NOT :b}}
      {AND :b {NOT :a}}}}}
}

_p Nous en verrons une application un peu plus loin. Dans la foulée nous définissons quelques fonctions moins évidentes mais tout aussi utiles comme nous le verrons par la suite

{pre
'{def NIL {lambda {} TRUE}}            // la constante "nulle"
-> {def NIL {lambda {} TRUE}}    
'{def !NIL {lambda {} FALSE}}          // l'inverse de NIL
-> {def !NIL {lambda {} FALSE}}
'{def NIL? {lambda {:c} {:c !NIL}}}    // teste si la valeur est NIL
-> {def NIL? {lambda {:c} {:c !NIL}}}

'{NIL? NIL}
-> {NIL? NIL}
'{NIL? !NIL}
-> {NIL? !NIL}

{{trace}
0: '{NIL? NIL}
1: '{{lambda {:c} {:c !NIL}} NIL}
                   |<------|__|
3: '{NIL !NIL}
4: '{{lambda {} TRUE} FALSE}   
5: TRUE
}
 
}

_h2 paires

_p Jusqu'à présent les processus de remplacement de texte se font sur des mots isolés, les phrases sont des séquences de mots sans aucune structure. Le concept de {b paire} permet d'assembler deux mots en une entité nouvelle, une {b structure de données} contenant deux mots auxquels on pourra accéder à la demande.

{pre

'{def PAIR {lambda {:a :b :c} {:c :a :b}}}
-> {def PAIR {lambda {:a :b :c} {:c :a :b}}}
'{def LEFT {lambda {:c} {:c TRUE}}}
-> {def LEFT {lambda {:c} {:c TRUE}}}
'{def RIGHT {lambda {:c} {:c FALSE}}}  
-> {def RIGHT {lambda {:c} {:c FALSE}}}  
 
'{LEFT {PAIR a b}}
-> {LEFT {PAIR a b}}
'{RIGHT {PAIR a b}}
-> {RIGHT {PAIR a b}}

{{trace}
0: '{LEFT {PAIR a b}}
1: '{LEFT {{lambda {:a :b :c} {:c :a :b}} a b}}
2: '{LEFT {lambda {:c} {:c a b}}}
3: '{{lambda {:c} {:c TRUE}} {lambda {:c} {:c a b}}}
                   |<-------|____________________|
4: '{{lambda {:c} {:c a b}} TRUE}
5: '{TRUE a b}
6: '{{lambda {:a :b} :a} a b}
7: a
}
}
 
_p Une paire contient deux mots ... qui peuvent être des référeces à des fonctions anonymes ou des noms de fonctions. Nous pouvons ainsi construire des compositions complexes et nous allons nous intéresser aux deux plus connues,  les {b listes} et les {b arbres binaires}.

_h2 listes

_p Une paire contient deux mots. On définit une {b liste} comme étant une paire dont le terme de gauche est un mot et le terme de droite est une paire, et ainsi de suite, la dernière se terminant par NIL. Notez que la liste est une paire définie en utilisant le mot paire, il s'agit d'un premier exemple de ce qu'on appelle une {b forme récursive}, un concept d'une rare puissance. Exemple:

{pre
'{def L {PAIR a {PAIR b {PAIR c {PAIR d NIL}}}}}  
-> {def L {PAIR a {PAIR b {PAIR c {PAIR d NIL}}}}}
}

_p Pourquoi utiliser NIL comme fin de liste ? Notons qu'appliquée à une paire la fonction {b NIL?} retourne {b FALSE}, alors qu'appliquée à {b NIL} elle retourne {b TRUE}

{pre
'{NIL? NIL}
-> {NIL? NIL}
'{NIL? {PAIR a b}}
-> {NIL? {PAIR a b}}

{{trace}
0: '{NIL? {PAIR a b}}
1: '{NIL? {{lambda {:a :b :c} {:c :a :b}} a b}}
2: '{NIL? {lambda {:c} {:c a b}}}
3: '{{lambda {:c} {:c !NIL}} {lambda {:c} {:c a b}}} 
                  |<--------|____________________|
4: '{{lambda {:c} {:c a b}} !NIL}
                  |<-------|__|
5: '{!NIL a b}
6: '{{lambda {} FALSE} a b}
7: FALSE
}

}

_p Une liste étant une paire on peut accéder à ses éléments en utilisant les fonctions {b LEFT} et {b RIGHT} et procéder à quelques tests avec la fonction {b NIL?}

{pre
'{LEFT {L}} -> a
'{LEFT {RIGHT {L}}} -> b
'{LEFT {RIGHT {RIGHT {L}}}} -> c
'{LEFT {RIGHT {RIGHT {RIGHT {L}}}}} -> d

'{NIL? {L}} -> FALSE
'{NIL? {RIGHT {L}}} -> FALSE
'{NIL? {RIGHT {RIGHT {L}}}} -> FALSE
'{NIL? {RIGHT {RIGHT {RIGHT {L}}}}} -> FALSE
'{NIL? {RIGHT {RIGHT {RIGHT {RIGHT {L}}}}}} -> TRUE

}

_p Cette séquence d'extractions et de tests peut se résumer en une {b fonction récursive} affichant tous les éléments de la liste

{pre
'{def L.DISP
 {lambda {:l}
  {{IF {NIL? :l} 
   {lambda {:l} }
   {lambda {:l} {LEFT :l}
                {L.DISP {RIGHT :l}}}} :l}}} 
-> {def L.DISP
 {lambda {:l}
  {{IF {NIL? :l}   
   {lambda {:l} }
   {lambda {:l} {LEFT :l}
                {L.DISP {RIGHT :l}}}} :l}}}

'{L.DISP {L}}
-> {L.DISP {L}}

{{trace}
0: '{L.DISP {L}}
1: '{{lambda {:l}
    {{IF {NIL? :l} 
     {lambda {:l} }
     {lambda {:l} {LEFT :l} {L.DISP {RIGHT :l}}}} :l}} {L}}
2: '{{IF {NIL? {L}} 
    {lambda {:l} }
    {lambda {:l} {LEFT :l} {L.DISP {RIGHT :l}}}} {L}} 
3: '{{IF FALSE 
    {lambda {:l} }
    {lambda {:l} {LEFT :l} {L.DISP {RIGHT :l}}}} {L}} 
4: '{{lambda {:l} {LEFT :l} {L.DISP {RIGHT :l}}} {L}} 
5: '{LEFT {L}} '{L.DISP {RIGHT {L}}} 
6: a '{L.DISP {PAIR b {PAIR c {PAIR d NIL}}}}

.: a b '{L.DISP {PAIR c {PAIR d NIL}}}

.: a b c '{L.DISP {PAIR d NIL}}

.: a b c d '{L.DISP NIL}

.: a b c d '{{lambda {:l}
            {{IF {NIL? :l} 
             {lambda {:l} }
             {lambda {:l} {LEFT :l} {L.DISP {RIGHT :l}}}} :l}} NIL} 
.: a b c d '{{IF {NIL? NIL} 
             {lambda {:l} }
             {lambda {:l} {LEFT :l} {L.DISP {RIGHT :l}}}} NIL}
.: a b c d '{{IF TRUE
             {lambda {:l} }
             {lambda {:l} {LEFT :l} {L.DISP {RIGHT :l}}}} NIL}
.: a b c d '{{lambda {:l} } NIL}

.: a b c d 
}

}

_p La fonction {b L.DISP} fournit un premier exemple de structure de contrôle, on parle de {b récursion}, permettant de répéter une action dans une {b boucle}. Construite suivant la même logique voici une fonction inversant l'ordre d'une liste.

{pre
'{def L.REV
 {def L.REV.r
  {lambda {:a :b}
   {{IF {NIL? :a}
    {lambda {:a :b } :b}
    {lambda {:a :b}
     {L.REV.r {RIGHT :a} {PAIR {LEFT :a} :b}}}} :a :b}}}
 {lambda {:l}
  {L.REV.r :l NIL}}}
-> {def L.REV
 {def L.REV.r
  {lambda {:a :b}
   {{IF {NIL? :a}
    {lambda {:a :b } :b}
    {lambda {:a :b}
     {L.REV.r {RIGHT :a} {PAIR {LEFT :a} :b}}}} :a :b}}}
 {lambda {:l}
  {L.REV.r :l NIL}}}

'{L.DISP {L.REV {L}}}
-> {L.DISP {L.REV {L}}}

}

_p Comme application remarquable de liste voici, {i sans autre explication}, le jeu des {b Tours de Hanoï}. Plusieurs disques de taille décroissante sont empilés sur une tige. Le jeu consiste à déplacer chaque disque sur une deuxième tige via une troisième en respectant la règle suivante : "{i ne jamais mettre un disque sur un plus petit}". Le code est construit sur une fonction doublement récursive.

{pre
'{def HANOI          
 {lambda {:n :from :to :via}
  {{IF {NIL? :n}
   {lambda {:n :from :to :via} }
   {lambda {:n :from :to :via}
    {HANOI {RIGHT :n} :from :via :to}
      {br} move {LEFT :n} from tower :from to tower :to 
    {HANOI {RIGHT :n} :via :to :from} }}
   :n :from :to :via}}}
-> {def HANOI          
 {lambda {:n :from :to :via}
  {{IF {NIL? :n}
   {lambda {:n :from :to :via} }
   {lambda {:n :from :to :via}
    {HANOI {RIGHT :n} :from :via :to}
      {br} move {LEFT :n} from tower :from to tower :to 
    {HANOI {RIGHT :n} :via :to :from} }}
   :n :from :to :via}}}
}

_p Nous supposerons ici qu'il y a 4 disques représentés par les termes de la liste {b L = (a b c d)}

{pre
'{HANOI {L} A B C}
-> {HANOI {L} A B C}
}

_h2 arbres binaires

_p Un arbre binaire est une paire dont chaque terme est une paire ou une feuille, {b LEAF}, cad une paire dont le terme de gauche est un mot et le terme de droite est NIL.

{pre

'{def T.DISP
 {lambda {:t}
  {{IF {NIL? {RIGHT :t}}
   {lambda {:t} {LEFT :t}}
   {lambda {:t} ({T.DISP {LEFT :t}}
                {T.DISP {RIGHT :t}})}} :t}}}
-> {def T.DISP
 {lambda {:t}
  {{IF {NIL? {RIGHT :t}}
   {lambda {:t} {LEFT :t}}
   {lambda {:t} ({T.DISP {LEFT :t}}
                {T.DISP {RIGHT :t}})}} :t}}}

'{def LEAF {lambda {:a} {PAIR :a NIL}}}
-> {def LEAF {lambda {:a} {PAIR :a NIL}}}

'{T.DISP 
 {PAIR {LEAF a} {LEAF b}} 
}
-> {T.DISP 
 {PAIR {LEAF a} {LEAF b}} 
}

{{trace}
0: '{T.DISP {PAIR {LEAF a} {LEAF b}}}
1: '{{lambda {:t}
  {{IF {NIL? {RIGHT :t}}
   {lambda {:t} {LEFT :t}}
   {lambda {:t} ({T.DISP {LEFT :t}}
                {T.DISP {RIGHT :t}})}} :t}} {PAIR {LEAF a} {LEAF b}}}
2: '{{IF {NIL? {RIGHT {PAIR {LEAF a} {LEAF b}}}}
   {lambda {:t} {LEFT :t}}
   {lambda {:t} ({T.DISP {LEFT :t}}
                {T.DISP {RIGHT :t}})} {PAIR {LEAF a} {LEAF b}}}}
3: '{{IF {NIL? {LEAF b}}
   {lambda {:t} {LEFT :t}}
   {lambda {:t} ({T.DISP {LEFT :t}}
                {T.DISP {RIGHT :t}})} {PAIR {LEAF a} {LEAF b}}}} 
4: '{{IF FALSE
   {lambda {:t} {LEFT :t}}
   {lambda {:t} ({T.DISP {LEFT :t}}
                {T.DISP {RIGHT :t}})} {PAIR {LEAF a} {LEAF b}}}} 
5: '{{lambda {:t} ({T.DISP {LEFT :t}}
                {T.DISP {RIGHT :t}})} {PAIR {LEAF a} {LEAF b}}}
6: ('{T.DISP {LEFT {PAIR {LEAF a} {LEAF b}}}} 
    '{T.DISP {RIGHT {PAIR {LEAF a} {LEAF b}}}})
7: ('{T.DISP {LEAF a}} '{T.DISP {LEAF b}})
...
8: (a b)
}

'{T.DISP
 {PAIR
  {PAIR {LEAF a} {LEAF b}}
  {PAIR {LEAF c} {LEAF d}}
 }
}
-> {T.DISP
 {PAIR
  {PAIR {LEAF a} {LEAF b}}
  {PAIR {LEAF c} {LEAF d}}
 }
}

'{T.DISP
 {PAIR
  {PAIR
   {PAIR {LEAF a} {LEAF b}}
   {PAIR {LEAF c} {LEAF d}}}
  {PAIR
   {PAIR {LEAF e} {LEAF f}}
   {PAIR {LEAF g} {LEAF h}}} 
 }
}
-> {T.DISP
 {PAIR
  {PAIR
   {PAIR {LEAF a} {LEAF b}}
   {PAIR {LEAF c} {LEAF d}}}
  {PAIR
   {PAIR {LEAF e} {LEAF f}}
   {PAIR {LEAF g} {LEAF h}}} 
 }
}

'{T.DISP
 {PAIR
  {PAIR
   {PAIR
    {PAIR {LEAF a} {LEAF b}}
    {PAIR {LEAF c} {LEAF d}}}
   {PAIR
    {PAIR {LEAF e} {LEAF f}}
    {PAIR {LEAF g} {LEAF h}}}}
  {PAIR
   {PAIR
    {PAIR {LEAF i} {LEAF j}}
    {PAIR {LEAF k} {LEAF l}}}
   {PAIR
    {PAIR {LEAF m} {LEAF n}}
    {PAIR {LEAF o} {LEAF p}}}}
 }
}
-> {T.DISP
{PAIR
 {PAIR
  {PAIR
   {PAIR {LEAF a} {LEAF b}}
   {PAIR {LEAF c} {LEAF d}}}
  {PAIR
   {PAIR {LEAF e} {LEAF f}}
   {PAIR {LEAF g} {LEAF h}}}}
 {PAIR
  {PAIR
   {PAIR {LEAF i} {LEAF j}}
   {PAIR {LEAF k} {LEAF l}}}
  {PAIR
   {PAIR {LEAF m} {LEAF n}}
   {PAIR {LEAF o} {LEAF p}}}}}
 }

}

_h2 conclusion

_p Voir une exploration de l'arithmétique binaire dans [[words_numbers2ØØ et dans les pages [[coding]], [[oops6]], ...

_p {i alain marty 2022/06/21-27}

_h2 refs
_ul https://www-sop.inria.fr/members/Yves.Bertot/courses/lambda-pur.pdf
_ul https://justine.lol/lambda/
_ul ...

{{hide}
{def trace
 div 
  {@ class="trace" 
     onclick="this.style.height=(this.style.height==='15px')? 'auto' : '15px'"}
 {b TRACE...}}
}

{style 
.trace { height:auto; overflow:scroll; margin:0; color:blue; font-size:12px; }
}