α-wwwiki

α-wwwiki :: history/evaluation/20131008-204056.txt

editor : alpha [82.248.194.227] 2013/10/08 20:40:56
{center {i A work in progress ; would you like an english translation ?}}

_h1 s-expressions evaluation

_p Les structures arborescentes sont partout (cf page [[YAW]]). La représentation d'un arbre se fait normalement de façon multidimensionnelle (matrices, voxels), mais il est souvent pratique d'en utiliser une représentation aplatie, linéaire, séquentielle. Cette notation fait appel à ce qu'on appelle des "expressions symboliques" ou "{b s-expressions}". 
_p Par exemple le caractère arborescent de la phrase : {b « l'oiseau pose ses pattes sur la branche »} (d'apparence si simple pour tout le monde), peut être représenté par ce schéma bidimensionnel :
{pre .                      S
                      / \
                     /   \
                    /     \         
                   /       \         
                  /         \         
                 /           \         
                /             \         
               /               GV
              /               / \
             /               /   \
            /               /     \
           GN              /       \
          / \             /         \
         /   \           /           \
        /     \         /             \
       l'   oiseau     GV             GP
                      / \             / \
                     /   \           /   \
                    /     \         /     \
                  pose    GN       sur    GN
                          / \             / \
                        ses  pattes      la  branche
}

_p ou par cette s-expression aplatie :
{center {b °°{S {GN l'oiseau} {CV pose {GN ses pattes} {CP sur {GN la branche}}}°°}}

_p Le caractère arborescent de l'expression mathématique « {b {math {msqrt {mrow {msup {mi 3}{mn 2}}{mo +}{mrow {msup {mi 4}{mn 2}}}}}}} » (d'apparence si complexe pour beaucoup) peut être représenté par ce schéma bidimensionnel :
{pre .    square_root
           |
           +
          / \
         /   \
        *     *
       / \   / \
      3   3 4   4
}

_p ou par cette s-expression aplatie : 
{center {b °°{square_root {+ {* 3 3} {* 4 4}}}°°}}

_p On imagine sans peine la complexité des représentations bi-dimensionnelles de longues phrases "convolutées" ou d'expressions mathématiques faisant appel à des intégrales, différentielles, matrices, ... On notera la similitude de la notation (infixe) qu'il s'agisse de phrases ou d'expressions mathématiques. On entre dans un monde révélé il y a un demi-siècle par le langage LISP et rassemblant dans une notation universelle l'ensemble des informations (data) et des opérateurs (code) sur ces informations. Le monde de l'{b [[homoiconicité|http://en.wikipedia.org/wiki/Homoiconicity]]} (the language text has the same structure as its abstract syntax tree) et des [[meta-evaluateurs circulaires|http://en.wikipedia.org/wiki/Meta-circular_evaluator]] (two functions eval() and apply() call each other in circular fashion to fully evaluate a program) !

_h3 1) s-expression
_p Une expression symbolique respecte une forme unique :

{pre {@ style="font-size:2em; text-align:center;"} °°{°°first rest°°}°°}
 
_p où "{b first}" est une fonction pré-définie appartenant à un dictionnaire extensible, et "{b rest}" est soit une s-expression °°{°°first rest°°}°°, soit une chaîne de caractères à l'exception de °°{ et }°° ; et les éléments du dictionnaire sont des fonctions écrites dans le langage hôte, qui dans un navigateur est le javascript. 
_p {b Note :} Le choix des accolades "{b °°{ et }°°}" et non des parenthèses {b "( et )"} comme marqueurs/séparateurs apparaît préférable dans un environnement wiki où le "texte" est l'essentiel du contenu et les parenthèses sont des caractères comme les autres.

_h3 2) fonctionnement de l'évaluation

_p Comment une s-expression est-elle évaluée ? Deux approches seront comparées.

_p 21) La première évalue directement chaque s-expression dans une boucle à travers un filtre, une expression régulière appliquée depuis les feuilles jusqu'à la racine

{pre {@ style="white-space:pre-wrap;"}°°
input = {sqrt {+ {* 3 3} {* 4 4}}}
{sqrt
  {+
    {* 3 3} 
    {* 4 4}
  }
}

boucle 1 :
  {* 3 3} -> (function (x,y) { return x*y})(3,3) -> 9
  {* 4 4} -> (function (x,y) { return x*y})(4,4) -> 16
output = {sqrt {+ 9 16}}

boucle 2 :
  {+ 9 16} -> (function (x,y) { return x+y})(9,16) -> 25
output = {sqrt 25}

boucle 3 :
  {sqrt 25} = (function (x) { return Math.sqrt(x) })(25) 
output = 5
°°}

_p 22) La seconde transforme chaque s-expression en un tableau emboîté (array) ; ce tableau est parcouru et évalué récursivement depuis la racine jusqu'aux feuilles.

{pre {@ style="white-space:pre-wrap;"}°°
input = {sqrt {+ {* 3 3} {* 4 4}}
output = nested_array(input) = 
['sqrt',
  ['+',
    ['*','3','3'],
    ['*','4','4']
  ]
]
output = 
(function (x) { return Math.sqrt(x) })(
  (function (x,y){ return x+y })(
    (function (x,y){ return x*y })(3,3),
    (function (x,y){ return x*y })(4,4)
  )
) 
output = 5
°°}

_h3 3) fonctions de l'évaluateur
_p L'évaluateur est écrit dans le langage natif du navigateur, le JavaScript. On donnera le nom de "string" à l'évaluateur qui travaille sur les s-expressions (qui sont des chaînes) et de "array" celui qui les transforme en tableaux (array).

_h5 31) évaluateur "string"
{pre {@ style="white-space:pre-wrap;"}°°

input = (sqrt (+ (* 3 3) (* 4 4) ) )
   output = doLoop( input ) = 5

1) l'expression régulière filtrant les s-expressions {first rest} :
var loop_rex = /\(([^\s()]*)(?:[\s]*)([^()]*)\)/g;

2) la boucle :
function doLoop( str ) {
  while (str != (str = str.replace( loop_rex, dispatch ))) ; 
  return str;
}

3) la fonction dispatch() :
function dispatch (m, first, rest) {
  if (dico.hasOwnProperty( first )) { // si first est dans le dico
    var func = dico[first];           // prendre sa valeur, une fonction
    var rest = rest.split(' ');       // transformer rest en tableau
    return func.apply(null,rest);     // appliquer first à rest
  } else                              // sinon afficher simplement
    return '['+first+' '+rest+']';    // [first rest]] pour info
}

4) le dictionnaire, premiers éléments :
dico['+'] = function (x,y) { return x+y };
dico['*'] = function (x,y) { return x*y };
dico['sqrt'] = function (x) { return Math.sqrt(x) };

°°}
_h5 32) évaluateur "array"
{pre {@ style="white-space:pre-wrap;"}°°

input = (sqrt (+ (* 3 3) (* 4 4) ) )
x = build_flat_array(input) = ['(','sqrt','(','+','(','*','3','3',')','(','*','4','4',')',')',')']
   x = build_nested_array(x) = 
   ['sqrt',['+',['*','3','3'],['*','4','4']]]
   output = evaluate(x) = 5

1) fonction transformant la s-expression en un tableau plat
function build_flat_array (str) { hors sujet, cf code complet }

2) fonction transformant le tableau plat en un tableau emboîté
function build_nested_array (str) { hors sujet, cf code complet }

3) la fonction evaluate()
function  evaluate = function (x) { // nombre ou nom ou tableau 
  if (is_number(x))	            // un nombre
    return x;                       // est retourné tel quel
  else if (is_symbol(x))            // un nom de fonction
    return dico[x];                 // la fonction associée
  else {                            // c'est un tableau
    var xx = x.map(evaluate);       // les éléments sont évalués
    var func = xx.shift();          // le premier est retiré
    return func.apply(null,xx);     // et est appliqué aux autres
  }
};

dico['+'] = function (x,y) { return x+y };
dico['*'] = function (x,y) { return x*y };
dico['sqrt'] = function (x) { return Math.sqrt(x) };

°°}
_p {b Note :} le dictionnaire est identique dans les deux cas, "string" ou "array".

_h3 4) extension du dictionnaire
_p Comment ajouter une nouvelle fonction ? Par exemple, comment créer la fonction "hypo" (hypoténuse) qui n'est pas pré-définie dans le dictionnaire :

{pre °° {hypo 3 4} -> 5 °°}

_h5 41) statiquement dans le dictionnaire
_p La fonction est écrite directement dans le langage natif du navigateur, le Javascript. Le côté positif est que l'évaluateur est inchangé dans les deux cas, "string" ou "array". Le côté négatif est que l'écriture ne peut se faire en ligne, il faut modifier le dictionnaire dans le code lui-même.

{pre {@ style="white-space:pre-wrap;"}°°
dico['hypo'] = function (a,b) { 
  return Math.sqrt( a*a + b*b ) } 
};
°°}

_h5 42) dynamiquement dans le code
_p La fonction est écrite en ligne sous une forme faisant appel à des s-expressions °°{first rest}°° ... mais pas tout à fait :

{pre {@ style="white-space:pre-wrap;"}°°
{def hypo (a b) 
  {sqrt {+ {* a a} {* b b}}}
}
°°}
_p Un nouvel opérateur, "{b def}" fait son apparition ; il est suivi du nom de la fonction, de la liste des paramètres entre parenthèses et d'une (ou plusieurs) s-expression(s) formant le corps de la fonction. 
_p Il se trouve que cette écriture nécessite une transformation radicale de l'évaluateur, qu'il soit "string" ou "array". Dans les deux cas, l'évaluateur primitif suppose connues les valeurs des termes "first" et "rest". Or dans ce cas, le nom est inconnu (on est en train de le définir), les valeurs des paramètres ne sont pas connues (elles le seront à l'appel de la fonction) et le corps de la fonction comprend des termes dont on ne connait pas la valeur (ils prendront la valeur des paramètres à l'appel de la fonction). L'opérateur "{b def}" exige un traitement spécial, et nous allons voir que plusieurs approches sont possibles pour ce faire.

_h5 43) écriture du code
_p Nous examinerons trois approches, de la plus simple à la plus complète :
_ul 1) le cas de l'évaluateur "string", (par les expressions régulières)
_ul 2) le cas de l'évaluateur "array" :
_ul50 21) avec un seul dictionnaire extensible, (par un deepArrayReplace)
_ul50 22) avec un emboîtement de dictionnaires (un classique du LISP)

_p Pour l'instant, les codes complets sont déjà visibles ici :
_ul 1) [[stringlisp|data/stringlisp/stringlisp.js]]
_ul 21) [[monodicolisp|data/monodicolisp/monodicolisp.js]]
_ul 22) [[alphalisp|data/alphalisp/alphalisp.js]]

_p Les explications viendront bientôt. It's a work in progress :) :)

_h6 and ...

{p Please, click on me {input 
  {@ type="submit" 
     value="°°{sqrt {+ {* 3 3} {* 4 4}}}°°" 
     onclick="°°

this.value = '{sqrt {+ {* 3 3} {* 4 4}}} = ' + 
(function (x) { return Math.sqrt(x) })(
  (function (x,y){ return x+y })(
    (function (x,y){ return x*y })(3,3),
    (function (x,y){ return x*y })(4,4)
  )
)

°°"}}. Cute isnt'it ?}