lambdaway :: divine

2 | list | login |load

| |

{toggle} 
{toggle2}

_h2 recursion | [[florilege|?view=Y_en2]]

{{block}
{uncover http://lambdaway.free.fr/workshop/data/le-doigt-de-Dieu.jpg 100 300 Le doigt de Dieu.}

_h2 introduction
  
_pfr {i « L'itération est humaine, la récursion divine. »}
_pen {i « Iteration is human, recursion divine. »}

_pfr En d'autres termes "passez votre chemin" vous ne comprendrez rien à la récursion si vous ne faites pas partie des heureux élus. Dans ce papier, prenant des chemins de traverse oubliés, je me propose de démontrer le contraire, de montrer pourquoi elle nous est consubstantielle et pourquoi elle nous concerne tous en tant qu'humains. 
_pen In other words "go your way" you will not understand anything about recursion if you are not among the lucky ones. In this paper, taking forgotten byways, I propose to demonstrate the opposite, to show why recursion is consubstantial to us and why it concerns us all as humans.

_pfr Je commencerai le voyage avec cette étrange et minuscule expression :
_pen I'll start the journey with this strange and tiny expression:

{center {pre λw.x w}}

_pfr écrite au milieu des années 30 à Princeton par le mathématicien [[Alonzo Church|https://fr.wikipedia.org/wiki/Alonzo_Church]] dans la syntaxe d'un langage qu'il développait, le λ-calcul, une dizaine d'années avant l'apparition du premier ordinateur. 
_pen written in the mid-1930s at Princeton by the mathematician [[Alonzo Church|https://fr.wikipedia.org/wiki/Alonzo_Church]] in the syntax of a language he was developing, the λ-calculus, about ten years before the first computer appeared.

_pfr Le λ-calcul est habituellement défini par les règles suivantes
_pen The λ-calculus is usually defined by the following rules

{pre
x := w               // mot/word
   | λw.x            // abstraction
   | x x             // application
}

_pfr ce qui se lit ainsi « {i une expression {b x} est soit un mot, {b w}, soit une abstraction, {b λw.x}, soit une application, {b x x}.} », ce qui ne nous avance guère pour l'instant. Je note simplement que dans l'application {b x x} le premier {b x} peut être une abstraction, {b λ.w x}, et le second {b x} un mot, {b w}, ce qui conduit à l'expression {b λw.x w} qui va nous servir de base.
_pen which reads " {i an expression {b x} is either a word, {b w}, or an abstraction, {b λw.x}, or an application, {b x x} }", which does not advance us much for the moment. I simply note that in the application {b x x} the first {b x} can be an abstraction, {b λ.w x}, and the second {b x} a word, {b w}, which leads to the expression {b λw.x w} which will serve as a basis.

_pfr Et ça simplifie tout !
_pen And that simplifies everything!

{{geek}
_h4en This page is an editable lambdatalk program!
_h4fr Cette page est un programme lambdatalk modifiable !
_pfr Ce qui veut dire que vous pouvez ouvrir l'éditeur du code de la page - en cliquant sur le mot "concepts"  du titre en haut et à gauche de la page - survoler le code en repérant les correspondances avec l'affichage - c'est facile pour les blocs de texte pur - et, une fois familiarisés, vous pouvez modifier à votre guise, sans autre risque que de devoir recharger la page si les choses vont mal. C'est en bidouillant le code qu'on finit par le comprendre.
_pen This means that you can open the page's code editor - by clicking on the word "concepts" in the title at the top left of the page - hover over the code, spotting matches with the display - this is easy for pure text blocks - and, once you're familiar with it, you can modify it as you like, without any risk other than having to reload the page if things go wrong. It's only by tinkering with the code that you get the hang of it.  
}
}

{{block}
{uncover http://lambdaway.free.fr/workshop/data/le-doigt-de-Dieu.jpg 100 300 Le doigt de Dieu.}
_h2 syntax

_pfr Je ne réécrirai pas, après tant d'autres, une introduction "académique" à ce langage, jugé par certains comme inaccessible au commun des mortels et je commencerai par une commande simple écrite dans mon langage natal, le français.
_pen I will not rewrite, after so many others, an "academic" introduction to this language, considered by some as inaccessible to the common man, and I will start with a simple command written in my native language, french.

{pre
{b remplace :} :a & :b
    {b dans :} Je m'appelle :b, :a :b !
     {b par :} james & bond
}

_pfr Il s'agit donc simplement de remplacer deux mots "{b :a}" et "{b :b}" dans la phrase "{b Je m'appelle :b, :a :b !}" par deux autres mots "{b james}" et "{b bond}". Et je suis sûr que vous devinez la réponse : "{b Je m'appelle bond, james bond !}"
_pen So it's just a matter of replacing two words "{b :a}" and "{b :b}" in the sentence "{b My name is :b, :a :b !}" with two other words "{b james}" and "{b bond}". And I'm sure you can guess the answer, "{b My name is bond, james bond!}"

_pfr Bienvenue dans le monde du {b code}, vous venez d'écrire votre premier "programme", et vous pourrez l'appliquer à toute sorte de prénoms et noms, Ward Cunningham, Monica Bellucci, ... et jouer avec bien d'autres combinaisons différentes, à l'infini.
_pen Welcome to the world of {b code}, you have just written your first "program", and you will be able to apply it to all kinds of names, Ward Cunningham, Monica Bellucci, ... and play with many other different combinations, endlessly.

_pfr Il reste un petit problème : mon ordinateur ne comprend pas ce langage, ne serait-ce que parce qu'il est ... anglophone. J'ai bien essayé de lui parler en anglais 
_pen There is still one small problem: my computer doesn't understand this language, if only because it is... English-speaking. I tried to talk to it in English

{pre
{b replace :} :a & :b
     {b in :} My name is :b, :a :b!
     {b by :} james & bond
}

_pfr sans plus de succès.
_pen without further success.

_pfr Je me suis donc adressé à Alonzo Church qui m'a gentiment proposé de réécrire la formule {b λw.x w} en suivant la syntaxe parenthésée préfixée d'un de ses descendants, John McCarthy, l'inventeur du LISP en 1958. J'ai donc écrit
_pen So I approached Alonzo Church who kindly offered to rewrite the formula {b λw.x w} following the prefixed parenthetical syntax of one of his descendants, John McCarthy, the inventor of LISP in 1958. So I wrote

{pre
'{{lambda {:a :b} 
          My name is :b, :a :b!
 } james bond}
}

_pfr où l'on voit que le mot {b lambda} remplace le mot {b replace} et que les conjonctions {b &, in, by} sont remplacées par un jeu "bien balancé" d'accolades, {b '{}}.
_pen where we see that the word {b lambda} replaces the word {b replace} and that the conjunctions {b &, in, by} are replaced by a "well balanced" set of braces, {b '{}}.

_pfr {b Et ça marche !} Mon ordinateur répond 
_pen {b And it works!} My computer responds

{pre
{{lambda {:a :b} 
          My name is :b, :a :b!
 } james bond} 
}

_pfr {b Note :} Vous pouvez le vérifier par vous-même : ouvrez l'éditeur de cette page (en repérant le titre de la page, {b lambdaway :: divine_recursion} et en cliquant sur le mot {b divine_recursion}) ; puis faites défiler le code jusqu'au passage précédent et constatez que la portion de code {b '{{lambda {:a :b} My name is :b, :a :b!} james bond}} a bien été remplacée par {b {{lambda {:a :b} My name is :b, :a :b!} james bond}}. Remplacez les noms par ce que vous voulez et constatez les changements.
_pen {b Note:} You can check this for yourself: open the editor for this page (by locating the title of the page, {b lambdaway :: divine_recursion} and clicking on the word {b divine_recursion}); then scroll down to the previous passage and see that the portion of code {b '{{lambda {:a :b} My name is :b, :a :b! } james bond}} has been replaced by {b {{lambda {:a :b} My name is :b, :a :b!} james bond}}. Replace the names with whatever you want and see the changes.

_pfr Cette syntaxe est évidemment moins "lisible" que la commande initiale mais le gain est énorme, {b je ne suis plus seul}, j'ai maintenant un compagnon d'une infinie patience qui peut me seconder dans de nombreuses explorations dans le monde des algorithmes, à l'infini. Un compagnon présent dans n'importe quel navigateur web, sur n'importe quel ordinateur, tablette ou smartphone.
_pen This syntax is obviously less "readable" than the initial command but the gain is enormous, {b I am no longer alone}, I now have a companion of infinite patience who can assist me in many explorations in the world of algorithms. A companion present in any web browser, on any computer, tablet or smartphone.

_pfr De manière générale la formule {b λw.x w} s'écrira ainsi
_pen In general, the formula {b λw.x w} can be written as follows

{center {pre 
'{{lambda {:variables} expression} values} 
}}

_pfr Avant de commencer une exploration qui nous conduira pas à pas vers la compréhension sans ombre de la {b récursion}, qui est l'objet de ce papier, je voudrais répondre à une question que vous vous êtes probablement posée : « Pourquoi les noms de variables sont-ils préfixés par un caractère ":" ? » 
_pen Before we begin an exploration that will lead us step by step to the shadowless understanding of {b recursion}, which is the focus of this paper, I would like to answer a question you have probably asked yourself, "Why are variable names prefixed by a ":" character?"

_pfr Testons donc l'écriture sans les ":"
_pen Let's test the writing without the ":"

{pre
'{{lambda {a b} 
          My name is b, a b!
 } james bond} 
-> {{lambda {a b} 
          My name is b, a b!
 } james bond}
}

_pfr Pas vraiment le résultat attendu ! Et pourtant très logique, le caractère {b a} du mot {b name} a lui aussi été remplacé par le mot {b james}, devenant ainsi {b n{u james}me}, et ce n'est pas ce que nous voulons. En préfixant le nom des variables par un caractère "spécial", {b :a}, on protège le caractère {b a} du mot {b name}. Un autre avantage à systématiquement respecter cette convention est que les noms de variable se distinguent mieux des autres mots de la phrase. 
_pen Not really the expected result! And yet very logical, the character {b a} of the word {b name} has also been replaced by the word {b james}, thus becoming {b n{u james}me}, and this is not what we want. By prefixing variable names with a "special" character, {b :a}, we protect the {b a} character of the word {b name}. Another advantage of consistently following this convention is that variable names are more distinct from other words in the sentence.

_pfr La commande initiale s'applique bien sûr à d'autres noms, par exemple
_pen The initial command applies of course to other names, for example

{pre
'{{lambda {:a :b} My name is :b, :a :b!} james bond} 
-> {{lambda {:a :b} My name is :b, :a :b!} james bond}

'{{lambda {:a :b} My name is :b, :a :b!} ward cunningham} 
-> {{lambda {:a :b} My name is :b, :a :b!} ward cunningham}

'{{lambda {:a :b} My name is :b, :a :b!} monica bellucci} 
-> {{lambda {:a :b} My name is :b, :a :b!} monica bellucci} 
}
}

{{block}
{uncover http://lambdaway.free.fr/workshop/data/le-doigt-de-Dieu.jpg 100 300 Le doigt de Dieu.}
_h2 lambda & def

_pfr C'est quand même un peu lourd et répétitif. Donnons un nom simple, par exemple {b HI}, à l'expression interne {b '{lambda {:a :b} My name is :b, :a :b!}} qui revient trois fois à l'identique
_pen It's still a bit cumbersome and repetitive. Let's give a simple name, for example {b HI}, to the internal expression {b '{lambda {:a :b} My name is :b, :a :b!}} which comes back three times in the same way

{pre
'{def HI {lambda {:a :b} My name is :b, :a :b!}}
-> {def HI {lambda {:a :b} My name is :b, :a :b!}}
} 
 
_pfr où {b def} signifie {b définir}. On vient de créer une {b abstraction}, on a caché l'expression {b '{lambda {:a :b} My name is :b, :a :b!}} sous le nom {b HI}. Nous avons créé une {b fonction} attendant deux mots, cette fonction est enregistrée dans un {b dictionnaire}. Et on peut maintenant réécrire de façon très lisible les trois commandes précédentes
_pen where {b def} means {b define}. We have just made an {b abstraction}, we have hidden the expression {b '{lambda {:a :b} My name is :b, :a :b!}} under the name {b HI}. We have created a {b function} waiting for two words, this function is stored in a {b dictionary}. And we can now rewrite the three previous commands in a very readable way

{pre
'{HI james bond}
-> {HI james bond}

'{HI ward cunningham}
-> {HI ward cunningham}

'{HI monica belluci}
-> {HI monica belluci}
}

_pfr Nous avons appliqué des {b abstractions} à des {b mots}. C'est exactement ainsi que nous allons procéder pour la suite, utilisant de façon conjointe des {b abstractions} et des {b applications} opérant sur des {b mots}. L'abstraction, principe féminin, le Yin, et l'application, principe masculin, le Yang, opêrant sur un océan de mots. Au début êtait le {b verbe}. Un avant-gout du {b TAO}. Pourquoi pas ? 
_pen We have applied {b abstractions}, (functions) to words. This is exactly how we will proceed in the following, using both {b abstractions} and {b applications} operating on {b words}. The abstraction, the feminine principle, Yin, and the application, the masculine principle, Yang, operating on a sea of words. In the beginning was the {b verb}. A foretaste of {b TAO}. Why not?

_pfr Nous avons maintenant l'outillage nécessaire et suffisant pour construire les fondations d'un langage primitif.
_pen We now have the necessary and sufficient tools to build the foundations of a primitive language.

_pfr {b Note :} j'ai pris le parti de choisir l'anglais dans les exemples de code, afin de rester proche des noms utilisés dans la littérature informatique. 
_pen {b Note :} I have chosen to use English in the code examples, in order to stay close to the names used in the computer literature.

_pfr Comme premier exemple de fonction voici la fonction identité, {b I}
_pen As a first example of a function here is the identity function, {b I}

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

'{I james}
-> {I james}

'{I ward}
-> {I ward}
}

_pfr On a bien compris, {b I} n'est autre que {b '{lambda {:a} :a}} qui attend un mot et le retourne tel quel. Continuons avec une fonction échangeant deux mots
_pen We have understood well, {b I} is none other than {b '{lambda {:a} :a}} which waits for a word and returns it as is. Let's continue with a function exchanging two words

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

'{SWAP james bond}
-> {SWAP james bond}
}

_pfr Rien n'empêche de combiner les fonctions {b HI} et {b SWAP}
_pen There is nothing to prevent combining the functions {b HI} and {b SWAP}

{pre
'{def YEP
 {lambda {:a :b}
  My name is :b, {SWAP :a :b}!
}} 
-> {def YEP
 {lambda {:a :b}
  My name is :b, {SWAP :a :b}!
}}

'{YEP james bond}
-> {YEP james bond}
}

_pfr Faites une pause. Essayez d'écrire la fonction {b YEP} en langage naturel et vous comprendrez vite en quoi la syntaxe choisie devient vite indispensable.
_pen Take a break. Try to write the function {b YEP} in natural language and you will quickly understand how the chosen syntax becomes indispensable.

_pfr Dans tout ce qui précède il ne s'agit que de remplacement de texte, on joue avec des mots. Mais d'habiles combinaisons de mots et de fonctions vont nous permettre de créer des {b assemblages} bien plus complexes, à l'infini. Commençons par un jeu de fonctions introduisant un concept clé, le {b choix}.
_pen In all of the above, we are only talking about text replacement, we are playing with words. But clever combinations of words and functions will allow us to create much more complex {b assemblies}, ad infinitum. Let's start with a set of functions introducing a key concept, the {b choice}.
}

{{block}
{uncover http://lambdaway.free.fr/workshop/data/le-doigt-de-Dieu.jpg 100 300 Le doigt de Dieu.}
_h2 bifurcation

_pfr Il y a toujours le moment où l'on doit choisir entre deux chemins. C'est là qu'apparaissent deux mots chargés de sens, le vrai et le faux, {b TRUE & FALSE}.
_pen There is always the moment when one has to choose between two paths. This is where two words with meaning appear, true and false, {b TRUE & FALSE}.

{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 da niet}
-> {TRUE da niet}

'{FALSE da niet}
-> {FALSE da niet}
}

_pfr Analysons {b '{TRUE da niet}}
_pen Let's analyse {b '{TRUE da niet}}

{pre
0: '{TRUE da niet}

- TRUE => '{lambda {:a :b} :a}
  - da   => da
  - niet => niet

↑‾‾‾‾‾‾↓
1: '{{lambda {:a :b} :a} da niet}
              ↑__________↓

2: da
}

_pfr A ce stade l'essentiel est de comprendre la simplicité du processus, la fonction {b TRUE} retourne le premier des deux mots, la fonction {b FALSE} retourne le second. On ajoute une troisième fonction, {b IF}
_pen At this stage the main thing is to understand the simplicity of the process, the function {b TRUE} returns the first of the two words, the function {b FALSE} returns the second. We add a third function, {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}
}

_pfr Que peut bien signifier le corps de la lambda, {b '{:a :b :c}} ? Analysons le fonctionnement de l'expression {b '{IF TRUE oui non}} en remplaçant les noms par leurs lambda expressions 
_pen What can the body of the lambda expression, {b '{:a :b :c}}, mean? Let's analyze how the expression {b '{IF TRUE oui non}} works by replacing the names with their lambda expressions

{pre {@ ondblclick="showblock(this)"}
0: '{IF TRUE oui non}

- IF   => '{lambda {:a :b :c} {:a :b :c}}
  - TRUE => '{lambda {:a :b} :a}
  - oui  => oui
  - non  => oui

↓‾‾‾‾‾‾‾‾‾↑_________________
1: '{{lambda {:a :b :c} {:a :b :c}} {lambda {:a :b} :a} oui non}
                            ↑__↑________________________↓___↓

- :a => '{lambda {:a :b} :a}, ;; qui forme un tout
  - :b => oui,
  - :c => non.

↑‾‾‾‾‾‾↓
2: '{{lambda {:a :b} :a} oui non}
              ↑__________↓
  - :a => oui

3: oui

et voilà !
}

_pfr Relisez bien, lentement, jusqu'à ce que cette suite de remplacements vous devienne famillière. C'est du solfège, de l'algèbre, c'est un cap à passer, pas si facile. Mais c'est bien plus simple que les règles du tennis ... que je n'ai jamais eu la patience de lire jusqu'au bout. Mais ici l'effort nous donne la clé d'accès au monde du code. Le retour sur investissement est assuré. Courage.
_pen Read it again, slowly, until this sequence of replacements becomes familiar to you. It's solfeggio, algebra, it's a step to take, not so easy. But it is much simpler than the rules of tennis ... which I never had the patience to read to the end. But here the effort gives us the key to the world of code. The return on investment is assured. Take heart.

_pfr En l'espace de trois petites fonctions nous venons de créer une "structure de contrôle" {b if then else}, "{i si une condition est remplie alors prend le premier mot sinon le second.}" Notons que cela ne fonctionne que pour deux mots, il n'est pas encore possible de choisir entre deux phrases. Pour cela nous devrons construire des aggrégations de mots, des structures de données, à commencer par l'agrégation de deux mots.
_pen In the space of three small functions we have just created a "control structure" {b if then else}, "{i if a condition is met then takes the first word otherwise the second.}" Note that this only works for two words, it is not yet possible to choose between two sentences. For that we will have to build word aggregations, data structures, starting with the two-word aggregation.
}

{{block}
{uncover http://lambdaway.free.fr/workshop/data/le-doigt-de-Dieu.jpg 100 300 Le doigt de Dieu.}
_h2 agregation

_pfr Une phrase est une suite de mots, il est utile de la considérer comme un tout. Commençons avec deux mots.
_pen A sentence is a sequence of words, so it is useful to think of it as a whole. Let's start with two words.

_pfr On définit une {b paire}, un couple de deux mots, à l'aide de trois fonctions, une fonction construisant la paire, {b PAIR}, et deux fonctions retournant chacun des deux mots aggrégés, {b LEFT & RIGHT}.
_pen We define a {b pair}, a pair of two words, using three functions, a function constructing the pair, {b PAIR}, and two functions returning each of the two aggregated words, {b LEFT & RIGHT}.

{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 JB {PAIR james bond}}
-> {def JB {PAIR james bond}}

'{LEFT {JB}}
-> {LEFT {JB}}

'{RIGHT {JB}}
-> {RIGHT {JB}}
}

_pfr Analysons le fonctionnement de l'expression {b '{LEFT {JB}}} en remplaçant les noms par leurs lambda expressions 
_pen Let's analyze how the expression {b '{LEFT {JB}}} works by replacing the names by their lambda expressions

{pre {@ ondblclick="showblock(this)"}
0: '{LEFT {JB}}
  - LEFT => '{lambda {:c} {:c TRUE}}
  - '{JB} => '{PAIR james bond}

1: '{{lambda {:c} {:c TRUE}} {PAIR james bond}}
  - TRUE => '{lambda {:a :b} :a}
  - PAIR => '{lambda {:a :b :c} {:c :a :b}}

2: '{{lambda {:c} {:c {lambda {:a :b} :a}}}
                            {{lambda {:a :b :c} {:c :a :b}} james bond}}
  - '{{lambda {:a :b :c} {:c :a :b}} james bond}
         => '{lambda {:c} {:c james bond}}

3: '{{lambda {:c} {:c {lambda {:a :b} :a}}}
                            {lambda {:c} {:c james bond}}}
  - :c => '{lambda {:c} {:c james bond}}

4: '{{lambda {:c} {:c james bond}} {lambda {:a :b} :a}}
  - :c => '{lambda {:a :b} :a}

5: '{{lambda {:a :b} :a} james bond}
  - :a => james

6: james
}

_pfr Toujours là ?
_pen Still here?
 
_pfr Oui c'est laborieux, mais c'est une application absolument systématique du processus de remplacement qui devrait devenir quasi automatique, et qui l'est de fait pour l'ordinateur, sans état d'âme, à la vitesse de la lumière.
_pen Yes, it is laborious, but it is an absolutely systematic application of the replacement process which should become almost automatic, and which is in fact automatic for the computer, without any qualms, at the speed of light.

_pfr  Le seul point délicat, car nouveau, se trouve dans le passage de la ligne {b 2:} à la ligne {b 3:}. En effet dans l'expression {b '{{lambda {:a :b :c} {:c :a :b}} james bond}} on note que la fonction attend trois valeurs, {b :a, :b, :c} et qu'elle n'en reçoit que deux. Eh bien elle s'en contente et retourne à la volée une nouvelle fonction "anonyme" {b '{lambda {:c} {:c james bond}}} dans laquelle les variables {b :a & :b} ont été remplacées par les mots {b james & bond}, et ainsi mémorisés. Cette fonction qui ne possède qu'un argument, {b :c}, est appelée par la fonction {b LEFT} qui fera son travail d'extraction jusqu'au résultat, {b james}.
_pen The only tricky point, because it is new, is in the passage from the line {b 2:} to the line {b 3:}. In the expression {b '{{lambda {:a :b :c} {:c :a :b}} james bond}} we note that the function expects three values, {b :a, :b, :c} and that it receives only two. Well, it is satisfied with this and returns a new "anonymous" function {b '{lambda {:c} {:c james bond}}} in which the variables {b :a & :b} have been replaced by the words {b james & bond}, and thus stored. This function which has only one argument, {b :c}, is called by the function {b LEFT} which will do its job of extracting the result, {b james}.

_pfr Plutôt que d'être effrayé par l'apparente complexité de la séquence des remplacements, {i dont on n'aura jamais à se soucier}, je vous propose de louer la puissance d'une telle syntaxe qui cache un mécanisme "pénible" sous une simple expression, {b '{LEFT {JB}}}. Qui n'a d'égale que la puissance elle-même du concept de {b PAIR}e.
_pen Rather than being frightened by the apparent complexity of the sequence of replacements, {i which one will never have to worry about}, I suggest you praise the power of such a syntax which hides a "painful" mechanism under a simple expression, {b '{LEFT {JB}}}. Which is matched only by the power itself of the concept of {b PAIR}e.

_pfr Deux fonctions supplémentaires, {b NIL & ISNIL}, vont nous être utiles pour répondre à la question : "est-ce une paire ou non ?". 
_pen Two additional functions, {b NIL & ISNIL}, will be useful to answer the question: "is it a pair or not?".

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

'{ISNIL NIL}
-> {ISNIL NIL}

'{ISNIL {JB}}
-> {ISNIL {JB}}
}

_pfr Acceptez ces définitions sans plus d'explications pour l'instant. Je vous laisse le loisir de détailler le fonctionnement des deux dernières expressions.
_pen Accept these definitions without further explanation for now. I will leave it to you to explain in detail how the last two expressions work.
}

{{block}
{uncover http://lambdaway.free.fr/workshop/data/le-doigt-de-Dieu.jpg 100 300 Le doigt de Dieu.}
_h2 recursion

_pfr Une {b liste} est une {b paire} dont le terme de gauche est un {b mot} et le terme de droite est une {b paire} ou la fonction {b NIL}. Notons que la définition contient en son corps le mot qu'on cherche à définir, {b paire = liste}, il s'agit du premier exemple d'une forme auto-référente, une structure {b récursive}. 
_pen A {b list} is a {b pair} whose left term is a {b word} and whose right term is a {b pair} or the {b NIL} function. Note that the definition contains in its body the word we want to define, {b paire = list}, this is the first example of a self-referential form, a {b recursive} structure.

_pfr Par exemple
_pen For instance

{pre
'{def LIST
 {PAIR hello
  {PAIR brave
   {PAIR new
    {PAIR world NIL}}}}}
-> {def LIST
 {PAIR hello
  {PAIR brave
   {PAIR new
    {PAIR world NIL}}}}}
}

_pfr Voici comment on accède à chacun des termes de la liste:
_pen Here is how to access each of the terms in the list:

{pre
1: '{LEFT {LIST}}                         -> {LEFT {LIST}}
2: '{LEFT {RIGHT {LIST}}}                 -> {LEFT {RIGHT {LIST}}}
3: '{LEFT {RIGHT {RIGHT {LIST}}}}         -> {LEFT {RIGHT {RIGHT {LIST}}}}
4: '{LEFT {RIGHT {RIGHT {RIGHT {LIST}}}}} -> {LEFT {RIGHT {RIGHT {RIGHT {LIST}}}}}
}

_pfr Par curiosité testons à chaque étape la partie droite de la liste
_pen For curiosity let's test at each step the right part of the list

{pre
'{ISNIL {LIST}}                                 -> {ISNIL {LIST}}
'{ISNIL {RIGHT {LIST}}}                         -> {ISNIL {RIGHT {LIST}}}
'{ISNIL {RIGHT {RIGHT {LIST}}}}                 -> {ISNIL {RIGHT {RIGHT {LIST}}}}
'{ISNIL {RIGHT {RIGHT {RIGHT {LIST}}}}}         -> {ISNIL {RIGHT {RIGHT {RIGHT {LIST}}}}}
'{ISNIL {RIGHT {RIGHT {RIGHT {RIGHT {LIST}}}}}} -> {ISNIL {RIGHT {RIGHT {RIGHT {RIGHT {LIST}}}}}}
}

_pfr On peut voir apparaître un {b motif} répétitif. Sans plus d'explication voici un algorithme qui automatise tout cela :
_pen We can see a repetitive {b pattern} appear. Without further explanation here is an algorithm that automates all this:

{pre
'{def DISP
 {lambda {:list}
  {{IF {ISNIL :list}
   {lambda {:list} }
   {lambda {:list} {LEFT :list}
                   {DISP {RIGHT :list}}}} :list}}}
-> {def DISP
 {lambda {:list}
  {{IF {ISNIL :list}
   {lambda {:list} }
   {lambda {:list} {LEFT :list}
                   {DISP {RIGHT :list}}}} :list}}}

'{DISP {LIST}}
-> {DISP {LIST}}
}

_pfr Ça marche et il ne reste plus qu'à comprendre comment ça marche. En donnant des noms, {b YES & NO}, aux deux lambdas internes :
_pen It works and all that's left is to understand how it works. By giving names, {b YES & NO}, to the two internal lambdas:

{pre
'{def YES {lambda {:list} }}
-> {def YES {lambda {:list} }}
'{def NO {lambda {:list} {LEFT :list} {DISP {RIGHT :list}}}}
-> {def NO {lambda {:list} {LEFT :list} {DISP {RIGHT :list}}}}
}

_pfr la fonction {b DISP} s'écrit plus simplement
_pen the function {b DISP} is written more simply

{pre
'{def DISP
 {lambda {:list}
  {{IF {ISNIL :list} YES NO} :list}}}
}

_pfr Lançons-nous dans l'analyse de l'expression {b '{DISP {LIST}}}
_pen Let's analyse th {b '{DISP {LIST}}} expression

{pre {@ ondblclick="showblock(this)"} 
 
0: '{DISP {LIST}}
  - DISP => '{lambda {:list} {{IF {ISNIL :list} YES NO} :list}}
  - '{LIST} =>  '{PAIR hello {PAIR brave {PAIR new {PAIR world NIL}}}}

1: '{{lambda {:list} {{IF {ISNIL :list} YES NO} :list}}
             {PAIR hello {PAIR brave {PAIR new {PAIR world NIL}}}}}
  - :list => '{PAIR hello {PAIR brave {PAIR new {PAIR world NIL}}}}

2: '{{IF {ISNIL {PAIR hello {PAIR brave {PAIR new {PAIR world NIL}}}}} YES NO}
        {PAIR hello {PAIR brave {PAIR new {PAIR world NIL}}}}}
  - '{ISNIL {PAIR hello {PAIR brave {PAIR new {PAIR world NIL}}}}} 
          => FALSE

3: '{{IF FALSE YES NO} {PAIR hello {PAIR brave {PAIR new {PAIR world NIL}}}}}
  - '{IF FALSE YES NO} => NO

4: '{NO {PAIR hello {PAIR brave {PAIR new {PAIR world NIL}}}}}
  - NO => '{lambda {:list} {LEFT :list} {DISP {RIGHT :list}}}

5: {{lambda {:list} {LEFT :list} {DISP {RIGHT :list}}}
                 {PAIR hello {PAIR brave {PAIR new {PAIR world NIL}}}}}
  - :list => '{PAIR hello {PAIR brave {PAIR new {PAIR world NIL}}}}

6: '{LEFT {PAIR hello {PAIR brave {PAIR new {PAIR world NIL}}}}} 
       '{DISP {RIGHT {PAIR hello {PAIR brave {PAIR new {PAIR world NIL}}}}}}
  - '{LEFT {PAIR hello {PAIR brave {PAIR new {PAIR world NIL}}}}} => hello
  - '{DISP {RIGHT {PAIR hello {PAIR brave {PAIR new {PAIR world NIL}}}}}}
          => '{DISP {PAIR brave {PAIR new {PAIR world NIL}}}}

7: hello '{DISP {PAIR brave {PAIR new {PAIR world NIL}}}}
}

_pfr A cet instant le premier terme est affiché et la fonction {b DISP} est appliquée au reste de la liste, {b brave new world}. En recommençant successivement le même processus on obtient
_pen At this moment the first term is displayed and the function {b DISP} is applied to the rest of the list, {b brave new world}. By repeating successively the same process we obtain

{pre
1: hello '{DISP {PAIR brave {PAIR new {PAIR world NIL}}}}
2: hello brave '{DISP {PAIR new {PAIR world NIL}}}
3: hello brave new '{DISP {PAIR world NIL}}
4: hello brave new world '{DISP NIL}
}

_pfr Finalement l'expression {b '{DISP NIL}} s'évalue ainsi
_pen Finally the expression {b '{DISP NIL}} is evaluated as follows

{pre
0: '{DISP NIL}
  - DISP => '{lambda {:list} {{IF {ISNIL :list} YES NO} :list}}

1: '{{lambda {:list} {{IF {ISNIL :list} YES NO} :list}} NIL} 
  - :list => NIL

2: '{{IF {ISNIL NIL} YES NO} NIL}
  - '{ISNIL NIL} => TRUE

3: '{{IF TRUE YES NO} NIL}
  - '{IF TRUE YES NO} => YES

4: '{YES NIL}
  - YES => '{lambda {:list} }

5:  rien/nothing
}

_pfr Et voilà ! {b DISP} est donc une fonction récursive affichant automatiquement les termes d'une liste {b LIST}, {b hello brave new world}. En voici une autre renversant l'ordre des mots de la liste :
_pen So {b DISP} is a recursive function that automatically displays the terms of a list {b LIST}, {b hello brave new world}. Here is another one that reverses the order of the words in the list:

{pre
'{def REVERSE
 {lambda {:list}
  {{IF {ISNIL :list}
   {lambda {:list} }
   {lambda {:list} {REVERSE {RIGHT :list}}
                   {LEFT :list}}} :list}}}
-> {def REVERSE
 {lambda {:list}
  {{IF {ISNIL :list}
   {lambda {:list} }
   {lambda {:list} {REVERSE {RIGHT :list}}
                   {LEFT :list}}} :list}}}

'{REVERSE {LIST}}
-> {REVERSE {LIST}}
}

_pfr Et une dernière retournant la longueur de la liste.
_pen And a last one returning the length of the list.

{pre
'{def LENGTH
 {lambda {:list}
  {{IF {ISNIL :list}
   {lambda {:list} }
   {lambda {:list} •{LENGTH {RIGHT :list}}}} :list}}}
-> {def LENGTH
 {lambda {:list}
  {{IF {ISNIL :list}
   {lambda {:list} }
   {lambda {:list} •{LENGTH {RIGHT :list}}}} :list}}}

'{LENGTH {LIST}}
-> {LENGTH {LIST}}
}

_pfr Je suis sûr que vous lisez {b 4}, sous une forme primaire boen sûr, mais qui laisse imaginer comment on pourrait introduire les nombres et l'arithmétique dans un monde qui ne connait que les mots. La page [[coding]] en indique quelques pistes. 
_pen I'm sure you read {b 4}, in a primary form of course, but that lets you imagine how one could introduce numbers and arithmetic in a world that only knows words. The [[coding]] page shows some tracks.

_pfr En conclusion provisoire, il faut se rappeler que depuis le début il ne s'agit que de remplacements de texte, un processus systématique, sans exception. En utilsant les deux formes spéciales {b lambda} et {b def} nous avons construit les fonctions booléennes {b TRUE, FALSE, IF}, les fonctions sur les paires {b PAIR, LEFT, RIGHT, NIL, ISNIL}, les listes et quelques fonctions opérant sur les listes. Il en existe bien d'autres mais c'est une autre histoire. Dans ce papier nous allons retourner aux sources, du côté de cette petite formule où tout a commencé : {b λw.x w}.
_pen As a provisional conclusion, it should be remembered that from the beginning it is only about text replacements, a systematic process, without exception. Using the two special forms {b lambda} and {b def} we have built the boolean functions {b TRUE, FALSE, IF}, functions on pairs {b PAIR, LEFT, RIGHT, NIL, ISNIL}, lists and some functions operating on lists. There are many others but that's another story. In this paper we will go back to the sources, to the side of this little formula where it all started: {b λw.x w}.
}

{{block}
{uncover http://lambdaway.free.fr/workshop/data/le-doigt-de-Dieu.jpg 100 300 Le doigt de Dieu.}
_h2 back to lambdas

_pfr Afin de comprendre la puissance contenue dans l'expression initiale {b '{{lambda {:variables} expression} valeurs}} nous allons démontrer qu'une expression comme {b '{DISP {LIST}}} peut s'écrire sous la forme d'une cascade de lambdas. Pour cela nous devons remplacer les noms par leurs lambda expression équivalentes. 
_pen In order to understand the power contained in the initial expression {b '{{lambda {:variables} expression} values}} we will demonstrate that an expression like {b '{DISP {LIST}}} can be written as a cascade of lambdas. To do this we need to replace the names with their equivalent lambda expressions.

_pfr Il y a un obstacle majeur à cela, la fonction {b DISP} est récursive et contient dans son corps son propre nom. Il faut trouver une expression équivalente ne faisant aucune auto-référence au nom. La solution relève de la magie, elle a fait couler beaucoup d'encre mais au fond c'est très simple.
_pen There is one major obstacle to this, the function {b DISP} is recursive and contains in its body its own name. We need to find an equivalent expression that does not self-reference the name. The solution is magic, it has been much talked about but it is actually very simple.

_pfr On commence par remplacer la fonction récursive {b DISP} par une nouvelle {b ADISP}, presque récursive, qui contient son nom sous forme de référence locale, et on l'applique à elle même puis à la liste
_pen We start by replacing the recursive function {b DISP} by a new {b ADISP}, almost recursive, which contains its name as a local reference, and we apply it to itself and then to the list

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

'{ADISP ADISP {LIST}}
-> {ADISP ADISP {LIST}}
}

_pfr On améliore cette technique en définissant une fonction annexe, appelée le {b Ω combinateur}, qui applique la fonction à elle-même
_pen We improve this technique by defining an auxiliary function, called the {b Ω combiner}, which applies the function to itself

{pre
'{def Ω {lambda {:f} {:f :f}}}
-> {def Ω {lambda {:f} {:f :f}}}

'{{Ω ADISP} {LIST}}
-> {{Ω ADISP} {LIST}}
}

_pfr On fusionne les deux fonctions en une nouvelle fonction {b ΩDISP}
_pen We merge the two functions into a new function {b ΩDISP}

{pre
'{def ΩDISP {lambda {:l} {{Ω ADISP} :l}}}
-> {def ΩDISP {lambda {:l} {{Ω ADISP} :l}}}
}

_pfr soit
_pen in other words

{pre
'{def ΩDISP
 {lambda {:l}
  {{{lambda {:f} {:f :f}} 
   {lambda {:f :l}
    {{IF {ISNIL :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 {ISNIL :l}
     {lambda {:f :l} }
     {lambda {:f :l} {LEFT :l} {:f :f {RIGHT :l}}}} :f :l}}} :l}}}

'{ΩDISP {LIST}}
-> {ΩDISP {LIST}}
}

_pfr On peut maintenant oublier le nom {b ΩDISP}
_pen We can now forget the name {b ΩDISP}

{pre
'{{lambda {:l}
  {{{lambda {:f} {:f :f}} 
   {lambda {:f :l}
    {{IF {ISNIL :l}
     {lambda {:f :l} }
     {lambda {:f :l} {LEFT :l} {:f :f {RIGHT :l}}}} :f :l}}} :l}}
 {LIST}}
-> {{lambda {:l}
  {{{lambda {:f} {:f :f}} 
   {lambda {:f :l}
    {{IF {ISNIL :l}
     {lambda {:f :l} }
     {lambda {:f :l} {LEFT :l} {:f :f {RIGHT :l}}}} :f :l}}} :l}}
 {LIST}}
}

_pfr et enfin remplacer soigneusement tous les noms par leurs lambda expressions
_pen and then carefully replace all the names with their lambda expressions

{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}} hello
             {{lambda {:a :b :c} {:c :a :b}} brave
             {{lambda {:a :b :c} {:c :a :b}} new
             {{lambda {:a :b :c} {:c :a :b}} world 
               {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}} hello
            {{lambda {:a :b :c} {:c :a :b}} brave
            {{lambda {:a :b :c} {:c :a :b}} new
            {{lambda {:a :b :c} {:c :a :b}} world 
              {lambda {:a} 
               {lambda {:a :b} :a}}}}}}}
}
}

{{block}
{uncover http://lambdaway.free.fr/workshop/data/le-doigt-de-Dieu.jpg 100 300 Le doigt de Dieu.}

_h2 conclusion

_pfr Le λ-calcul tel que nous l'avons exploré dans ce papier nous a permis de construire sur une seule forme, la {b lambda} expression agissant sur des mots, est sans aucune zone d'ombre, les briques essentielles d'un langage de programmation, notamment la {b divine récursion}. Le reste peut être analysé ailleurs dans ce wiki, notamment dans [[coding]] et [[concepts]].
_pen The λ-calculus as we explored it in this paper allowed us to build on a single form, the {b lambda} expression acting on words, is without any grey area, the essential building blocks of a programming language, notably the {b divine recursion}. The rest can be analyzed elsewhere in this wiki, notably in [[coding]] and [[concepts]].

_pfr Reste maintenant à montrer en quoi la récursion nous est "consubstantielle" et en quoi elle nous concerne tous. 
_pen It remains now to show how recursion is "consubstantial" to us and how it concerns us all.

_pfr En quoi par exemple la cascade de lambdas produisant la phrase "{b hello brave new world}" est-elle révélatrice du fonctionnement de notre cerveau, ou tout au moins de notre pensée ? Dans une autre page, [[4bit_adder2]], j'ai écrit ceci
_pen For example, how does the cascade of lambdas producing the sentence "{b hello brave new world}" reveal the functioning of our brain, or at least our thinking? In another page, [[4bit_adder2]], I wrote this

{pre
'{def 4bitsAdder
 {lambda {:a4 :a3 :a2 :a1 
          :b4 :b3 :b2 :b1}
  {{lambda {:a4 :a3 :a2 :b4 :b3 :b2 :fa1}
  {{lambda {:a4 :a3 :b4 :b3 :fa1 :fa2}
  {{lambda {:a4 :b4 :fa1 :fa2 :fa3}   
  {{lambda {:fa1 :fa2 :fa3 :fa4}
           {car :fa4} {cdr :fa4} {cdr :fa3}
                      {cdr :fa2} {cdr :fa1}
   } :fa1 :fa2 :fa3 {fullAdder :a4 :b4 {car :fa3}}}
   } :a4 :b4 :fa1 :fa2 {fullAdder :a3 :b3 {car :fa2}}}
   } :a4 :a3 :b4 :b3 :fa1 {fullAdder :a2 :b2 {car :fa1}}}
   } :a4 :a3 :a2 :b4 :b3 :b2 {halfAdder :a1 :b1} 
}}} 
-> 4bitsAdder

'{4bitsAdder false true true true         //   0111    3
            false false false true}      // + 0001  + 1
-> false true false false false          // = 1000  = 4
}

_pfr Nous voila devant un algorithme statique, sans boucle, capable de faire la somme de deux nombres binaires, ici {b 3+1=4}. C'Est ainsi que fonctionnent les portes logiques dans une unité de traitement parmi les millions que contient un microprocesseur. Deux nombres se présentent en entrée et par une mystérieuse percolation à travers ces portes logiques se retrouve leur somme en sortie. Une opération qui ne peut s'imaginer que comme une suite d'étapes du genre 3+4 = 2+5 = 1+6 = 0+7 donc le résulat est 7 semble "hard-codée", codée en dur dans le coeur du processeur. 
_pen Here we are in front of a static algorithm, without loop, able to make the sum of two binary numbers, here {b 3+1=4}. This is how logic gates work in a processing unit among the millions that a microprocessor contains. Two numbers are presented as input and by a mysterious percolation through these logic gates, their sum is found as output. An operation that can only be imagined as a sequence of steps like 3+4 = 2+5 = 1+6 = 0+7, so the result is 7, seems to be "hard-coded", hard-coded in the heart of the processor.

_pfr Dans une autre page, [[concepts]], j'en suis arrivé à cette autre cascade de lambdas :
_pen In another page, [[concepts]], I came to this other cascade of lambdas:

{pre
'{{{lambda {:g} {:g :g}} 
   {lambda {:g :n :a :b :c}
  {{{lambda {:a :b :c} {:a :b :c}}
    {{lambda {:c} {:c 
      {lambda {:a :b} 
       {lambda {:a :b} :b}}}} :n}
        {lambda {:g :n :a :b :c} }
         {lambda {:g :n :a :b :c} {:g :g 
         {{lambda {:c} {:c 
           {lambda {:a :b} :b}}} :n} :a :b :c} {div} move 
           {{lambda {:c} {:c 
             {lambda {:a :b} :a}}} :n} from tower :a to tower :b {:g :g
             {{lambda {:c} {:c 
               {lambda {:a :b} :b}}} :n} :c :b :a} }} :g :n :a :b :c}}}
               {{lambda {:a :b :c} {:c :a :b}} ■■■■.■■■■
               {{lambda {:a :b :c} {:c :a :b}}  ■■■.■■■
               {{lambda {:a :b :c} {:c :a :b}}   ■■.■■
               {{lambda {:a :b :c} {:c :a :b}}    ■.■   
                 {lambda {:a}
                  {lambda {:a :b} :a}}}}}} A B C}
->
{{{lambda {:g} {:g :g}} 
   {lambda {:g :n :a :b :c}
  {{{lambda {:a :b :c} {:a :b :c}}
    {{lambda {:c} {:c 
      {lambda {:a :b} 
       {lambda {:a :b} :b}}}} :n}
        {lambda {:g :n :a :b :c} }
         {lambda {:g :n :a :b :c} {:g :g 
         {{lambda {:c} {:c 
           {lambda {:a :b} :b}}} :n} :a :b :c} {div} move 
           {{lambda {:c} {:c 
             {lambda {:a :b} :a}}} :n} from tower :a to tower :b {:g :g
             {{lambda {:c} {:c 
               {lambda {:a :b} :b}}} :n} :c :b :a} }} :g :n :a :b :c}}}
               {{lambda {:a :b :c} {:c :a :b}} ■■■■.■■■■
               {{lambda {:a :b :c} {:c :a :b}}  ■■■.■■■
               {{lambda {:a :b :c} {:c :a :b}}   ■■.■■
               {{lambda {:a :b :c} {:c :a :b}}    ■.■   
                 {lambda {:a}
                  {lambda {:a :b} :a}}}}}} A B C}
}

_pfr Il s'agit de la suite des mouvements de disques dans le jeu des Tours de Hanoï. L'évaluateur a remplacé la cascade figée par une noria de disques. L'évaluateur a parcouru le labyrinthe des lambdas à la vitesse de l'éclair et 4 disques empilés sont passés d'une tour à l'autre.
_pen This is the sequence of disc movements in the Towers of Hanoi game. The evaluator replaced the frozen waterfall with a noria of discs. The evaluator went through the maze of lambdas at lightning speed and 4 stacked discs went from one tower to another.

_pfr Prenez bien conscience qu'il y a une totale équivalence entre la cascade de lambdas, le code, et la séquence de mouvements, le résultat, "code is data". Ce sont deux aspects de la même chose, les deux faces de la même pièce. Mais il y quand même une différence, on peut passer des lambdas aux mouvements mais pas l'inverse. Une histoire d'entropie croissante. Même énergie mais qualité différente. On a perdu l'algorithme pour ne garder que le résultat. Je pense que notre cerveau conserve les algorithmes et que nos prises de conscience en sont des évaluations fulgurantes. Enseigner, par exemple, ce n'est pas partager les résultats, c'est partager les algorithmes. Convaincre ce n'est pas asséner des résultats, c'est échanger des algorithmes. Les images que nous mémorisons ne peuvent être vues dans un scanner, le scanner ne voit que des aiguillages. Observer un microprocesseur au microscope ne donne aucune information sur les algorithmes qui l'habitent, percolent à travers les portes logiques.
_pen Be aware that there is a total equivalence between the cascade of lambdas, the code, and the sequence of movements, the result, "code is data". They are two aspects of the same thing, two sides of the same coin. But there is a difference, we can go from lambdas to movements but not the other way around. A story of increasing entropy. Same energy but different quality. We lost the algorithm to keep only the result. I think that our brain keeps the algorithms and that our awarenesses are lightning evaluations of them. Teaching, for example, is not sharing results, it is sharing algorithms. To convince is not to assert results, it is to exchange algorithms. The images we store cannot be seen in a scanner, the scanner only sees switches. Observing a microprocessor under a microscope gives no information about the algorithms that inhabit it, that percolate through the logic gates.

_pfr Pour moi tout ceci est une fenêtre ouverte vers de nouveaux mondes. Je pense au crible d'Érathostène qui produit la série des nombres premiers. Je pense aux ravinements sur les flancs d'une montagne qui vont guider les eaux de pluie, je pense aux gouttes d'eau sur une vitre qui suivent des chemins toujours changeants. Je pense aux influx nerveux qui se propagent dans le cerveau, de neurone en neurone, en fonction des la résistance électique des synapses. Des arbres lumineux qui s'entrecroisent dans le cortex, l'espace d'un instant. 
_pen For me all this is a window open to new worlds. I think of the sieve of Erathostene which produces the series of prime numbers. I think of the gullies on the sides of a mountain that guide the rainwater, I think of the drops of water on a window that follow ever-changing paths. I think of the nerve impulses that propagate in the brain, from neuron to neuron, according to the electic resistance of the synapses. Luminous trees that intersect in the cortex, for a moment.

_pfr La récursion est au coeur de la plupart des algorithmes, et nous avons vu que cette récursion peut être représentée par une cascade figée de lambdas. Notre pensée est algorithmique. Notre pensée est récursive, arborescente, une forêt d'éclairs qui s'entrecroisent et fleurissent en canopée. Notre pensée est une sculpture géométrique, fractale. La sculpture EST la pensée, hors du temps. 
_pen Recursion is at the heart of most algorithms, and we have seen that this recursion can be represented by a fixed cascade of lambdas. Our thinking is algorithmic. Our thought is recursive, tree-like, a forest of lightning bolts that intertwine and bloom in a canopy. Our thought is a geometrical sculpture, fractal. The sculpture IS the thought, out of time.

_pfr Notre cerveau est le siège d'une myriade de réécritures permanentes qui se passent hors de notre conscience. Nous arrivons parfois, péniblement, à reconstituer des bribes de phrases, des associations d'idées, nous en prenons conscience, nous élaborons des séquences de mots que nous exprimons au dehors, on parle, on écrit, on dessine, on échange.
_pen Our brain is the seat of a myriad of permanent rewritings that take place outside our consciousness. We sometimes manage, painfully, to reconstitute snatches of sentences, associations of ideas, we become aware of them, we elaborate sequences of words that we express outside, we speak, we write, we draw, we exchange.

_pfr Et mon ordinateur est là qui m'attend, comme un chien fidèle, qui attend que j'écrive quelques cascades de lambdas qu'il évaluera instantanément, sans relache, sans état d'âme. Le curseur clignote ...|... et attend de lancer le fidèle robot, {b λw.x w}, à l'assaut d'un océan de mots.
_pen And my computer is there waiting for me, like a faithful dog, waiting for me to write a few stunts of lambdas that it will evaluate instantly, without relenting, without a qualm. The cursor blinks ...|... and waits to launch the faithful robot, {b λw.x w}, to the assault of an ocean of words.

_p See also [[florilege|?view=Y_en2]].

_p {i alain marty 2022/01/09 - 2023/03/11}

_img https://upload.wikimedia.org/wikipedia/commons/a/a5/Tsunami_by_hokusai_19th_century.jpg

{center Thanks to DeepL.com/Translator (free version)}
;; {center [[HN|https://news.ycombinator.com/item?id=29896620]]}
}

;; coder's corner

{macro _h(\d)fr ([^\n]+)\n to {h€1 {@ class="fr"}€2}}
{macro _h(\d)en ([^\n]+)\n to {h€1 {@ class="en"}€2}}
{macro _pfr ([^\n]+)\n to {p {@ class="fr"}€1}} 
{macro _pen ([^\n]+)\n to {p {@ class="en"}€1}} 
{macro _l([\d]*)fr ([^\n]+)\n to {ul {@ class="fr" style="margin-left:€1px;"} {li €2}}}
{macro _l([\d]*)en ([^\n]+)\n to {ul {@ class="en" style="margin-left:€1px;"} {li €2}}}

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

{def geek
 blockquote {@ style="transform:rotate(-2deg); border:1px dashed; padding:10px;"}}

{def toggle
 {input
  {@ type="button" value="french" onclick="toggle(this)"
     style="position:fixed; top:10px; left:10px; z-index:2;
            font:normal 1.0em courier; color:#fff; background:#f00;
            border:0; border-radius:30px; box-shadow:0 0 8px #fff;
            padding:5px 10px;"
}}}

{def toggle2
 {input
  {@ type="button" value="horizontal" onclick="toggle2(this)"
     style="position:fixed; top:10px; right:10px; z-index:2;
            font:normal 1.0em courier; color:#fff; background:#f00;
            border:0; border-radius:30px; box-shadow:0 0 8px #fff;
            padding:5px 10px;"
}}}

}

{style 
body { background:#444; }  
#page_frame {
 border:0; background:transparent; width:600px; 
 margin:auto;     ;; margin-left:0; 
}
#page_content {
 background:transparent; color:#fff; border:0; 
 box-shadow:0 0 0; font:normal 1.2em optima; 
 width:600px;     ;; 5500px
}

.page_menu { background:transparent; color:#fff; } 
a { color:#f80; }
pre {
 position:relative; z-index:1;  
 ;; overflow-x: scroll;
 padding:10px; background:#555; color:#fff; 
}

b { color:cyan; }
h1 { font-size:4.0em; margin:0; color:#fff; }
h2 { font-size:3.0em; margin:0; color:#fff; }
h3 { font-size:1.5em; margin:0; color:#fff; }
h4 { font-size:1.2em; margin:0; color:#fff; }

code { font-style:bold; }
.fr { display:none; }
.en { display:block; }
}

{script 
var toggle = function(obj) {
  var frs = document.getElementsByClassName('fr');
  var ens = document.getElementsByClassName('en');
  if (obj.value==='english') {
    for (var i=0; i< frs.length; i++) frs[i].style.display="none";
    for (var i=0; i< ens.length; i++) ens[i].style.display="block";
    obj.value = 'français';
  } else {
    for (var i=0; i< frs.length; i++) frs[i].style.display="block";
    for (var i=0; i< ens.length; i++) ens[i].style.display="none"; 
    obj.value = 'english';   
  }
};