α-wwwiki

α-wwwiki :: history/evaluation/20131007-185616.txt

editor : alpha [82.250.66.246] 2013/10/07 18:56:16
{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, dans un navigateur c'est le javascript :
{pre dico['first'] = function (args) °°{ JS expressions ; return valeur }°°}

_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
value = {sqrt {+ 9 16}}

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

boucle 3 :
  {sqrt 25} = (function (x) { return Math.sqrt(x) })(25) 
value = 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}}
value = nested_array(input) = 
['sqrt',
  ['+',
    ['*','3','3'],
    ['*','4','4']
  ]
]
value = 
(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)
  )
) 
value = 5
°°}
_h3 3) l'évaluateur en JavaScript

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

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

function doLoop( str ) {
  var loop_rex   = /\(([^\s()]*)(?:[\s]*)([^()]*)\)/g;
  while (str != (str = str.replace( loop_rex, dispatch ))) ; 
  return str;
}

function dispatch (m, f, r) {
  if (dico.hasOwnProperty( f )) {
    var func = dico[f];
    var xx = r.split(' ');
    return func.apply(null,xx);
  } else
    return '[' + f + ' ' + r + ']';
}

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']]]
value = evaluate(x) = 5

function build_flat_array (str) { ... }
function build_nested_array (str) { ... }

function  evaluate = function (x) { 
  if (is_number(x))	        
    return x;
  else if (is_symbol(x))        
    return dico[x];
  else {                      
    var xx = x.map(evaluate);					
    var func = xx.shift();
    return func.apply(null,xx);				
  }
};

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

°°}

_h3 4) extension du dictionnaire
_p Comment ajouter une nouvelle fonction ? Par exemple la fonction "carré" (square) :

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

_h5 41) statiquement dans le dictionnaire

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

dico['square'] = function (x) { return x*x };

°°}

_h5 42) dynamiquement dans le code

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

{def square (x) {* x x}}

°°}

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

°°"}}