workshop

user:anonymous

{blockquote {center {b (lambda code)} can be tested out of the wiki, [[console|data/lambdacode]], or in the wiki, [[lambdacode_inside]].
{br}
A reduced lambda-calculus style version to see in [[lambdacode_inside_min]]
{br}
See a [[single dictionary|?view=eval]] version where words are not evaluated, as it is in lambdatalk.
}}

{hr}

{img {@ src="data/lambdacode_splashscreen.jpg" width="100%"
  title="Copyscreen of the console."}}

_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 (lambda code)} is my (last) translation of the Peter Norvig's LISP engine, replacing pairs and lists by arrays and adding strings and HTML/CSS capabilities.

_h3 introducing the syntax

{pre {WRAP}
A lambdacode {code expression} is made of {b words} and {b nested forms}, {code (expression1 expression2)}, translated into an abstract syntax tree, a nested array, which is recursively evaluated to words.}

_p For instance:

{pre
{b (+ 1 (* 2 3) 4)}                // a nested form as input 
-> ["+","1",["*","2","3"],"4"] // translated into a nested array
-> {b 11}                          // recursively to a word
}

_h5 1) words

{pre {WRAP}
- {b words} are made of any characters except {code spaces} and {code ()},
- {b numbers} are special words made of digits, ie {code 123, 3.1416, 1.0e10}, and are evaluated to themselves,
- {b other words} are evaluated as references to built-in primitives defined in the initial {b dictionary}, ie. {code +, -, *, /, ..., sqrt, ...}, or user defined functions added to the dictionary, ie. {code myadd, fac, ...}. A word which is not such a reference {b must} be quoted, {code 'word -> word}.
}

_h5 2) nested forms
_p Basically forms are evaluated {b eagerly}.

{pre {WRAP}
{code (expression1 expression2)} evaluates {code expression1} to a function's reference and {b recursively} evaluates {code expression2} to words on which the function is finally applied.
}

_h5 3) special forms
_p There are a few edge cases for which expression2 cannot or must not be evaluated. Those special forms are evaluated {b lazily}.

{pre {WRAP}
- {code (lambda (arguments) body)} creates an anonymous function coming with a local environment built on {code arguments}, which will receive values when the function is called and in which {code body} will be evaluated,
- {code (def name body)} evaluates {code body} and adds {code name} to the dictionary,
- {code (if bool one two)} evaluates and returns {code one} if {code bool} is true else {code two},
- {code (@ any expression)} returns {b any expression} unevaluated ; use the built-in primitive {code (join ...)} when some part of {code any expression} has to be evaluated,
- {code (quote (+ 1 2)} or {code '(+ 1 2)} returns {b (+ 1 2)} unevaluated.
}

_h5 4) dictionary

{pre {WRAP}
DICT: (116) [ 
{b various}
find, lib, glue, join,
{b MATHS} built on Javscript operators and functions
+, *, -, /, %, <, >, <=, >=, =, not, or, and, equal?,
abs, acos, asin, atan, atan2, ceil, cos, exp, floor, log, max, min, pow, random, round, sin, sqrt, tan, PI, E, 
{b ARRAYS} built on the Javascript Array object and methods
#.new, #.array?, #.disp, #.length, #.first, #.last, #.rest, #.get, #.slice, #.concat, #.reverse, #.sort, #.set!, #.pop!, #.shift!, #.push!, #.unshift!, 
{b HTML} a subset built on HTML/CSS tags and rules
div, span, a, ul, ol, li, dl, dt, dd, table, tr, td, h1, h2, h3, h4, h5, h6, p, b, i, u, center, hr, br, blockquote, sup, sub, del, code, img, pre, textarea, canvas, audio, video, source, select, option, object, 
{b SVG} a subset built on SVG functions
svg, line, rect, circle, ellipse, polygon, polyline, path, text, g, mpath, use, textPath, pattern, image, clipPath, defs, animate, set, animateMotion, animateTransform
{b MORE} ... to come!
]
}

_p Note that there are neither [{code cons,car,cdr}] nor list structures, nothing but {code arrays} built on the flexible and powerful Javascript's Array object. Adding a small set of Lisp-like functions, [{code first, rest}], allows using arrays in a similar way pairs, lists and trees are used in Lisp and its dialects. Lambdacode is purely functional, no {code set!} function, but arrays can be mutated inside functions via a {code #.set!} function.

_h3 a quick look

_p Playing with words, styles, numbers, functions:

{pre
'Hello 'World
-> Hello World

(@ Hello World)
-> Hello World

(span (@ style="color:red;) (@ Hello World))
-> {span {@ style="color:red;"} Hello World}

(+ 1 (* 2 3) 4)
-> {+ 1 {* 2 3} 4}
'(+ 1 (* 2 3) 4)
-> (+ 1 (* 2 3) 4)

(def add (lambda (a b) (+ a b)))
-> add
(add 3 4)
-> 7

'and 'so 'on
-> and so on
}

_p Note how words must be quoted to avoid any undesired evaluation. See [[https://people.eecs.berkeley.edu/~bh/pdf/ssch01.pdf|https://people.eecs.berkeley.edu/~bh/pdf/ssch01.pdf]] for something similar in Scheme. It's interesting to compare lambdacode and lambdatalk, the language used to write this current page.

_h3 lambdacode or lambdatalk?

_p In lambdatalk we would write the previous examples like this:

{pre
Hello World
-> Hello World
'{span {@ style="color:red;"} Hello World}
-> {span {@ style="color:red;"} Hello World}

'{+ 1 {* 2 3} 4}
-> {+ 1 {* 2 3} 4}
''{+ 1 {* 2 3} 4}
-> '{+ 1 {* 2 3} 4}

'{def add {lambda {:a :b} {+ :a :b}}}
-> add
'{add 3 4}
-> 7

and so on
-> and so on
}

_p In {b lambdatalk} words are {i de facto} not evaluated, {code Hello World} displays {b Hello World}. In {b lambdacode} words must be quoted to be prevented from evaluation, {code 'Hello 'World} or {code (@ Hello World)}. Any unquoted word is considered as a primitive or a user function's reference and leads to an error - simply locking the evaluation - if it's not the case.

_p {b This behaviour is not exactly a good thing in a wiki context} where simple text is 95% of the input. '{lambda talk} was created to {b invert} the process. In '{lambda talk} any text can be written as easily as in standard text and spreadsheet editors. And when some expression must be evaluated it has to be composed with curly braces, ie. {code 1+2} displays as {b 1+2} and {code '{+ 1 2}} is evaluated to {b 3}. Remember that in a spreadsheet writing {code 1+2} simply displays as {b 1+2}, you must write {code =1+2} to get {b 3}. Any different behaviour would have been painful!

_p As another comparison, this is how we define a block in lambdacode:

{pre
(def block 
 (lambda (bak col siz font txt)
  (div (join 'style=" 'text-align:center ';
                      'background: bak '; 
                      'color: col '; 
                      'font:normal siz font '; '") txt)))

(block 'black 'white '3.0em 'georgia (@ Hello World))
}

_p and the same in lambdatalk:

{pre
'{def block 
 {lambda {:bak :col :siz :font :txt}
  {div {@ style="text-align:center;
                 background: :bak; 
                 color: :col; 
                 font:normal :siz :font;"} {:txt}}}}
-> {def block 
 {lambda {:bak :col :siz :font :txt}
  {div {@ style="text-align:center;
                 background: :bak; 
                 color: :col; 
                 font:normal :siz :font;"} {:txt}}}}

'{block black white 3.0em georgia {def HI Hello World}}
}

_p everyone displaying:

{block black white 3.0em georgia
 {def HI Hello World}}

_p '{lambda talk} is introduced in [[quick_intro]] (fr|en), [[oxford_slides]], [[factory]], [[NIL]] and other pages in the lambdaway [[workshop|../]].

_h3 code

_p The code can be seen in  [[lambdacode.js|data/lambdacode/lambdacode.js]].

_p For instance {code (+ 1 (* 2 3) 4)} is first transformed into a nested array {code ["+","1",["*","2","3"],"4"]}, then recursively evaluated by this single function: 
{pre °°
var evaluate = function (x, env) {
  env = env || dict;                     // default is dict
  if ( isNumber(x) ) {                   // a number
    return x;                            // is evaluated to itself
  } else if ( isWord(x) ) {              // a quoted word 'Hello
    return x.substring(1);               // is evaluated to iteself Hello 
  } else if ( isOp(x) ) {                // any other word must be a reference
    return env.find(x)[x];               // to a function in the chain of environments 
  } else if ( x[0] === 'quote' ) {       // either '(+ 1 2) or (quote (+ 1 2))
    return array2string( x.slice(1) );   // -> (+ 1 2)
  } else if ( x[0] === '@' ) {           // (@ any words) 
    return x.slice(1).join(' ');         // returns any words unevaluated                  
  } else if ( x[0] === 'if' ) {          // (if bool one two)
    return evaluate(                     // evaluates
              (evaluate( x[1], env)?     // if bool is true 
                 x[2] :                  // then one
                 x[3]), env );           // else two
  } else if ( x[0] === 'lambda' ) {      // (lambda (args) body)
    return function () {                 // creates a new environment
      var new_env = create_env( x[1], arguments, env );  // with arguments
      return evaluate( x[2], new_env );  // in which body is evaluated
    }
  } else if ( x[0] === 'def' ) {         // (def name body)
    env[x[1]] = evaluate( x[2], env );   // evaluates body and add name to dict
    return x[1];                         // optional
  } else {                               // (+ 1 (* 2 3) 4)
    for (var xx = [], i=0; i < x.length; i++)
      xx[i] = evaluate( x[i], env ); // evaluates + 1 * 2 3 4
    var proc = xx.shift();               // + and * are functions
    return proc.apply(null, xx);         // applied to given values 1 2 3 4
  }
};
°°}

_p which does all the work and returns {b 11}.

_p This function could be rewritten

{pre °°
var evaluate = function (x, env) {
  env = env || dict;
  if ( isNumber(x) )            return eval_number(x)
  else if ( isWord(x) )         return eval_word(x)
  else if ( isOp(x) )           return eval_op(x)
  else if ( x[0] === 'quote' )  return eval_quote(x)
  else if ( x[0] === '@' )      return eval_@(x)
  else if ( x[0] === 'if' )     return eval_if(x)
  else if ( x[0] === 'lambda' ) return eval_lambda(x)
  else if ( x[0] === 'def' )    return eval_def(x)
  else                          return eval_apply(x)
};
°°}

_p with appropriate sub functions.

_h3 examples

_p Copy/paste the following examples in the lambdacode's console to see results

{pre {WRAP}

{h3 HTML}

'hello 'world
(b (join 'hello 'world))
(b (@ hello world))

(def STYLE (@ style="font:bold 4em georgia; color:red;"))
(def HI (@ Hello World))
(div STYLE HI)

(center
 (img
  (@ src="data/dancing_minions.gif"
     width="100%"
     title="Dancing Minions") 
  (div (@ style="font:bold 3.0em Georgia;") (@ Dancing Minions))
 )
)

(div 
 (@ style="background:#822; 
           color:white; 
           white-space:pre-wrap; 
           padding:10px;")
(@ Welcome in the '{lambda way} project, a workshop built on a wiki, '{lambda tank}, coming with a true functional programming language, '{lambda talk}. Fly over the top-left menu [1 2 3 4 5 6] to visit its content, a 360° exploration of its functionalities. It's a work in progress and, please, your opinion is welcome in the page forum.   
))

(def block 
 (lambda (bak col siz font txt)
  (div (join 'style=" 'text-align:center ';
                      'background: bak '; 
                      'color: col '; 
                      'font:normal siz font ';
             '") txt)))

(block 'black 'white '3.0em 'georgia
 (@ Hello World))
(block 'yellow 'blue '2.0em 'papyrus 
 (@ Amélie Poulain is a nice doll!))

{h3 numbers}

'(+ 1 (* 2 3) 4) '-> (+ 1 (* 2 3) 4)
'(= 1 1) '-> (= 1 1)
'(= 1 2) '-> (= 1 2)

'((lambda (x y) (+ x y)) 1 2) 
'-> ((lambda (x y) (+ x y)) 1 2)

(def add (lambda (x y) (+ x y)))
'(add 2 3) 
'-> (add 2 3)

(def fac
 (lambda (n)
  (if (= n 0)
   1
   (* n (fac (- n 1))))))

'(fac 15) 
'-> (fac 15)

{h3 arrays}

(def A (#.new 12 34 56 78 90))
(#.disp A)
(#.get A 0)
(#.get A 1)
(#.get A 2)
(#.get A 3)
(#.get A 4)
(#.get A 5)

(#.slice A 1 3)
(#.reverse A)
(def B (#.new 3 1 -1 10 11 0))
(#.sort B 'up)
(def C (#.new 3 1 -1 10 11 0)) (#.disp C)
(#.sort C 'down)
(#.concat (#.new 12 34) (#.new 56 78))
'===  
(def D (#.new 12 34 56 78)) (#.disp D)
(#.pop! D)   (#.disp D)
(#.shift! D)   (#.disp D)
(#.push! D 'yes)   (#.disp D)
(#.unshift! D 'no)   (#.disp D)
(#.set! D 1 90)  (#.disp D)

(def display
 (lambda (arr)
  (if (#.empty? arr)
      (b ')
      (join (#.first arr)
            (display (#.rest arr))))))

(def mylength
 (lambda (arr)
  (if (#.empty? arr)
      0
      (+ 1 (mylength (#.rest arr))))))

(def squared
 (lambda (arr)
  (if (#.empty? arr)
      0 
      (join (* (#.first arr) (#.first arr))
            (squared (#.rest arr))))))

(display A) 
(mylength A)
(squared A)

{h3 newton horner}

(def newton 
  (lambda (i x)
    (if (< i 1) 
     1 
     (/ (+ (newton (- i 1) x)
           (/ x (newton (- i 1) x)))
        2))))

(b (@ 1. √2))
(sqrt 2)
(newton 7 2)

(b (@ 2. golden ratio))
(/ (+ 1 (sqrt 5)) 2)
(/ (+ 1 (newton 7 5)) 2)

(def horner
  (lambda (:l :x)
   (horner.rec :l :x 0 0)))
(def horner.rec 
 (lambda (:l :x :q :p)
   (if (= (#.length :l) 0)
     (#.new :p (/ :p :q))
     (horner.rec (#.rest :l) :x 
                   (+ (* :x :q) :p)
                   (+ (* :x :p) (#.first :l))))))

(p (@ Note that the horner function returns the pair [f(x),f(x)/f'(x)]. The first term will be used to evaluate f(x) for a given value x. For instance:))

(#.first (horner (#.new 9 8 7 6 5 4 3 2 1) 10))
'-> 987654321 (@ as expected!)

{h3 SVG}

(def svgPt (lambda (p) (join (#.get p 0) (#.get p 1))))

(def p0 (#.new 10 10))
(def p1 (#.new 100 190))
(def p2 (#.new 100 10))
(def p3 (#.new 590 10))

(svg (@ width="100%" height="200px" style="background:#ccc;")

(join
(polyline
 (join 'points=" (svgPt p0) (svgPt p1) (svgPt p2) (svgPt p3) '" 
  'stroke-width="1" 'stroke="#888" 'fill="transparent") '.)

(path 
 (join 'd=" 'M (svgPt p0) 'C (svgPt p1) (svgPt p2) (svgPt p3) '" 
  'stroke-width="2" 'stroke="#f00" 'fill="transparent") '.))
)

{h3 pairs and lists with lambdas}

(def PAIR (lambda (x y) (lambda (z) (z x y))))
(def LEFT (lambda (z) (z (lambda (x y) x))))
(def RIGHT (lambda (z) (z (lambda (x y) y))))
(LEFT (PAIR 'yes 'no))
(RIGHT (PAIR 'yes 'no))
'---
(def YN (PAIR 'yes 'no))
(LEFT YN)
(RIGHT YN)
'---
(def NIL (lambda (s z) z))
(def ISNIL (lambda (n) (n (lambda (x) RIGHT) LEFT)))
'---
((ISNIL NIL) YN)
((ISNIL FRUITS) YN)
'---
(def FRUITS
 (PAIR 'apple
  (PAIR 'banana
   (PAIR 'lemon
    (PAIR 'grapes
     (PAIR 'orange NIL))))))
'---
((ISNIL (RIGHT FRUITS)) YN)
((ISNIL (RIGHT (RIGHT FRUITS))) YN)
((ISNIL (RIGHT (RIGHT (RIGHT FRUITS)))) YN)
((ISNIL (RIGHT (RIGHT (RIGHT (RIGHT FRUITS))))) YN)
((ISNIL (RIGHT (RIGHT (RIGHT (RIGHT (RIGHT FRUITS)))))) YN)
'---
(def LIST.DISP
 (lambda (list)
  (((ISNIL list)
   (PAIR
    (lambda (list) '.)
    (lambda (list) (join (LEFT list) (LIST.DISP (RIGHT list)) ) 
   ))) list)))

(LIST.DISP FRUITS)

}

_h3 speed

_p The naïve version of the fibonacci function is often used for testing the evaluation's speed of a language.

{pre
1) lambdatalk        // {b can be tested in this page unquoting '{fibo 10}}
'{def fibo  
 {lambda {:n} 
  {if {< :n 3}
   then 1
   else {+ {fibo {- :n 1}} {fibo {- :n 2}} } }}}
-> {def fibo  
 {lambda {:n} 
  {if {< :n 3}
   then 1
   else {+ {fibo {- :n 1}} {fibo {- :n 2}} } }}}

'{fibo 10}
-> 55

2) lambdacode                             // {b can be tested in [[console|data/lambdacode]]}
(def fibo
 (lambda (n)
  (if (< n 3)
   1
   (+ (fibo (- n 1)) (fibo (- n 2)) ) )))

(fibo 10)
}

_p Here is a comparizon between lambdatalk and lambdacode on a recent MacBook Pro.

{table {@ style="text-align:center"}
 {tr {td {b n}} {td {b lambdatalk}} {td {b lambdacode}}}
 {tr {td 10} {td 1ms} {td 3ms}}
 {tr {td 20} {td 80ms} {td 120ms}}
 {tr {td 30} {td 8 000ms} {td 17 400ms}}
 {tr {td 35} {td 100 000ms} {td 186 500ms}}
}

_p {b Lambdacode is about twice slower than lambdatalk}. It's an unexpected result! Should be tested with other algorithms. Meanwhile, it looks like if implementing an evaluator on regular expressions - considered as {b ugly} by purists - could be more effective than the standard and so smart {b eval( build_AST( tokenize( str )))} process? with nested environments, closures and so on.

_p Something wrong in my implementation? But testing on the [[insertion_sort]] algorithm, lambdacode is 2 times faster than lambdatalk.

{pre
(def array.sort
 (lambda (a)
  (array.sort.rec a (#.new)) ))

(def array.sort.rec 
 (lambda (a1 a2)
  (if (#.empty? a1)
      a2 
      (array.sort.rec (#.rest a1)
                      (array.sort.insert a2 (#.first a1))) )))

(def array.sort.insert 
 (lambda (a x)
  (if (#.empty? a)
      (#.new x)
      (if (<= x (#.first a))
          (#.unshift! a x)
          (#.unshift! (array.sort.insert (#.rest a) x)  
                      (#.first :a)) ))))

(def array.random
 (lambda (n)
  (array.random.rec (#.new) n)))
(def array.random.rec
 (lambda (a n)
  (if (< n 0)
      a
      (array.random.rec (#.push! a (floor (* 1.e5 (random))))
                        (- n 1)) )))

'=======
(div (@ style="word-wrap: break-word;") 
(join
 (def A (array.random 100))
(br)'-> (#.disp A)
(br)'->
 (#.disp (array.sort A))
))
}

{pre {WRAP}
array.sort
array.sort.rec
array.sort.insert
array.random
array.random.rec
=======
A 
 -> [65256,99527,62322,32301,8778,88436,1928,95993,15620,84364,61488,26927,97178,59817,5605,51278,47230,92592,48001,62361,20870,94010,57525,93522,10378,8319,1270,45403,55721,13748,48755,47440,43344,8739,93220,15074,34709,36052,52775,84541,24037,2810,82407,50329,52906,85909,63484,34831,65436,88812,50543,56936,14294,66159,65158,94339,99515,53423,88393,72974,34638,40605,78431,13500,9550,54056,80639,15010,84585,9048,18079,31459,90630,58286,297,77858,70558,48080,54957,8484,19502,2413,20415,74342,93013,37655,40148,72205,4663,96727,74802,57955,87082,57948,48967,80266,19218,88299,94917,9295,87003] 
 -> [297,1270,1928,2413,2810,4663,5605,8319,8484,8739,8778,9048,9295,9550,10378,13500,13748,14294,15010,15074,15620,18079,19218,19502,20415,20870,24037,26927,31459,32301,34638,34709,34831,36052,37655,40148,40605,43344,45403,47230,47440,48001,48080,48755,48967,50329,50543,51278,52775,52906,53423,54056,54957,55721,56936,57525,57948,57955,58286,59817,61488,62322,62361,63484,65158,65256,65436,66159,70558,72205,72974,74342,74802,77858,78431,80266,80639,82407,84364,84541,84585,85909,87003,87082,88299,88393,88436,88812,90630,92592,93013,93220,93522,94010,94339,94917,95993,96727,97178,99515,99527]
}

_p More to come ... it's a work in progress. Your opinion is welcome in the [[forum]] page.

_p Alain Marty | 2017/11/21

{{hide}

{def WRAP {@ style="white-space:pre-wrap; word-wrap: break-word;"}}

}

{style 
code { font:bold 1.0em courier; color:#800; }
}