workshop

user:anonymous

_img data/chevaux.jpg

_h1 towards λ-calculus

{center ( {i See full version in [[lambdacode]] and also [[NIL2]] and [[helloworld]].} ){br}( See comments in [[HN|https://news.ycombinator.com/item?id=16970131]]  )}

_p When reading papers on the {b λ-calculus}, for instance [[A Tutorial Introduction to the Lambda Calculus|http://www.inf.fu-berlin.de/lehre/WS03/alpi/lambda.pdf]] by Raul Rojas, one can be quickly lost in the clutter of expressions and the way recursion is introduced, using UFOs like Y-combinators. {i At least that's my case!} So in this wiki page I write in 60 lines my own implementation of a pure λ-calculus evaluator built on expressions made of [{b words, applications, abstractions}] using an S-expression based syntax

{pre
expression    := 
|        word := [^\s()]*
| application := (expression1 expression2) 
| abstraction := (lambda (words) expression)
}

_p In order to understand what can be done with so little, we focuse on a single example creating and displaying a list, {b FRUITS}, using nothing but {b lambdas} - and a single primitive, {b join}, leading to an expression in a pure λ-calculus style.

{pre {@ style="white-space:pre-wrap"}
((lambda (f n) (f f n)) (lambda (f list) ((((lambda (n) (n (lambda (x) (lambda (z) (z (lambda (x y) y)))) (lambda (z) (z (lambda (x y) x))))) list) ((lambda (x y) (lambda (z) (z x y))) (lambda (list) '.) (lambda (list) (join ((lambda (z) (z (lambda (x y) x))) list) (f f ((lambda (z) (z (lambda (x y) y))) list)) )))) list)) ((lambda (x y) (lambda (z) (z x y))) 'apple ((lambda (x y) (lambda (z) (z x y))) 'banana ((lambda (x y) (lambda (z) (z x y))) 'lemon ((lambda (x y) (lambda (z) (z x y))) 'grapes ((lambda (x y) (lambda (z) (z x y))) 'orange (lambda (s z) z)))))))
-> apple banana lemon grapes orange .
}

_p This {b unreadable} expression - to be compared with the lambdatalk version, [[NIL]] or [[helloworld]] - is the result of a progressive construction using the {b lambda} special form and, temporarily, a second one, {b def}. So, in the input frame below, we define successively

_ul {b 1.} the {b pair} data structure, [{b PAIR LEFT RIGHT}]
_ul {b 2.} the {b list} data structure, {b FRUITS}, with an ending word, {b NIL}
_ul {b 3.} a control structure using {b recursion}. A recursive function calls itself in its body until some condition is reached. Here this condition is called {b NIL} and the predicate function is {b ISNIL}.
_ul {b 4.} the {b LIST.DISP} function displays the elements of {b FRUITS}
_ul {b 5.} in order to discard the {b def} special form, we define a {b Y-combinator} function and an almost-recursive function, {b ALMOST}
_ul {b 6.} we replace {b Y} and {b ALMOST} by their lambda definitions, creating an anonymous function immediatelly called on a value, {b FRUITS}
_ul {b 7.} and we replace {b FRUITS} by its lambda definition.

_p Note that words, ie {b 'banana, '---}, must be quoted to be protected from evaluation.

_h3 1. input

_p {b The frame below is editable}. Test under your responsability. Some help can be seen in [[lambdacode]].

{textarea
 {@ id="input"
    style="width:99%; height:950px;
           background:#eee; color:#000;
           box-shadow:0 0 8px #000;
           font:normal 1.0em courier"
    onkeyup="display()"}

(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))))
'---
(def AP (PAIR 'Amélie 'Poulain))
(LEFT AP)
(RIGHT AP)
'---
(def NIL (lambda (s z) z))
(def ISNIL (lambda (n) (n (lambda (x) RIGHT) LEFT))) 
'---
(def FRUITS
 (PAIR 'apple
  (PAIR 'banana
   (PAIR 'lemon
    (PAIR 'grapes
     (PAIR 'orange NIL))))))
'---
(def LIST.DISP
 (lambda (list)
  (((ISNIL list)
   (PAIR
    (lambda (list) '.)
    (lambda (list) (join (LEFT list)
                         (LIST.DISP (RIGHT list)) ) 
   ))) list)))
(LIST.DISP FRUITS)
'---
(def Y (lambda (f n) (f f n)))
(def ALMOST
 (lambda (f list)
  (((ISNIL list)
   (PAIR
    (lambda (list) '.)
    (lambda (list) (join (LEFT list) (f f (RIGHT list)) ) 
   ))) list)))
(Y ALMOST FRUITS)
'---
((lambda (f n) (f f n)) 
 (lambda (f list)
  (((ISNIL list)
   (PAIR
    (lambda (list) '.)
    (lambda (list) (join (LEFT list) (f f (RIGHT list)) ) 
   ))) list)) FRUITS)
'---
((lambda (f n) (f f n)) (lambda (f list) ((((lambda (n) (n (lambda (x) (lambda (z) (z (lambda (x y) y)))) (lambda (z) (z (lambda (x y) x))))) list) ((lambda (x y) (lambda (z) (z x y))) (lambda (list) '.) (lambda (list) (join ((lambda (z) (z (lambda (x y) x))) list) (f f ((lambda (z) (z (lambda (x y) y))) list)) )))) list)) ((lambda (x y) (lambda (z) (z x y))) 'apple ((lambda (x y) (lambda (z) (z x y))) 'banana ((lambda (x y) (lambda (z) (z x y))) 'lemon ((lambda (x y) (lambda (z) (z x y))) 'grapes ((lambda (x y) (lambda (z) (z x y))) 'orange (lambda (s z) z)))))))

}

{center {@ id="infos"}}

_p Note how lambdas introduce a "zest" of {b lazyness} in an applicative order (call by value) evaluation. Depending on list, {b ISNIL} returns {b LEFT} or {b RIGHT} and selects the first or the second term of {b PAIR}, anstracted from evaluation. Then the selected lambda is applied on list, triggering the evaluation.

_h3 2. output

{pre
 {@ id="output"
    style="background:#eee; white-space:pre-wrap;
           font:bold 1.0em verdana"}}

_h3 3. code

_p The code below - in 60 lines out of comments - is the minimum required for the evaluation of the last expression made of words and lambdas.

{pre °°
1. EVALUATION

// 2. ASSOCIATE FUNCTIONS

// 3. DICTIONARY

_p Note in {b eval_apply()} the applicative order of recursive evaluations and in {b create_env} how closures are built via nested environments. To be compared with '{lambda talk} which evaluates also in an applicative order, via regexps working repeatidely from inside out, but doesn't use environments, and so doesn't use closures but partial applications.

_h4 conclusion

_p We have seen that adding a second special form {b def} brings to coding a little bit of humanity. Adding a third special form {b (if bool one two)} would help writing more readable recursive functions. With 5 special forms, [{b lambda def if quote @}], and more than a hundred primitives we get a true programmable programming language working in any modern web browsers, see [[lambdacode]].

_p {b Still here?} Copy the code below, paste it in [[encryption3]] and think over!

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

_img data/brussels/turing_machine.png

_p {i Alain Marty 2018/05/01}

{script

var display = function() {
  var input = getId('input').value;
  var code = LAMBDACODE.parser( input );
  getId('infos').innerHTML = 
       '(' + code.bal[0] + '|' + code.bal[1] + 
            ') [' + code.time + ' ms]';         
  if ( code.bal[0] === code.bal[1] ) 
    getId('output').innerHTML = code.val;
};

setTimeout(display,1)

var LAMBDACODE = (function () {

////
var create_env = function (args,vals,out) {
  var env = {}, outer = out || {};
  if (args.length !== 0)
    for (var i=0; i < args.length; i++)
      env[args[i]] = vals[i];
  env.find = function (op) {
    return (env.hasOwnProperty(op))? env : outer.find(op)
  };
  return env;
}
var dict = create_env([],[]);

//// populating the dictionary inside

dict['lib'] = function() {
  var str = '', index = 0;
  for (var key in LAMBDACODE.dict) {
    if(LAMBDACODE.dict.hasOwnProperty(key)) { 
      str += key + ', '; index++; 
    }
  }
  return 'DICT: ('+ index + ') [ '+ str.substring(0,str.length-2) + ' ]';
};
dict['glue'] = function(){
  return [].slice.call(arguments).join('\n')
}; 
dict['join'] = function() {
  return [].slice.call(arguments).join(' ')
};

//// other primitives are defined outside

return { dict:dict, parser:parser }

}());

//// the dictionary extended

//// maths
LAMBDACODE.dict['+'] = function () {
  for (var r=0, i=0; i < arguments.length; i++) { 
    r += Number( arguments[i] ) 
  }
  return r; 
};
LAMBDACODE.dict['*'] = function () {
  for (var r=1, i=0; i < arguments.length; i++) { 
    r *= arguments[i] 
  }
  return r;  
};
LAMBDACODE.dict['-'] = 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; 
};
LAMBDACODE.dict['/'] = 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; 
};
LAMBDACODE.dict['%'] = function () {
  return parseFloat(arguments[0]) % parseFloat(arguments[1]) 
};

LAMBDACODE.dict['<']  = function(){
  return parseFloat(arguments[0]) < parseFloat(arguments[1]) 
};
LAMBDACODE.dict['>']  = function(){
  return parseFloat(arguments[0]) > parseFloat(arguments[1]) 
};
/*
// not to be used in the wiki context where <= is broken
LAMBDACODE.dict['<=']  = function(){  
  return parseFloat(arguments[0]) <= parseFloat(arguments[1]) 
};
*/
LAMBDACODE.dict['>=']  = function(){
  return parseFloat(arguments[0]) >= parseFloat(arguments[1]) 
};
LAMBDACODE.dict['=']  = function () {
  var a = parseFloat(arguments[0]), b = parseFloat(arguments[1]);  
  return !(a < b) && !(b < a) 
};
LAMBDACODE.dict['not'] = function () {
return !arguments[0]
};
LAMBDACODE.dict['or'] = function () { 
  for (var i=0; i< arguments.length; i++) { if (arguments[i]) return true }
  return false; 
};
LAMBDACODE.dict['and'] = function () { 
  for (var i=0; i< arguments.length; i++) { if (arguments[i]) return false }
  return true; 
};
LAMBDACODE.dict['equal?'] = function(a, b){ return a === b };

//// arrays

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

//// HTML

}

{style

@import url(https://fonts.googleapis.com/css?family=Quicksand);

#page_view { font-family: Quicksand;}

b, pre { font:bold 1.0em courier new; color:#400; }

}