α-wwwiki

α-wwwiki :: history/eval_evolution/20130726-044902.txt

editor : alpha [82.64.19.24] 2013/07/26 04:49:03
_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 1
_ul30 [[amlisp]] : Peter Norvig + SreedathNS

_ul Phase 2
_ul30 1) [[psil]] : a smart pocket lisp interpreter written by Pablo Vidal
_ul30 2) [[psil2]] : add a lexer and integrate in a wiki page
_ul30 3) [[evaluator]] : 8 lines evaluator with Alan Dipert
_ul30 4) [[evaluator2]] : the same integrated in a wiki page
_ul30 5) [[evaluator3]] : add define operator

_ul Phase 3
_ul30 1) [[basic_evaluator]], a minimal set
_ul30 2) [[extended_evaluator]], an extended one with a "def" operator
_ul30 3) [[regexp_evaluator]], another on a loop
_ul30 4) [[lisp_evaluator]], a true lisp engine

_ul Phase 4
_ul30 1) [[jsonlisp|data/jsonlisp/]] : using JSON functions
_ul30 2) [[littlelisp|data/littlelisp/]] : from Mary Rose Cook
_ul30 3) [[monodicolisp|data/monodicolisp/]] : what can do an evaluator based on a unique dictionary

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