{λ way}

user:anonymous

{img {@ src="data/alan_turing_20160904.jpg" width="100%" title="A statue of Turing by sculptor Stephen Kettle, on display at Bletchley Park, where he worked to decipher the Enigma code during World War II."}}

{img {@ src="data/Turing_Tape.jpg" width="100%" title="Turing machine"}}
{center [[Turing machines implemented in JavaScript|http://www.turing.org.uk/book/update/tmjavar.html]]}

_p We want to demonstrate that [[lambdatalk|?view=quick]] is a kind of Turing machine. {b Not by mimicking} the initial approach, (see [[https://en.wikipedia.org/wiki/Turing_machine|https://en.wikipedia.org/wiki/Turing_machine]]), but by {b focusing on the way lambdatalk works} on a single string used as a storage/memory containing a program based on a finite set of elementary instructions and datas progressively evolving from the input to the output state. 
_p For instance such a string "{code X = '{+ 1 {* 2 3} 4}}" will be successively replaced by "{code X = '{+ 1 6 4}}" then by "{code X = 11}" like this:

{pre °°
1: | | | |X| |=| |{|+| |1| |{|*| |2| |3|}| |4|}| | | | | | | | | | |
2: | | | |X| |=| |{|+| |1| |6| |4|}| | | | | | | | | | | | | | | | |
3: | | | |X| |=| |1|1| | | | | | | | | | | | | | | | | | | | | | | |

°°}

_h3 1) introducing the machine

_p We say that lambdatalk has a {b tape}, a {b window} and a {b finite set of elementary instructions}:

_ul 1) the {b tape} is the string containing {b words} and {b forms}, {code '{first rest}}, where {code first} is a word (or a lambda, see later), and {code rest} is made of words and forms, giving to the code a recursive flatten tree structure, as in "{code X = '{+ 1 {* 2 3} 4}}",
_ul 2) the {b window} is a {b regular expressions}, "{code °°/\{([^\s{}]*)(?:[\s]*)([^{}]*)\}/g °°}", catching terminal forms, '{word words}, and replacing them by words according to a {b dictionary},
_ul 3) the {b dictionary} is a {b finite set of elementary instructions} - which could be initially empty - for instance the set of primitive functions [+, -, *, =, sqrt, ..., when, ...] getting words and returning words, for instance {code '{+ 1 2} -> 3}.

_p {b Forms} {code '{first rest}} can be {b simple} or {b special}:

_ul 1) {b simple forms} are recursively caught from leaves (terminal forms) to the root and replaced by words according to the dictionary, for instance {code '{+ 1 {* 2 3} 4}} is replaced by {code '{+ 1 6 4}} then by {b 11}.

_ul 2) {b special forms} are forms whose {code first} term belongs to the set {code [lambda, def, if]} and are evaluated specifically:

_ul30 {code '{lambda {args} body}} is replaced by a reference to a function added to the dictionary, binding {code args} to future values in {code body} made of words and forms,

_ul30 {code '{def name body}} is replaced by {code name} as a reference to {code body} added to the dictionary,

_ul30 {code '{if bool then one else two}} is replaced by the simple form {code '{when bool the one else two}} where {code bool, one, two} are unevaluated, introducting a kind of {b lazyness}, {code one} OR {code two} being evaluated according to {code bool}.

_h3 2) running the machine

_p We follow the evaluation of a recursive function to build a demonstration:

{pre
'{def fac
 {lambda {:n}
  {if {= :n 1}
   then 1
   else {* {fac {- :n 1}}}
}}}
'{fac 4}
}

_p will be replaced by
{pre
fac
24
}

_p Special forms are first replaced in several loops, then simple forms in a single loop. Thereafter we will write the functions's definition and the call in a single line, each character stored in a cell of a virtual tape.

_h4 1) looping on special forms

_p During the preprocessing phase special forms {code [lambda,def,if]} are evaluated in this order {code if, lambda, def}:

{pre
.   0         1         2         3         4         5         6         7         8
    012345678901234567890123456789012345678901234567890123456789012345678901234567890
00: '{def fac {lambda {:n} {if {= :n 1} then 1 else {* :n {fac {- :n 1}}}}}} '{fac 4}
    special form {code '{if ...}} is replaced by '{when ...} where terms are escaped from evaluation, {code '{} -> []}
01: '{def fac {lambda {:n} {when [= :n 1] then 1 else [* :n [fac [- :n 1]]]}}} '{fac 4}
    special form {code '{lambda ...}} is replaced by some internal reference, say lambda_1234,
02: '{def fac lambda_1234} '{fac 4}
    special form {code '{def ...}} is replaced by the given name, fac
03: fac '{fac 4}
}

_h4 2) looping on simple forms

_p Control structures have been delayed, lambdas have been stored, names have been given, the resulting string "{code fac '{fac 4}}" can be now evaluated:

{pre
.   0         1         2         3         4         5         6         7         8
    012345678901234567890123456789012345678901234567890123456789012345678901234567890
00: fac '{fac 4} 
      - the first fac is a word and will be ignored by the window
      - in '{fac 4} fac is replaced by its value    
    '{{lambda {:n} {when [= :n 1] then 1 else [* :n [fac [- :n 1]]]}} 4}  
      - lambda replaces the occurences of :n by 4           
01: fac '{when [= 4 1] then 1 else [* 4 [fac [- 4 1]]]}    
      - when unquotes and evaluates bool:
      '{when false then 1 else [* 4 [fac [- 4 1]]]}
      - then chooses and unquotes the else term
      '{* 4 {fac {- 4 1}}}
02: fac '{* 4 {fac 3}}  
      - and so on until stop case when :n = 1                                             
03: fac '{* 4 {when [= 3 1] then 1 else [* 3 [fac [- 3 1]]]}}            
04: fac '{* 4 {* 3 {fac 2}}}                                           
05: fac '{* 4 {* 3 {when [= 2 1] then 1 else [* 2 [fac [- 2 1]]]}}}      
06: fac '{* 4 {* 3 {* 2 {fac 1}}}}                                     
07: fac '{* 4 {* 3 {* 2 {when [= 1 1] then 1 else [* 1 [fac [- 1 1]]]}}}}
    then we can evaluate the stacked products from 4 to 1: 
08: fac '{* 4 {* 3 {* 2 1}}}                                           
09: fac '{* 4 {* 3 2}}                                                 
10: fac '{* 4 6}                                                       
11: fac 24                                                            
}

_p More explanations can be seen in page [[recursion]].

_h3 3) conclusion

_p We have seen that the entire process is done on a string which begins with about 80 characters and ends with 6, "{code fac 24}". The dictionary acts as a CPU applying some table of decision to the content of each cell under the "running" window. It looks soon like a {b Universal Turing machine}, isnt'it, but in order to improve the demonstration {b the dictionary can be reduced to zero}, as shown in page [[calc2talk]] where lambdatalk is seen as a dialect of the [[lambda_calculus]]. This is the code leading to {b 6!} where {b λ} is written for {code lambda}:

{pre {@ style="white-space:pre-wrap"}°°
6! = {{λ {:n} {{λ {:p} {:p {λ {:x :y} :y}}} {{:n {λ {:p} {{λ {:a :b :m} {{:m :a} :b}} {{λ {:n :f :x} {:f {{:n :f} :x}}} {{λ {:p} {:p {λ {:x :y} :x}}} :p}} {{λ {:n :m :f} {:m {:n :f}}} {{λ {:p} {:p {λ {:x :y} :x}}} :p} {{λ {:p} {:p {λ {:x :y} :y}}} :p}}}}} {{λ {:a :b :m} {{:m :a} :b}} {λ {:f :x} {:f :x}} {λ {:f :x} {:f :x}}}}}} {λ {:f :x} {:f {:f {:f {:f {:f {:f :x}}}}}}}} = 720
°°}

_p Now the "finite set of elementary instructions" is reduced to two operations, {b abstraction} with {code '{lambda {args} body}} and {b application} with {code '{first rest}} working on words and nested forms stored in a string, the virtual tape. We can think that lambdatalk is a kind of Turing machine.

_p {i Alain Marty 2016/09/04}

{hr}

_h4 Your opinion is welcome in [[forum]]. Thanks.