α-wwwiki

α-wwwiki :: history/monodicolisp/20130919-184724.txt

editor : alpha [82.253.96.67] 2013/09/19 18:47:24
_h1 monodicolisp {sup (5)}

{div {@ style="text-align:center; color:red; background:#eee;box-shadow:0 0 8px black;"} 
[[basic evaluator|?view=basic_evaluator]] | 
[[extended eval|?view=extended_evaluator]] | 
[[regexp eval|?view=regexp_evaluator]] | 
[[alpha lisp|?view=lisp_evaluator]] |
monodico lisp
}

_p This work is not integrated in this wiki page and can be analyzed and tested in the  :
{div {@ style="text-align:center; color:red; background:#eee;box-shadow:0 0 8px black;font-size:3em;"}[[monodicolisp console|data/monodicolisp/]]}

_p This page gives a description of the code, focusing on its essential part. The plain code can be seen in the file [[monodicolisp.js|data/monodicolisp/monodicolisp.js]]. 
_p {u An analyze (in french) can be seen in the page : [[analyze|?view=monodico_analyze]]}.

_h3 CONSOLE
_p Below is an example of the console content with some symbolic-expressions (s-expressions) shown with their evaluations after ">"

{pre °°
(+ 1 2) 
> 3

(sqrt 
  (+ 
    (* 3 3) 
    (* 4 4)
) )
> 5

(define square 
  (lambda (x) 
    (* x x)
) )
(square 12) 
> 144

(define foo
  (lambda (x)
    (begin
      (define bar 
        (lambda (x) (* x x))
      )
      (* 2 (bar x))
) ) )
(foo 12)
> 288

(define fac 
  (lambda (n) 
    (if (< n 1) 
      1 
      (*  n  (fac (- n 1)))
) ) )
> [fac]

(fac 6) 
> 720
°°}
_p An {b s-expression} has this form {b (first rest)}, where first is a {b function} and rest is an s-expression, a number or a string (word) ; so, an s-expression is an arborescent structure. In the console, any s-expression can be written on several lines, and several expressions can be evaluated in sequence. To be valid, the s-expressions must be written between {b balanced parenthesis}, the {b built-in functions} must belong to the defined dictionary (see [[monodicolisp presentation|data/monodicolisp/]]) and the {b special forms} must be choosen in this reduced set : [{b lambda, define, if, quote, begin, set!}]. More can be seen in the [[console|data/monodicolisp|data/monodicolisp/]].

_h3 HTML INTERFACE
_p Two containers are created in a HTML file : a {b textarea} for the input and a {b pre} ({u pre}serving line returns and spaces) for the output. For each character entered in the {b input} frame, the function {b do_evaluate()} is called ; it catches the value of the {b input} frame, calls the function {b parser()} given by the {b MONODICOLISP} modulus and returns the evaluation in the {b output} frame.

{pre °°
< textarea id="input" onkeyup="do_evaluate()">...< /textarea >
< pre id="output" >...< /pre >

function do_evaluate() { 
  var input = document.getElementById( 'input' ).value;
  var output = MONODICOLISP.parser( input );
  document.getElementById( 'output' ).innerHTML = output;
}
°°}

_h3 INTERPRETER
_p The function {b parser()} is given by the modulus {b MONODICOLISP}. This modulus is a function defined and executed on loading which creates a dictionary containing a set of couples [{b function_name:function_value}], then defines the function {b parser()} and its associated. This function calls successively three functions :
_ul 1) {b tokenize()} transforming an s-expression {b (first rest)} (a string) into a flat array,
_ul 2) {b build_tree()} transforming the flat array in a nested one (a tree),
_ul 3) {b evaluate()} recursively evaluating it and returning a value (a string).
 
{pre °°
var MONODICOLISP = (function () {

var dico = {}; // will be populated like this :
...
dico['name'] = function () { do something with arguments }
...

function parser( str ) {
  var arr = tokenize( str );  // a flat array
  arr = build_tree( arr );    // a nested array
  str = evaluate( arr );      // an evaluated expression, a string
  return str;
}

return { parser:parser }; // public function

})(); // end defining and calling MONODICOLISP 
°°}

_h3 TOKENIZE()
_p The function {b tokenize()} takes a string, a valid s-expression, and returns a flat array. It puts spaces around parenthesis, cleans spaces before and after the string and {b creates a flat array} by splitting the string at every sequences of spaces (or line returns and tabs). For instance :
{pre 
(sqrt 
  (+ (* 3 3) 
     (* 4 4)
  )
) ->
['(','sqrt','(','+','(','*','3','3',')','(','*','4','4',')',')',')']
}
_p The code uses regular expressions :
{pre °°
function tokenize( s ) { 
  return s.replace(/\(/g, ' ( ') // put spaces around '('
          .replace(/\)/g, ' ) ') // and ')'
          .trim()                // clean spaces before and after
          .split(/\s+/);         // create a flat array on spaces
}
°°}

_h3 BUILD_TREE()
_p The function {b build_tree()} reads every elements of the flat array. It creates a new array for each '(' and fills it {b recursively} until the first ')', generating a tree structure. For instance :

{pre 
['(','sqrt','(','+','(','*','3','3',')','(','*','4','4',')',')',')']
->
['sqrt'              // first array
  ['+'               // inner array
    ['*','3','3'],   // first inner/inner array
    ['*','4','4']    // second inner/inner array
  ]
]
}
_p The code :

{pre °°
function build_tree(tokens) {
  var token = tokens.shift();
  if (token !== '(') 
    return token;
  var arr = [];
  while (tokens[0] !== ')')
    arr.push( build_tree(tokens) );
  tokens.shift();
  return arr;
}
°°}
_p Note that the javascript {b eval()} function is not used.

_h3 EVALUATE()
_p The function {b evaluate()} will evaluate the tree structure given as input and will return its value. It works on a unique dictionary created and populated with javascript primitive functions associated to names. This primitive set can be extended by the user grace to the {b define} function which produces constants and user functions. The function {b evaluate()} receives a nested array {b x} and returns a string according to the following filter in nine cases :

{pre °°
var evaluate = function (x) { 
1:  if (is_number(x))	          return eval_number( x );
2:  else if (is_symbol(x))        return eval_symbol( x );
3:  else if (is_function(x))      return eval_function( x );
4:  else if ( x[0] === 'quote' )  return eval_quote( x );
5:  else if ( x[0] === 'if' )     return eval_if( x );
6:  else if ( x[0] === 'lambda' ) return eval_lambda( x );
7:  else if ( x[0] === 'define' ) return eval_define( x );
8:  else if ( x[0] === 'set!' )   return eval_set( x );
9:  else                          return eval_apply( x );
}; // evaluate
°°}

_ul {span {@ style="font-size:2em"}1)} if {b x} is a number, it returns that number, for instance  :
{pre 5 
-> 5
}

_ul {span {@ style="font-size:2em"}2)} if {b x} is a string, it looks in the dico and returns the value of the function associated to this name, for instance :
{pre °° sqrt 
-> dico['sqrt'] 
-> function() { return Math.sqrt(arguments[0]) }°°}

_ul {span {@ style="font-size:2em"}3)} if {b x} is a function, it returns that function "as it is", for instance :
{pre °° function() { doSomething } 
-> function() { doSomething }
°°}
_p This test solves this kind of situation, where the operator has been previously evaluated before being given to the lambda :
{pre
((lambda (op) (op 3 4))*) -> 12        
((lambda (op) (op 3 4))+) -> 7     
'*' and '+' are soon replaced by their value, a function !
}
_p This simple "trick" allows to use operators as arguments and opens the door to currying, see the example of the derivee function "D".

_ul {span {@ style="font-size:2em"}4)} if the first element of {b x}, {b x[0]} is {b quote}, it builds an array minus this first item and returns an {b unevaluated} string built on the elements separated by a space :
{pre ['quote','MONO', 'DICO', 'LISP'] 
-> ['MONO', 'DICO', 'LISP'] 
-> 'MONO DICO LISP'}

_ul {span {@ style="font-size:2em"}5)} if the first element of {b x}, {b x[0]} is {b if} :
{pre ['if',['< ','1','2'], ['+','2,'3'], ['*','2,'3']] }
_ul50 it evaluates the second element {b x[1]}
{pre 
['< ','1','2']
-> true
 }
_ul50 the condition is true, so it evaluates and returns {b x[2]}, here '{b 5}'
{pre 
['+','2','3']
-> 5
 }
_ul50 and doesn't evaluate {b x[3]}
{pre 
['*','2','3']
}

_ul {span {@ style="font-size:2em"}6)} if the first element of {b x}, {b x[0]} is {b lambda}, for instance :
{pre 
['lambda', ['x', 'y'], ['+', 'x', 'y']]
}
_ul50 the arguments and the body's arrays are stored in two local vars : 
{pre 
{b args = x[1] = ['x', 'y']} 
{b body = x[2] = ['+', 'x', 'y']} 
}
_ul50 and an anonymous function is defined ; when called with some values, this function will successively replace the elements in the body listed in the args array with the values passed as arguments, then will evaluate and return the body, for instance : 
{pre °°
1) a lambda can be called with some values like this :
   [['lambda', ['x', 'y'], ['+', 'x', 'y']], '3', '4']

2) according to the args array ['x', 'y'], 
   and with the given arguments array ['3', '4']
   the body ['+', 'x', 'y'] will become  ['+', 3, 4] 
   and evaluated to 7
°°} 
_p The replacement {b args -> values} has to be made in a nested array, and a custom function {b deepArrayReplace()} has had to be created. Grace to this {i original} approach, there is no need of creation of a local dictionary with the pairs [args:values], nor an extension of the global dictionary. The substitution is dynamic, not lexical.

_ul {span {@ style="font-size:2em"}7)} if the first element of {b x}, {b x[0]} is {b define}, for instance :
{pre 
['define', 'twoPI', ['*', '2', '3.1416']]
}
_ul50 a function is added to the dictionary which will return the value of the expression :

{pre °°
dico[x[1]] = function () { return evaluate( x[2] ) }
°°}

_ul50 if the expression is a {b lambda}, this "anonymous function" will be given a name :
{pre 
['define', 'add', ['lambda', ['x', 'y'], ['+', 'x', 'y']]]
}
_ul50 when the name will be called with some values, it will be replaced by the body of the lambda for an evaluation associated with these values :

{pre
['add', '3', '4']
-> [['lambda', ['x', 'y'], ['+', 'x', 'y']], '3', '4']
-> ['+', 3, 4]
-> 7
}

_ul {span {@ style="font-size:2em"}8)} if the first element of {b x}, {b x[0]} is {b set!} (should be pronounced {i set-bang}), for instance :

{pre ['set!', 'x', ['+', 'x', '1']] }

_p provided the name {b x} has been previously defined, this value will be incremented. With this special form, it becomes possible to create {b side effects} ; see the bank example in the console.

_ul {span {@ style="font-size:2em"}9)} else ... every special forms have been handled and now the s-expressions can be actually evaluated !
_ul50 a new array {b xx} is created with the evaluated elements of {b x}, for instance :
{pre 
['+', ['*', '3', '3'], ['*', '4', '4']]
the three elements will be evaluated :
1)  '+' -> function() °°{ return arguments[0] + arguments[1] }°°
2)  ['*', '3', '3'] -> 9
3)  ['*', '4', '4'] -> 16
}
_ul50 then the first element will be applyed to the rest of the array {b xx} 
{pre
(function() °°{ return arguments[0] + arguments[1] }°°(9,16))
-> 25
}
_ul50 and the result will be returned.

_p Here is the code of the function evaluate() and its associated :

{pre °°
var evaluate = function (x) { 
  if (is_number(x))	        return eval_number( x );
  else if (is_symbol(x))        return eval_symbol( x );
  else if (is_function(x))      return eval_function( x );
  else if ( x[0] === 'quote' )  return eval_quote( x );
  else if ( x[0] === 'if' )     return eval_if( x );
  else if ( x[0] === 'lambda' ) return eval_lambda( x );
  else if ( x[0] === 'define' ) return eval_define( x );
  else if ( x[0] === 'set!' )   return eval_set( x );
  else                          return eval_apply( x );
}; // evaluate

var eval_lambda = function ( x ) {
  var args = x[1], body = x[2];
  return function() {             // will replace args by arguments
    var _body = deepArrayCopy( body ); // working on a copy of body
    for (var i=0; i < arguments.length; i++)
      deepArrayReplace( _body, args[i], arguments[i] );
    return evaluate( _body );
  };
};

var eval_set = function ( x ) {     // ['set!',name, s-expression]
  var name = x[1],                  // dico[name] must exist
      new_val = evaluate( x[2] );
  dico[name] = function () { return new_val };
  return dico[name]();              // feedback
};

var eval_begin = function ( x ) {
  var xx = x.map(evaluate);         // eval in sequence
  return xx[xx.length-1];           // return the last
};

var eval_apply = function (x ) {
  var xx = x.map(evaluate);					
  var func = xx.shift();						
  return func.apply(null,xx);				
};
°°}

_p {b Notes} : the {b define} operator extends the primitive dictionary with user functions whose body is made of s-expressions. In standard Lisp evaluators, when user functions are called, a new temporary dictionary is created with the pairs [args:values] which will be used for the evaluation. Evaluation must always be done in a local context (linked to the global one). In order to keep things simple, it's not the choice here. More standard and complete Lisp interpreters can be seen here : [[lisp_evaluator]] and [[littlelisp|data/littlelisp/]].

_h3 DICTIONARY
_p The {b MONODICOLISP} modulus creates and starts populating the primitive global environment with a set of associations {b name:function}. In this introduction, the set is limited to the minimum required for the definition the examples {b hypo} and {b fac}. A more complete dictionary can be seen in the file [[monodicolisp.js|http://epsilonwiki.free.fr/alphawiki/data/monodicolisp/monodicolisp.js]].

_p This is a (short) abstract of the code creating and populating the dictionary :

{pre °°
var dico = {};

dico['+']    = function() { return arguments[0] + arguments[1] };
dico['*']    = function() { return arguments[0] * arguments[1] };
dico['< ']    = function() { return arguments[0] < arguments[1] };
dico['sqrt'] = function() { return Math.sqrt(arguments[0]) };

// and so on ...
°°}

_h3 next
_p With this minimal structure, as it can be seen in the examples joined to [[monodicolisp|http://epsilonwiki.free.fr/alphawiki/data/monodicolisp/]], it is possible :
_ul to evaluate any sequence of nested s-expressions,
_ul to define user functions.
_ul functions can be defined inline but, being in the dico, they are in the global scope.
_ul functions can be recursive, 
_ul and curryed : (foo a b) -> ((foo a) b) ; see examples in the console.

_p Today, basic lists functions (car, cdr, ...) are not stabilized, some combinations don't work as expected. The evaluate() function's body doesn't catch every combinations of s-expressions and a deep analyze of primitives such is-symbol(), is_function(), is_null(), ... must be done.

_p {b I have a question} : does these explanations on a basic lisp interpreter (without the burden of nested environments) give {b you} answers to some questions you might have had about a Lisp interpreter, {u as it does for me} ? Your opinion is welcome in the page [[forum]].