lambdaway
::
essais
5
|
list
|
login
|
load
|
|
{uncover http://epsilonwiki.free.fr/epsilonwiki/data/E58A1743-7F97-45CE-A4A0-48A371635C50.jpg 300 1000 Ma di cosa sta parlando questo ragazzo?} _h1 une introduction au langage lambdatalk _p Suivant Wittgenstein « {i Les limites de mon langage signifient les limites de mon propre monde.} » et si l'on en croit Sapir & Whorf « {i les représentations mentales dépendent des catégories linguistiques} », autrement dit, « {i la façon dont on perçoit le monde dépend du langage".} » Je vous propose donc d'en analyser les concepts fondateurs, dans ce qu'ils ont de minimaliste et d'universel. _p Le projet {b lambdaway} est un éditeur de texte, {b lambdatank}, doté d'un langage de programmation, {b lambdatalk}, lointain dialecte d'un langage formel, le {b λ-calcul}, créé dans les années 30 par un logicien américain, Alonzo Church. Si comme Monica vous pensez aussitôt « {i Ma di cosa sta parlando questo ragazzo?} » alors je vais en tenter une présentation "douce" de nature à vous en faire devenir "addict", de lambdatalk s'entend. Il suffit que vous ayez une fois manipulé un traitement de texte, même élémentaire, et que vous ayez entr'aperçu la fonction "remplacement de texte". _h2 1) écrire _p Réduit à sa plus simple expression lambdatalk peut se résumer en cette formule énigmatique {pre '{{lambda {mot1} phrase contenant des occurences du mot1} mot2} -> phrase contenant des occurences du mot2 } _p qui s'éclaire immédiatement sur ce premier exemple {pre '{{lambda {:a} Mon prénom est :a} James} -> {{lambda {:a} Mon prénom est :a} James} } _p où l'on voit que le mot {b James}, appelé {b valeur}, a remplacé le mot {b :a}, appelé {b variable}, dans la phrase "{b Mon prénom est :a}". Il suffit d'écrire une expression contenant un jeu balancé d'accolades et le mot {b lambda} signifiant {i pour des raisons purement historiques} {b remplacer} pour que lambdatalk exécute la commande de remplacement. {i Comme vous le feriez vous-même à la main.} _p On peut aller un peu plus loin et remplacer deux variables {pre '{{lambda {:a :b} Je m'appelle :b, :a :b.} James Bond} -> {{lambda {:a :b} Je m'appelle :b, :a :b.} James Bond} } _p L'expression parenthésée interne {b '{lambda {:a :b} Je m'appelle :b, :a :b.}} contient deux mots non définis et ne prend un sens que quand chaque variable aura obtenu une valeur. En donnant un nom à cette expression "inachevée", appelée {b fonction}, par exemple {b HI} {pre '{def HI {lambda {:a :b} Je m'appelle :b, :a :b. }} -> {def HI {lambda {:a :b} Je m'appelle :b, :a :b.}} } _p on peut écrire le remplacement de façon plus concise, plus lisible {pre '{HI James Bond} -> {HI James Bond} '{HI Monica Bellucci} -> {HI Monica Bellucci} } _p Ce faisant on vient d'ajouter le nom d'une {b fonction} au dictionnaire du langage et de l'appliquer à différents mots, appelés {b valeurs}. Rien de bien sorcier dans tout cela, lambdatalk est fondamentalement un outil de remplacement/substitution de texte. Mais un outil muni d'une syntaxe qui va nous permettre de combiner des suites de remplacements, de {b coder}. Coder c'est définir un ensemble de fonctions et les appliquer à des mots, à l'infini. Un langage de programmation contient les outils qui permettent de l'enrichir à partir d'une base minimale, à l'infini, c'est ce que nous avons commencé à faire à partir de cette simple formule, {b '{{lambda {mot} suite de mots} mot}}. _p Au départ lambdatalk ne connait donc que deux opérateurs, {b lambda & def}, agissant sur des {b mots} et rien d'autres, et notamment pas les {b nombres}. Mais on peut construire de nouvelles fonctions avec lesquelles lambdatalk saura aussi quoi faire des nombres. _h2 2) calculer _p Si je vous demande de calculer "{i la somme de deux nombres 1 & 2}", il est probable que vous répondrez {b 3}. En reprenant le style d'appel de fonction que nous venons de découvrir, il me suffit d'écrire {pre '{+ 1 2} -> {+ 1 2} } _p et miracle lambdatalk répond {b 3}. _p Notez que je n'ai pas écrit {b 1+2}, qui se lit {b 1 plus 2} et que lambdatalk laisserait d'ailleurs en l'état, n'y voyant que trois mots parmi d'autres. J'ai écrit {b '{+ 1 2}} et cette notation parenthésée préfixée, qui peut être déconcertante au premier abord, est au final d'une grand puissance. Les accolades signifient que ce qu'elles encadrent doit être évalué et remplacé par une valeur en fonction de l'opérateur collé à l'accolade ouvrante. Lambdatalk comprend donc {b évalue la somme de 1 et 2} et affichera le résultat, {b 3}. _p Si j'écris {b '{+ 1 2 3 4 5}}, lambdatalk comprend {b évalue la somme de 1 2 3 4 5} et retourne {b {+ 1 2 3 4 5}}. Si j'écris {b '{+ {S.serie 1 100}}} lambdatalk comprendra {b évalue la somme de la série de nombres de 1 à 100}, remplacera {b '{S.serie 1 100}} par la séquence de nombres {b 1 2 3 ... 99 100} et affichera l'évaluation de {b '{+ 1 2 3 ... 99 100}} soit {b {+ {S.serie 1 100}}}. _p Allons plus loin. Si je vous demande de {b calculer la racine carrée de la somme du produit de 3 par 3 et du produit de 4 par 4} il se peut que vous ayez un peu plus de mal à répondre. Sauf si vous traduisez "mot pour mot" votre demande dans la syntaxe lambdatalk {pre '{sqrt {+ {* 3 3} {* 4 4}}} } _p où {b sqrt} est le mot anglais pour {b racine carrée}. Le résultat sera un mot d'une lettre, {b 5}, c'est à dire la longueur de l'hypoténuse d'un triangle rectangle de côtés {b 3} et {b 4}. Que s'est-il passé dans le détail ? _p Le moteur de lambdatalk, appelé {b évaluateur}, est construit de telle manière qu'il scanne les expressions à la recherche d'expressions internes élémentaires ne contenant aucune accolade. Un peu comme on suit les branches d'un arbre à la recherche des feuilles terminales. _p Dans notre cas il va découvrir les expressions, {b '{* 3 3}} et {b '{* 4 4}}. _p Dans chacune il va repérer le mot collé à droite de l'accolade ouvrante, ici {b *}, et le ou les mots suivants jusqu'à l'accolade fermante, ici {b 3 3} et {b 4 4}. L'évaluateur va voir si le mot {b *} existe dans son dictionnaire. Il existe effectivement une {b primitive} de ce nom, construite pour « {b faire le produit de tous les nombres qui suivent jusqu'à l'accolade fermante} ». L'évaluateur lui transmet donc le bébé. La fonction analyse les séquences de mots {b 3 3} et {b 4 4}, constate qu'il s'agit bien de nombres, qu'il est donc possible d'en faire le produit et fournit en retour les nombres {b 9} et {b 16}. L'expression initiale est donc devenue plus simple {pre '{sqrt {+ {* 3 3} {* 4 4}}} -> '{sqrt {+ 9 16}} } _p L'évaluateur recommence la recherche d'une expression interne sans accolade et trouve {b '{+ 9 16}}. Le mot {b +} étant bien une primitive capable d'additionner deux nombres, il en fait le calcul et l'expression se simplifie un peu plus {pre '{sqrt {+ 9 16}} -> '{sqrt 25} } _p La primitive {b sqrt} existe bien dans le dictionnaire et est appliquée au nombre {b 25} {pre '{sqrt 25} -> 5 } _p Fin du voyage ! _p L'expression initiale pouvait se lire « {i La diagonale d'une rectangle de côtés 3 et 4 est égale à la racine carrée de la somme du produit de 3 par 3 et du produit de 4 par 4 }» et l'évaluation la transforme en un nombre qui est la valeur de cette diagonale. Ainsi donc une expression complexe aura été remplacée par une plus simple et ainsi de suite jusqu'à ce qu'il n'y ait plus rien à remplacer. _p Chemin faisant on est passé d'une commande au résultat, d'un processus à une valeur, {b 5}. Notons que l'inverse est impossible, on ne peut pas déduire de la valeur {b 5} qu'elle dérive de l'expression de la diagonale d'un rectangle de côtés 3 et 4. Il y a bien {b équivalence} mais la relation est {b dissymétrique}. En algèbre une expression comme {b (a-b)*(a+b)} se transforme en {b a*a-b*b}, ou {b a{sup 2}-b{sup 2}}, et il est possible d'effectuer la transformation inverse, appelée factorisation. On peut se demander dans quel sens de la transformation il y a diminution de l'information, augmentation du désordre, entropie croissante, ou bien augmentation de l'information, diminution du désordre, néguentropie croissante ? La question est ouverte. _h2 3) coder _p Si je vous demande de calculer la somme de deux mots {b a & b} vous ne saurez probablement que répondre. L'ordinateur non plus {pre '{+ a b} -> {+ a b} } _p ce qui n'est pas étonnant, {b NaN} signifie {b Not a Number}. Sauf si on la bonne idée de remplacer auparavant ces mots par des nombres, ce qui pourrait s'énoncer ainsi {pre remplace a & b dans '{+ a b} par 1 & 2 } _p En suivant cette commande l'expression {b '{+ a b}} devient {b '{+ 1 2}} qui sera évidemment remplacée par {b 3}. Vous avez bien sûr reconnu une procédure de remplacement de texte analogue à celle vue en introduction. De façon abrégée, {i codée}, on pourra donc écrire {pre '{{lambda {:a :b} {+ :a :b}} 1 2} } _p en marquant toujours les variables d'un simple caractère préfixe "{b :}". Comme précédemment une telle expression est assez difficile à manipuler et on a tout intérêt à donner un nom à la sous-expression parenthésée invariante {b '{lambda {:a :b} {+ :a :b}}} {pre '{def add {lambda {:a :b} {+ :a :b}} } -> {def add {lambda {:a :b} {+ :a :b}}} } _p L'expression complète devient immédiatement bien plus simple : {b '{add 1 2}}. On dispose ainsi d'un nouvel opérateur, {b add}, aussi facile à utiliser que l'opérateur prédéfini, {b +}, et applicable à diverses valeurs {pre '{add 1 2} -> {add 1 2} '{add 123 456} -> {add 123 456} } _p On peut se demander pourquoi appeler {b add} un opérateur existant, {b +}. Voici donc un opérateur plus bavard {pre '{def smart_add {lambda {:a :b} La somme de :a et de :b est égale à {+ :a :b} }} -> {def smart_add {lambda {:a :b} La somme de :a et de :b est égale à {+ :a :b} }} } _p utilisé ainsi {pre '{smart_add 3 4} -> {smart_add 3 4} } _p Question: voyez-vous la raison de préfixer d'un "{b :}" les deux variables {b :a & :b} ? Que se passerait-il si on ne le faisait pas ? _p Dan tous les cas on a augmenté le dictionnaire, et en fait on est passé d'une calculatrice préprogrammée une fois pour toutes à un outil de programmation, un {b langage} permettant de créer des fonctions en fonction des besoins et cela, en principe, sans limite. De façon générale {b coder} consistera à créer un ensemble coordonné de fonctions et à les appliquer à différentes valeurs. _h2 4) boucler _p Prenons un autre exemple, plus intéressant. Imaginons que nous ayons besoin de faire la {i somme des nombres de 0 à 1000}. _p Bon, vous connaissez déjà la réponse, il suffit d'écrire {pre '{+ {S.serie 1 1000}} -> {+ {S.serie 1 1000}} } _p Mais supposons que le dictionnaire ne connaisse pas cette primitive et que vous ne disposiez que des opérateurs {b + & -}. Voici comment vous pourriez faire : la somme des nombres de 0 à 100 ... est égale à la somme des nombres de 100 à 0 -- ok ? -- qui est égale à la somme de {b n} et de la somme des nombres de {b n-1} à {b 0}, qui est égale à la somme de {b n}, de {b n-1} et de la somme des nombres de {b n-2} à {b 0}, qui est égale etc, etc, etc jusqu'au moment est atteinte la somme de {b 0} à {b 0}, fin du parcours. Voici cette longue phrase écrite de façon plus condensée : {pre la somme des nombres de {b n} à {b 0} est égale : si {b n} est supérieur à {b 0} : alors à {b n} + somme des nombres de {b n-1} à {b 0} sinon à {b 0}. } _p et voici le code lambdatalk équivalent où l'on définit une fonction {b somme} et on l'applique ensuite à la valeir {b 1000} {pre '{def somme {lambda {:n} {if {> :n 0} then {+ :n {somme {- :n 1}}} else 0 }}} -> {def somme {lambda {:n} {if {> :n 0} then {+ :n {somme {- :n 1}}} else 0 }}} '{somme 1000} -> {+ {S.map {lambda {:i} :i} {S.serie 0 1000 1}}} } _p Suivons l'exécution de cet algorithme pas à pas pour {b n = 10} : {pre 0: '{somme 10} 1: '{+ 10 {somme {- 10 1}}} 2: '{+ 10 {+ 9 {somme {- 9 1}}}} 3: '{+ 10 {+ 9 {+ 8 {somme {- 8 1}}}}} 4: '{+ 10 {+ 9 {+ 8 {+ 7 {somme {- 7 1}}}}}} 5: '{+ 10 {+ 9 {+ 8 {+ 7 {+ 6 {somme {- 6 1}}}}}}} 6: '{+ 10 {+ 9 {+ 8 {+ 7 {+ 6 {+ 5 {somme {- 5 1}}}}}}}} 7: '{+ 10 {+ 9 {+ 8 {+ 7 {+ 6 {+ 5 {+ 4 {somme {- 4 1}}}}}}}}} 8: '{+ 10 {+ 9 {+ 8 {+ 7 {+ 6 {+ 5 {+ 4 {+ 3 {somme {- 3 1}}}}}}}}}} 9: '{+ 10 {+ 9 {+ 8 {+ 7 {+ 6 {+ 5 {+ 4 {+ 3 {+ 2 {somme {- 2 1}}}}}}}}}}} 10: '{+ 10 {+ 9 {+ 8 {+ 7 {+ 6 {+ 5 {+ 4 {+ 3 {+ 2 {+ 1 {somme {- 1 1}}}}}}}}}}}} 11: '{+ 10 {+ 9 {+ 8 {+ 7 {+ 6 {+ 5 {+ 4 {+ 3 {+ 2 {+ 1 0}}}}}}}}}} 12: '{+ 10 {+ 9 {+ 8 {+ 7 {+ 6 {+ 5 {+ 4 {+ 3 {+ 2 1}}}}}}}}} 13: '{+ 10 {+ 9 {+ 8 {+ 7 {+ 6 {+ 5 {+ 4 {+ 3 3}}}}}}}} 14: '{+ 10 {+ 9 {+ 8 {+ 7 {+ 6 {+ 5 {+ 4 6}}}}}}} 15: '{+ 10 {+ 9 {+ 8 {+ 7 {+ 6 {+ 5 10}}}}}} 16: '{+ 10 {+ 9 {+ 8 {+ 7 {+ 6 15}}}}} 17: '{+ 10 {+ 9 {+ 8 {+ 7 21}}}} 18: '{+ 10 {+ 9 {+ 8 28}}} 19: '{+ 10 {+ 9 36}} 20: '{+ 10 45} 21: 55 } _p Vous voyez l'idée ? {b C'est ça la récursion}. La somme des nombres de 10 à zéro est 10 ... plus la somme des nombres de 9 à zéro ... et on recommence autant de fois que nécessaire jusqu'à zéro, où tout s'arrête. _p Et la magie c'est que tout {b processus itératif} peut être traité par ce moyen. Enfin presque. {b Kurt Gödel} a démontré dans les années trente qu'il existe des algorithmes récursifs qui ne se terminent pas, qui s'emballent à l'infini, qui {i divergent}. C'est son {b Théoreme d'Incomplétude} qui a mis à mal l'égo des logiciens qui croyaient avec Hilbert que les mathématiques pouvait être construites comme un systéme logique complet et sans faille. C'est impossible. Deux autres logiciens sont arrivés au même moment à la même conclusion. Le premier s'appelait {b Alonzo Church}, le père du lambda-calcul, ancêtre de lambdatalk, et l'un de ses élèves, {b Alan Turing}, qui a imaginé la première machine universelle à calculer tout et n'importe quoi, prise comme modèle pour les ordinateurs qui allaient apparaître dix ans après leurs obscures élucubrations. On sait que le début du XXème Siècle a connu deux révolutions intellectuelles, la Théorie de la Relativité avec {b Einstein} et la Mécanique Quantique avec {b Dirac} et bien d'autres. On connait moins les deux autres, la Théorie des Fractales avec {b Mandelbrot} et la Théorie des Fonctions Récursives avec {b Gödel} et autres, cette dernière constituant le fondement théorique des ordinateurs qui nous aident à explorer le monde de l'information. _h2 et alors ? _p Pas vraiment fan de maths, les chiffres vous ennuient ? Alors que pensez-vous de ce code (peu importe le détail) {pre '{S.replace (\[|\]) by in {S.replace \]\s\[ by {br} in {S.replace , by space in {S.replace \],\[ by space in {A.disp {permut {A.new {A.new Belle marquise} {A.new vos beaux yeux} {A.new me font mourir} {A.new d'amour}}} }}}}} } _p Produisant cette amusante permutation cyclique à partir de quelques mots {center {pre Belle marquise vos beaux yeux me font mourir d'amour vos beaux yeux Belle marquise me font mourir d'amour vos beaux yeux me font mourir Belle marquise d'amour vos beaux yeux me font mourir d'amour Belle marquise Belle marquise me font mourir vos beaux yeux d'amour me font mourir Belle marquise vos beaux yeux d'amour me font mourir vos beaux yeux Belle marquise d'amour me font mourir vos beaux yeux d'amour Belle marquise Belle marquise me font mourir d'amour vos beaux yeux me font mourir Belle marquise d'amour vos beaux yeux me font mourir d'amour Belle marquise vos beaux yeux me font mourir d'amour vos beaux yeux Belle marquise Belle marquise vos beaux yeux d'amour me font mourir vos beaux yeux Belle marquise d'amour me font mourir vos beaux yeux d'amour Belle marquise me font mourir vos beaux yeux d'amour me font mourir Belle marquise Belle marquise d'amour vos beaux yeux me font mourir d'amour Belle marquise vos beaux yeux me font mourir d'amour vos beaux yeux Belle marquise me font mourir d'amour vos beaux yeux me font mourir Belle marquise Belle marquise d'amour me font mourir vos beaux yeux d'amour Belle marquise me font mourir vos beaux yeux d'amour me font mourir Belle marquise vos beaux yeux d'amour me font mourir vos beaux yeux Belle marquise }} _p La page [[perm2]] vous expliquera comment on utilise la récursion pour lister toutes ces combinaisons poétiques propres à emballer une belle marquise. Il suffit d'utiliser lambdatalk pour remplacer dans le texte précédent les deux mots {b Belle marquise} par {b Monica Bellucci} ... et l'affaire est emballée ! _p Alors, la récursion, vous en voyez un peu mieux l'utilité ? _p Bienvenue dans le monde du code. _p {i alain marty | 2022/06/07 - 2024/11/27} {style body, #page_frame, #page_content, .page_menu { background:#444; color:#fff; } pre { box-shadow:0 0 8px #000; padding:5px; } b { color:#0ff; } }
lambdaway v.20211111