lambdaway :: meta4

3 | list | login |load

| |

{center [[meta]] | [[meta2]] | [[meta3]] | meta4 | [[meta5]]}

_img https://upload.wikimedia.org/wikipedia/commons/3/3d/Maquina.png

_h1 is metatalk a Turing machine?

_p It's a short version of [[meta3]] where some more detailed explanations are given.

_h2 1) syntax & evaluation
{pre
exp := word        : [^\s()]*             // not evaluated
    |  abstraction : (fun (words) exp)    // evaluated first
    |  definition  : (def word exp)       // evaluated second (optional)
    |  application : (exp exp)            // evaluated last (from inside out)
}

_p Nothing else, there are no primitives, the dictionary is empty, no booleans, no numbers, no data structures, no control structures. Nada. Basically abstractions do nothing but simple string rewriting, text substitution, via Immediately Invoked Function Expressions (IIFE) {code ((fun (args) body) values)}, for instance:

{pre
((fun (:a :b) ... :b :a ...) hello world)   // the IIFE, where
-> ((fun (:b) ... :b hello ...) world)      // hello replaces :a
-> ((fun () ... world hello ...))           // world replaces :b
-> ... world hello ...                      // the body is returned
}
_p Note that the four lines above are {i equivalent}, just as this algebric expression {code (a-b)*(a+b)} is equivalent to {code a{sup 2}-b{sup 2}}. Everything that follows is a matter of more or less complex compositions of words, abstractions, definitions and applications. Note that definitions are optional, just introduced for lisibility and could theoretically be avoided.

_h2 2) words

_p Please note that the following examples are actually evaluated on the page, the code is active and editable on demand.

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

(def SWAP (fun (:a :b) :b :a))   // a name given to an anonymous function
-> {eval (def SWAP (fun (:a :b) :b :a))}
(SWAP hello world)               // applying a function on two values                 
-> {eval (SWAP hello world)}

(def HI hello world)                                 
-> {eval (def HI hello world)}
HI                               // a word is not evaluated                  
-> HI
(HI)                             // forcing an evaluation                         
-> {eval (HI)}

(def TRUE (fun (:a :b) :a))                          
-> {eval (def TRUE (fun (:a :b) :a))}
(def FALSE (fun (:a :b) :b))                         
-> {eval (def FALSE (fun (:a :b) :b))}
(def IF (fun (:c :a :b)  (:c :a :b)))                
-> {eval (def IF (fun (:c :a :b)  (:c :a :b)))}
(IF TRUE yes no)                // more in [[meta3]]         
-> {eval (IF TRUE yes no)}
(IF FALSE yes no)                                    
-> {eval (IF FALSE yes no)}

(def CONS (fun (:a :b :c) (:c :a :b)))    // waits for 3 values
-> {eval (def CONS (fun (:a :b :c) (:c :a :b)))}
(def HEAD (fun (:p) (:p TRUE)))           // waits for a function            
-> {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))          // this partial application                    
-> {eval (def P (CONS hello world))}                                // returns (fun (:c) (:c hello world))
(HEAD (P))                          
-> {eval (HEAD (P))}                            
(TAIL (P))                                           
-> {eval (TAIL (P))}

(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))))}
(NILP NIL)                                           
-> {eval (NILP NIL)}
(NILP (P))                                           
-> {eval (NILP (P))}

We have everything required to build recursive processes:

(def DISP
 (fun (:l)
  ((IF (NILP :l)                                // more in [[meta3]]
       (fun (:l) )                              // fun postpones evaluation
       (fun (:l) (HEAD :l) (DISP (TAIL :l))))   // until the choice is done
   :l)                                          // forcing evaluation now
)) 
-> {eval (def DISP
 (fun (:l)
  ((IF (NILP :l)
       (fun (:l) )
       (fun (:l) (HEAD :l) (DISP (TAIL :l)))) :l)))}

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

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

using this pattern, let's build REVERSE, APPEND, LENGTH, ...

(def REVERSE
 (def REVERSE.r
  (fun (:a :b)
   ((IF (NILP :a)
    (fun (:a :b) :b)
    (fun (:a :b) (REVERSE.r (TAIL :a) (CONS (HEAD :a) :b))))
     :a :b)))
 (fun (:a) (REVERSE.r :a NIL)))                     
-> {eval (def REVERSE
 (def REVERSE.r
  (fun (:a :b)
   ((IF (NILP :a)
    (fun (:a :b) :b)
    (fun (:a :b) (REVERSE.r (TAIL :a) (CONS (HEAD :a) :b))))
     :a :b)))
 (fun (:a) (REVERSE.r :a NIL)))}

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

(def APPEND                            
 (def APPEND.r
  (fun (:a :b)
   ((IF (NILP :b)
    (fun (:a :b) :a)
    (fun (:a :b) (APPEND.r (CONS (HEAD :b) :a)
                                 (TAIL :b)))) :a :b)))
 (fun (:a :b) (APPEND.r (REVERSE :a) :b)))         
-> {eval (def APPEND                            
 (def APPEND.r
  (fun (:a :b)
   ((IF (NILP :b)
    (fun (:a :b) :a)
    (fun (:a :b) (APPEND.r (CONS (HEAD :b) :a)
                                 (TAIL :b)))) :a :b)))
 (fun (:a :b) (APPEND.r (REVERSE :a) :b)))}

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

(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))}   // it's a primitive notation for the number 4
 
}

_h2 3) numbers

_p The {b LENGTH} function displays the length of a list as a sequence of dots, let's define numbers as lists of dots begining with {b NIL}, ie {b ZERO}.

{pre

(def SUCC (fun (:n) (CONS . :n)))                 
-> {eval (def SUCC (fun (:n) (CONS . :n)))}
(def PREV (fun (:n) (TAIL :n)))                   
-> {eval (def PREV (fun (:n) (TAIL :n)))}

(def ONE (SUCC (NIL)))  -> {eval (def ONE (SUCC (NIL)))} {eval (DISP (ONE))}
(def TWO (SUCC (ONE)))  -> {eval (def TWO (SUCC (ONE)))} {eval (DISP (TWO))}
(def TRE (SUCC (TWO)))  -> {eval (def TRE (SUCC (TWO)))} {eval (DISP (TRE))}
(def FOR (SUCC (TRE)))  -> {eval (def FOR (SUCC (TRE)))} {eval (DISP (FOR))}
(def FIV (SUCC (FOR)))  -> {eval (def FIV (SUCC (FOR)))} {eval (DISP (FIV))}

once more we use the recursive pattern to define 
three arithmetical operators, ADD, MUL, FAC

(def ADD
 (fun (:a :b)
  ((IF (NILP :a)
   (fun (:a :b) :b)
   (fun (:a :b) (ADD (PREV :a) (SUCC :b)))) :a :b)))  
-> {eval (def ADD
 (fun (:a :b)
  ((IF (NILP :a)
   (fun (:a :b) :b)
   (fun (:a :b) (ADD (PREV :a) (SUCC :b)))) :a :b)))}

(def MUL
 (def MUL.r
  (fun (:a :b :c)
   ((IF (NILP :b)
    (fun (:a :b :c) :c)
    (fun (:a :b :c) (MUL.r :a (PREV :b) (ADD :a :c)))) :a :b :c)))
 (fun (:a :b)
  (MUL.r :a :b NIL)))
-> {eval (def MUL
 (def MUL.r
  (fun (:a :b :c)
   ((IF (NILP :b)
    (fun (:a :b :c) :c)
    (fun (:a :b :c) (MUL.r :a (PREV :b) (ADD :a :c)))) :a :b :c)))
 (fun (:a :b)
  (MUL.r :a :b NIL)))}

(def FAC
 (fun (:a :b)
  ((IF (NILP :b)
   (fun (:a :b) :a)
   (fun (:a :b) (FAC (MUL :a :b) (PREV :b)))) :a :b)))
-> {eval (def FAC
 (fun (:a :b)
  ((IF (NILP :b)
   (fun (:a :b) :a)
   (fun (:a :b) (FAC (MUL :a :b) (PREV :b)))) :a :b)))}
}

{prewrap
(DISP (ADD (FIV) (FIV))) 
-> {eval (DISP (ADD (FIV) (FIV)))}  // 10 dots
(DISP (MUL (FIV) (FIV))) 
-> {eval (DISP (MUL (FIV) (FIV)))}  // 25 dots
(DISP (FAC (ONE) (FIV))) 
-> {eval (DISP (FAC (ONE) (FIV)))}  // 120 dots
}

_h2 4) the towers of hanoï

_p A set of disks of decreasing size are stacked on a rod. The game consists in deplacing each disk to a second rod via a third one in respect of the following rule: never put a disk on a smaller one. The code is built on a doubly recursive function.

{pre
(def HANOI
 (fun (:n :from :to :via)
  ((IF (NILP :n)
   (fun (:n :from :to :via) )
   (fun (:n :from :to :via)
    (HANOI (TAIL :n) :from :via :to)
     <{span}br>move (LENGTH :n) from tower :from to tower :to 
    (HANOI (TAIL :n) :via :to :from) ))
   :n :from :to :via)))
-> {eval (def HANOI
 (fun (:n :from :to :via)
  ((IF (NILP :n)
   (fun (:n :from :to :via) )
   (fun (:n :from :to :via)
    (HANOI (TAIL :n) :from :via :to)
     <br>move (LENGTH :n) from tower :from to tower :to 
    (HANOI (TAIL :n) :via :to :from) ))
   :n :from :to :via)))}

(HANOI (FIV) A B C)
-> {eval (HANOI (FIV) A B C)}

and so on...
}  
  
_h2 conclusion

_p Don't forget that the dictionary is empty, there are no primitives, just a reduced set of user defined expressions. See them as a sequence of characters  written on a Turing machine's stripe whose table of rules contains two processes, {b abstraction} and {b application}. It's not so amazing, the λ calculus is equivalent to a Turing machine.

{pre {center
[ table of rules: ]
[   abstraction   ]
[   application   ]
|
|
[ cells in the stripe are initially empty (displayed as dots) ]
.......................................................
.......((fun.(:a.:b).....:b.:a....).hello.world).......
..........((fun.(:a).....world.:a....).hello)..........
............((fun.().....world.hello....)).............
....................world.hello........................

}}

_p Just four equivalent expressions of decreasing entropy.

_p See more in [[fromroots2canopy]], and you can analyze the [[METATALK's evaluator code|javascript:LAMBDATANK.toggle_display('page_editor')]] inside the script section. See also [[https://news.ycombinator.com|https://news.ycombinator.com/item?id=23711343#23723807]], ... where people talk about things that don't have much to do with what's written on this page. It's kind of sad.

_p And yes, lambdatalk is metatalk with a set of 9 special forms {code [ lambda def let if quote macro script style require]} and a hundred primitives {code [ MATH WORD SEQUENCE ARRAY HTML SVG DOM ... ]} and can be used as a true language, for instance to write, test and compute in real time [[FFT]], [[permutations|?view=perm2]] or to write this wiki page.

_p {i Alain Marty | 2020/06/11-27}

{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

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

}

{style 
body { background:#444; }
#page_frame, #page_content, .page_menu { background:transparent; color:#fff; border:0; box-shadow:0 0 0 #000; }
 }