α-wwwiki

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

editor : alpha [82.248.194.227] 2013/10/08 09:26:31
{center {i  travail en cours}}

_h1 s-expressions evaluation

_p Les structures arborescentes sont partout. 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}". Par exemple :
_ul la phrase « l'oiseau pose ses pattes sur la branche » s'écrira :
_ul50 (S (GN l'oiseau) (CV pose (GN ses pattes) (CP sur (GN la branche)))
_ul l'expression mathématique « 1 + 2*3 + 4 » s'écrira :
_ul50 (+ 1 (* 2 3) 4)

_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. Le choix des séparateurs "{b °°{ et }°°}" et non {b "( et )"} apparaît préférable dans un environnement wiki où le "texte" est l'essentiel du contenu.

_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 "carré" (square) qui n'est pas pré-définie dans le dictionnaire :

{pre °° {square 12} -> 144 °°}

_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['square'] = function (x) { 
  return x*x 
};
°°}

_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 square (x) 
  {* x x}
}
°°}
_p Un nouvel opérateur, "{b def}" fait son apparition ; il est suivi du nom de la fonction, de la liste des arguments entre parenthèses et d'une (ou plusieurs) s-expression(s) formant le corps de la fonction. Mais cette écriture nécessite une transformation assez radicale de l'évaluateur, qu'il soit "string" ou "array".

_h5 43) écriture du code

{pre {@ style="white-space:pre-wrap;"}°°

... a work in progress

°°}

{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)
  )
)

°°"}}