5 | list | login |load

| {195:195} 623ms |

_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; }
}

meta | meta2 | meta3 | meta4 | meta5

undefined

uncover
develop     
showhide

As simple as that!

(meta talk) ^{^{see a short version in meta4}}

As an aside of the lengthy fromroots2canopy page, we are going to build from scratch the foundations of a functional language, metatalk, embedded in this wiki page via a single eval lambdatalk function:

{eval metatalk expression} -> words

1) syntax

A metatalk expression is defined as follows:

exp := words | abstractions | definitions | applications

where

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

2) evaluation

The implementation of metatalk insures that evaluations are done in this order: 1) first abstractions, 2) then definitions, 3) and finally 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.

More precisely (but this can be skipped in a first read):

• 1: words are simply ignored by the eval function and so not evaluated,

• 2: an abstraction (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 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,

• 3: a definition (def word exp) is evaluated to the given word, a name referencing a function added to the dictionary whose body is the evaluated expression exp,

• 4: an application (exp exp) is evaluated to a sequence of words, from inside out, if the first exp can be evaluated to a function, or if not, is replaced by a gentle error message [exp exp].

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

3) text replacements

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

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

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

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

or in a single line: 

((fun (:a :b) ... :b :a ...) hello world)
-> ... world hello ...

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

(def SWAP (fun (:a :b) ... :b :a ...))
-> SWAP

(SWAP hello world)
-> ... world hello ...

(SWAP james bond)
-> ... bond james ...

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

The second special form (def name expression) creates global constants

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

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

Let's go further and define a few useful data structures.

4) booleans

We need booleans and control structures.

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

(IF TRUE yes no)
-> yes
(IF FALSE yes no) 
-> no

Let's explain the evaluation of (IF TRUE yes no):

(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.

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

(def POT I like potatoes)
-> POT
(def TOM I like tomatoes)
-> TOM

((IF TRUE POT TOM))
-> I like potatoes
((IF FALSE POT TOM))
-> I like tomatoes

or, preferably but more tricky

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

Note the double starting and ending braces to force the value after the choice.

5) pairs

We need aggregated data, beginning with pairs.

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

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

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

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

6) lists & recursion

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

(def NIL (fun (:a) TRUE))
-> NIL
(def NILP (fun (:p) (:p (fun (:a :b) FALSE))))
-> NILP

(NIL everything)
-> TRUE

(NILP NIL)
-> TRUE
(NILP (P))
-> FALSE

Let's nest several pairs of two words in a list of several words ending with NIL

(def L (CONS hello
       (CONS brave
       (CONS new
       (CONS world
             NIL)))))
-> L

We can manually extract every elements

(HEAD (L)) -> hello
(HEAD (TAIL (L))) -> brave
(HEAD (TAIL (TAIL (L)))) -> new
(HEAD (TAIL (TAIL (TAIL (L))))) -> world

or get them automatically via a recursive function

(def DISP
 (fun (:l)
  ((IF (NILP :l)
       (fun (:l) )
       (fun (:l) (HEAD :l) (DISP (TAIL :l)))) :l)))
-> DISP

(DISP (L)) 
-> hello brave new world

Generally speaking a recursive function follows this pattern

(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
))

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

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

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 DISP function into a LENGTH function:

(def LENGTH
 (fun (:l)
  ((IF (NILP :l)
       (fun (:l) )
       (fun (:l) .(LENGTH (TAIL :l)))) :l)))
-> LENGTH

(LENGTH (L))
-> ....          // read 4

Yes, we just created the number 4, in a primitive notation, the length of the 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:

(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 ........

7) the terrifying Y-combinator

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

(def Y (fun (:f) (:f :f)))

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

(((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))
-> hello brave new world

A pure λ-calculus expression - where fun is for 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.

Alain Marty | 2020/06/08

annexe

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

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+')';
};