+
1
|
list
|
skin
|
login
|
editor
α-wwwiki
::
monodico_analyze
user:none
(7582 bytes)
{center {i If you should like a translation of this page, tell me in page [[forum]] !}} _h1 [[monodicolisp]] / analyse _p En complément de la page [[monodicolisp]] et de la [[console|data/monodicolisp/]], voici quelques réflexions centrées sur l'évaluateur de l'opérateur "lambda". _h3 environnements _p Dans mes tentatives de comprendre le LISP/SCHEME en l'implémentant dans un langage "LISP habillé en C", {b Javascript}, j'ai toujours eu des difficultés avec le concept de chaine d'environnements, même expliqué avec une luxe de détails et d'efforts pédagogiques par des maîtres en la matière comme Peter Norwig, Pascal Gribomont, Jean-Paul Roy, ... J'en comprenais la "musique" mais je butais toujours sur les "paroles" et en tout cas, je suis longtemps resté incapable d'écrire un code Javascript traduisant clairement toutes les "élégantes convolutions" liées à cette approche. Aujourd'hui, c'est chose faite, un code lisible est maintenant visible dans la page [[alphalisp|?view=lisp_evaluator]]. _h3 monodicolisp _p Dans l'approche appelée "[[monodicolisp]]", j'ai tenté d'esquiver la barrière de la chaîne d'environnements en me concentrant sur ce qui me paraît caractériser {i a minima} une fonction. Par exemple la fonction qui calcule l'hypothénuse d'un triangle rectangle peut s'écrire : {pre (lambda (a b) (sqrt (+ (* a a) (* b b)))) } _p Quand on applique cette fonction à un couple de valeurs, par exemple "3" et "4" : {pre ((lambda (a b) (sqrt (+ (* a a) (* b b)))) 3 4) } _p les occurrences des arguments "a" et "b" se trouvant dans le corps de la fonction seront remplacées par les valeurs "3" et "4" : {pre (sqrt (+ (* 3 3) (* 4 4))) } _p et ce corps de fonction sera évalué et retourné : {pre 5} _p Au fond, la 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. _h3 implémentation _p Dans l'implémentation Javascript, les listes sont écrites sous forme de tableaux : {pre (sqrt (+ (* a a) (* b b))) } _p s'écrit : {pre ["sqrt",["+",["*","a","a"],["*","b","b"]]] } _p Quand la fonction {b evaluate()} (cf [[code|data/monodicolisp/monodicolisp.js]]) reçoit une expression de la forme : {pre x = ["lambda",["a","b"],["sqrt",["+",["*","a","a"],["*","b","b"]]]] } _p le premier élément du tableau est : {pre x[0] == "lambda" } _p et l'expression x est (sous-)traitée à la fonction {b eval_lambda()} : {pre °° var eval_lambda = function ( x ) { var args = x[1], body = x[2]; // extract {args, body} return function() { // var _body = deepArrayCopy( body ); // local copy of body for (var i=0; i < arguments.length; i++) // put values in args deepArrayReplace( _body, args[i], arguments[i] ); return evaluate( _body ); // evaluate and return a deep array }; }; °°} _p Cette fonction "conserve" dans une fermeture les expressions : {pre args = ["a","b"] body = ["sqrt",["+",["*","a","a"],["*","b","b"]]] } _p et retourne le résultat d'un appel {b futur} effectué avec un couple de valeurs qui remplaceront les éléments du tableau en correspondance avec les paramètres de la fonction : {pre les "a" seront remplacés par la valeur "3", les "b" seront remplacés par la valeur "4", } _p Il se trouve que les fonctions {b deepArrayCopy()} et {b deepArrayReplace()} n'existent pas en javascript. En voici une écriture possible : {pre °° function deepArrayCopy(obj) { // create a new array from obj if (Array.isArray( obj )) { for (var out = [], i = 0; i < obj.length; i++ ) { out[i] = deepArrayCopy(obj[i]); } return out; } return obj; } function deepArrayReplace(obj, arg, val) { if (Array.isArray( obj )) { for (var i = 0; i < obj.length; i++ ) { obj[i] = (obj[i] === arg)? val : obj[i]; deepArrayReplace(obj[i], arg, val); } } } °°} _h3 premiers résultats _p La console [[monodicolisp|data/monodicolisp/]] permet de tester les fonctionnalités d'un interpréteur LISP basé sur ce choix d'un unique dictionnaire extensible. Les premiers résultats sont les suivants : _ul on peut définir et appliquer immédiatement une fonction : {pre ((lambda (x) (* x x))12) > 144 } _ul on peut donner un nom à une fonction (et donc étendre le dictionnaire) : {pre (define square (lambda (x) (* x x)) ) (square 12) > 144 } _ul la récursion est reconnue (ce qui n'était pas évident) : {pre (define fac (lambda (n) (if (< n 1) 1 (* n (fac (- n 1))) ) ) ) (fac 6) > 720 ... et d'autres exemples visibles dans [[monodicolisp]] } _ul les définitions de fonctions sont acceptées dans le corps d'une fonction : {pre {@ style="white-space:pre-wrap"} (define foo (lambda (x) (begin (define foo_bar (lambda (x) (* x x)) ) (* 2 (foo_bar x)) ) ) ) (foo 12) > 288 Note: ces fonctions internes sont ajoutées au dictionnaire unique, elles ont donc une portée globale et peuvent entrer en conflit avec d'autres défines avec le même nom par ailleurs ; ce mauvais point doit être corrigé en préfixant leurs noms avec le nom de la fonction englobante, par exemple : bar -> foo_bar. } _ul les fonctions peuvent être curryfiées : {pre (define foo (lambda (a b c) (a b c))) (foo * 2 3) > 6 peut s'écrire : (define goo (lambda (a) (lambda (b) (lambda (c) (a b c) ) ) ) ) (((goo *)2)3) > 6 et on peut donc aussi jouer avec des combinaisons de dérivées : (define D (lambda (f) (lambda (x) (begin (define dx 0.000001) (/ (- (f (+ x (dx))) (f (- x (dx)))) (* 2 (dx))) ) ) ) ) > [D] (define cubic (lambda (x) (* x x x))) > [cubic] (cubic 1) = 1 ((D cubic) 1) ≠ 3 ((D (D cubic)) 1) ≠ 6 ((D (D (D cubic))) 1) ≠ 6 ((D (D (D (D cubic)))) 1) ≠ 0 } _p Les exemples précédents peuvent être testés dans la page [[console|data/monodicolisp/]]. _p D'autres fonctionnalités sont encore à tester. Il sera intéressant de trouver {b les limites de cette approche} (comme le caractère global des définitions internes noté plus haut). Et d'envisager {b une forme d'écriture qui les ferait sauter} ... sans avoir à revenir à l'approche classique basée sur le chainage dynamique d'environnements (par exemple [[alphalisp|data/alphalisp/]]). _p Dernière remarque : si Javascript est {b vraiment} un "LISP habillé en C", il devrait être possible d'écrire du code Javascript qui ressemble à du LISP comme deux gouttes d'eau. La page [[jslambda]] en donne un exemple dont voici un extrait : {pre var foo = (zero ) (end )(0); // 0 var foo = (succ (zero )) (end )(0); // 1 var foo = (succ (succ (zero ))) (end )(0); // 2 var foo = (succ (succ (succ (zero )))) (end )(0); // 3 var foo = (add (succ (succ (succ (zero )))) (succ (succ (zero ))) (end )(0)); // 3+2 = 5 var foo = (mul (succ (succ (succ (zero )))) (succ (succ (zero ))) (end )(0)); // 3*2 = 6 var foo = (pow (succ (succ (succ (zero )))) (succ (succ (zero ))) (end )(0)); // 3^2 = 9 } _p Au vu de cet exemple, on pourrait même imaginer aboutir à un interpréteur LISP réduit à presque rien, sinon zéro ! _p Chiche ! _h6 notes _ul [[Sur-le-probleme-de-Hamming|http://www.apmep.asso.fr/Sur-le-probleme-de-Hamming-l]] _ul ...