+
1
|
skin
|
login
|
edit
workshop
::
fabrique
user:anonymous
{require lib_BN lib_turtle} {style body { background: #444} } {LAFABRIQUE} _h2 introduction _p Nous nous proposons de {b fabriquer un langage informatique} en partant des bases les plus simples. Notre environnement de travail sera n'importe quel navigateur web fonctionnant sur n'importe quel système. Depuis lequel nous accèderons à un traitement de texte trés rudimentaire, un {b wiki} appelé '{lambda tank}, situé quelque part sur la toile. _p Succédant au premier {b wiki} inventé en 1995 par {b Ward Cunningham} des centaines d'autres wikis nous ont progressivement fait passer de simples consommateurs d'informations glanées sur le web en créateurs d'informations partageables. Mais ces outils sont en général équipés de syntaxes assez rudimentaires et hétérogènes pour entrer du texte, l'enrichir et le structurer. '{lambda tank} dispose d'un véritable langage, '{lambda talk}, permettant non seulement d'enrichir le texte et de le structurer, mais aussi de lui donner vie. En un mot de {b coder}. _p Les langages informatiques sont en général présentés à partir de leurs fonctionnalités, des objets qu'ils proposent - les chaines, les nombres, les tableaux, ... - des fonctions associées, et à l'aide de nombreux exemples d'utilisation de leurs syntaxes. On apprend ainsi à résoudre tel ou tel problème, pas vraiment à comprendre les raisons de leur conception. Une grande part de mystère demeure que seuls ceux qui ont eu accès à la fabrication de ces langages peuvent lever. _p C'est donc ce que nous allons faire. Nous allons construire '{lambda talk} à partir des briques les plus élémentaires. Une poignée de règles "jugées évidentes", pas de zone d'ombre, pas de fonctions magiques, pas de concepts abstraits. Tout juste des mots qu'on assemble et qu'on pourrait manipuler "à la main", sans ordinateur. _p A commencer par les substitutions de texte. _h2 1. remplacer avec '{lambda ...} _p Supposons que nous voulions remplacer les mots "{b fruit}" et "{b inconnue}" dans la phrase "{b Les fruits sont de couleur inconnue.}" par les mots "{b banane}" et "{b jaune}", pour obtenir "{b Les bananes sont de couleur jaune.}" Bien que cette commande décrive parfaitement l'action à entreprendre, elle reste assez lourde à écrire et à lire, avec ses guillemets marquant les mots à remplacer, la phrase objet du remplacement et les mots de remplacement. _p Nous conviendrons d'une syntaxe plus compacte, une sorte de {b sténographie}, construite sur cette définition {pre {@ style="font:normal 1.2em courier; text-align:center;"} phrase = mot | abstraction | application } _p En d'autres termes, une {b phrase} est constituée de {b mots}, d"{b abstractions} et d"{b applications} où _ol 1) un {b mot} est fait de tous caractères autres que les espaces séparant les mots et les accolades '{} déclenchant les actions. _ol 2) une {b abstraction} s'écrit sous la forme {b '{lambda {mots} phrase}} _ol 3) une {b application} s'écrit sous la forme {b '{abstraction phrase}} _p Noter ce mot étrange, {b lambda}, que nous devrons comprendre comme signifiant l'action de {b remplacer}. C'est le nom choisi dans les années 1930 par {b Alonzo Church}, l'inventeur du {b lambda calcul}. Et repris dans tous les langages informatiques. Nous ferons de même. _p Une phrase faite de mots, d'abstractions et d'applications est dans un {b état instable}. _ul 1) un {b mot} est stable, il ne change pas, _ul 2) une {b abstraction} est immédiatement "abstraite" de la phrase et remplacée par un mot, la référence à une fonction ajoutée dans un {b DICTIONNAIRE} initialement vide ; cette fonction est chargée de conserver la sélection des mots à remplacer et la phrase sur laquelle s'opèreront les remplacements, _ul 3) une {b application} est remplacée par le résultat de ... l'application du premier terme, une abstraction, aux mots constituant la phrase, ces mots pouvant être le résultat de précédentes applications toujours effectuées {b de l'intérieur vers l'extérieur}. _p Quand la phrase a atteint son {b état stable}, c'est à dire une séquence de mots, elle est envoyée au navigateur qui fait le gros du travail, afficher proprement le contenu. _p Ainsi, en {b composant} une abstraction et une application {pre {@ style="font:normal 1.5em courier; text-align:center;"} '{{lambda {mots} phrase} phrase} } _p nous pouvons écrire notre commande initiale sous une forme plus compacte {pre '{{lambda {fruit inconnue} Les fruits sont de couleur inconnue.} banane jaune} -> Les bananes sont de couleur jaune. } _p et l'appliquer à d'autres valeurs tout aussi facilement {pre '{{lambda {fruit inconnue} Les fruits sont de couleur inconnue.} cerise rouge} -> Les cerises sont de couleur rouge. '{{lambda {fruit inconnue} Les fruits sont de couleur inconnue.} pomme verte} -> Les pommes sont de couleur verte. } _p Avec cette syntaxe réduite nous pouvons remplacer des mots sélectionnés par d'autres mais la lisibilité reste à désirer. _h2 2. nommer avec '{def ...} _p Afin de rendre le code plus lisible, nous introduisons une quatrième règle, {pre {@ style="font:normal 1.5em courier; text-align:center;"} '{def nom phrase}} _p qui nous permet de remplacer de longues phrases complexes par un simple mot, de les nommer. Par exemple écrire {pre '{def PHRASE Les arbres sont en fleur.} -> {def PHRASE Les arbres sont en fleur.} } _p remplace la phrase "{b Les arbres sont en fleur.}" par le mot {b PHRASE}. Il suffira d'écrire '{PHRASE} pour la restituer autant de fois que souhaité. _p En donnant un nom à la forme complexe {b '{lambda {fruit inconnue} Les fruits sont de couleur inconnue.}} {pre '{def AFFIRMATION {lambda {fruit inconnue} Les fruits sont de couleur inconnue.}} -> {def AFFIRMATION {lambda {fruit inconnue} Les fruits sont de couleur inconnue.}} } _p les applications seront bien plus faciles à lire et à écrire {pre '{AFFIRMATION cerise rouge} -> {AFFIRMATION cerise rouge} '{AFFIRMATION pomme verte} -> {AFFIRMATION pomme verte} '{AFFIRMATION banane jaune} -> {AFFIRMATION banane jaune} } _p Avec cette syntaxe construite sur quatre règles nous pouvons donc remplacer des mots sélectionnés par d'autres et nommer de longues phrases. Mais nous pouvons faire bien plus que remplacer, nous pouvons coder ! _h2 3. coder _p Pour l'instant le dictionnaire de '{lambda talk} ne contient qu'un seul mot, {b AFFIRMATION}, et c'est bien peu pour coder. Coder consistera à construire des abstractions et les appliquer à des mots pour les regrouper en {i structures de données}, à les transformer en nombres sur lesquels s'appliqueront des opérateurs, à créer des {i structures de contrôle} permettant la répétition d'une action, enfin à rassembler toutes ces fonctionnalités en "modules/bibliothèques" étendant le langage à l'infini. _p Le résultat sera un ensemble arborescent de phrases, une forêt dont il ne nous restera plus qu'à parcourir la {b canopée} pour contempler le résultat. Par exemple, en utilisant le module {b lib_turtle} nous pourrons écrire {pre °° {def tree {lambda {:e :s :k :a :b} {if {< :s :e} then {T-30 M:s T120 M:s T120 M:s T150} :s} else M:s T:a {tree :e {* :k :s} :k :a :b} T-{+ :a :b} {tree :e {* :k :s} :k :a :b} T:b M-:s }}} {tree 10 200 {/ 2 3} 40 4} -> red tree {tree 10 180 {/ 2 3} 40 10} -> green tree {tree 10 180 {/ 2 3} 4 20} -> blue tree {tree 10 150 {/ 2 3} 4 50} -> black tree °°} _p pour définir les points d'un graphique SVG affichant {svg {@ width="600px" height="600px" style="border:1px solid #888"} {polyline {@ points="{turtle 340 590 180 {tree 10 200 {/ 2 3} 40 4}}" fill="transparent" stroke="red" stroke-width="1"}} {polyline {@ points="{turtle 340 590 180 {tree 10 180 {/ 2 3} 40 10}}" fill="transparent" stroke="green" stroke-width="1"}} {polyline {@ points="{turtle 340 590 180 {tree 10 180 {/ 2 3} 4 20}}" fill="transparent" stroke="blue" stroke-width="1"}} {polyline {@ points="{turtle 340 590 180 {tree 10 150 {/ 2 3} 4 50}}" fill="transparent" stroke="black" stroke-width="1"}} } _p Commençons avec les mots. _h3 3.1. mots _p Que peut-on faire avec des mots ? Tout d'abord les regrouper. _h4 3.1.1. paires _p Une structure fondamentale est la {b PAIRE}, comprenant deux éléments auxquels on peut accéder par {b GAUCHE} et {b DROITE}. {pre '{def PAIRE {lambda {x y z} {z x y}}} -> {def PAIRE {lambda {x y z} {z x y}}} '{def GAUCHE {lambda {z} {z {lambda {x y} x}}}} -> {def GAUCHE {lambda {z} {z {lambda {x y} x}}}} '{def DROITE {lambda {z} {z {lambda {x y} y}}}} -> {def DROITE {lambda {z} {z {lambda {x y} y}}}} '{GAUCHE {PAIRE Amélie Poulain}} -> {GAUCHE {PAIRE Amélie Poulain}} '{DROITE {PAIRE Amélie Poulain}} -> {DROITE {PAIRE Amélie Poulain}} } _p Analysons un instant la cascade de remplacements qui aboutit au premier résultat. {pre '{GAUCHE {PAIRE Amélie Poulain}} -> Amélie } _ul 1) Dans l'expression les noms {b GAUCHE PAIRE} sont remplacés par leurs définitions : {pre '{{lambda {z} {z {lambda {x y} x}}} {{lambda {x y z} {z x y}} Amélie Poulain}} } _ul 2) Les lambdas sont capturées et évaluées à un mot, {b _LAMB_xxx}, faisant référence à une fonction ajoutée au dictionnaire: {pre °° 1: capture de la première lambda -- {lambda {z} {z {lambda {x y} x}}} a) évaluation de la lambda interne: {lambda {x y} x} -> _LAMB_1 b) evaluation de la lambda externe: {lambda {z} {z _LAMB_1}} -> _LAMB_2 2: capture de la seconde lambda: -- {lambda {x y z} {z x y}} -> _LAMB_3 -> {_LAMB_2 {_LAMB_3 Amélie Poulain}} °°} _ul 3) {u Les lambdas ne créent pas de fermeture mais acceptent l'application partielle}. {b _LAMB_3} prend donc les deux valeurs données (sur les trois attendues) et retourne une nouvelle lambda, {b _LAMB_4}, attendant la troisième valeur: {pre °° 1: {_LAMB_3 Amélie Poulain} {{lambda {x y z} {z x y}} Amélie Poulain} -- {lambda {z} {z Amélie Poulain}} -> _LAMB_4 -> {_LAMB_2 _LAMB_4} °°} _ul 4) Tout est en place pour terminer l'évaluation, toujours de l'intérieur vers l'extérieur {pre °° 2: {_LAMB_2 _LAMB_4} -- {{lambda {z} {z _LAMB_1}} _LAMB_4} 3: {_LAMB_4 _LAMB_1} -- {{lambda {z} {z Amélie Poulain}} _LAMB_1}} 4: {_LAMB_1 Amélie Poulain} -- {{lambda {x y} x} Amélie Poulain} 5: Amélie // CQFD ! °°} _p Cette série de remplacements est un peu "casse-tête" et serait quasi impossible à suivre sans l'aide d'une syntaxe "sténographique". Et nous n'en sommes qu'au début ! _p Pour information voici comment seraient implémentés {b PAIRE GAUCHE DROITE} en {b Lisp/Scheme} où les lambdas créent des fermetures mais n'acceptent pas l'application partielle: {pre (def PAIRE (lambda (x y) (lambda (z) (z x y)))) // fermeture (def GAUCHE (lambda (z) (z (lambda (x y) x))) ) // même code (def DROITE (lambda (z) (z (lambda (x y) y))) ) // même code } _h4 3.1.2. listes _p En composant des paires on construit des {b LISTES}. {pre '{def REPUBLIQUE {PAIRE Liberté {PAIRE Egalité {PAIRE Fraternité {PAIRE Laïcité NIL}}}}} // tiens, pourquoi NIL ? -> {def REPUBLIQUE {PAIRE Liberté {PAIRE Egalité {PAIRE Fraternité {PAIRE Laïcité NIL}}}}} } _p Les éléments de la liste sont accessibles avec GAUCHE et DROITE {pre '{GAUCHE {REPUBLIQUE}} -> {GAUCHE {REPUBLIQUE}} '{GAUCHE {DROITE {REPUBLIQUE}}} -> {GAUCHE {DROITE {REPUBLIQUE}}} '{GAUCHE {DROITE {DROITE {REPUBLIQUE}}}} -> {GAUCHE {DROITE {DROITE {REPUBLIQUE}}}} '{GAUCHE {DROITE {DROITE {DROITE {REPUBLIQUE}}}}} -> {GAUCHE {DROITE {DROITE {DROITE {REPUBLIQUE}}}}} } _p Le mot un peu étrange qui termine la dernière paire, {b NIL}, va nous permettre d'afficher automatiquement les éléments de la liste. On définit quatre fonctions {pre '{def VRAI {lambda {:z} {:z {lambda {:x :y} :x}}}} // identique à GAUCHE -> {def VRAI {lambda {:z} {:z {lambda {:x :y} :x}}}} '{def FAUX {lambda {:z} {:z {lambda {:x :y} :y}}}} // identique à DROITE -> {def FAUX {lambda {:z} {:z {lambda {:x :y} :y}}}} '{def NIL {lambda {:f :x} :x}} -> {def NIL {lambda {:f :x} :x}} '{def ISNIL {lambda {:n} {:n {lambda {:x} FAUX} VRAI}}} -> {def ISNIL {lambda {:n} {:n {lambda {:x} FAUX} VRAI}}} } _p avec lesquelles on peut déterminer si une liste est vide ou pas {pre '{ISNIL NIL} -> {ISNIL NIL} '{ISNIL {REPUBLIQUE}} -> {ISNIL {REPUBLIQUE}} } _p et construire une fonction affichant de façon récursive les éléments d'une liste se terminant par NIL {pre si liste = NIL alors stop sinon affiche le premier élément affiche le reste de liste '{def LISTE.AFFICHE {lambda {:list} {{{ISNIL :list} // si la liste est vide {PAIRE {lambda {:list} } // on ne fait rien, on s'arrête {lambda {:list} {GAUCHE :list} // sinon on affiche le premier élément {LISTE.AFFICHE // et on recommence avec le reste de la liste {DROITE :list}}}}} :list}}} -> {def LISTE.AFFICHE {lambda {:list} {{{ISNIL :list} {PAIRE {lambda {:list} } {lambda {:list} {GAUCHE :list} {LISTE.AFFICHE {DROITE :list}}}}} :list}}} '{LISTE.AFFICHE {REPUBLIQUE}} -> {LISTE.AFFICHE {REPUBLIQUE}} } _p Ce code récursif est un premier exemple de structure de boucle. Noter que nous n'avons pas utilisé de structure de contrôle {b '{IF THEN ELSE}}. La structure [{b PAIRE, GAUCHE, DROITE}] en fournit l'équivalent ... à la condition d'introduire un peu de {i paresse} dans l'évaluation normalement {i gloutonne} des termes à l'aide de {b lambdas} bien placées, bloquant ainsi le terme non choisi. Ne pas le faire lancerait la récursion dans une boucle infinie ... _p Noter les {b deux-points ":"} préfixant les noms des arguments. Nous le ferons à présent systématiquement pour bien marquer le caractère {b variable locale} de ces mots (et pour une raison plus technique qui sera exposée plus tard). Il convient de bien faire la différence entre un "nom global", par exemple la constante {b PHRASE} et la fonction {b AFFIRMATION} vues plus haut, et une "variable locale", par exemple l'argument {b :list} dans la fonction {b LISTE.AFFICHE}. Une constante a une portée globale et n'est pas modifiable, une variable a une porté locale et est modifiable dans l'appel d'une fonction. _h4 3.2. nombres _p On peut réinventer l'arithmétique. _p L'arithmétique commence avec les nombres [0,1,2,3...] et les opérateurs associés [+,*,-,/,...], avec lesquels on peut calculer des expressions comme 1*2*3*4*5 = 120 et bien plus. _h5 3.2.1. Les nombres de CHURCH _p Suivant l'inventeur du lambda calcul, {b Alonzo Church}, un nombre naturel {b N} est défini comme étant {b N fois} l'application d'une abstraction à un mot. Eh oui, on fait avec les seuls outils dont on dispose, des mots, des abstractions et des applications. C'est une façon un peu alambiquée de jouer avec les nombres en les représentant par des bâtons, comme nos lointains ancêtres en quelque sorte. {pre '{def ZERO {lambda {:f :x} :x}} -> {def ZERO {lambda {:f :x} :x}} '{def ONE {lambda {:f :x} {:f :x}}} -> {def ONE {lambda {:f :x} {:f :x}}} '{def TWO {lambda {:f :x} {:f {:f :x}}}} -> {def TWO {lambda {:f :x} {:f {:f :x}}}} '{def THREE {lambda {:f :x} {:f {:f {:f :x}}}}} -> {def THREE {lambda {:f :x} {:f {:f {:f :x}}}}} '{def FOUR {lambda {:f :x} {:f {:f {:f {:f :x}}}}}} -> {def FOUR {lambda {:f :x} {:f {:f {:f {:f :x}}}}}} '{def FIVE {lambda {:f :x} {:f {:f {:f {:f {:f :x}}}}}}} -> {def FIVE {lambda {:f :x} {:f {:f {:f {:f {:f :x}}}}}}} '{def SIX {lambda {:f :x} {:f {:f {:f {:f {:f {:f :x}}}}}}}} -> {def SIX {lambda {:f :x} {:f {:f {:f {:f {:f {:f :x}}}}}}}} } _p Appliquer {b FIVE} à un "bâton" affichera cinq bâtons et ça risque de devenir compliqué à lire pour les grands nombres. On définit alors une fonction utilitaire, {b CHURCH}, qui assurera un affichage un peu plus moderne. {pre '{def CHURCH {lambda {:n} {{:n {lambda {:x} {+ :x 1}}} 0}}} -> {def CHURCH {lambda {:n} {{:n {lambda {:x} {+ :x 1}}} 0}}} '{CHURCH ZERO} -> {CHURCH ZERO} '{CHURCH ONE} -> {CHURCH ONE} '{CHURCH FIVE} -> {CHURCH FIVE} } _h5 3.2.2. quelques opérateurs _p Dans l'optique de {b Church} les nombres sont "vivants", ce sont des fonctions, en fait des {b itérateurs}, des atomes de code bien plus que des atomes de donnée. Ils peuvent agir les uns sur les autres et vont être au coeur du code des {b opérateurs}. _p L'opérateur {b ISZERO} nous permet de reconnaître si un nombre est nul ou pas. {pre '{def ISZERO {lambda {:n} {:n {lambda {:x} FAUX} VRAI}}} -> {def ISZERO {lambda {:n} {:n {lambda {:x} FAUX} VRAI}}} // identique à ISNIL '{ISZERO ZERO} -> {ISZERO ZERO} '{ISZERO ONE} -> {ISZERO ONE} } _p L'opérateur {b SUCC} produira le successeur de tout nombre. Ainsi, il nous suffit de ZERO et de SUCC pour construire l'ensemble des entiers naturels. {pre '{def SUCC {lambda {:n :f :x} {:f {{:n :f} :x}}}} -> {def SUCC {lambda {:n :f :x} {:f {{:n :f} :x}}}} '{CHURCH {SUCC ZERO}} -> {CHURCH {SUCC ZERO}} } _p L'opérateur {b PRED} qui produit le précédent d'un nombre est moins évident à coder. C'est {b Stephen Cole Kleene}, un des élèves de Church, qui a trouvé l'astuce en utilisant les PAIRES : {i Les nombres de Church peuvent être utilisés pour itérer et les paires pour agréger.} Considérant cette séquence de transformations où {b [a,b]} est une paire: {pre 1: [0,0] -> [0,0+1] 2: [1,1] -> [1,1+1] 3: [2,2] -> [2,2+1] 4: [3,3] -> [3,3+1] {b 5}: [4,4] -> [{b 4},4+1] -> {b 4} // the predecessor of {b 5} } _p nous créons deux fonctions _ul 1) {b PRED.PAIR} qui prend une paire {b [a,a]} et retourne la paire {b [a,a+1]}, _ul 2) {b PRED} qui calcule {b n} itérations de {b PRED.PAIR} partant de la paire {b [0,0]} et terminant à la paire {b [n-1,n]} et retourne finalement la première, {b n-1}. _p ce qui se traduit par {pre '{def PRED {def PRED.PAIR {lambda {:p} {PAIRE {FAUX :p} {SUCC {FAUX :p}}}}} {lambda {:n} {VRAI {{:n PRED.PAIR} {PAIRE ZERO ZERO}}}}} -> {def PRED {def PRED.PAIR {lambda {:p} {PAIRE {FAUX :p} {SUCC {FAUX :p}}}}} {lambda {:n} {VRAI {{:n PRED.PAIR} {PAIRE ZERO ZERO}}}}} '{CHURCH {PRED ONE}} -> {CHURCH {PRED ONE}} '{CHURCH {PRED ZERO}} -> {CHURCH {PRED ZERO}} // il n'y a pas de nombre négatif dans {b N}! } _p Nous pouvons maintenant construire les opérateurs addition {b ADD}, soustraction {b SUBTRACT}, multiplication {b MUL} et puissance {b POWER}. {pre '{def ADD {lambda {:n :m :f :x} {{:n :f} {{:m :f} :x}}}} -> {def ADD {lambda {:n :m :f :x} {{:n :f} {{:m :f} :x}}}} '{def SUBTRACT {lambda {:m :n} {{:n PRED} :m}}} -> {def SUBTRACT {lambda {:m :n} {{:n PRED} :m}}} '{def MUL {lambda {:n :m :f :x} {:m {:n :f} :x}}} -> {def MUL {lambda {:n :m :f :x} {:m {:n :f} :x}}} '{def POWER {lambda {:n :m :f :x} {{:m :n :f} :x}}} -> {def POWER {lambda {:n :m :f :x} {{:m :n :f} :x}}} '{CHURCH {ADD TWO THREE}} -> {CHURCH {ADD TWO THREE}} '{CHURCH {SUBTRACT FIVE ONE}} -> {CHURCH {SUBTRACT FIVE ONE}} '{CHURCH {MUL TWO THREE}} -> {CHURCH {MUL TWO THREE}} '{CHURCH {POWER TWO THREE}} -> {CHURCH {POWER TWO THREE}} } _p Construire l'opérateur division {b DIV} est beaucoup moins simple. Nous choisirons de le construire suivant un processus récursif et la factorielle en est l'exemple introductif. _h5 3.2.3. la factorielle _p La factorielle d'un nombre {b n} est la valeur notée {b n!} de {b 1*2*3* ... *(n-2)*(n-1)*n}. Ce nombre apparaît dans un grand nombre de formules en mathématique. Il est d'usage de le definir de manière récursive {pre si n = 0 alors n! = 1 sinon n! = n*(n-1)! } _p ce qui se traduit par le code suivant {pre '{def FAC {lambda {:n} {{{ISZERO :n} {PAIRE {lambda {:n} ONE} {lambda {:n} {MUL :n {FAC {PRED :n}}}}}} :n}}} -> {def FAC {lambda {:n} {{{ISZERO :n} {PAIRE {lambda {:n} ONE} {lambda {:n} {MUL :n {FAC {PRED :n}}}}}} :n}}} '{CHURCH {FAC FIVE}} -> 120 } _p Voici les états successifs de {code '{FAC 5}}, en affichant les nombres de Church sous la forme "naturelle" pour plus de lisibilité : {pre °° {FAC 5} -> {MUL 5 {FAC 4}} -> {MUL 5 {MUL 4 {FAC 3}}} -> {MUL 5 {MUL 4 {MUL 3 {FAC 2}}}} -> {MUL 5 {MUL 4 {MUL 3 {MUL 2 {FAC 1}}}}} -> {MUL 5 {MUL 4 {MUL 3 {MUL 2 {MUL 1 {FAC 0}}}}}} -> {MUL 5 {MUL 4 {MUL 3 {MUL 2 {MUL 1 1}}}}} -> {MUL 5 {MUL 4 {MUL 3 {MUL 2 1}}}} -> {MUL 5 {MUL 4 {MUL 3 2}}} -> {MUL 5 {MUL 4 6}} -> {MUL 5 24} -> 120 °°} _p En voici une version plus efficace, où l'appel récursif est terminal {pre '{def TFAC {lambda {:a :b} {{{ISZERO :b} {PAIRE {lambda {:a :b} :a} {lambda {:a :b} {TFAC {MUL :a :b} {PRED :b}}}}} :a :b}}} -> {def TFAC {lambda {:a :b} {{{ISZERO :b} {PAIRE {lambda {:a :b} :a} {lambda {:a :b} {TFAC {MUL :a :b} {PRED :b}}}}} :a :b}}} '{CHURCH {TFAC ONE FIVE}} -> 120 } _p Voici les états successifs de {code '{TFAC 1 5}}, en affichant les nombres de Church sous la forme "naturelle" pour plus de lisibilité : {pre °° {TFAC 1 5} -> {TFAC {MUL 1 5} {PRED 5}} -> {TFAC 5 4} -> {TFAC {MUL 5 4} {PRED 4}} -> {TFAC 20 3} -> {TFAC {MUL 20 3} {PRED 3}} -> {TFAC 60 2} -> {TFAC {MUL 60 2} {PRED 2}} -> {TFAC 120 1} -> {TFAC {MUL 120 1} {PRED 1}} -> {TFAC 120 0} -> 120 °°} _p {b De manière générale} un code récursif est écrit sous la forme suivante : {pre °° {def FUNC {lambda {:n :args} {{{ISZERO :n} {PAIRE {lambda {:n :args} some end with :args} {lambda {:n :args} {FUNC :new_n :new_args} } }} :n :args} }} °°} _p et est évalué ainsi : {pre °° {FUNC N ARGS} -> {{{ISZERO N} GD} N ARGS} // où GD est la paire de lambdas -> {{FAUX GD N ARGS} -> {{lambda {:n :args} {FUNC :new_n :new_args} N ARGS} -> {FUNC NEW_N NEW_ARGS} et ainsi de suite jusqu'à : -> {{VRAI GD} N ARGS} -> {{lambda {:n :args} some end with :args} N ARGS} -> some end with ARGS °°} _h5 3.2.4. le terrible Y-combinator _p Habituellement la récursion est abordée dans le lambda-calcul par le biais d'une étrange construction appelée {b Y-combinator}. Nous venons de voir qu'il n'est en rien un passage obligé. Sauf si nous souhaitons revenir au lambda calcul {b pur} qui ne connait pas les noms. Ce qui semble incompatible avec la définition d'une fonction récursive qui contient en son corps une référence au nom. Voici comment on peut s'y prendre avzc lambdatalk. _p En premier lieu, nous remplaçons la fonction recursive par une version {b presque-recursive}, sur laquelle nous appliquerons un {b Y-combinator} approprié : {pre '{def Y {lambda {:g :n} {:g :g :n}}} -> {def Y {lambda {:g :n} {:g :g :n}}} '{def PRESQUE_FAC {lambda {:g :n} {{{ISZERO :n} {PAIRE {lambda {:g :n} ONE} {lambda {:g :n} {MUL :n {:g :g {PRED :n}}} } }} :g :n}}} -> {def PRESQUE_FAC {lambda {:g :n} {{{ISZERO :n} {PAIRE {lambda {:g :n} ONE} {lambda {:g :n} {MUL :n {:g :g {PRED :n}}} } }} :g :n}}} '{CHURCH {Y PRESQUE_FAC FIVE}} -> {b 120} } _p Nous composons les deux: {pre '{def YFAC {lambda {:n} {{lambda {:g :n} {:g :g :n}} {lambda {:g :n} {{{ISZERO :n} {PAIRE {lambda {:g :n} ONE} {lambda {:g :n} {MUL :n {:g :g {PRED :n}}} } }} :g :n }} :n}}} -> {def YFAC {lambda {:n} {{lambda {:g :n} {:g :g :n}} {lambda {:g :n} {{{ISZERO :n} {PAIRE {lambda {:g :n} ONE} {lambda {:g :n} {MUL :n {:g :g {PRED :n}}} } }} :g :n }} :n}}} '{CHURCH {YFAC FIVE}} -> {b 120} } _p Nous pouvons nous passer du nom {b YFAC} en définissant et appelant immédiatement la lambda sur la valeur {b FIVE}: {pre '{CHURCH {{lambda {:n} {{lambda {:g :n} {:g :g :n}} {lambda {:g :n} {{{ISZERO :n} {PAIRE {lambda {:g :n} ONE} {lambda {:g :n} {MUL :n {:g :g {PRED :n}}} } }} :g :n }} :n}} FIVE}} -> {b 120} } _p Enfin, replaçant les constantes par leurs définitions, nous aboutissons à une pure expression {b lambda-calcul} : {pre {@ style="word-wrap: break-word; white-space:pre-wrap;"} '{CHURCH {{lambda {:n} {{lambda {:g :n} {:g :g :n}} {lambda {:g :n} {{{{lambda {:n} {:n {lambda {:x} {lambda {:z} {:z {lambda {:x :y} :y}}}} {lambda {:z} {:z {lambda {:x :y} :x}}}}} :n} {{lambda {:x :y :z} {:z :x :y}} {lambda {:g :n} {lambda {:f :x} {:f :x}}} {lambda {:g :n} {{lambda {:n :m :f :x} {:n {:m :f} :x}} :n {:g :g {{lambda {:n} {{lambda {:z} {:z {lambda {:x :y} :x}}} {{:n {lambda {:p} {{lambda {:x :y :z} {:z :x :y}} {{lambda {:z} {:z {lambda {:x :y} :y}}} :p} {{lambda {:n :f :x} {:f {{:n :f} :x}}} {{lambda {:z} {:z {lambda {:x :y} :y}}} :p}}}}} {{lambda {:x :y :z} {:z :x :y}} {lambda {:f :x} :x} {lambda {:f :x} :x}}}}} :n}}}}}} :g :n }} :n}} {lambda {:f :x} {:f {:f {:f {:f {:f :x}}}}}}}} -> {b 120} } _p Cette descente dans les fondations du langage démontre la puissance des trois règles initiales ... et l'absolue nécessité d'en ajouter une quatrième ! _h5 3.2.5. quelques exemples de la récursion _p La récursion nous ouvre la porte vers toute sorte de boucles de calcul. En voici quelques premiers exemples. _h6 1) Longueur d'une liste {pre si liste = vide alors longueur(liste) = 0 sinon longueur(liste) = 1 + longueur(reste de la liste) '{def LIST.LENGTH {lambda {:list} {{{ISNIL :list} {PAIRE {lambda {:list} ZERO} {lambda {:list} {ADD ONE {LIST.LENGTH {DROITE :list}}}}}} :list}}} -> {def LIST.LENGTH {lambda {:list} {{{ISNIL :list} {PAIRE {lambda {:list} ZERO} {lambda {:list} {ADD ONE {LIST.LENGTH {DROITE :list}}}}}} :list}}} '{CHURCH {LIST.LENGTH {REPUBLIQUE}}} -> {b 4} } _h6 2) liste des puissances de {b 2}, {b 2{sup n}}, pour {b n ∈ [0,10]} {pre '{def PUISSANCES {def PUISSANCES.r {lambda {:n :N} {{{ISZERO :n} {PAIRE {lambda {:n :N} {CHURCH {POWER TWO :N}}} {lambda {:n :N} {CHURCH {POWER TWO {SUBTRACT :N :n}}} {PUISSANCES.r {PRED :n} :N}}}} :n :N}}} {lambda {:n} {PUISSANCES.r :n :n} }} -> {def PUISSANCES {def PUISSANCES.r {lambda {:n :N} {{{ISZERO :n} {PAIRE {lambda {:n :N} {CHURCH {POWER TWO :N}}} {lambda {:n :N} {CHURCH {POWER TWO {SUBTRACT :N :n}}} {PUISSANCES.r {PRED :n} :N}}}} :n :N}}} {lambda {:n} {PUISSANCES.r :n :n} }} '{PUISSANCES {MUL TWO FIVE}} -> 1 2 4 8 16 32 64 128 256 512 1024 } _h6 3) opérateur division {b DIV} _p {b a} et {b b} étant donnés nous recherchons le quotient {b q} et le reste {b r} tels que {b a = b * q + r} {pre '{def DIV {def DIV.r {lambda {:a :b :q :r} {{{ISZERO {SUBTRACT {MUL :b :q} :a}} {PAIRE {lambda {:a :b :q :r} {DIV.r :a :b {SUCC :q} {SUBTRACT :a {MUL :b :q}}}} {lambda {:a :b :q :r} {PAIRE {PRED :q} :r}} }} :a :b :q :r} }} {lambda {:a :b} {{lambda {:d} [{CHURCH {GAUCHE :d}} {CHURCH {DROITE :d}}]} {DIV.r :a :b ZERO :b}} }} -> {def DIV {def DIV.r {lambda {:a :b :q :r} {{{ISZERO {SUBTRACT {MUL :b :q} :a}} {PAIRE {lambda {:a :b :q :r} {DIV.r :a :b {SUCC :q} {SUBTRACT :a {MUL :b :q}}}} {lambda {:a :b :q :r} {PAIRE {PRED :q} :r} } }} :a :b :q :r} }} {lambda {:a :b} {{lambda {:d} [{CHURCH {GAUCHE :d}} {CHURCH {DROITE :d}}]} {DIV.r :a :b ZERO :b}} }} '{DIV ZERO TWO} -> [0 0] // 0 = 2 * 0 + 0 '{DIV ONE TWO} -> [0 1] // 1 = 2 * 0 + 1 '{DIV TWO TWO} -> [1 0] // 2 = 2 * 1 + 0 '{DIV THREE TWO} -> [1 1] // 3 = 2 * 1 + 1 '{DIV FOUR TWO} -> [2 0] // 4 = 2 * 2 + 0 '{DIV FIVE TWO} -> [2 1] // 5 = 2 * 2 + 1 '{DIV SIX TWO} -> [3 0] // 6 = 2 * 3 + 0 } _h6 4) Les 3 Tours de Hanoï _p Un dernier exemple utilisant une double récursion nous montrera comment définir la suite des déplacements de {b n} disques dans le jeu des 3 Tours de Hanoï : {img {@ src="https://upload.wikimedia.org/wikipedia/commons/thumb/0/07/Tower_of_Hanoi.jpeg/260px-Tower_of_Hanoi.jpeg" width="100%"}} {pre '{def MOVE {lambda {:n :de :vers :via} {{{ISZERO :n} {PAIRE {lambda {:n :de :vers :via} } {lambda {:n :de :vers :via} {MOVE {PRED :n} :de :via :vers} {br}déplacer le disque de :de vers :vers {MOVE {PRED :n} :via :vers :de} }}} :n :de :vers :via}}} -> {def MOVE {lambda {:n :de :vers :via} {{{ISZERO :n} {PAIRE {lambda {:n :de :vers :via} } {lambda {:n :de :vers :via} {MOVE {PRED :n} :de :via :vers} {br}déplacer le disque de :de vers :vers {MOVE {PRED :n} :via :vers :de} }}} :n :de :vers :via}}} '{MOVE FOUR 1 2 3} -> déplacer le disque de 1 vers 3 déplacer le disque de 1 vers 2 déplacer le disque de 3 vers 2 déplacer le disque de 1 vers 3 déplacer le disque de 2 vers 1 déplacer le disque de 2 vers 3 déplacer le disque de 1 vers 3 déplacer le disque de 1 vers 2 déplacer le disque de 3 vers 2 déplacer le disque de 3 vers 1 déplacer le disque de 2 vers 1 déplacer le disque de 3 vers 2 déplacer le disque de 1 vers 3 déplacer le disque de 1 vers 2 déplacer le disque de 3 vers 2 } _p L'analyse de la ligne "{code '{br}déplacer le disque de :de vers :vers}" montre la facilité avec laquelle il est possible de mélanger du texte et des variables. Dans '{lambda talk} il n'existe pas d'objet {b string/chaine} à "protéger" entre guillemets. {i Parce qu'on n'en a simplement pas besoin !} _p Un autre point essentiel de la syntaxe utilisée est qu'elle est réduite à sa plus simple expression, {b des mots et des accolades} assemblés suivant les trois règles initiales. Des accolades il y en a beaucoup mais leur usage est systématique et on n'a besoin d'aucun autre symbole, signes de ponctuation, mot-clés. Le gain est inestimable ! _p Pour résumer, il semble que les possibilités de calcul d'un langage n'utilisant que trois règles, [{b abstraction, application, definition}], la dernière étant en théorie optionnelle, et jouant sur de simples {b mots}, soient sans fin. On démontre que c'est bien le cas, tout est théoriquement possible ... à condition de disposer de suffisamment d'espace de mémoire et de temps. Disons quelques milliers d'années pour calculer {b 50!} _p C'est peut-être le moment de passer à la vraie vie ... _h2 conclusion {center {img {@ src="data/brussels/browsers_icons.jpg" height="90"}} {img {@ src="data/brussels/braces.png" height="90" style="background:#888"}} {br}{i tel un nain sur les épaules de géants} } _p '{lambda talk} s'appuit en fait - et heureusement - sur les puissantes fonctions des navigateurs, JAVASCRIPT, HTML/CSS, DOM, SVG, ... ce qui permet d'éviter de ré-inventer la roue et de construire des codes bien plus efficaces. _p Par exemple les nombres et les opérateurs associés [+, -, *, /, ..., =, <, >, ...] tels que définis par Javascript et l'ajout d'une structure de contrôle {b '{if bool then one else two}} apportant "gratuitement" l'évaluation paresseuse laborieusement construite dans les fonctions récursives précédentes, conduisent à des codes lisibles et bien plus efficaces. {pre '{def fac {lambda {:n} {if {= :n 0} then 1 else {* :n {fac {- :n 1}}}}}} -> {def fac {lambda {:n} {if {= :n 0} then 1 else {* :n {fac {- :n 1}}}}}} '{fac 5} -> {fac 5} '{fac 50} -> {fac 50} } _p En faisant appel à un script approprié, {b lib_BN}, on peut même construire un code calculant la valeur exacte de la factorielle de {b 50} {pre '{def fact {lambda {:n} {if {< :n 2} then {BN.new 1} else {BN.* :n {fact {- :n 1}}}}}} -> {def fact {lambda {:n} {if {< :n 2} then {BN.new 1} else {BN.* :n {fact {- :n 1}}}}}} '{fact 50} -> 30414093201713378043612608166064768844377641568960512000000000000 } _p Ou appeler la fonction prédéfinie {b BN.fac} pour calculer la factorielle de {b 500} {pre {@ style="word-wrap: break-word; white-space:pre-wrap;"} '{BN.fac 500} -> 1220136825991110068701238785423046926253574342803192842192413588385845373153881997605496447502203281863013616477148203584163378722078177200480785205159329285477907571939330603772960859086270429174547882424912726344305670173270769461062802310452644218878789465754777149863494367781037644274033827365397471386477878495438489595537537990423241061271326984327745715546309977202781014561081188373709531016356324432987029563896628911658974769572087926928871281780070265174507768410719624390394322536422605234945850129918571501248706961568141625359056693423813008856249246891564126775654481886506593847951775360894005745238940335798476363944905313062323749066445048824665075946735862074637925184200459369692981022263971952597190945217823331756934581508552332820762820023402626907898342451712006207714640979456116127629145951237229913340169552363850942885592018727433795173014586357570828355780158735432768888680120399882384702151467605445407663535984174430480128938313896881639487469658817504506926365338175055478128640000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 } _p C'est avec ce genre d'arithmétique qu'on sécurise nos cartes bancaires ... et les échanges {b bitcoin} pour ceux qui souhaitent retrouver une certaine liberté. _p Bon, la factorielle vous fatigue un peu ? Allez donc voir la page [[fibonacci]] et constater comment un algorithme {b poussif} peut être extraordinairement {b boosté} si l'on s'y prend bien. _p L'important est de comprendre qu'il n'y a pas de magie derrière tout celà. Tout peut toujours se réduire à une série de remplacements sur une séquence de mots disposés sur un long ruban. Par exemple on a pu démontrer (en utilisant le "terrible" {b Y-combinator} qui en a terrassé plus d'un) que le code de la fonction {b FAC} obtenu précédemment pouvait se réduire à une pure expression lambda calcul faite de mots, d'abstractions et d'applications. En remplaçant le mot {b lambda} par la lettre "{b λ}" et oubliant de préfixer les arguments par le caractère "{b :}", en fait inutile ici, on réduit le code à une poignée de caractères et d'accolades marquant les deux opérations d'abstraction et d'application travaillant sur un dictionaire initialement vide : {pre {@ style="word-wrap: break-word; white-space:pre-wrap;"} °° {{λ {n} {{λ {g n} {g g n}} {λ {g n} {{{{λ {n} {n {λ {x} {λ {z} {z {λ {x y} y}}}} {λ {z} {z {λ {x y} x}}}}} n} {{λ {x y z} {z x y}} {λ {g n} {λ {f x} {f x}}} {λ {g n} {{λ {n m f x} {n {m f} x}} n {g g {{λ {n} {{λ {z} {z {λ {x y} x}}} {{n {λ {p} {{λ {x y z} {z x y}} {{λ {z} {z {λ {x y} y}}} p} {{λ {n f x} {f {{n f} x}}} {{λ {z} {z {λ {x y} y}}} p}}}}} {{λ {x y z} {z x y}} {λ {f x} x} {λ {f x} x}}}}} n}}}}}} g n }} n}} {λ {f x} {f {f {f {f {f x}}}}}}}} °° } _p Nous somme très proche du processus qu' {b Alan Turing}, un élève de {b Church}, avait traduit sous la forme d'une machine hypothétique dans les années 30. {img {@ src="data/brussels/turing_machine.png" width="100%"}} _p Il peut être intéressant de savoir que dans '{lambda talk} les remplacements des expressions entre accolades se font à travers une {b fenêtre} construite sur une unique {b expression régulière} {pre {@ style="font:normal 1.2em courier; text-align:center;"} {quote /\{([^\s{}]*)(?:[\s]*)([^{}]*)\}/g }} _p suivant la syntaxe d'un langage inventé par {b Stephen Cole Kleene}, cet autre élève de {b Church}. Ces expressions régulières sont aussi présentes au coeur du fonctionnement des lambdas, qui ne sont que de simple machines à remplacer des mots par d'autres mots. _p Alonzo Church et ses élèves travaillaient à Princeton dans les années 30, avec pour tout outil du papier, un crayon et une gomme. Il devait être passionnant de vivre à Princeton dans ces années-là ! A condition d'avoir dans la tête, comme eux, la puissance des ordinateurs qui n'existaient pas encore. _p La suite se voit dans le [[workshop|../workshop]] du projet '{lambda way} où vous trouverez des introductions plus directes au langage '{lambda talk}, notamment [[introduction]], [[primal]], [[rosetta]], [[lambdapub]], [[oxford_slides]] ainsi que de nombreux exemples d'application aux maths et au web design ou à l'enseignement, [[teaching]]. _p Bienvenue dans la '{lambda way} ! _p {i alain marty 10/11/2017 - dernière MàJ 23/12/2017} {blockquote _p Cette page a été composée dans le wiki '{lambda tank} en utilisant les fonctions HTML/CSS du dictionnaire de '{lambda talk}. Tous les exemples de code présentés sont effectivement calculés dans la page, mais les exemples sont désactivés afin de ne pas alourdir le temps de calcul de l'ensemble. Il suffit de les réactiver au besoin (bouton + et edit) pour vérifier leur bon fonctionnement. _p Le projet '{lambda way}, {b 50 kilo-octets, zéro dépendance}, est librement téléchargeable [[ICI|?view=download]]. } {{hide} {def LAFABRIQUE {img {@ src="data/brussels/operators.jpg" width="100%"}} {div {@ style="font:italic 5.0em courier new; text-align:center; color:#f00; text-shadow:0 0 4px #000; margin-top:-1.0em;"}la fabrique} } }