lambdaway :: function

2 | list | login |load

| |

_h1 un éditeur de texte extensible

{{block}   
;; {uncover http://epsilonwiki.free.fr/epsilonwiki/data/lepetitnicolas.jpg 200 1000 A l'évidence ...}

_h2 introduction

_p En cliquant sur le mot {b function} à droite du titre {b lambdaway :: function} vous ouvrez (et vous pourrez refermer) une fenêtre affichant un texte "brut", où les paragraphes se déroulent "au kilomètre", sans aucun bouton pour mettre en gras, en italique ou appliquer tel ou tel style. Du texte vraiment brut, une chaîne de mots sans aucune structure. En observant de plus près vous notez quelques caractères étranges, {b _{span}h1, _{span}p, ...} et une ribambelle d'accolades assez mystérieuses. On se croirait revenu aux premières heures de l'informatique ...

{uncover data/function_screencopy.jpg 100 350 Session de travail dans lambdatank}

_p Et sous cette fenêtre ou à côté, en légère transparence la page s'affiche dans toute sa complexité. Une présentation en multi-colonnage sur un fond sombre, des titres, des styles (gras, italique, couleurs, ...), des images et des blocs contenant des expressions parenthésées contenant des mots, des nombres et des opérateurs suivies de leurs évaluations. On voit même la liste des mouvements des disques dans le jeu des [[Tours de Hanoï|?view=hanoi]], la valeur d'une factorielle et un nombre de Fibonacci.

_p Comme par magie le texte brut est devenu un être vivant, un {b code} actif que vous pouvez même modifier à volonté, en temps réel, sans risque. Essayez.

_p Bienvenue dans le projet {b lambdaway} comprenant un wiki, {b lambdatank}, installable sur tout navigateur web et doté d'un langage de programmation, {b lambdatalk}, avec lequel cette page a été créée. Vous en trouverez une présentation rapide dans la page [[accueil|?view=start]] de ce wiki et plus approfondie dans la page [[coding]] et les deux suivantes.

_p L'objectif ici est de montrer comment on peut doter un outil d'édition de texte élémentaire comme celui qui est installé dans tout navigateur web, {b textarea}, d'un langage de programmation construit sur une fondation minimale, inspirée d'un formalisme {i ésotérique} datant des années 30, le {b [[λ-calcul|?view=lc_french]]}. En s'arrêtant dans cette page aux concepts fondamentaux, essentiellement les structures de données et de contrôle dont tout le reste découle.

_p {b Tout commence avec un simple processus de remplacement de texte} comme :

{pre
remplace :a & :b
    dans :b :a
     par James & Bond
}

_p dont on imagine sans peine le résultat : {b Bond James}. Vous ne voyez pas ? Essayez, lentement. N'allez pas plus loin tant que cela n'est pas clair dans votre esprit.

_p Pour être compris par mon traitement de texte j'utilise ... du texte, sous une {b forme codée}, une sorte de sténographie

{uncover https://upload.wikimedia.org/wikipedia/commons/e/ef/Eclectic_shorthand_by_cross.png 100 1000 Sténographie}

_p {b non, non pas celle-là}, encore utilisée par ma tante Marguerite qui a fêté ses 104 ans le 10 Juillet passé et qu'elle lit et écrit sans problème, mais celui-ci bien moins effrayant :

{pre
'{{lambda {:a :b}
          :b :a
        } James Bond}
}

_p où le verbe "remplace" est remplacé par "{b lambda}" (c'est plus smart dans les soirées mondaines) et les conjonctions "&, dans, par" sont remplacées par un jeu balancé d'accolades grisées, lui donnant un petit air du LISP des années 50, cet étrange langage rempli de parenthèses qui a accompagné les débuts de l'IA. En tout cas mon ordinateur est content et affiche le même résultat : {b Bond James}.

_p Là aussi prenez la peine de comparer les deux écritures, la première en langage courant et la seconde en langage codé, sténographié, que nous appelerons {b lambdatalk}. Un langage supposé pour l'instant réduit à cet étrange opérateur {b lambda} qui ne sait faire qu'une chose, remplacer des mots par d'autres.

_p Voici un autre exemple affichant le code et le résultat juste en dessous

{pre
'{{lambda {:a :b}
         Je m'appelle :b, :a :b.}
         James Bond}
-> {{lambda {:a :b} Je m'appelle :b, :a :b.} James Bond}
}

_p {b Notes:}
_ul La disposition des mots est libre,
_ul on convient de préfixer par un caractère ":" les mots à remplacer, {b :a & :b},  
_ul Savez-vous pourquoi il est nécessaire de préfixer les mots à remplacer ? Essayez sans et constatez ce qui cloche. Oui, au fait, vous pouvez tester tout ce que vous voulez dans le code. Sans risque.

_p Mais même si c'est plus lisible que la sténographie de Marguerite, c'est quand même bien lourd tout ça, et puis on a compris qu'il s'agit de remplacement de texte, et il n'y a pas de quoi en faire tout un fromage. What else ?

}

{{block}
;; {uncover http://epsilonwiki.free.fr/epsilonwiki/data/lepetitnicolas.jpg 200 1000 A l'évidence ...}

_h2 1) abstraction & application

_p C'est là que se trouve {b l'idée simple et géniale} qui fait d'un banal processus de remplacement de texte le germe d'un langage de programmation à part entière : on convient de simplifier l'écriture et la lecture de cette expression

{pre
'{{lambda {:a :b}
         Je m'appelle :b, :a :b.}
         James Bond}
}
_p en procédant en deux étapes. Et donc, suivant l'exemple du {b λ calcul}, on définira

_ul 1) l{b 'abstraction}, une mise entre parenthèses, une sorte de procrastination, au moyen d'un second opérateur, {b def}

{pre

'{def HI                             ;; // on définit HI comme nom
 {lambda {:a :b}                    ;; // d'une fonction de deux variables
         Je m'appelle :b, :a :b.    ;; // dont voici le corps
 }                                  ;;  // fin fonction
}                                   ;;  // fin définition
-> {def HI {lambda {:a :b} Je m'appelle :b, :a :b.}}
}
_p On a ainsi créé une {b fonction} de deux variables {b :a & :b}, présentes dans le corps de la fonction, {b Je m'appelle :b, :a :b.}, on a donné le nom {b HI} à cette {b fonction anonyme} en utilisant l'opérateur {b def}, et on a ajouté ce nom à un {b dictionnaire} supposé initialement vide,

_ul 2) et l{b 'application}, le passage à l'acte, au réel, l'expression se réduisant ainsi
{pre

'{HI James Bond}
-> {HI James Bond}
}
 
_p On est bien d'accord, il s'agit de la même expression - remplacez {b HI} par sa lambda expression - mais on a gagné quelque chose, on est passé à l'étage supérieur. Voyons comment.

_p Ce nom peut être appliqué à bien d'autres valeurs, par exemple

{pre
'{HI Monica Bellucci}
-> {HI Monica Bellucci}

'{HI Nicolas de Caritat de Condorcet}
-> {HI Nicolas de Caritat de Condorcet}
}

_p Nous avons caché le fonctionnement de la fonction, on peut l'oublier et on peut l'utiliser autant que de besoins.

_h3 notes techniques

_p Telles qu'elles sont "implémentées" dans lambdatalk les lambdas possèdent quelques propriétés particulières qu'il est préférable de connaître pour comprendre les constructions qui vont suivre.

_h4 1) variadicité
_p Dans le dernier exemple observons que le mot {b Nicolas} a été "capturé" par la variable {b :a} et que les quatre mots suivants "{b de Caritat de Condorcet}" ont été "capturés" par la variable {b :b}. C'est une intéressante propriété des fonctions de lambdatalk - appelée {b variadicité} - utilsable de façon naturelle, ce qui n'est pas le cas de tous les langages.

_h4 2) appel partiel
_p Rien n'interdit d'appliquer une fonction de deux variables à une seule valeur (si si ça peut être utile)

{pre
'{HI James}
-> _LAMB_123   // ooops, kézako ?
}

_p Cet étrange résultat n'est pas une erreur, la fonction {b HI} a bien enregistré la valeur donnée {b James} dans la variable {b :a}, a construit une nouvelle fonction (anonyme) {b '{lambda {:b} Je m'appelle :b, James :b.}} et l'a ajoutée au dictionnaire sous une référence {b _LAMB_123}, inconnue de l'utilisateur. En lui fournissant une seconde valeur, {b Bond}, cetre fonction retournera le résultat complet attendu. Voilà donc une seconde intéressante propriété des fonctions, l{b 'appel partiel}, simple à utiliser, ce qui n'est pas le cas de tous les langages. On en verra une application dans la section {b 2.2) paires}.

_h4 3) boites noires

_p Les lambdas sont des boites noires ne connaissant rien d'autre - en dehors du dictionnaire global - que les arguments explicitement définis. Il n'y a pas de variables dites libres prenant leurs valeurs dans tel ou tel contexte local, il n'y a  pas ce qu'on appelle une {b fermeture}, une puissante fonctionnalité que l'on trouve dans la plupart des langages modernes. Une faiblesse heureusement compensée par l'utilisation "naturelle" de l'application partielle, associée à la redéfinition "manuelle" des variables externes à la fonction, celles dont a besoin. Dans cette page il se trouve qu'on n'en aura pas besoin.

_h3 la suite ?

_p Nous avons tout ce qu'il faut, l'abstraction et l'application, le Yin et le Yang, le {b TAO} du code. Muni des deux opérateurs {b lambda & def} (aussi appelés formes spéciales), {b lambda} pour créer des fonctions anonymes et {b def} pour leur donner des noms, on peut commencer à construire quelques premières {b structures de données et de contrôle} faisant de {b lambdatalk} un véritable langage de programmation.
}

{{block}
;; {uncover http://epsilonwiki.free.fr/epsilonwiki/data/lepetitnicolas.jpg 200 1000 A l'évidence ...}

_h2 2) booléens & paires

_p Jusqu'ici le seul "matériau" que nous pouvons manipuler c'est du texte, des phrases, des séquences de mots. Un mot ne représente rien d'autre que lui-même. C'est d'ailleurs la raison pour laquelle il est complètement ignoré par {b lambdatalk}. Grâce aux deux formes spéciales {b lambda & def} nous en avons créé un de plus, {b HI}, qui a la particularité d'être une référence à une fonction anonyme. On va utiliser cette propriété pour créer de nouveaux mots faisant référence à des concepts communément utilisés dans les langages de programmation, les booléens, les paires, les listes, ... et bien sûr les boucles. Chaque fois que {b lambdatalk} rencontrera un tel mot "référence" dans ce genre d'expression {b '{func séquence de mots}} il appliquera la fonction correspondant à {b func} à la {b séquence de mots} fournie et en retournera le résultat, d'autres mots qui peuvent représenter ou non d'autres fonctions, etc, etc, ...

_p Trois premiers exemples pour se mettre en bouche, la fonction {b VIDE} n'attendant rien et ne retournant rien

{pre
'{def VIDE {lambda {} }}
-> {def VIDE {lambda {} }}

'{VIDE}
-> {VIDE}         // vide, comme son nom l'indique
}

_p puis la fonction {b CONSTANTE} retournant toujours la même chose

{pre
'{def CONSTANTE {lambda {} toujours la même chose}}
-> {def CONSTANTE {lambda {} toujours la même chose}}

'{CONSTANTE hello}
-> {CONSTANTE hello}

'{CONSTANTE good bye}
-> {CONSTANTE good bye}
}

_p et enfin la fonction {b IDENTITE} retournant à l'identique ce qui lui est fourni

{pre
'{def IDENTITE {lambda {:a} :a}}
-> {def IDENTITE {lambda {:a} :a}}

'{IDENTITE une chose}
-> {IDENTITE une chose}
'{IDENTITE tout à fait autre chose}
-> {IDENTITE tout à fait autre chose}
}

_p Sans plus d'explication ! Notez sur le dernier exemple la "variadicité" abordée plus haut, la variable {b :a} capture n'importe quelle suite de mots.

_h3 2.1) booléens

_p Les concepts de {b vrai} et de {b faux} n'existent pas dans ce langage (supposé) vide et nous les définirons comme deux fonctions

{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 oui non}
-> {TRUE oui non}
'{FALSE oui non}
-> {FALSE oui non}
}

_p On a coutume d'en ajouter une troisième, {b IF}

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

'{IF TRUE oui non}
-> {IF TRUE oui non}
'{IF FALSE oui non}
-> {IF FALSE oui non}
}

_p On notera que la fonction {b IF} n'est pas indispensable. Elle est introduite pour retrouver la forme bien connue "{b si A est vrai alors B sinon C}". Et avant d'aller plus loin soyez sûr d'avoir bien compris le fonctionnement "{i remplacement de texte}" de ces trois premières fonctions.

_h3 2.2) paires

_p On a souvent besoin de regrouper sous un seul nom plusieurs autres mots, par exemple le prénom et le nom d'une personne. On est ainsi amené à créer le concept de {b paire} regroupant deux mots sous une unique référence de fonction manipulable comme un mot.

{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}}}

'{def P {PAIR James Bond}}     // notez l'application partielle
-> {def P {PAIR James Bond}}
'{LEFT {P}}
-> {LEFT {P}}
'{RIGHT {P}}
-> {RIGHT {P}}
}

_p Noter que la fonction {b PAIR} attend trois valeurs et qu'elle n'en reçoit que deux, il s'agit d'une application partielle. Le résultat est une fonction anonyme dont le corps contient les deux valeurs données et attendant la valeur manquante {b '{lambda {:c} {:c James Bond}}}. Les deux fonctions {b LEFT} et {b RIGHT} sont construites pour en retirer les deux valeurs fournies.

_p Les booléens et les paires sont les deux briques de base avec lesquelles nous allons construire tout le reste. 
}

{{block}
_h2 3) des listes & des boucles

_p Il est possible de composer des paires à l'infini, ce qui va nous permettre de regrouper bien plus que deux mots.

_h3 3.1) structures récursives

_p Une {b paire} dont l'élément de gauche est un mot et l'élément de droite est une {b paire} ou un mot "terminal" - disons {b NIL} - est une {b structure récursive} appelée {b liste}.

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

_p Il est facile d'accéder à chaque élement de la liste, par exemple {b '{LEFT {LEFT {L}}}} retourne {b b}.

_p On aura besoin de tester la fin de la liste {b L}, par exemple à l'aide d'une fonction {b '{NIL? {L}}} retournant {b TRUE} si la liste est réduite à {b NIL} et {b FALSE} sinon. Attention, il n'existe (pour l'instant) aucun "opérateur" pour comparer deux mots,  et c'est probablement la partie la plus "tordue" de ce qu'on a fait depuis le début. Aujourd'hui je dois m'y reprendre à deux fois avant de retrouver le code qui résout ce problème et je vous le donne tel quel, sans plus d'explication :

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

'{NIL? NIL}
-> {NIL? NIL}
'{NIL? {L}}
-> {NIL? {L}}
}

_p On peut donc maintenant afficher chaque élément de la liste et à chaque fois tester si le reste de la liste est ou n'est pas {b NIL}.

{pre
'{LEFT {L}} 
-> {LEFT {L}} 
'{NIL? {RIGHT {L}}}
-> {NIL? {RIGHT {L}}}
'{LEFT {RIGHT {L}}} 
-> {LEFT {RIGHT {L}}}
'{NIL? {RIGHT {RIGHT {L}}}}
-> {NIL? {RIGHT {RIGHT {L}}}}
'{LEFT {RIGHT {RIGHT {L}}}} 
-> {LEFT {RIGHT {RIGHT {L}}}} 
'{NIL? {RIGHT {RIGHT {RIGHT {L}}}}}
-> {NIL? {RIGHT {RIGHT {RIGHT {L}}}}}
'{LEFT {RIGHT {RIGHT {RIGHT {L}}}}}
-> {LEFT {RIGHT {RIGHT {RIGHT {L}}}}} 
'{NIL? {RIGHT {RIGHT {RIGHT {RIGHT {L}}}}}}
-> {NIL? {RIGHT {RIGHT {RIGHT {RIGHT {L}}}}}}
}

_p On a ainsi affiché successivement chaque élément de la liste jusqu'à ce que le test retourne {b TRUE}. Ceci nous conduit à cette fonction,

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

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

_p Cette fonction est fondamentale à plusieurs titres :

_ul 1) elle s'appelle elle-même, le nom {b DISP} se trouve dans son corps
_ul 2) il s'agit d'une boucle, contenant deux parts :
_ul20 2.1) quand {b '{NIL? :l} = TRUE} elle ne fait rien, ce qui termine la boucle,
_ul20 2.2) quand {b '{NIL? :l} = FALSE} elle affiche le premier terme de la liste puis s'appelle elle-même sur la suite de la liste.
_ul 3) les deux parts sont écrites à l'intérieur de lambdas, les protégeant de toute évaluation {b avant} le résultat du test {b NIL?}, 
_ul 4) quand la "bonne" lambda est choisie elle est appliquée à {b :l} et le résultat est retourné. Des explications plus détaillées sont visibles dans la page [[coding]].

_p Les techniciens noteront l'utilisation des lambdas pour transformer une évaluation "gloutonne" en évaluation "paresseuse". Et comprendront toute la puissance des structures de contrôle {b if then else} habituellement introduites sans autre explications. {u Il est bien évident} que {b lambdatalk} dispose d'une telle forme dite spéciale, {b '{if bool then one else two}}, réalisant ce travail sous le capot afin d'en simplifier l'écriture et la lecture. {u Mais ici} le {b deal est d'en rester au mécanisme de base.}

_h3 3.2) quelques exemples

_p Après la structure de donnée récursive {b L}, la fonction {b DISP} nous fournit le premier exemple de structure de contrôle dite {b récursive}, qui se révèle être un véritable couteau suisse. En effet sur ce modèle nous allons pouvoir construire plusieurs fonctions retournant la longueur d'une liste, renversant une liste, concaténant deux listes et même résolvant le problème des [[Tours de Hanoï|?view=hanoi]].

{pre
'{def LENGTH
 {lambda {:l}
  {{IF {NIL? :l}
   {lambda {:l} }
   {lambda {:l} •{LENGTH {RIGHT :l}}}}
            :l}}}
-> {def LENGTH
 {lambda {:l}
  {{IF {NIL? :l}
   {lambda {:l} }
   {lambda {:l} •{LENGTH {RIGHT :l}}}} :l}}}

'{LENGTH {L}}
-> {LENGTH {L}}     // une représentation "primitive" du nombre 4

'{def REVERSE
 {def REVERSE.rec
  {lambda {:a :b}
   {{IF {NIL? :a}
    {lambda {:a :b} :b}
    {lambda {:a :b} {REVERSE.rec {RIGHT :a}
                                 {PAIR {LEFT :a} :b}}}}
             :a :b}}}
 {lambda {:l}
  {REVERSE.rec :l NIL}}}
-> {def REVERSE
 {def REVERSE.rec
  {lambda {:a :b}
   {{IF {NIL? :a}
    {lambda {:a :b} :b}
    {lambda {:a :b} {REVERSE.rec {RIGHT :a} {PAIR {LEFT :a} :b}}}}
             :a :b}}}
 {lambda {:l}
  {REVERSE.rec :l NIL}}}

'{DISP {REVERSE {L}}}
-> {DISP {REVERSE {L}}}

'{def CONCAT
 {def CONCAT.rec
  {lambda {:a :b}
   {{IF {NIL? :a}
    {lambda {:a :b} :b}
    {lambda {:a :b} {CONCAT.rec {RIGHT :a}
                                {PAIR {LEFT :a} :b}}}}
             :a :b}}}
 {lambda {:a :b}
  {CONCAT.rec {REVERSE :a} :b}}}
-> {def CONCAT
 {def CONCAT.rec
  {lambda {:a :b}
   {{IF {NIL? :a}
    {lambda {:a :b} :b}
    {lambda {:a :b} {CONCAT.rec {RIGHT :a} {PAIR {LEFT :a} :b}}}} :a :b}}}
 {lambda {:a :b}
  {CONCAT.rec {REVERSE :a} :b}}}

'{DISP {CONCAT {L} {L}}} 
-> {DISP {CONCAT {L} {L}}}

'{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}
      {div} move the disk {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}
      {div}move the disk {LEFT :n} from tower :from to tower :to 
    {HANOI {RIGHT :n} :via :to :from} }}
   :n :from :to :via}}}

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

_p Et aussi (cf [[partition]])

{prewrap
'{def PARTITION
 {def PARTITION.r 
  {lambda {:a :b :w}
   {{IF {NIL? :w}
    {lambda {:a :b :w} :a}
    {lambda {:a :b :w} {PARTITION.r :a :a:b {RIGHT :w}} 
                       {PARTITION.r :a:b :b {RIGHT :w}}}}
             :a :b :w}}}
 {lambda {:a :b :w}
  {PARTITION.r :a :b :w} :b}}
-> {def PARTITION
 {def PARTITION.r 
  {lambda {:a :b :w}
   {{IF {NIL? :w}
    {lambda {:a :b :w} :a}
    {lambda {:a :b :w} {PARTITION.r :a :a:b {RIGHT :w}} 
                       {PARTITION.r :a:b :b {RIGHT :w}}}}
             :a :b :w}}}
 {lambda {:a :b :w}
  {PARTITION.r :a :b :w} :b}}

'{PARTITION a b {L}}
-> {PARTITION a b {L}}

'{PARTITION 0 1 {CONCAT {L} {L}}}
-> {PARTITION 0 1 {CONCAT {L} {L}}}
}

_p Voici donc ce qu'on peut faire avec très peu de choses. A titre d'exercice vous pourriez vous amuser à construire un [[arbre binaire|?view=oops]], dont les listes ne sont qu'un cas dégénéré. Pour la suite nous allons nous intéresser à un grand absent de notre petit monde ne contenant que des mots : le {b nombre}. 
}

{{block}
;; {uncover http://epsilonwiki.free.fr/epsilonwiki/data/lepetitnicolas.jpg 200 1000 A l'évidence ...}

_h2 4) les nombres entiers naturels

_p L'ensemble des nombres naturels peut être défini comme étant le nombre {b zéro} suivi de tous ses {b successeurs}.

{pre 
[0, succ(0), succ(succ(0)), succ(succ(succ0))), ...]
}

_p On a l'habitude de les représenter en notation décimale

{pre
[0, 1, 2, 3, ...]
}

_p Il existe de nombreuses façons de les "implémenter" au coeur des ordinateurs et des langages de programmation. Nous oublierons ici l'implémentation des nombres proposée par Alonzo Church, le créateur du {b λ-calcul} et nous les définirons simplement avec ce dont nous disposons pour l'instant, des {b listes}, disons des listes de points, {b •}.

{pre
[(), (•), (•(•)), (•(•(•))), ...]
}

_h3 4.1) les nombres

_p Le successeur d'un nombre {b n} sera construit à l'aide d'une fonction très simple, {b SUCC}, ajoutant un point en tête de la liste représentant ce nombre, et le nombre {b ZERO} sera un simple alias de {b NIL}. Voici les 5 premiers :

{pre
'{def SUCC {lambda {:n} {PAIR • :n}}}
-> {def SUCC {lambda {:n} {PAIR • :n}}}

'{def ZERO NIL}
-> {def ZERO NIL}
'{def ONE {SUCC {ZERO}}}
-> {def ONE {SUCC {ZERO}}}
'{def TWO {SUCC {ONE}}}
-> {def TWO {SUCC {ONE}}}
'{def THREE {SUCC {TWO}}}
-> {def THREE {SUCC {TWO}}}
'{def FOUR {SUCC {THREE}}}
-> {def FOUR {SUCC {THREE}}}
'{def FIVE {SUCC {FOUR}}}
-> {def FIVE {SUCC {FOUR}}}

'{LENGTH {ZERO}}
-> {LENGTH {ZERO}} // nada
'{LENGTH {ONE}}
-> {LENGTH {ONE}}
...

'{LENGTH {FIVE}}
-> {LENGTH {FIVE}}
}

_p Bon, cette façon de considérer les nombres est vraiment {b primitive} et on va faire une entorse à nos bonnes résolutions : {b lambdatalk} dispose d'une primitive comptant les nombre de caractères d'un mot, {b W.length}, et nous allons l'utiliser dans une petite fonction appelée {b NUMBER} pour l'occasion

{pre
'{def NUMBER
 {lambda {:l}
  {W.length {LENGTH :l}}}}   
-> {def NUMBER
 {lambda {:l}
  {W.length {LENGTH :l}}}}

'{NUMBER {ZERO}}
-> {NUMBER {ZERO}}
'{NUMBER {ONE}}
-> {NUMBER {ONE}}
'{NUMBER {FIVE}}
-> {NUMBER {FIVE}}
}

_p Nous aurons besoin de la fonction symétrique, {b PRED}, retournant le prédécesseur d'un nombre, un simple alias de {b RIGHT}

{pre
'{def PRED {lambda {:n} {RIGHT :n}}}
-> {def PRED {lambda {:n} {RIGHT :n}}}

'{NUMBER {PRED {FIVE}}}
-> {NUMBER {PRED {FIVE}}}
'{NUMBER {PRED {ONE}}}
-> {NUMBER {PRED {ONE}}} 
'{NUMBER {PRED {ZERO}}}
-> {NUMBER {PRED {ZERO}}}  // oops!
}

_p Dans la version simple donnée ici pour l'opérateur {b PRED} on évitera d'appeler le prédécesseur de {b ZERO}, les nombres négatifs ne font pas partie de cette esquisse pour une arithmétique. Nous en profitons pour ajouter un alias à la fonction {b NIL?}

{pre
'{def ZERO? {lambda {:n} {NIL? :n}}}
-> {def ZERO? {lambda {:n} {NIL? :n}}}

'{ZERO? {ZERO}}
-> {ZERO? {ZERO}}
'{ZERO? {FIVE}}
-> {ZERO? {FIVE}}
}

_p Les quatre fonctions {b SUCC, PRED, ZERO & ZERO?} nous fournissent ce qu'on appelle une "{b couche d'abstraction}" permettant d'oublier que les nombres sont des listes. C'est ainsi que les langages se développent.

_h3 4.2) l'addition

_p Nous additionnerons deux nombres en suivant ce schéma

{pre
.  a  b
-------
0: {b 3  4}
1: 4  3
2: 5  2
3: 6  1
4: {b 7}  0 -> 7
}

_p ce qui se traduit par

{pre 
'{def ADD                  
 {lambda {:a :b}
  {{IF {ZERO? :b}
   {lambda {:a :b} :a}
   {lambda {:a :b} {ADD {SUCC :a} {PRED :b}}}}
            :a :b}}}
-> {def ADD               
 {lambda {:a :b}
  {{IF {ZERO? :b}
   {lambda {:a :b} :a}
   {lambda {:a :b} {ADD {SUCC :a}  
                        {PRED :b}}}} :a :b}}}

'{NUMBER {ADD {THREE} {FOUR}}}   // 3+4
-> {NUMBER {ADD {THREE} {FOUR}}}
}

_h3 4.3) la multiplication

_p De même nous multiplierons deux nombres en suivant ce schéma

{pre
.  a  b  c 
-----------
0: {b 3  4}  0
1: 3  3  3
2: 3  2  6
3: 3  1  9
4: 3  0 {b 12}
}

_p qui se traduit par

{pre
'{def MUL
 {def MUL.r                    // la boucle recursive
  {lambda {:a :b :c}
   {{IF {ZERO? :b}
    {lambda {:a :b :c} :c}
    {lambda {:a :b :c} {MUL.r :a {PRED :b} {ADD :a :c}}}} 
             :a :b :c}}}
{lambda {:a :b}
 {MUL.r :a :b {ZERO}}}}        // initialise et boucle
-> {def MUL
 {def MUL.r
  {lambda {:a :b :c}
   {{IF {ZERO? :b}
    {lambda {:a :b :c} :c}
    {lambda {:a :b :c} {MUL.r :a {PRED :b} {ADD :a :c}}}} :a :b :c}}}
{lambda {:a :b}
 {MUL.r :a :b {ZERO}}}}

'{NUMBER {MUL {THREE} {FOUR}}}   // 3*4
-> {NUMBER {MUL {THREE} {FOUR}}}
}

_p La fonction {b MUL} prend en entrée les deux valeurs à multiplier, {b :a & :b}, initialise un compteur {b :c} à zéro puis appelle la fonction récursive {b MUL.r} réalisant la boucle de calcul, qui retournera en sortie la valeur de l'accumulateur {b :c}.

_h3 4.4) la factorielle

_p La factorielle d'un nombre {b n} est définie ainsi

{pre
fac(n) = n*fac(n-1) pour n > 0
       = 1          pour n = 0
}

_p conduisant à ce code

{prewrap
'{def FAC
 {lambda {:a}
  {{IF {ZERO? :a}
   {lambda {:a} {ONE}}
   {lambda {:a} {MUL :a {FAC {PRED :a}}}}}
            :a}}}
-> {def FAC
 {lambda {:a}
  {{IF {ZERO? :a}
   {lambda {:a} {ONE}}
   {lambda {:a} {MUL :a {FAC {PRED :a}}}}} :a}}}

'{NUMBER {FAC {FIVE}}}          // 5!
-> {NUMBER {FAC {FIVE}}}
}

_h3 4.5) fibonacci

_p A la définition habituelle d'un nombre de Fibonacci, trop lente

{pre
fibo(0) = 0
fibo(1) = 1
fibo(n) = fibo(n-1) + fibo(n-2) pour n > 0
}

_p je préfèrerai la version récursive dite terminale

{pre
a = 0
b = 1
fibo(a,b,n) = fibo(a+b,a,n-1) pour n > 0
            = a               pour n = 0
}

_p conduisant à

{pre
'{def FIBO
 {lambda {:a :b :c}
  {{IF {ZERO? :c}
   {lambda {:a :b :c} :a}
   {lambda {:a :b :c} {FIBO {ADD :a :b} :a {PRED :c}}}}
            :a :b :c}}}
-> {def FIBO
 {lambda {:a :b :n}
  {{IF {ZERO? :n}
   {lambda {:a :b :n} :a}
   {lambda {:a :b :n} {FIBO {ADD :a :b} :a {PRED :n}}}}
   :a :b :n}}}

'{NUMBER {FIBO {ZERO}
              {ONE}
              {ADD {FIVE} {FIVE}}}}   // fibo(10)
-> {NUMBER {FIBO {ZERO} {ONE} {ADD {FIVE} {FIVE}}}}
}

_p Bien sûr d'autres fonctions devraient être ajoutées comme {b SUB}, {b DIV}, {b MOD}, ... et puis {b SERIE}, {b MAP}, {b REDUCE}. Elles sont présentées dans la page [[coding]] et les suivantes.

_p Nous voilà donc avec un traitement de texte capable de calculer. 
_p Excel peut-il aller se rhabiller pour autant ? Pas encore. Cette approche minimaliste fonctionne mais s'essouffle dès que les nombres dépassent de très faibles valeurs. La page [[λ-calculus using binary numbers of variable length|?view=oops6]] montre comment on peut largement dépasser ces limites. Et bien sûr dans la vraie vie on peut appeler à l'aide {b Javascript} - qui est disponible dans les soutes du navigateur - pour faire tous les calculs souhaitables aussi bien qu'avec Excel.

}

{{block}
;; {uncover http://epsilonwiki.free.fr/epsilonwiki/data/lepetitnicolas.jpg 200 1000 A l'évidence ...}

_h2 5) retour aux sources

_p Où nous allons voir que tout ce qui précède peut être codé à l'aide de la seule forme spéciale {b lambda}.

_p Reconsidérons la première fonction récursive {b DISP}

{pre
'{def DISP
 {lambda {:l}
  {{IF {NIL? :l}
   {lambda {:l} }
   {lambda {:l} {LEFT :l} {DISP {RIGHT :l}}}}
            :l}}}
}

_p Cette fonction s'appelle elle-même mais on peut éviter cela en ajoutant une variable {b :f} dans laquelle le nom sera mémorisé {b au moment de l'appel}. On transforme donc la fonction récursive en fonction "presque-recursive", {b ADISP}

{pre
'{def ADISP
 {lambda {:f :l}
  {{IF {NIL? :l}
   {lambda {:f :l} }
   {lambda {:f :l} {LEFT :l} {:f :f {RIGHT :l}}}}
            :f :l}}}
-> {def ADISP
 {lambda {:f :l}
    {{IF {NIL? :l}
     {lambda {:f :l} }
     {lambda {:f :l} {LEFT :l} {:f :f {RIGHT :l}}}} :f :l}}}

'{ADISP ADISP {L}}
-> {ADISP ADISP {L}} 
}

_p Il suffit donc de donner son nom à la fonction {b ADISP} au moment de l'appel. Comme ça manque un peu d'élégance, on peut construire une fonction faisant la même chose, {b Ω}
 
{pre
'{def Ω {lambda {:f} {:f :f}}}
-> {def Ω {lambda {:f} {:f :f}}}

'{{Ω ADISP} {L}}
-> {{Ω ADISP} {L}}
}
_p Dans la littérature technique on appelle {b combinateur} ce genre de fonction. Certains "geeks" se tatouent même sur le bras le {b Y-combinator} - celui de Church ou de Turing faisant l'objet d'un véritable culte - passage obligé vers la récursion, en compagnie du "point fixe d'une fonction". Les "quarantièmes rugissants" du λ-calcul qui en arrêtent plus d'un. Alors qu'il ne s'agit que d'un simple bégaiement de code ...

_p On peut aller plus loin et composer les deux fonctions en une seule, {b ΩDISP}

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

'{ΩDISP {L}}
-> {ΩDISP {L}}
}

_p On n'a même pas besoin de lui donner un nom

{pre
'{{lambda {:l}
 {{{lambda {:f} {:f :f}} 
  {lambda {:f :l}
   {{IF {NIL? :l}
    {lambda {:f :l} }
    {lambda {:f :l} {LEFT :l} {:f :f {RIGHT :l}}}}
             :f :l}}}
          :l}}
 {L}}
-> {{lambda {:l}
  {{{lambda {:f} {:f :f}} 
   {lambda {:f :l}
    {{IF {NIL? :l}
     {lambda {:f :l} }
     {lambda {:f :l} {LEFT :l} {:f :f {RIGHT :l}}}} :f :l}}} :l}} {L}}
}

_p Il ne reste plus qu'une étape, remplacer les noms par leur lambda expressions, patiemment, pour obtenir ceci

{pre
'{{lambda {:l}
{{{lambda {:f} {:f :f}} 
   {lambda {:f :l}
  {{{lambda {:a :b :c} {:a :b :c}}
    {{lambda {:c} {:c 
      {lambda {:a :b} 
       {lambda {:a :b} :b}}}} :l}
        {lambda {:f :l} }
         {lambda {:f :l} 
         {{lambda {:c} {:c 
           {lambda {:a :b} :a}}} :l} {:f :f 
           {{lambda {:c} {:c 
             {lambda {:a :b} :b}}} :l}}}} :f :l}}} :l}} 
             {{lambda {:a :b :c} {:c :a :b}} a
             {{lambda {:a :b :c} {:c :a :b}} b
             {{lambda {:a :b :c} {:c :a :b}} c
             {{lambda {:a :b :c} {:c :a :b}} d 
               {lambda {:a} 
                {lambda {:a :b} :a}}}}}}}
-> {{lambda {:l}
{{{lambda {:f} {:f :f}} 
   {lambda {:f :l}
  {{{lambda {:a :b :c} {:a :b :c}}
    {{lambda {:c} {:c 
      {lambda {:a :b} 
       {lambda {:a :b} :b}}}} :l}
        {lambda {:f :l} }
         {lambda {:f :l} 
         {{lambda {:c} {:c 
           {lambda {:a :b} :a}}} :l} {:f :f 
           {{lambda {:c} {:c 
             {lambda {:a :b} :b}}} :l}}}} :f :l}}} :l}} 
             {{lambda {:a :b :c} {:c :a :b}} a
             {{lambda {:a :b :c} {:c :a :b}} b
             {{lambda {:a :b :c} {:c :a :b}} c
             {{lambda {:a :b :c} {:c :a :b}} d 
               {lambda {:a} 
                {lambda {:a :b} :a}}}}}}}

}

_p Cette {b cascade gelée} de lambdas aboutissant au même résultat que {b '{DISP {L}}} éclaire le fonctionnement ultime de tout ce processus. La limite entre les structures de données et de contrôle est totalement gommée, on ne distingue pas de boucle. Pas plus qu'il n'y a de boucles dans le réseau de portes logiques constituant la CPU d'un microprocesseur et probablement dans le monde interconnecté des neurones dans le cerveau. Un évaluateur "magique" percole à travers ces cascades, réseaux, interconnexions, réduisant sur son passage les expressions complexes en expressions plus simples jusqu'à ce qu'il ne reste plus que des mots. Un goût de {i néguentropie} ...

}

{{block}

_h2 conclusion

_p Dans cette rapide balade dans la fabrication d'un langage de programmation nous avons survolé plusieurs concepts :

_ul le remplacement de texte comme fondation ultime,
_ul la fonction anonyme avec "lambda", avec ses variables (aussi appelés arguments), son corps où on les retrouve en attente d'être remplacées par des valeurs à venir, pouvant être en nombre inférieur, égal ou supérieur au nombre des arguments. On peut noter l'absence de contexte lexical, de variable libre, de fermeture, pas d'effet de bord non plus, une fonction est une boite noire ne connaissant que le dictionnaire global,
_ul le nommage avec "def", le dictionnaire global qui contient les noms des fonctions et des primitives, bibliothèque du langage,
_ul les différents types de données, mots, booléens, paires, listes, ...
_ul la récursion, outil principal pour construire des boucles, 
_ul l'évaluation gloutonne ou paresseuse, pour comprendre ce que signifie vraiment le "if then else",
_ul le concept de couche d'abstraction,
_ul la construction des nombres, naturels, réels, complexes, ...
_ul le caractère universel du concept de lambda. auquel tout peut être réduit.

_p L'objectif était d'éviter les zones d'ombres. Ce n'est pas si simple.

_p Au final une page de ce petit traitement de texte contient des séquences de mots et de lambda-expressions analogues, les mots sont ignorés par l'évaluateur de lambdatalk, seules les expressions parenthésées sont évaluées et immédiatement remplacées par d'autres mots, jusqu'à ce qu'il ne reste plus que des mots envoyés au navigateur qui s'occupe de tout le reste jusqu'à l'affichage final.

_p Et voilà ! Pour l'instant ...

_p En attendant vous pourriez parcourir la page [[accueil|?view=start]], les trois pages [[coding]] et quelques autres où vous retrouverez les mêmes choses sous des approches différentes et avec des détails, des explications plus poussées et des applications intéressantes. C'est sans fin.

_p {i alain marty | 2022/10/20}

}

{{block}

_h2 post scriptum

_p Cette page wiki que vous lisez sur votre ordinateur, tablette ou smartphone est un programme lambdatalk, le texte qui la compose est écrit en lambdatalk, les titres, les paragraphes, les images et bien sûr chaque exemple de code sont du code lambdatalk, évalué en temps réel.

_p Le code est écrit dans une fenêtre, appelée fenêtre d'édition, et son évaluation est affichée dans la page wiki. Certains y verront un retour en arrière au début de l'informatique, dans les années 70 avant l'apparition des traitements de texte WYSIWYG tels qu'on les connait à présent, tout le monde connait WORD. Il y a du vrai, tout cela ressemble beaucoup aux consoles d'édition encore utilisées par les codeurs pour écrire les programmes dans des langages comme le C, C++, JAVA, PYTHON, JS, ... de quoi avoir très peur.

_p Mais peu de temps après le traitement de texte est apparu un autre outil qui lui aussi pouvait être perçu comme un retour en arrière, le tableur, et qui est pourtant devenu l'outil préféré des managers de toute sorte. Tout le monde connait EXCEL. Là aussi se trouvaient séparées la fenêtre d'édition contenant le code et la grille où s'affichaient les résultats.

_p Ajoutons au traitement de texte et au tableur le logiciel de présentation POWERPOINT et nous avons les trois piliers des suites bureautiques de MICROSOFT et son équivalent libre, OPENOFFICE.

_p Il se trouve que le monde d'aujourd'hui s'est déplacé sur INTERNET et que les outils pour y travailler sont encore loin des outils bureautiques. Disons que la plupart des gens travaillent en local et partagent leurs documents via des pièces attachées aux mails. Il est assez rare de voir monsieur/madame Toutlemonde construire une page dans un site visible sur le WEB et immédiatement partageable. Cela suppose encore quelques connaissances techniques.

_p En dehors bien sûr des pages FACEBOOK et autres WHATSAPP, INSTAGRAM, TWITTER généreusement fournies par les GAFAM.

_p « {i Quand le service est gratuit c'est nous le service.} »

_p Quand au milieu des années 90 Ward Cunningham a inventé le concept de WIKI, il harmonisait en un tout cohérent les techniques disparates utilisées pour écrire et partager directement sur le WEB, facilitant grandement le {b travail collectif}. Pensez à WIKIPEDIA.

{uncover data/whywikisworks.jpg Le travail collectif, avant et après la naissance du WIKI}

_p  Ceci se faisant au prix d'une séparation entre le code et l'affichage. On codait en utilisant une syntaxe de balisage, le HTML, ou dans une syntaxe plus lisible mais assez limitée, le MARKDOWN, bien suffisante pour écrire dans des forums et des blogs, et on faisait avec. Un certain retour en arrière empêchant d'aller au-delà et de se rapprocher des outils bureautiques. Ce qui a favorisé le glissement vers les solutions toutes faites fournies par les GAFAM, réduisant le plus souvent les échanges à des partages de selfies, de photos de pizzas et des clics sur des boutons LIKE. Dans la satisfaction générale.

_p « {i Tout est bien dans le Meilleur des Mondes.} » [[Il n'y a donc pas de problème !|?view=trombinoscope]]

_p Le projet lambdaway s'attaque modestement à ce "non problème". Il est donc normal que ce genre de tentative soit complètement ignorée. cf [[HN|https://news.ycombinator.com/item?id=42262536]].

_p Dont acte.
}

{{hide}
{def block 
  div {@ style="display:inline-block; width:600px; vertical-align:top; padding:5px; "}}
}

{style 
@font-face {
  font-family: 'Quicksand';
  src: url(data/quicksand.woff) format('woff');
}
body { background:#444; } 
#page_frame { border:0; background:#444; width:600px; margin-left:0; }
#page_content { background:transparent; color:#fff; border:0; width:5200px; box-shadow:0 0 0; font-family:Quicksand, optima; }
.page_menu { background:transparent; color:#fff; } 
a { color:#f80; }
pre { box-shadow:0 0 8px #000; padding:5px; background:#444; color:#fff; font:normal 1.0em courier; }
b { color:cyan; }
h1 { font-size:4.0em; margin:0; }
h2 { font-size:2.5em; margin:0; }
h3 { font-size:1.5em; margin:0; }
h4 { font-size:1.0em; margin:0; }
}