+
1
|
list
|
skin
|
login
|
editor
α-wwwiki
::
eval_evolution
user:none
(5733 bytes)
_h1 eval evolution {sup (update)} _p This page presents some steps in the lambdaway, a quest for a minimal, complete and understandable lisp engine. This engine should be able to evaluate nested s-expressions, nested environments/dictionaries, recursion, currying, ... all these bells and whistles of the LISP world integrated in a wiki structure. Here is a list of the pages storing the successive attempts : _ul Phase 4 _ul30 3) [[monodicolisp]] : what can do an evaluator based on a unique dictionary _ul30 2) [[littlelisp|data/littlelisp/]] : from Mary Rose Cook _ul30 1) [[jsonlisp|data/jsonlisp/]] : using JSON functions _ul Phase 3 _ul30 4) [[lisp_evaluator]], a true lisp engine named {b alphalisp} _ul30 3) [[regexp_evaluator]], another on a loop _ul30 2) [[extended_evaluator]], an extended one with a "def" operator _ul30 1) [[basic_evaluator]], a minimal set _ul Phase 2 _ul30 5) [[evaluator3]] : add define operator _ul30 4) [[evaluator2]] : the same integrated in a wiki page _ul30 3) [[evaluator]] : 8 lines evaluator with Alan Dipert _ul30 2) [[psil2]] : add a lexer and integrate in a wiki page _ul30 1) [[psil]] : a smart pocket lisp interpreter written by Pablo Vidal _ul Phase 1 _ul30 [[amlisp]] : Peter Norvig + SreedathNS _h3 code _p Two approaches of a s-expressions evaluator emerged : _ul the first is based on a "recursive evaluation working on an array", from the root to the leaves of the tree structure, _ul the second is based on a "regexp loop evaluation working on strings", from the leaves to the root of the tree structure. _p Here is a comparison between these two approaches written {i "a minima"} : {pre {@ id="code"}°° var EVALUATOR = (function () { // 1) the very basic dictionary shared by the two evaluators : var dico = {}; dico['find'] = function (op) { return this.hasOwnProperty(op) } dico['+'] = function () { for (var s=0, i=0; i< arguments.length; i++) s += Number(arguments[i]); return s; }; dico['*'] = function () { for (var p=1, i=0; i< arguments.length; i++) p *= arguments[i]; return p; }; dico['sqrt'] = function (a) { return Math.sqrt(a) }; // 2) the lisp-like evaluation working on an array expression var do_evaluate = function (str) { return evaluate(eval(str)); // needs the "evil" eval() function }; var evaluate = function(arr) { if (!Array.isArray(arr)) // it's not a s-expression return arr.toString(); var first = arr.shift(); // get function, clean array if (dico.find(first)) { // first is in the dico for (var rest = [], i=0; i< arr.length; i++) rest[i] = evaluate( arr[i] ); // evaluate inner arrays return dico[first].apply(null,rest); // first(rest) } else return '{'+first+' '+rest+'}'; // don't evaluate }; // 3) the regexp loop evalution working on true lisp-like s-expressions var do_loop = function( str ) { var looprex = /\(([^\s()]*)(?:[\s]*)([^()]*)\)/g; // -> (first rest) while (str != (str = str.replace( looprex, dispatch))); // one line return str; }; var dispatch = function (m, first, rest) { first = first || '', rest = rest || ''; // filter if (dico.find(first)) // first is in the dico return dico[first].apply(null, rest.split(' ')); // first(rest) else return '{'+first+' '+rest+'}'; // don't evaluate }; return { // public functions do_evaluate:do_evaluate, do_loop:do_loop }; }()); // EVALUATOR id now created °°} _h3 console _ul {b First click once} on the "create evaluators" button, _ul enter {b one} array-like expression in the first textarea _ul enter one or several lisp-like expression(s) in the second textarea _ul click on the "evaluate" buttons to display the evaluations. {input {@ type="submit" value="create evaluators" onclick="°° var js = document.createElement('script'); var input = getId('code').innerHTML; js.innerHTML = decode_html_entities(input); // < ,> document.head.appendChild( js ); this.value = 'OK, evaluators created !'; this.disabled='disabled'; °°"}} _h5 1) recursive evaluation on an array {textarea {@ id="input1" style="width:99%;height:50px;background:#ffe;font:normal 1em courier;"} ['sqrt', ['+', ['*',3,3], ['*',4,4]]] } {pre {@ id="output1"}} {input {@ type="submit" value="evaluate1" onclick="°° getId('output1').innerHTML = EVALUATOR.do_evaluate(getId('input1').value); °°"}} _h5 2) regexp loop evaluation on one or several string(s) {textarea {@ id="input2" style="width:99%;height:100px;background:#ffe;font:normal 1em courier;"} Hello strings ! (* 3 3) (+ (* 3 3) (* 4 4)) (sqrt (+ (* 3 3) (* 4 4))) } {pre {@ id="output2"}} {input {@ type="submit" value="evaluate2" onclick="°° getId('output2').innerHTML = EVALUATOR.do_loop(getId('input2').value); °°"}} _h5 notes _ul {b the first evaluator} works on {u only one} array and calls the eval() function in order to transform the "array looking" primitive input string in a true nested array. In the page [[basic-evaluator]] this function is replaced by two composed functions (tokenize() and build_tree()) allowing working on true s-expressions (and to forget the "array looking" string). _ul {b the second evaluator} works on {u one or several} strings, doesn't need any array structure and uses the power of the RegExp engine. Recursion is replaced by a unique loop catching s-expressions from the innermost to the root with the help of a unique RegExp. _ul Because of its {u text context}, the alphawiki's engine is built on the second evaluator type : see code in file [[JS.js|meca/JS.js]]. It looks like a good choice :) :)