lambdaway :: meta3

3 | list | login |load

| |

_h2 [[meta]] | [[meta2]] | meta3 | [[meta4]] | [[meta5]]

{require lib_uncover}
{uncover data/simplet.jpg 300 1000 As simple as that!}

_h1 (meta talk) {sup {sup see a short version in [[meta4]]}}

_p As an aside of the {i lengthy} [[fromroots2canopy]] page, we are going to build from scratch the foundations of a functional language, {b metatalk}, embedded in this wiki page via a single {code eval} lambdatalk function:

{pre {center '{eval metatalk expression} -> words}}
 
_h2 1) syntax

_p A {b metatalk} expression is defined as follows:

{pre {center exp := words | abstractions | definitions | applications }}

_p where

{pre
1: word        is any group of chars except spaces and braces ()
2: abstraction is {b (fun (words) exp)}, a first special form
3: definition  is {b (def word exp)}, an optional second special form
4: application is {b (exp exp)}, a nested form
}

_h2 2) evaluation

_p The implementation of metatalk insures that evaluations are done in this order: 1) first {b abstractions}, 2) then {b definitions}, 3) and finally {b applications}. The result is a sequence of words sent to the web browser which evaluates any residual HTML/CSS/SVG/DOM/JS code and outputs the result to the browser's window.

_p More precisely ({i but this can be skipped in a first read}):
{blockquote {i
_ul 1: {b words} are simply ignored by the eval function and so not evaluated,
_ul 2: an abstraction {b (fun (words) exp)} is evaluated to a system defined word, the reference of a javascript function with words as arguments and exp as the body, and added to a {b single dictionary initially empty}. Functions are first class, can be composed, nested and applied to a sequence of values lesser than, equal to or greater than the sequence of arguments,
_ul 3: a definition {b (def word exp)} is evaluated to the given {b word}, a name referencing a function added to the dictionary whose body is the evaluated expression {b exp},
_ul 4: an application {b (exp exp)} is evaluated to a sequence of words, from inside out, if the first {b exp} can be evaluated to a function, or if not, is replaced by a gentle {i error} message {b [exp exp]}.
}}

_p That's all! But what can be done with so little?

_h2 3) text replacements

_p Basically we have tools to process texts replacements, for instance writing:

{pre
.        replace: {b :a} and {b :b}
in this sentence: {b ... :b :a ...}       // where ... is any sequence of words
              by: {b hello} and {b world}
}

_p will obviously display {b ... world hello ...}. Using the metatalk syntax we would write, in a more compact way, replacing the noisy conjunction words "{i and, in this sentence, by}" by well balanced braces:

{pre
((fun (:a :b)
       ... :b :a ...
 )  hello world
)

or in a single line:

((fun (:a :b) ... :b :a ...) hello world)
-> {eval ((fun (:a :b) ... :b :a ...) hello world)}
}

_p an expression creating an {i abstraction}, an anonymous function {code (fun (:a :b) ... :b :a ...)} evaluated to a reference {code fun_ref} and immediately applied on two values, {code (fun_ref hello world)}. This expression will be preferably splitted into a {i definition} giving a name to the unknown function's reference, {code (def name function)}, followed by several {i applications} on any values, for instance:
{pre
(def SWAP (fun (:a :b) ... :b :a ...))
-> {eval (def SWAP (fun (:a :b) ... :b :a ...))}

(SWAP hello world)
-> {eval (SWAP hello world)}

(SWAP james bond)
-> {eval (SWAP james bond)}

(swap alan turing)
-> {eval (swap alan turing)}       // oops! it's an error, swap is not defined.
}

_p The second special form {code (def name expression)} creates global constants

{pre
(def HI hello world)
-> {eval (def HI hello world)}
HI                      // writing HI ...
-> HI                   // ... doesn't display the value
(HI)                    // we must embed the name between braces ...
-> {eval (HI)}          // ... to get the value
}

_p Note the {i inverted evaluation} process - words are not evaluated - reminding the behaviour of a speadsheet where writing {code PI} displays {b PI} and writing {code =PI()} displays the value {b {PI}}. Inverting evaluation is very useful in spreadsheet or wiki contexts where writing text must be as easy as possible.

_p Let's go further and define a few useful {i data structures}.

_h2 4) booleans

_p We need booleans and control structures.

{pre
(def TRUE (fun (:a :b) :a))     // given two words returns the first
-> {eval (def TRUE (fun (:a :b) :a))}
(def FALSE (fun (:a :b) :b))    // given two words returns the second
-> {eval (def FALSE (fun (:a :b) :b))}
(def IF (fun (:c :a :b)  (:c :a :b)))  // returns :a if :c is TRUE else :b
-> {eval (def IF (fun (:c :a :b)  (:c :a :b)))}

(IF TRUE yes no)
-> {eval (IF TRUE yes no)}
(IF FALSE yes no) 
-> {eval (IF FALSE yes no)}
}

_p Let's explain the evaluation of {code (IF TRUE yes no)}:

{pre
(IF TRUE yes no) is a function call equivalent to
     ((fun (:c :a :b) (:c :a :b)) (fun (:a :b) :a) yes no),

1: in the function's body (:c :a :b)
- :c will be replaced by (fun (:a :b) :a)
- :a will be replaced by yes
- :b will be replaced by no

2: the body becomes ((fun (:a :b) :a) yes no) which is a function call
where :a will be replaced by yes, which becomes the result.
}

_p Dealing with sentences - more than one word, yes or no - is more tricky. We will reduce them into a constant - using {code def} - or preferably using an anonymous function without arguments which won't pollute the dictionary with names used only once.

{pre
(def POT I like potatoes)
-> {eval (def POT I like potatoes)}
(def TOM I like tomatoes)
-> {eval (def TOM I like tomatoes)}

((IF TRUE POT TOM))
-> {eval ((IF TRUE POT TOM))}
((IF FALSE POT TOM))
-> {eval ((IF FALSE POT TOM))}

or, preferably but more tricky

((IF TRUE (fun () I like potatoes)
          (fun () I like tomatoes)))
-> {eval ((IF TRUE (fun () I like potatoes)
               (fun () I like tomatoes)))}
((IF FALSE (fun () I like potatoes)
           (fun () I like tomatoes)))
-> {eval ((IF FALSE (fun () I like potatoes)
               (fun () I like tomatoes)))}
}

_p Note the double starting and ending braces to {i force} the value after the choice.

_h2 5) pairs

_p We need aggregated data, beginning with pairs.

{pre
(def CONS (fun (:a :b :c) (:c :a :b)))    // waiting for three values
-> {eval (def CONS (fun (:a :b :c) (:c :a :b)))}
(def HEAD (fun (:p) (:p TRUE)))
-> {eval (def HEAD (fun (:p) (:p TRUE)))}
(def TAIL (fun (:p) (:p FALSE)))
-> {eval (def TAIL (fun (:p) (:p FALSE)))}

(def P (CONS hello world))         // yes, it's a partial application
-> {eval (def P (CONS hello world))}
(HEAD (P))
-> {eval (HEAD (P))}
(TAIL (P))
-> {eval (TAIL (P))}
}

_p Don't forget that {code (HEAD (P))} is nothing but a more convenient way to write this rather convoluted expression

{pre
((fun (:p) (:p (fun (:a :b) :a))) 
(((fun (:a :b :c) (:c :a :b)) hello world)))
-> hello
}

_h2 6) lists & recursion

_p Let's define first the nice {code NIL} function returning {code TRUE} everytime and the predicate {code NILP} returning {b TRUE} given {b NIL} and {b FALSE} given a pair.

{pre
(def NIL (fun (:a) TRUE))
-> {eval (def NIL (fun (:a) TRUE))}
(def NILP (fun (:p) (:p (fun (:a :b) FALSE))))
-> {eval (def NILP (fun (:p) (:p (fun (:a :b) FALSE))))}

(NIL everything)
-> {eval (NIL everything)}

(NILP NIL)
-> {eval (NILP NIL)}
(NILP (P))
-> {eval (NILP (P))}
}

_p Let's nest several pairs of two words in a list of several words ending with NIL
{pre
(def L (CONS hello
       (CONS brave
       (CONS new
       (CONS world
             NIL)))))
-> {eval (def L (CONS hello
       (CONS brave
       (CONS new
       (CONS world
             NIL)))))} 
}

_p We can manually extract every elements
{pre
(HEAD (L)) -> {eval (HEAD (L))}
(HEAD (TAIL (L))) -> {eval (HEAD (TAIL (L)))}
(HEAD (TAIL (TAIL (L)))) -> {eval (HEAD (TAIL (TAIL (L))))}
(HEAD (TAIL (TAIL (TAIL (L))))) -> {eval (HEAD (TAIL (TAIL (TAIL (L)))))}
}

_p or get them {i automatically} via a {b recursive} function 
{pre
(def DISP
 (fun (:l)
  ((IF (NILP :l)
       (fun (:l) )
       (fun (:l) (HEAD :l) (DISP (TAIL :l)))) :l)))
-> {eval (def DISP
 (fun (:l)
  ((IF (NILP :l)
       (fun (:l) )
       (fun (:l) (HEAD :l) (DISP (TAIL :l)))) :l)))}

(DISP (L)) 
-> {eval (DISP (L))}
}

_p Generally speaking a recursive function follows this pattern

{pre
(def RECUR
 (fun (:l)
  ((IF (NILP :)      // will select beetween the two anonymous functions
       (fun (:l) do something and exit)
       (fun (:l) do something with (HEAD :l)
                 (RECUR on (TAIL :l)))) 
   :l)   // forces the evaluation on :l of the chosen anonymous function
))
}

_p Once again, note the double brace before {code IF} and the ending {code :l)} wich {i forces} the evaluation according to the argument's list.

_p So, in a few lines, we have defined booleans, two data structures - pairs & lists - and a control structure, recursion, leading to a tiny but {i Turing complete} functional language. What's that for?

_p As a first exemple remember that metatalk knows nothing but words and has no idea of natural numbers. Let's create them! Just slightly modifying the {b DISP} function into a {b LENGTH} function:

{pre
(def LENGTH
 (fun (:l)
  ((IF (NILP :l)
       (fun (:l) )
       (fun (:l) .(LENGTH (TAIL :l)))) :l)))
-> {eval (def LENGTH
 (fun (:l)
  ((IF (NILP :l)
       (fun (:l) )
       (fun (:l) .(LENGTH (TAIL :l)))) :l)))}

(LENGTH (L))
-> {eval (LENGTH (L))}          // read 4
}

_p Yes, we just created the number {b 4}, in a primitive notation, the length of the {b L} list. The [[fromroots2canopy]] shows how, following Alonzo Church, a complete arithmetic of natural numbers can be built on such a simple foundation. For instance, we can compute the factorial of a number:

{pre

(def FAC
 (fun (:n)
  ((IF (NILP :n)
   (fun (:n) (ONE))
   (fun (:n) (MUL :n (FAC (PRED :n))))) :n)))
-> FAC

(FAC (SIX))               // where SIX is a list of length 6
-> ........ 720 dots ........
}

_h2 7) the {i terrifying} Y-combinator

_p We can avoid the optional {b definition} special form - which is in fact just {i syntactic sugar} - using a very simple function called the {code Y} combinator:

{pre {center (def Y (fun (:f) (:f :f)))}}

_p Thanks to this function the last expression {code (DISP (L))} can be replaced by the following one, where names have been replaced in {b DISP} by their "funny" expressions (see [[fromroots2canopy]] for details):

{pre
(((fun (:f) (:f :f)) 
   (fun (:f :l) 
  (((fun (:c :a :b)  (:c :a :b)) 
    ((fun (:p) (:p 
      (fun (:a :b)
       (fun (:a :b) :b)))) :l)
        (fun (:f :l) )
         (fun (:f :l) 
         ((fun (:p) (:p 
           (fun (:a :b) :a))) :l) (:f :f 
           ((fun (:p) (:p 
             (fun (:a :b) :b))) :l)))) :f :l)))
 (L))
-> {eval 
(((fun (:f) (:f :f)) 
   (fun (:f :l) 
  (((fun (:c :a :b)  (:c :a :b)) 
    ((fun (:p) (:p 
      (fun (:a :b)
       (fun (:a :b) :b)))) :l)
        (fun (:f :l) )
         (fun (:f :l) 
         ((fun (:p) (:p 
           (fun (:a :b) :a))) :l) (:f :f 
           ((fun (:p) (:p 
             (fun (:a :b) :b))) :l)))) :f :l)))
 (L))
} 
}

_p A pure λ-calculus expression - where {b fun} is for {b lambda}, containing nothing but words, abstractions and applications, the Yin and Yang of computing. The door to an exciting world of algorithms, as it can be seen in [[fromroots2canopy]].

_p {i Alain Marty | 2020/06/08}

_h2 annexe

_p The {code eval} function is written in 100 lines of plain javascript. Clikc below to read them...

{uncover http://epsilonwiki.free.fr/epsilonwiki/data/lepetitnicolas.jpg 100 1000
{pre °°
var META = (function() {
  var DICT = {},
      FUN_num = 0; 
  var regexp = /\(([^\s()]*)(?:[\s]*)([^()]*)\)/g;
  var evaluate = function(s) {
    s = eval_specials(s,'fun',eval_fun);          // lazy evaluation
    s = eval_specials(s,'def',eval_def, true);    // lazy evaluation
    s = eval_forms(s);                            // greedy evaluation
    return s;
  };
  var eval_forms = function(s) {
    while ( s !== (s = s.replace(regexp, eval_form))) ;
    return s;
  };
  var eval_form = function() {
    var f = arguments[1] || "", r = arguments[2] || "";
    return DICT.hasOwnProperty(f) ? DICT[f].apply(null, [r]) 
                                  : "[" + f + " " + r + "]";
  };
  var eval_specials = function(s,symbol,eval_symbol,flag) {
    while (s !== (s = special_replace(s, symbol, eval_symbol, flag)));
    return s;
  };
  var special_replace = function(str, symbol, func, flag) {
    symbol = "(" + symbol + " ";
    var s = special_catch(symbol, str);
    return s === "none" ? str
                        : str.replace(symbol + s + ")", func(s, flag));
  };
  var special_catch = function(symbol, str) {
    var start = str.indexOf(symbol);
    if (start == -1) return "none";
    var nb = 1, index = start;
    while (nb > 0) {
      index++;
      if (str.charAt(index) == "(") nb++;
      else if (str.charAt(index) == ")") nb--;
    }
    return str.substring(start + symbol.length, index);
  }; 
  var eval_fun = function(s) { 
    s = eval_specials(s,'fun',eval_fun);
    var index = s.indexOf(")"),
        argStr = supertrim(s.substring(1, index)),
        args = argStr === "" ? [] : argStr.split(" "),
        body = supertrim(s.substring(index + 2)),
        name = "_FUN_" + FUN_num++;
    DICT[name] = function() {
      var valStr = supertrim(arguments[0]),
          vals = valStr === "" ? [] : valStr.split(" "),
          bod = body;
      if (vals.length < args.length) {
          for (var i = 0; i < vals.length; i++)
            bod = bod.replace(RegExp(args[i], "g"), vals[i]);
          var _args_ = args.slice(vals.length).join(" ");
          bod = eval_fun("(" + _args_ + ") " + bod);
      } else if (vals.length === args.length) {
          for (var i=0; i < args.length; i++)
            bod = bod.replace( RegExp(args[i], "g"), vals[i] );
      } else {                              
          var _vals_ = vals.slice(0,args.length);
          _vals_[args.length-1] = vals.slice(args.length-1,vals.length).join(' ');
          for (var i=0; i < args.length; i++)
            bod = bod.replace( RegExp(args[i], "g"), _vals_[i] ); 
      }
      return eval_forms(bod);
    };
    return name;
  };
  var eval_def = function(s, flag) { 
    s = eval_specials(s,'def',eval_def,false);
    var index = s.search(/\s/);
    var name = s.substring(0, index).trim();
    var body = s.substring(index).trim();
    if (body.substring(0, 5) === "_FUN_") {
      DICT[name] = DICT[body];
    } else {
      body = eval_forms(body);
      DICT[name] = function() {
        return body;
      };
    }
    return flag ? name : "";
  };
  var supertrim = function(s) {
    return s.trim().replace(/\s+/g, " ");
  };
  var balance = function(s) {
    var strt = s.match(/\(/g), stop = s.match(/\)/g);
    strt = strt ? strt.length : 0;
    stop = stop ? stop.length : 0;
    return { left: strt, right: stop };
  };
  return {               // public functions
    balance:balance,     // valid expressions
    evaluate:evaluate    // eval expressions
  }
})();  // end META

// META can be used anywhere or in this wiki page
// via a single function, "eval", added to the LAMBDATALK dictionary

LAMBDATALK.DICT["eval"] = function() {
  var args = arguments[0].trim();
  var bal = META.balance(args);
  return (bal.left === bal.right) ?
    META.evaluate( args ) : '('+bal.left+'|'+bal.right+')';
};

°°}
}

{script

var META = (function() {

var DICT = {},
      FUN_num = 0; 
  var regexp = /\(([^\s()]*)(?:[\s]*)([^()]*)\)/g;

var evaluate = function(s) {
    s = eval_specials(s,'fun',eval_fun);          // lazy evaluation
    s = eval_specials(s,'def',eval_def, true);    // lazy evaluation
    s = eval_forms(s);                            // greedy evaluation
    return s;
  };

var eval_forms = function(s) {
    while ( s !== (s = s.replace(regexp, eval_form))) ;
    return s;
  };
  var eval_form = function() {
    var f = arguments[1] || "", r = arguments[2] || "";
    return DICT.hasOwnProperty(f) ? DICT[f].apply(null, [r]) : "[" + f + " " + r + "]";
  };

var balance = function(s) {
    var strt = s.match(/\(/g),
        stop = s.match(/\)/g);
    strt = strt ? strt.length : 0;
    stop = stop ? stop.length : 0;
    return { left: strt, right: stop };
  };

return {               // public functions
    balance:balance,     // valid expressions
    evaluate:evaluate    // eval expressions
  }

})();  // end META

}

{style 
pre { padding:10px; box-shadow:0 0 4px #000; text-align:left; }
blockquote { padding:10px; background:#eee; }
}