α-wwwiki

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

editor : alpha [82.250.66.246] 2013/10/07 08:29:29
_h1 s-expressions evaluation

_h3 1) s-expression
_p Définition d'une expression symbolique
{pre {@ style="white-space:pre-wrap;"}°°

forme d'une s-expression : {first rest} où
- first est une fonction définie dans un dictionnaire extensible
- rest est {first rest} ou une chaîne de cars sauf { et }
- les éléments du dictionnaire ont la forme : dico['first'] = function (args) { JS expressions ; return valeur }

°°}

_h3 2) fonctionnement de l'évaluation

_p Deux approches sont comparées.
_p 21) La première utilise les expressions régulières : chaque s-expression est directement évaluée dans une boucle appliquant une expression régulière depuis les feuilles jusqu'à la racine

{pre {@ style="white-space:pre-wrap;"}°°
input = {sqrt {+ {* 3 3} {* 4 4}}}
{sqrt       boucle 3
  {+        boucle 2
    {* 3 3} boucle 1
    {* 4 4} boucle 1
  }         boucle 2
}           boucle 3
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 utilise les tableaux emboîtés : chaque s-expression est transformée en un tableau emboîté ; ce tableau est parcouru 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 regexp
{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 tableau
{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 fonction utilisateur, par exemple :

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

°°"}}