α-wwwiki

α-wwwiki :: history/monodicolisp/20130729-102549.txt

editor : alpha [83.159.97.183] 2013/07/29 10:25:49
_h2 MONODICOLISP ([[console|data/monodicolisp]])
_p {b monodicolisp} is a small lisp console which can be tested here : {u [[monodicolisp|http://epsilonwiki.free.fr/alphawiki/data/monodicolisp|data/monodicolisp/]]}. This page gives a description of the code, focusing on its essential part. The plain code can be seen in the file [[monodicolisp.js|http://epsilonwiki.free.fr/alphawiki/data/monodicolisp/monodicolisp.js]].

_h3 CONSOLE
_p A lisp-like symbolic-expression (s-expression) is an arborescent structure such as :
{pre °°
(quote MONO DICO LISP)

(+ 1 2) 
> 3

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

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

(define fac 
  (lambda (n) 
    (if (< n 1) 
      1 
      (* 
        n 
        (fac (- n 1))
      )
    )
  )
)
> [fac]
(fac 6) 
> 720
°°}
_p In the editor frame, any s-expression can be written on several lines and several expressions can be evaluated in the same time. S-expressions are supposed to be valid : the parens must be balanced, the operators must belong to the defined dictionary (see [[monodicolisp.js|http://epsilonwiki.free.fr/alphawiki/data/monodicolisp/monodicolisp.js]]) and the special operators to the reduced set [{b lambda,define, if, quote}]. More can be seen in the console [[monodicolisp|http://epsilonwiki.free.fr/alphawiki/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 parseval()} 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" onkeyup="do_evaluate()" >...< /pre >

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

_h3 INTERPRETER
_p The function {b parseval()} 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 parseval()} 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 = {};
dico['name'] = function () { do something with arguments }

function parseval( str ) {
  str = '(tree ' + 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 { parseval:parseval }; // public function

})();
°°}
_p {b Note} : the function {b parseval()} waits for a {b unique s-expression}. In order to handle several s_expressions without boring with a catching loop, it encapsulates them in a {b (tree ...)} form which transforms the "forest" in a simple "tree".

_h3 TOKENIZE()
_p The function {b tokenize()} takes 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 :
{pre °°
function tokenize( s ) { 
  return s.replace(/\(/g, ' ( ')
          .replace(/\)/g, ' ) ')
          .trim()
          .split(/\s+/);
}
°°}

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

{pre 
['(','sqrt','(','+','(','*','3','3',')','(','*','4','4',')',')',')']
->
['sqrt'
  ['+'
    ['*','3','3'],
    ['*','4','4']
  ]
]
}
_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;
}
°°}

_h3 EVALUATE()
_p The function {b evaluate()} 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 lambda} and {b define} functions.  The function {b evaluate()} receives a nested array {b x} and returns a string according to the following filter in eight steps :

{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                          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 replaced by their value, a function !
}
_p This simple "trick" allows to use operators as arguments and opens the door to currying, see the examples "derivee and 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 a 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 an anonymous function is defined with an arguments array and a body  : 
{pre 
{b args = x[1] = ['x', 'y']} 
{b body = x[2] = ['+', 'x', 'y']} 
}
_ul50 when called with some values, this function will replace the variables in the body with these values according to the arguments, then will evaluate and return the body : 
{pre °°
1) a lambda can be called with values like this :
[['lambda', ['x', 'y'], ['+', 'x', 'y']], '3', '4']
2) according to the arguments ['x', 'y'], 
the body ['+', 'x', 'y'] will become  ['+', 3, 4] evaluated to 7
°°}

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

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

_ul50 it's a way to give a name to an anonymous function with arguments :
{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 and evaluated :

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

_ul {span {@ style="font-size:2em"}8)} else ... here things are actually evaluated !
_ul50 a new array {b xx} is created with the evaluated elements of {b x}
{pre ['+', ['*', '3', '3'], ['*', '4', '4']]
'+' -> function() °°{ return arguments[0] + arguments[1] }°°
['*', '3', '3'] -> 9
['*', '4', '4'] -> 16

}
_ul50 the first element is applyed to the rest of the array {b xx} 
{pre
(function() °°{ return arguments[0] + arguments[1] }°°(9,16))
-> 25
}
_ul50 and the result is 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                          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 = deepCopy( body ); // working on a copy of body
    for (var i=0; i < arguments.length; i++)
      _body = deepReplace( _body, args[i], arguments[i] );
    return evaluate( _body );
  };
};

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, hence some limitations to analyze further. 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]]. The operator {b tree} has been explained in the paragraph "INTERPRETER".

_p This is 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]) };
dico['tree'] = function() { return [].slice.call(arguments).join('\n') };
// and so on ...

°°}

_h3 next
_p With this minimal structure, as it can be seen in [[monodicolisp|http://epsilonwiki.free.fr/alphawiki/data/monodicolisp/]], it is possible to evaluate any sequence of nested s-expressions and to define user functions, functions can be recursive and curryed.

_p The last point is : does these explanations of a very basic lisp interpreter give answers to some questions you might have had about it, as it does for me ?