lambdaway :: lambdacode4

2 | list | login |load

| |

_h1 lambdacode {sup ( [[1|?view=lambdacode]] | [[2|?view=lambdacode2]] | [[3|?view=lambdacode3]] | 4 | [[5|?view=lambdacode5]]) }

{{block}
_h2 introduction
_p Everything in the {b LISP} world began with the initial code of John McCarthy on which worked a lot of good people, Abelson & Sussman, Paul Graham, and several others. {b Peter Norvig} wrote a smart and well documented LISP interpreter in the PYTHON language, [[lispy|http://norvig.com/lispy.html]]. A few young coders, {b Sreedathns, Sainamdar} and others, proposed their own translations in Javascript which inspired me greatly. {b lambdacode} is my translation of the Peter Norvig's LISP engine. The engine is a standard {b AST} evaluator, {b tokenizing} the input string, building an {b abstract syntaxic tree} and {b parsing} it, whose kernel is built in less than 100 JS lines. The dictionary is populated with a reduced set of math primitives and array primitives replacing pairs and lists commonly used in Lisp.

_p So, written inside {b lc} lambdatalk containers, (upper block), [[lambdacode|?view=lambdacode2]] expressions can be evaluated, (lower block).

{pre
'{lc 
  (+ 1 2)
}
}
_p displays
{pre
{lc
(+ 1 2)
}
}

_p Out of this wiki, in any HTML document without lambdatalk, lambdacode expressions can be evaluated similarily inside {b class "LC"} HTML containers, for instance
{pre 
<{span}pre class="LC"> 
  any lambdacode expression
<{span}/pre>
}

_h4 Notes

_ul The complete lambdacode's engine can be copied from this page and used in any HTML file, with very small adjustments.
_ul all lambdacode expressions written in a page are linked, functions defined here can be used there, freely intermixed with lambdatalk functions used for enriching and structuring wiki pages. So can we take benefit of both of the worlds, with AND without closures.

}

{{block}
_h2 basics

_p Everything begins with a text replacement process

{pre
please replace a & b
            in ... b a ...
            by hello & world
}

_p which should obviously display

{pre ... world hello ...}

_p In {b lambdacode} such a text replacement process is expressed as an {b IIFE}, an {b I}mmediately {b I}nvoked {b F}unction {b E}xpression

{pre
((lambda (a b) 
         (join '... b a '...)) 
         'hello 'world)
}

_p immediately evaluated to

{pre
{lc 
((lambda (a b) 
         (join '... b a '...)) 
         'hello 'world)
}}

_p In order to make things easier an {b IIFE} can be written in 3 steps: 
_ul 1) define a {b function} using the {b lambda} first special form
_ul 2) give it a {b name} using the {b def} second special form
_ul 3) and apply this function to values, {b (name values)}.

_p For instance

{pre
(def swap 
 (lambda (a b) 
         (join '... b a '...)))

(swap 'hello 'world)     // words must be quoted

(swap (@ james bond))    // or placed inside the @ special form
}

{pre
{lc
(def swap 
 (lambda (a b) 
         (join '... b a '...)))
'
(swap 'hello 'world)
'
(swap (@ james bond))
}}

_p So, remember that all that is nothing but text replacements.

_p Note that lambdacode tries to evaluate each word as a name, a function's reference, and words which are not - like {b hello}, {b world} and {b ...} - must be "escaped" either by the {b quote} character or placed inside the {b (@ ...)} special form.

_p We could suppose, as in {b λ-calculus}, that the dictionary is empty and so without any primitives. Using nothing but the {b lambda & def} special forms, we can can theoretically built every data and control structures ({b booleans, pairs, lists, recursion, ..}).

{pre
(def TRUE (lambda (x y) x))
(def FALSE (lambda (x y) y))
(def IF (lambda (x y z) (x y z)))
'
(def PAIR (lambda (x y) (lambda (z) (z x y))))
(def LEFT (lambda (z) (z TRUE)))
(def RIGHT (lambda (z) (z FALSE)))
'
(def NIL FALSE)
(def ISNIL (lambda (n) (n (lambda (x) FALSE) TRUE)))
'
((ISNIL NIL) 'yes 'no)
((ISNIL (PAIR 'a 'b)) 'yes 'no) 
'
(def DISP
 (lambda (list)
  ((IF (ISNIL list)
    (lambda (list) '.)
    (lambda (list) (join (LEFT list) (DISP (RIGHT list)) ))
   ) list)))
'
(def FRUITS
 (PAIR 'apple
  (PAIR 'banana
   (PAIR 'lemon
    (PAIR 'grapes
     (PAIR 'orange NIL))))))

(DISP FRUITS)   
}

{pre
{lc
(def TRUE (lambda (x y) x))
(def FALSE (lambda (x y) y))
(def IF (lambda (x y z) (x y z)))
'
(def PAIR (lambda (x y) (lambda (z) (z x y))))
(def LEFT (lambda (z) (z TRUE)))
(def RIGHT (lambda (z) (z FALSE)))
'
(def NIL FALSE)
(def ISNIL (lambda (n) (n (lambda (x) FALSE) TRUE)))
'
((ISNIL NIL) 'yes 'no)
((ISNIL (PAIR 'a 'b)) 'yes 'no)
'
(def DISP
 (lambda (list) 
  ((IF (ISNIL list)
    (lambda (list) '.)
    (lambda (list) (join (LEFT list) (DISP (RIGHT list)) ))
   ) list))) 
'
(def FRUITS
 (PAIR 'apple
  (PAIR 'banana
   (PAIR 'lemon
    (PAIR 'grapes
     (PAIR 'orange NIL))))))

(DISP FRUITS)

}}

_p And so on. See numerous examples of such constructions elsewhere in the wiki.
}

{{block}
_h2 towers of hanoï

_p In the previous section we have built from scratch the {b IF} control structure, using lambdas to prevent unwanted evaluations before the boolean's result. Fortunately lambdacode comes with an {b if} builtin special form making recursion much more easier.

{pre
(def hanoi          
 (lambda (n from to via)
  (if (= n 0)
   '
   (join
    (hanoi (- n 1) from via to)
      '<{span}br>
      'move n 'from 'tower from 'to 'tower to 
    (hanoi (- n 1) via to from) ))))

(hanoi 6 'A 'B 'C)

}

{pre
{lc
(def hanoi          
 (lambda (n from to via)
  (if (= n 0)
   '
   (join
    (hanoi (- n 1) from via to)
      '<br>
      'move n 'from 'tower from 'to 'tower to 
    (hanoi (- n 1) via to from) 
))))

(hanoi 6 'A 'B 'C)

}}

}

{{block}
_h2 some maths

_p The lambdacode's dictionary contains a small set of math primitives we can play with.

_h3 hypotenuse

{pre
(sqrt (+ (* 3 3) (* 4 4)))
}

{pre
{lc
(sqrt (+ (* 3 3) (* 4 4))) 
}}

{pre
(def hypo 
 (lambda (a b)
  (sqrt (+ (* a a) (* b b))) 
))
'
(hypo 3 4)
}

{pre
{lc
(def hypo 
 (lambda (a b)
  (sqrt (+ (* a a) (* b b))) 
))
'
(hypo 3 4) 
}}

_h3 long factorial

{pre
(def fac 
 (lambda (n)
  (if (< n 1)
   1 
   (long_mult n (fac (- n 1))))))
'
(fac 100)
}

{prewrap
{lc
(def fac
 (lambda (n)
  (if (< n 1)
   1
   (long_mult n (fac (- n 1))) )))
'
(fac 100)
}}

_h3 triangle area

{pre
(def area
 (lambda (a b c)
  (let ( (s (/ (+ a b c) 2))
       ) (sqrt (* s (- s a)
                    (- s b) 
                    (- s c)))))) 
'
(area 3 4 5) 
}

{pre
{lc
(def area
 (lambda (a b c)
  (let ( (s (/ (+ a b c) 2))
       ) (sqrt (* s (- s a) (- s b) (- s c))))
    ))
'
(area 3 4 5)
}}

_h3 horner & newton

{pre
(def #.horner
 (lambda (:a :z)
  (#.horner.rec :a :z 0 0) )) 
'
(def #.horner.rec 
  (lambda (:a :z :q :p)
   (if (#.empty? :a)
    (#.new :p (/ :p :q))
    (#.horner.rec (#.rest :a)
                  :z 
                  (+ (* :z :q) :p)
                  (+ (* :z :p) (#.first :a))) ))) 
'
(def #.newton
 (lambda (:l :x)
  (let ( (:h (#.horner :l :x))
       ) (if (< (abs (#.first :h)) 1.0e-15)
         :x   
         (#.newton :l (- :x (#.last :h)))))))
'
(#.horner (#.new 1 -1 -1) 1.618033988749895)
'
(#.newton (#.new 1 -1 -1) 1) 
}

{pre
{lc 
(def #.horner
 (lambda (:a :z)
  (#.horner.rec :a :z 0 0) )) 
'
(def #.horner.rec 
  (lambda (:a :z :q :p)
   (if (#.empty? :a)
    (#.new :p (/ :p :q))
    (#.horner.rec (#.rest :a)
                  :z 
                  (+ (* :z :q) :p)
                  (+ (* :z :p) (#.first :a))) ))) 
'
(def #.newton
 (lambda (:l :x)
  (let ( (:h (#.horner :l :x))
       ) (if (< (abs (#.first :h)) 1.0e-15)
         :x   
         (#.newton :l (- :x (#.last :h)))))))
'
(#.horner (#.new 1 -1 -1) 1.618033988749895)
'
(#.newton (#.new 1 -1 -1) 1) 
}}

_p And so on ...
}

{{block}
_h2 graphics

_p lambdacode doesn't come with graphics primitives but lambdatalk can help.
_p Let's define a  parametrical curve {b y(t) = e{sup it} + {sup 1}/{sub 2}e{sup A*it} + {sup i}/{sub 3}e{sup B*it}},  compute values from 0 to 2π and plot it.

{pre
(def A (floor (* 10 (random))))
(def B (floor (* -5 (random))))

(def cyclic
 (lambda (t)
  (#.new
   (* 150 (+ (cos t)
             (* (/ 1 2) (cos (* A t)))        
             (* (/ 1 -3) (sin (* B t)))))    
   (* 150 (+ (sin t)
             (* (/ 1 2) (sin (* A t)))        
             (* (/ 1 3) (cos (* B t))))) )))

(def curve
 (#.map 
  (lambda (t)
   (let ( (point (cyclic t))
        ) (join (#.first point) 
                (#.last point)))) 
  (#.serie 0 (* 2 (PI)) 0.01))) 
}

{pre
{lc
;; (def deg2rad (/ (PI) 180))
(join (def A (floor (* 10 (random)))) '= A)
(join (def B (floor (* -5 (random)))) '= B)   
'
;; (def sinusoid (lambda (t) (* 100 (sin (* deg2rad  t)))))

(def cyclic
 (lambda (t)
  (#.new
  (* 150 (+ (cos t)
     (* (/ 1 2) (cos (* A t)))        
     (* (/ 1 -3) (sin (* B t)))))    
  (* 150 (+ (sin t)
     (* (/ 1 2) (sin (* A t)))        
     (* (/ 1 3) (cos (* B t))))) )))    
'
(def curve
 (#.map (lambda (t)
                (let ( (point (cyclic t))
                     ) (join (#.first point) (#.last point))
                     )
        ) (#.serie 0 (* 2 (PI)) 0.01))) 
}
}

_p Currently lambdacode has no graphical functionalities and the sequence of SVG formatted 2D points is sent to lambdatalk's SVG primitives

{pre
'{svg {@ width="780px" height="300px"} 
 {g {axes 780 300}
  {polyline 
   {@ points="{lc curve}" {stroke #f00 1} }}}} 
}

_p displaying

{svg {@ width="580px" height="580px" style=""} 
 {g {axes 580 580}
  {polyline        
   {@ points="{lc curve}" 
      {stroke #888 3} 
}}}}

}

{{block}
_h2 conclusion

_p Here is the list of primitives and user functions defined in this page.

{pre (lib) } 
{prewrap {lc (lib)} }

°°°
{def sinusoid {lambda {:t} :t {* 100 {sin {* {/ {PI} 180} :t}}}}}

{svg {@ width="780px" height="300px"} 
 {g {AXES 780 300}
  {polyline 
   {@ points="{S.map sinusoid {S.serie -180 180 1}}" 
      {stroke #f00 4} 
}}}}  
°°°

_h2 the {i magic} function

_p The whole evaluation is done in a single function, {b evaluate}, working on a single nested array built from the code string.

{pre °°
var evaluate = function (x, env) {
  env = env || LCDICT;
  if ( !isNaN(parseFloat(x)) && isFinite(x) ) {
    return x; 
  } else if ( typeof x === 'string' && x.charAt(0) === "'" ) {
    return x.slice(1);
  } else if ( typeof x === 'string' ) {
    return env.find(x)[x]; 
  } else if ( x[0] === '@' ) { 
    return x.slice(1).join(' ');                  
  } else if ( x[0] === 'if' ) {
    return evaluate( (evaluate( x[1], env)? x[2] : x[3]), env );
  } else if ( x[0] === 'lambda' ) {
    return function () {
      var new_env = create_env( x[1], arguments, env );
      return evaluate( x[2], new_env ); 
    }
  } else if ( x[0] === 'let' ) {
    var vv = x[1], body = x[2], vars = [], vals = [];
    for (var i=0; i < vv.length; i++) {
      vars.push( vv[i][0] );
      vals.push( evaluate(vv[i][1], env) );
    }
    var new_env = create_env( vars, vals, env );
    return evaluate( body, new_env ); 
  } else if ( x[0] === 'set!' ) {           // (set! var exp)
    env.find(x[1])[x[1]] = evaluate( x[2], env )
  } else if ( x[0] === 'def' ) {
    env[x[1]] = evaluate( x[2], env );
    return x[1];
  } else {
    for (var xx = [], i=0; i < x.length; i++)
      xx[i] = evaluate( x[i], env );
    var proc = xx.shift();
    return proc.apply(null, xx);
  }
};

°°}

_p And yes, it is a kind of magic. Thank you Lisp.

_p {i alain marty (2021/08/20)}

}

{{hide}

{def axes
 {lambda {:w :h}
  {@ transform="translate({/ :w 2},{/ :h 2}) scale(1,-1)"} 
  {line {@ x1="-{/ :w 2}:w" y1="0" 
           x2="{/ :w 2}" y2="0"
           stroke="red" fill="transparent"}}
  {line {@ x1="0" y1="-{/ :h 2}" 
           x2="0" y2="{/ :h 2}"
           stroke="green" fill="transparent"}} 
}}
 
{def stroke
 {lambda {:col :w}
 stroke=":col" fill="transparent" stroke-width=":w" }}

{def block div
 {@ style="display:inline-block;
           width:600px; padding:5px; margin:10px;
           text-align:left; vertical-align:top; 
           background:#444; color:#fff"}}
}

{style 
body { background:#444; } 
#page_frame { border:0; background:#444; color:#000; width:600px; margin-left:0; }
#page_content { background:#444; color:#fff; border:0; width:4500px; box-shadow:0 0 0; font-family:papyrus, optima; }
.page_menu { background:transparent; color:#fff; }
a { color:#f80; }
pre { box-shadow:0 0 8px #000; padding:5px; background:#444; color:#fff; font:normal 1.0em courier; }
b { color:cyan; }
h1 { font-size:4.0em; margin-left:0; color:#fff}
h2 { font-size:3.0em; }
h3 { font-size:2.0em; }
}

{script

//// 1) INTERFACE

//// 1.1) OUT OF LAMBDATALK

var LC_run = function() {
  var lcs = document.getElementsByClassName("LC");
  if (!lcs) return
  for (var key in lcs)
    lcs[key].innerHTML = LC.parser( lcs[key].innerHTML )
};

// setTimeout( LC_run, 1 );  // uncomment when used in a standard HTML file

//// 1.2) WITH LAMBDATALK

LAMBDATALK.DICT['lc'] = function() {
  return LC.parser( arguments[0] )
};

//// 2) THE KERNEL

var LC = (function () {

var parser = function ( str ) {
  var bal = balance( str );
  if (bal[0] === bal[1]) {
    str = '(console ' + str + ')'; // root
    str = tokenize( str );
    str = build_tree( str );
    str = evaluate( str );
  }
  return str
};

var tokenize = function ( s ) { 
  return s.replace(/\(/g, ' ( ')
          .replace(/\)/g, ' ) ')
          .trim()
          .split(/\s+/);        
};

var build_tree = function (tokens) {
  var token = tokens.shift();
  if (token !== '(') 
    return token;
  var arr = [];
  while (tokens[0] !== ')')
    arr.push( build_tree(tokens) );
    tokens.shift();
    return arr;
  };

var balance = function ( str ) {
  var acc_open = str.match( /\(/g );
  var acc_close = str.match( /\)/g );
  var nb_acc_open = (acc_open)?  acc_open.length : 0;
  var nb_acc_close = (acc_close)? acc_close.length : 0;
  return [nb_acc_open , nb_acc_close];  
};

var supertrim = function(s) {
    return s.trim().replace(/\s+/g, " ");
};
 
return { parser, create_env, supertrim }

}());

//// 3) POPULATING THE DICTIONARY

// a global LCDICT is created and populated outside the LC function

var LCDICT = LC.create_env([],[]);

LCDICT['lib'] = function() {
  var str = '', index = 0;
  for (var key in LCDICT) {
    if(LCDICT.hasOwnProperty(key)) { 
      str += key + ', '; index++; 
    }
  }
  return '<b>LCDICT: </b>('+ index+') [ '+ str.substring(0,str.length-2)+' ]<br />';
};

LCDICT['console'] = function(){
  return [].slice.call(arguments).join('\n')
}; 
LCDICT['join'] = function() {
  return [].slice.call(arguments).join(' ')
};
LCDICT['glue'] = function() {
  return [].slice.call(arguments).join('')
};

LCDICT['equal?'] = function(a, b){ return a === b };

//// MATHS

LCDICT['+'] = function () {
  for (var r=0, i=0; i < arguments.length; i++) { 
    r += Number( arguments[i] ) 
  }
  return r; 
};
LCDICT['*'] = function () {
  for (var r=1, i=0; i < arguments.length; i++) { 
    r *= arguments[i] 
  }
  return r;  
};
LCDICT['-'] = function () {
  var r = arguments[0];
  if (arguments.length === 1) { 
    r = -r;
  } else { 
    for (var i=1; i < arguments.length; i++) { 
      r -= arguments[i] 
    } 
  }
  return r; 
};
LCDICT['/'] = function () {
  var r = arguments[0];
  if (arguments.length === 1) {
    r = 1/r;
  } else { 
    for (var i=1; i < arguments.length; i++) { 
      r /= arguments[i] 
    } 
  }
  return r; 
};
LCDICT['%'] = function () {
  return parseFloat(arguments[0]) % parseFloat(arguments[1]) 
};

LCDICT['<']  = function(){
  return parseFloat(arguments[0]) < parseFloat(arguments[1]) 
};
LCDICT['>']  = function(){
  return parseFloat(arguments[0]) > parseFloat(arguments[1]) 
};
LCDICT['<=']  = function(){  
  return parseFloat(arguments[0]) <= parseFloat(arguments[1]) 
};

LCDICT['>=']  = function(){
  return parseFloat(arguments[0]) >= parseFloat(arguments[1]) 
};
LCDICT['=']  = function () {
  var a = parseFloat(arguments[0]), b = parseFloat(arguments[1]);  
  return !(a < b) && !(b < a) 
};
LCDICT['not'] = function () {
  return !arguments[0]
};
LCDICT['or'] = function () { 
  for (var i=0; i< arguments.length; i++) { if (arguments[i]) return true }
  return false; 
};
LCDICT['and'] = function () { 
  for (var i=0; i< arguments.length; i++) { if (arguments[i]) return false }
  return true; 
};

//// LONG INTEGER

LCDICT['long_add'] = function () {
  var a = arguments[0].split("").reverse(),
      b = arguments[1].split("").reverse(),
      n = Math.max(a.length, b.length), 
      c = [], 
      d = 0;
  for (var i=0; i < n; i++) {
    c[i] = (a[i] | 0) + (b[i] | 0) + d;
    if (c[i] > 9) {
      c[i] -= 10;
      d = 1;
    } else {
      d = 0;
    }
  } 
  if (d === 1) c.push(1);
  return c.reverse().join('') 
};

LCDICT['long_mult'] = function () {
  var a = arguments[0]; 
  var b = arguments[1];

a = (Array.isArray(a)) ? a.split("").reverse() : [a].reverse();  // ???
  b =  b.split("").reverse();
  
  var c = [];
  for ( var i1 = 0; i1 < a.length; i1++ ) {
    for ( var i2 = 0; i2 < b.length; i2++ ) {
      var j = i1 + i2;
      c[j] = a[i1] * b[i2] + (c[j] | 0);
      if ( c[j] > 9 ) { 
        var f = Math.floor( c[j] / 10 );
        c[j] -= f * 10;
        c[j+1] = f + (c[j+1] | 0);
      }
    }   
  }
  return c.reverse().join("")
};

//// ARRAYS

LCDICT['#.new'] = function() {
  return [].slice.call(arguments)
};
LCDICT['#.array?'] = function() {
  return Array.isArray( arguments[0] )
};
LCDICT['#.disp'] = function() {
  var args = arguments[0];
  return ( Array.isArray( args ) )? JSON.stringify( args ) : args
};
LCDICT['#.length'] = function() {
  return arguments[0].length
};
LCDICT['#.empty?'] = function() {
  return arguments[0].length === 0
};
LCDICT['#.first'] = function() {
  var args = arguments[0];
  return (Array.isArray( args ))? args[0] : args 
};
LCDICT['#.last'] = function() {
  var args = arguments[0];
  return (Array.isArray( args ))? args[args.length-1] : args 
};
LCDICT['#.rest'] = function() {
  var args = arguments[0];
  return (Array.isArray( args ))? args.slice(1) : args 
};
LCDICT['#.get'] = function() {  // (#.get i a)
  var val = arguments[1][arguments[0]];
  return (val !== undefined)? val : 'undefined'        
};
LCDICT['#.slice'] = function() { // (#.slice i1 i2 a)
  return arguments[2].slice(arguments[0],arguments[1])
};
LCDICT['#.concat'] = function() {
  return arguments[0].concat( arguments[1] )
};
LCDICT['#.reverse'] = function() {
  return arguments[0].reverse()
};
LCDICT['#.sort'] = function() {
  return (arguments[1] === 'up')? 
    arguments[0].sort( function(a,b) { return a - b } ) :
    arguments[0].sort( function(a,b) { return b - a } )
};
LCDICT['#.set!'] = function() {  // (#.set! i v a)
  arguments[2][arguments[0]] = arguments[1]
  return arguments[2]
};
LCDICT['#.pop!'] = function() {
  return arguments[0].pop()
};
LCDICT['#.shift!'] = function() {
  return arguments[0].shift()
};
LCDICT['#.push!'] = function() {  // (#.push! v a)
  arguments[1].push( arguments[0] )
  return arguments[1];
};
LCDICT['#.unshift!'] = function() {  // (#.unshift! v a)
  arguments[1].unshift( arguments[a] )
  return arguments[0];
};

LCDICT['#.map'] = function () { // (#.map func arr)
  var f = arguments[0], 
      a = arguments[1],
      b = [];
    for (var i=0; i< a.length; i++) 
        b.push( f.call( null, a[i] ) )      
  return  b
};

LCDICT['#.serie'] = function() {
  var a = parseFloat( arguments[0]),
      b = parseFloat( arguments[1]),
      c = parseFloat( arguments[2]),
      d = [];
  for (var i=a; i<=b; i+=c)
    d.push(i)
  return d
};

//// AND SO ON ...
}