α-wwwiki

α-wwwiki :: history/lambdaway/20131022-072832.txt

editor : alpha [82.64.18.92] 2013/10/22 07:28:32
{center {i Would you like an english translation ? Ask me in the [[forum]] !}}
{div
  {@ style="
     position:absolute; 
     top:-20px; left:400px;
     font:bold 5em times;
     color:red;
     text-shadow:0 0 8px black;
     z-index:1;
 "}
  °°{λy}°°
}

{div {@ style="display:none;"}
{define cod () °°
  var args = [].slice.call(arguments).join( ' ' );
  var style=
    "font:normal 0.8em arial;"
   +"background:#888;"
   +"color:#fff;"
   +"text-align:center;"
   +"padding:0 10px;"
   +"border:1px solid;"
   +"box-shadow:0px 0px 2px black;"
   +"-webkit-border-radius:10px;" 
   +"-moz-border-radius:10px;" 
   +"border-radius:10px;";
  return '{span {@ style="' + style + '"}' + args + '}';
°°}
}

_h1 évaluer une S-expression
_p Evaluer une expression symbolique, une {b S-expression}, dans le cadre d'un {b dictionnaire} pré-défini est une chose assez simple, cf pages [[evaluation]] et [[yaw]]. Cela se complique lorsque certains de ses termes ne sont pas connus au moment de l'écriture. C'est à ce moment-là qu'interviennent les opérateurs {cod if}, {cod lambda} et {cod def}, et que le dictionnaire se met à grossir. On entre alors dans le domaine du codage ...

_h3 1. S-expression
_p L'évaluation d'une  S-expression {cod °°{first rest}°°} consiste en l'application de l'opérateur {cod first} aux arguments contenus dans {cod rest}. Le terme {cod first}  est un nom de fonction ou une S-expression produisant un nom de  fonction, {cod rest} est une chaîne de mots (un mot est suite de caractères sans espace), de nombres (au sens où ils sont compris par l'environnement) et de S- expressions.

_p Classiquement, l'évaluation se fait suivant le modèle récursif {b valeur = evaluate(build_nested_array(tokenize( S-expressions )))}, cf par exemple [[lisp_evaluator]]. En ce qui concerne [[lambdatalk|?view=lambdatalk]] destiné à être embarqué dans un wiki, un autre modèle plus adapté à ce contexte est choisi. Il est basé sur {b une boucle appliquant un filtre} (une expression régulière) à la séquence de S-expressions, l'évaluation se faisant en commençant par les S-expressions terminales (ne contenant aucune S-expression) jusqu'à la S-expression englobante, des feuilles à la racine. C'est ce modèle qui servira de fond aux considérations qui suivent.

_h3 2. évaluation immédiate : {span {@ style="color:red;"}dico}
_p Tout est pour le mieux quand tous les termes d'une S-expression ont une valeur connue. Par exemple, dans l'expression {cod °°{+ 1 {* 2 3} 4}°°} les symboles {cod +} et  {cod *} appartiennent au dictionnaire de fonctions prédéfinies, {cod 1, 2, 3, 4} sont des symboles reconnus comme étant des nombres et évalués à eux-mêmes. Selon le modèle {b lambdatalk} l'évaluation se fait en deux temps : 
_ul 1) la S-expression interne {cod °°{* 2 3}°°} est capturée et traitée : la fonction {cod *} est appliquée aux arguments {cod 2, 3} pour produire {cod 6}
_ul 2) la S-expression {cod °°{+ 1 6 4} °°} résultante est capturée et traitée : la fonction {cod +} est appliquée aux arguments {cod 1, 6, 4} pour produire {cod 11}

_p Toute calculatrice sait faire cela ! Pour mémoire, dans une {i Texas Instrument}® on entre {cod  1+2*3+4} (en notation infixée) ;  dans une {i Hewlett Packard}®, on entre {cod °°1 2 3 * 4 +°°} (en notation post-fixée). Dans les deux cas, l'expression est ré-écrite sous la forme d'une S-expression {cod °°{+ 1 {* 2 3} 4}°°} (en notation pré-fixée) envoyée à l'évaluateur qui retourne {cod 11}.

_h3 3. évaluation contrôlée : {span {@ style="color:red;"}if}
_p Il est parfois nécessaire d'Introduire des branchements dans le processus d'évaluation. On définit pour cela un opérateur spécial {b if} suivant la syntaxe : {cod °°{if bool then then_term else else_term}°°}, où {b bool} est une valeur booléenne (true ou false), pouvant être le résultat de l'évaluation d'une S-expression utilisant des opérateurs booléens prédéfinis {cod = < > <= >= not or and} et qui provoquera l'évaluation de l'un des deux termes {b  then_term} ou {b else_term}. Exemples:
_ul {cod °°{if {< 1 2} then {/ 1 2} else {/ 1 0}}°° -> -0.5} : OK !!
_ul {cod °°{if {> 1 2} then {/ 1 2} else {/ 1 0}}°° -> Infinity} : oops !!!

_p Dans les deux cas précédents tous les termes sont connus et, suivant ce qui a été vu plus haut, les quatre S-expressions (oui 4 !) devraient être évaluées. Mais même en ne considérant que le premier cas, la division par zéro provoquée par l'évaluation inutile du second {b else_term} génèrerait une erreur et bloquerait probablement l'évaluation. En fait, l'évaluation des termes du {b if} {u doit être reportée}, (on parle d'évaluation paresseuse), seul le terme associé à la valeur true ou false du booléen sera évalué, et l'autre sera simplement "oublié". La section {b 6.} en montre une application importante.

_h3 4. évaluation différée : {span {@ style="color:red;"}lambda}
_p Examinons avec Pythagore cette expression {cod °°{sqrt {+ {* a a} {* b b}}}°°}. En plus des termes {cod sqrt} (racine carrée), {cod +} et {cod *} qui appartiennent au dictionnaire, elle contient deux symboles {cod a} et {cod b}, qui ne sont ni des nombres ni des S-expressions. Leur valeur n'est pas connue au moment de l'écriture de la S-expression et son évaluation {u doit être reportée}. On la conserve dans le dictionnaire sous la forme d'une fonction (un enclos, une fermeture, une lambda, une liaison) associant à tous les termes  {cod a} et {cod b} contenus dans le corps les valeurs qui seront fournies à l'appel de la fonction, par exemple les valeurs {cod 3} et {cod 4} (au fond, une fonction ne fait rien d'autre qu'un remplacement des arguments par des valeurs suivant une mise en correspondance établie dans la liste de ses paramètres).

_p On définit pour cela l'opérateur spécial {b lambda}. L'expression {cod °° {lambda {:a :b} {sqrt {+ {* a a} {* b b}}} } °°} crée cette fonction en lui attribuant un nom aléatoire, du type {cod lambda_12345}, inconnu en principe de l'utilisateur, une fonction anonyme. S'il était connu, on pourrait écrire l'expression {cod °°{lambda_12345 3 4}°°} qui produirait la valeur {cod 5}. Dans la mesure où le nom est inconnu, on couple en réalité la définition de la fonction et son appel : {cod °° {{lambda {:a :b} {sqrt {+ {* a a} {* b b}}}} 3 4} -> 5°°}. Et la fonction anonyme retourne ensuite dans les limbes du "garbage collector".

_h3 5. extension du dictionnaire : {span {@ style="color:red;"}def}
_p On aimerait conserver plus longtemps cette fonction, ne serait-ce que pour pouvoir l'utiliser plusieurs fois sans avoir à écrire sa définition. Il suffit de découpler la définition et l'appel de la fonction en lui donnant un nom. On définit pour cela l'opérateur spécial {b def} et l'expression {cod °°{def pythagore {lambda {:a :b} {sqrt {+ {* a a} {* b b}}}}°°} associe {u de façon permanente} le nom {cod pythagore} à la définition de la fonction. L'expression {cod °° {pythagore 3 4}°°} produira {cod 5} et {cod °°{pythagore 1 1}°°} produira {cod {sqrt 2}}, au grand dam de Pythagore qui y voyait le signe du diable !

_p De façon générale, {cod °°{def nom expression}°°} associe un nom à une S-expression, augmentant ainsi le dictionnaire des fonctions pré-définies. Si l'expression ne contient que des termes évaluables, par exemple {cod °°{def myPI 3.1416} > myPI °°} et {cod °° {myPI} > 3.1416°°} ou {cod °°{def 2PI {* 2 {PI}} > 2PI °°} et {cod °° {2PI} > 6.283185307179586 °°}  elle est évaluée et mémorisée sous forme de constante. Sinon, elle est mémorisée à l'aide de l'opérateur {cod lambda} sous la forme d'une fonction dont l'appel fournira les valeurs manquantes.
 
_h3 6. application : {span {@ style="color:red;"}recursion}
_p Les 3 opérateurs "spéciaux" {cod if, lambda, def} sont dits {b speciaux} parce qu'ils n'appartiennent pas au dictionnaire de base. Ils sont utilisés de la même façon que les autres mais ils doivent être traités avant l'évaluation proprement dite afin de désactiver les S-expressions imbriquées et retarder ainsi leur évaluation à un moment opportun. Ces trois opérateurs ouvrent la voie aux codes récursifs et aux boucles, et donc au codage de tous les programmes imaginables.
_p Le cas d'école d'un tel code est celui de la fonction factorielle {b n!}. On la définit ainsi : {b n! est le produit des nombres entiers de 1 à n}. Et pour que l'évaluateur puisse faire quelque chose de cette belle phrase, on écrit un algorithme récursif : {b si n est nul alors n! = 1  sinon n! = n*(n-1)}. Avec l'aide des opérateurs def, lambda et if on écrira :
_ul {cod °° {def ! {lambda {n} {if {< n 1} then 1 else {* n {! {- n 1}}}}}} -> !  °°}

_p ou de façon plus lisible :
{pre °°
{def !
  {lambda {n}
    {if {< n 1}
      then 1
      else {* n {! {- n 1}}}
} } }
{! 6} -> 720
°°}

_p Une fois ajoutée au dictionnaire, cette nouvelle fonction {cod !} pourra être appelée comme n'importe quelle fonction primitive autant de fois que souhaité :
_ul {cod 6! = °° {! 6} -> 720  °°}
_ul {cod 20! = °° {! 20} -> 2432902008176640000  °°}

_p Dans un langage ne connaissant pas la récursion on écrirait une boucle :
{pre °°
function fac (n) {
  var result = n;
  for (var i = n-1; i > 1; i = i-1) {
    result = result * i;
  }
  return result;
}
fac( 6 ) -> 720
°°}
_p On notera au passage la multiplication des notations dans cette syntaxe et l'introduction de variables annexes (result et i). Avec la récursion, les boucles deviennent possibles sans faire appel au concept de compteur, sans faire appel au concept d'affectation et de mutation de variable. On est dans la programmation fonctionnelle où les fonctions retournent toujours la même valeur, sans effet de bord. A moins qu'on définisse un nouvel opérateur {cod set!}, mais ceci est une autre histoire ! (voir l'exemple "bank_account" dans [[alphalisp|data/alphalisp/]] ou [[monodicolisp|data/monodicolisp/]]).

_h3 7. coder
_p Ecrire et éxécuter un programme, c'est créer un ensemble de fonctions inter-agissant sur un ensemble de données et appeler la fonction {b maître} qui les exécutera. Les langages courants (Pascal, C, C++, Java, Python, Ruby, ...) disposent de syntaxes plus ou moins complexes faisant toujours une nette différence entre les données et les fonctions qui les traitent. Dans le cas d'un évaluateur de S-expressions, on notera la similitude des notations entre les opérateurs et les données. C'est le point commun des dialectes du {b LISP} défini en 1960 sur un nombre très réduit de {cod 5 ou 7} formes primitives capables de générer tous les codes imaginables. « Les Equations de Maxwell de l'Informatique », comme le disait le père de SmallTalk, Alan Kay.

_p Mon dernier évaluateur en date, [[lambdatalk|data/lambdatalk/]], s'appuie sur les principes minimalistes du LISP (sans tenter d'en être un nième dialecte comme [[alphalisp|?view=lisp_evaluator]]), et bénéficie de la fondation confortable des navigateurs WEB et de leurs langages intégrés, le HTML, le CSS, et le LISP habillé en C malencontreusement appelé JavaScript. Lambdatalk dispose ainsi "gratuitement" de {b 50} opérateurs HTML, des {b 30} fonctions mathématiques intégrées dans le JavaScript, et ajoute à cette base solide {b 20} nouveaux opérateurs et les {b 3} formes spéciales indispensables {cod if, lambda, def} permettant d'en créer de nouveaux. Associé au moteur PHP d'alphawiki qui assure les fonctions de lecture et d'écriture sur le WEB, le [[code de lambdatalk|data/lambdatalk/lambdatalk.js]], réduit à très peu de lignes (une centaine pour l'évaluateur, environ quatre cent pour le dictionnaire pré-défini), semble se révèler suffisant pour autoriser dans des conditions confortables la composition et le codage de pages multimedia interactives et complexes. Au moins autant que l'ancêtre [[epsilonwiki|../]] et le présent [[alphawiki|?view=start]]. Qu'en pensez-vous ? 
_p N'hésitez pas à tester la [[console lambdatalk|data/lambdatalk/]] et à me donner votre avis dans le [[forum]].

_p alain marty 21/10/2013

{hr}

_p {b Remarque :} à la relecture, malgré tous mes efforts, je dois constater que tout ceci n'est pas encore bien clair et ça se mélange un peu. Du travail en perspective ...