lambdaway :: fromroots2canopy

2 | list | login |load

| |

{center {@ style="background:#000 url('data/amelie_poulain.jpg'); color:#fff;"}  
_img data/tarver_tree.png 
{i Credit [[Mark Tarver|http://www.marktarver.com/]] & Amélie Poulain}
}

{macro \/\/ ([^\n]*)\n to // €1}

{div {@ style="font:italic 3.0em optima; text-align:center;"} from roots to canopy}

{div {@ style="height:20px; overflow:hidden; cursor:grab" onclick="this.style.height=(this.style.height==='20px')?'auto':'20px'"}
{center ({b french intro})}
 
{prewrap
>   Cette page n'est ni une introduction au langage lambdatalk ni une présentation du lambda-calcul, mais la {b balade quasiment poétique} le long de quelques points clés qui conduisent à un langage de programmation.

Le voyage commence avec un simple processus de {b substitution de texte}, il s'agit de remplacer des mots {b variables} dans une phrase par d'autres mots {b valeurs}. Pensez à une lettre type où des mots tiroirs comme {b #nom#} et {b #ville#} sont à remplacer par les mots {b Colette} et {b Oran}.

On nomme la lettre type {b abstraction} et la lettre finale {b application}. On aurait pu les appeler aussi {b Yin & Yang}. Pourquoi pas ?
 
Ce processus est immédiatement {b codé} sous une forme compacte:

expression = '{{remplace {variables} expression} mots},

Cette écriture {b sténographique} reçoit le doux nom de {b IIFE} (peu importe sa signification pour l'instant) et sera le point de départ de tout ce qui va suivre. L'expression interne '{remplace {variables} expression} est donc l'abstraction. Il nous sera utile de lui donner un nom en écrivant '{def ma_fonction abstraction} et l'expression ainsi nommée '{ma_fonction mots} sera bien sûr l'application.

Pour des raisons historiques nous conviendrons de remplacer le mot {b remplace} par le mot {b lambda}, peu importe pourquoi pour l'instant. Avouez que ça fait plus d'effet dans les salons...

La scène est campée : dans ce processus de substitution de texte, nous disposons de trois acteurs, les mots, les abstractions et les applications.

Mais pour quoi faire, doux Jésus ?

Par exemple vous devriez facilement comprendre que cette expression

'{{lambda {:a :b} bla bla :a :b bli bli} hello world}

sera "évaluée" à

bla bla hello world bli bli     // une séquence de mots

Au fait, comprenez-vous pourquoi il est préférable de préfixer les variables a & b par un caractère d'échappement, ici les deux points ":" ?

L'expression suivante

'{{lambda {:a :b} bla bla :b :a bli bli} hello world}

sera évidemment évaluée à

bla bla world hello bli bli    // une séquence de mots

Nous avons tout ce qu'il faut pour écrire notre première fonction, SWAP, c'est à dire {i échanger, intervertir} en anglais

'{def SWAP {lambda {:a :b} :b :a}}    // cette expression est ...
	-> SWAP                              // ... évaluée à un mot

et l'utiliser ainsi

'{SWAP hello world}                   // cette expression est ...
	-> world hello                       // ... évaluée à une
                                             // séquence de mots
	'{SWAP james bond}                   
	-> bond james

Vous venez simplement de créer une abstraction nommée - une {b fonction} nommée SWAP - et vous venez de l'appliquer deux fois. Vous venez d'écrire votre premier programme et il a été exécuté. Et ce programme votre voisine coiffeuse et l'ordinateur peuvent le comprendre et l'exécuter.

{b Bienvenue dans le monde merveilleux du code !}

Tout le reste n'est que pure {b mécanique algébrique} à la portée de votre ordinateur et de votre voisine coiffeuse.
}}
 
 
{center {prewrap
{i This page is {br}neither an introduction to the lambdatalk language {br}nor a presentation of lambda-calculus, {br}but the {b quasi poetic walk} along a few key points {br}that lead {b from nothing} to a programming language. {br}Less is more.
}}}
_p You could also compare this page to
_ul 1) [[A Tutorial Introduction to the Lambda Calculus (Raul Rojas)|http://www.inf.fu-berlin.de/lehre/WS03/alpi/lambda.pdf]] or 
_ul 2) [[Le λ-calcul comme modèle de calculabilité|https://www.irif.fr/~carton/Enseignement/Complexite/ENS/Redaction/2009-2010/pablo.rauzy.pdf]] or
_ul 3) [[Perl and the Lambda Calculus |https://perl.plover.com/yak/lambda/samples/]], 
_p and analyze the different way basic concepts are introduced, booleans, pairs, recursion, numbers. See also [[meta3]], [[meta4]], [[ifac_rfac]], ... {b What follows is simple but not simplistic}. It is about concepts very often hidden under accumulations of notations, definitions and implicit behaviors. The parenthesed and prefixed notation {b has been chosen here} for its uniqueness, minimalism and the absence of any implicit behaviour. This is what is required to address in so few lines so many concepts that provide the foundation of a language.
_p Anyway your opinion is welcome via lambdaway©free•fr.

_h2 plan
_ul introduction
_ul 1) syntax & evaluation
_ul 2) lambda & def
_ul20 2.1) lambdas
_ul20 2.2) defs
_ul 3) data & control structures
_ul20 3.1) booleans
_ul20 3.2) pairs
_ul20 3.3) lists & recursion
_ul20 3.4) the Y-combinator
_ul 4) applications
_ul20 4.1) towers of hanoï
_ul20 4.2) the hilbert's curve
_ul20 4.3) fractal trees
_ul20 4.4) arithmetic
_ul20 4.5) range, map, reduce
_ul20 4.6) the left factorial
_ul conclusion
_ul references

_h1 introduction

_p The '{lambda way} project is a light framework built on a wiki, '{lambda tank}, and a functional programming language, '{lambda talk}.

_p In this page, using '{lambda talk} reduced to two special forms, {code lambda & def}, and an empty dictionary, ie. no primitives, we will define a few data and control structures and explore some interesting things, {i syntax & evaluation, anonymous functions, pure functions, partial application, curryfication, no closure, composition, then pairs, lists, recursion, Y-combinator, some applications on arithmetic and graphics, and also map, reduce, ...}, in other words some of the foundations of a functional programming language.

_p As a foreword let's consider the following command

{pre
{b replace} x {b and} y
     {b in} ... y x ...       // where ... is any sequence of words
     {b by} hello {b and} world
-> ... world hello ...
}

_p It's obviously very easy to understand that this command is nothing but a simple text replacement process: {i two words must be swapped.}.

_p And we can understand that the following strange expression
{pre
'{{lambda {:x :y} 
          ... :y :x ...
       }  hello world}
}

_p is just a {b compact} way to rewrite the command: the conjunction words {b and, in, by} have been replaced by a set of well balanced curly braces and the verb {b replace} has been replaced by a {i strange one}, {b lambda}, choosen for historical reasons (don't worry). And we can guess that such a syntax will be very useful to build deeply nested combinations. It's what we are going to explore a little bit.

_p {i But first let me congratulate you: you've just written your first computer program!}

_h1 1) syntax & evaluation

_p Following the λ calculus created in the 30s by Alonzo Church a '{lambda talk} expression is defined as follows
{center {pre expression := words | abstractions | definitions | applications }}

_p where

{pre
.              {b syntax                           evaluated to}
word        := any chars except spaces and '{}   itself
abstraction := '{lambda {:words} expression}     a function's reference    
definition  := '{def word expression}            word as alias to expression 
application := '{abstraction expression}         a sequence of words
}

_p Note that the character "{code s}" ending {code words, abstractions, definitions & applications} means {b a sequence of}. And note that words inside the lambda expression, {code '{:words}}, should be prefixed with a colon, ":", enlighting them as local variables and protecting against unwanted replacements in the lambda's body. Moreover these words must be chosen so that their intersection is null, for instance {code '{:a1 :a2 :a3}} is ok because {code :a1^:a2 === 0} but {code '{:a :a1 :a2}} is not because {code :a^:a1 === :a}. The rule is "{i choose variables'names thinking in terms of replacements}".

;; The evaluator doesn't translate the code string into a tree of tokens, but does its work inside the string iself, going back and forth in a sequence of textual substitutions resulting in a sequence of words.

_p The implementation of '{lambda talk} 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 possibly HTML/CSS/JS code and outputs the result to the browser's window.

_h1 2) lambda & def

{blockquote

{center {i This section can be skipped in a first reading.}}

_p The prefixed parenthesized expression

{pre
°°{{°°lambda °°{°°:a{sub 0} :a{sub 1} ... :a{sub n-1}°°}°°
          expression containing some occurences of :a{sub i}°°}°°
          v{sub 0} v{sub 1} ... v{sub p-1}°°}°°
}

_p so called {b IIFE} (Immediately Invoked Function Expression), defines an {i anonymous function} containing a sequence of n arguments {code :a{sub i}}, {i immediately invoked} on a sequence of p values {code v{sub i}}, and returning the expression in its body as so modified:

_ul {b if p < n} :

_ul20 the occurrences of the p first arguments are replaced in the function's body by the corresponding p given values,
_ul20 a function waiting for missing n-p values is created,
_ul20 and its reference is returned.
_ul20 example:
{pre
'{{lambda {:x :y} ... :y ... :x ...} hello} 
-> '{lambda {:y} ... :y ... hello ...} // replaces :x by hello
-> LAMB_123 // the new functions's reference
}
_ul20 finally called with the value {b world} this function will return ... world ... hello ...

_ul {b if p = n} :
_ul20 the occurences of the n arguments are replaced in the function's body by the corresponding p given values, 
_ul20 the body is evaluated and the result is returned.
_ul20 example
{pre
'{{lambda {:x :y} ... :y ... :x ...} hello world}
-> '{{lambda {:y} ... :y ... hello ...} world} // replaces :x by hello
-> '{{lambda {} ... world ... hello ...} } // replaces :y by world
-> ... world ... hello ... // the value
}

_ul {b if p > n} :
 
_ul20 the occurrences of the n-1 first arguments are replaced in the function's body by the corresponding n-1 given values, 
_ul20 the occurrences of the last argument are replaced in the body by the sequence of p-n supernumerary values, 
_ul20 the body is evaluated and the result is returned.
_ul20 example:
{pre
'{{lambda {:x :y} ... :y ... :x ...} hello world good morning}
-> '{{lambda {:y} ... :y ... hello ...} world good morning} 
-> '{{lambda {} ... world good morning ... hello ...}} 
-> ... world good morning ... hello ... // the value
} 
}

_h2 2.1) lambdas

_p Lambdas can be used as arguments, as return values, to create local blocks of code and can be applyed on any number of values. Geeks give names for such a behaviour: {i first class, partial application, currying, variadicity, ...}.

_p A lambda has access to user defined constants|functions and eventual built-in primitives, but is a {b pure black box}, totally independent of the context and without any side effect. At the time of invocation, the occurrences of the lambda's arguments {i and they alone} are replaced in the lambda's body by the given values. Outer lambda's variables are inaccessible. If they are required they must be {i manually redefined} in the inner lambda's list of arguments and their values assigned (more later...).

_p In short lambdatalk doesn't know what geeks call {i closures}, but thanks to the lambdas' behaviour there is a life without closures.

_p More to see in the page [[lambda]].

_h2 2.2) defs

_p Lambdas can be deeply nested and expressions could become completely obfuscated. For convenience we therefore introduce a second special form {code '{def name expression}} which will greatly simplify writing and reading code. This second special form {code def} simply evaluates {code expression}, stores the result in a dictionary (initially empty) and returns {code name} as a reference, a {i constant}. Constants thus defined are global and immutable. Using defs we can split the IIFE seen in the introduction

{pre
'{{lambda {:x :y} :y :x} hello world}
}

_p into an abstraction and an application:

{pre
'{def SWAP {lambda {:x :y} :y :x}} 
-> {def SWAP {lambda {:x :y} :y :x}}

'{SWAP hello world} 
-> {SWAP hello world}
}

_p We can also define global constants:

{pre
'{def HI hello world} 
-> {def HI hello world}

HI               // remember that words are not evaluated
-> HI            // stay unchanged

'{HI}             // we must bracket the name ...
-> {HI}   // ... to get the value
}

_p Things are similar in a spreadsheet, (Excel, OpenOffice.calc, ...). Remember that in a spreadsheet's cell writing 1+2 displays "1+2" and you must write =1+2 to get the value, "3". Writing PI displays PI and you must write =PI() to get the value, {PI}.

_p What can be done with so little?

_h1 3) data and control structures

_h2 3.1) booleans

{pre
'{def TRUE {lambda {:a :b} :a}} 
-> {def TRUE {lambda {:a :b} :a}}
'{def FALSE {lambda {:a :b} :b}}
-> {def FALSE {lambda {:a :b} :b}}
'{def IF {lambda {:c :a :b}  {:c :a :b}}}
-> {def IF {lambda {:c :a :b}  {:c :a :b}}}

'{IF TRUE white black}
-> {IF TRUE white black}
'{IF FALSE white black}
-> {IF FALSE white black}

'{def CHOOSE
 {lambda {:bool :then :else}
  {IF :bool :then :else}}}
-> {def CHOOSE
 {lambda {:bool :then :else}
  {IF :bool :then :else}}}

'{CHOOSE TRUE white black}
-> {CHOOSE TRUE white black}
'{CHOOSE FALSE white black}
-> {CHOOSE FALSE white black}

}

_p Considering {code '{IF TRUE white black}} it's easy to understand that when the {code IF} function is given the three values awaited, its body becomes {code '{TRUE white black}}, and the {code TRUE} function returns the first value, {b white}. It's not {i magic}, it's just text substitution.

_p The IF function can choose between two words, not two sentences. Lambdas without argument can help, replacing their body by a word.

{pre
'{{CHOOSE TRUE {lambda {} I say white}
              {lambda {} {I say black}}}}
-> {{CHOOSE TRUE {lambda {} I say white} {lambda {} {I say black}}}}
}

_p In fact the CHOOSE function returns a word, the choosen function's reference, not its value. It's the reason why we must embed the whole expression between two curly braces to get the value.

_p Other boolean functions can be built, for instance AND, OR, NOT, XOR,...

{pre
'{def AND {lambda {:a :b} {IF :a :b FALSE}}}
-> {def AND {lambda {:a :b} {IF :a :b FALSE}}}
'{def OR {lambda {:a :b} {IF :a TRUE :b}}}
-> {def OR {lambda {:a :b} {IF :a TRUE :b}}}
'{def NOT {lambda {:a} {IF :a FALSE TRUE}}}
-> {def NOT {lambda {:a} {IF :a FALSE TRUE}}}

'{def XOR
 {lambda {:a :b} 
  {OR {AND :a {NOT :b}}
      {AND :b {NOT :a}}}}}
-> {def XOR
 {lambda {:a :b} 
  {OR {AND :a {NOT :b}}
      {AND :b {NOT :a}}}}}

'{AND TRUE FALSE}
-> {AND TRUE FALSE}
'{AND TRUE TRUE}
-> {AND TRUE TRUE}
'{OR TRUE FALSE}
-> {OR TRUE FALSE}
'{OR FALSE FALSE}
-> {OR FALSE FALSE}
'{NOT TRUE}
-> {NOT TRUE}
'{NOT FALSE}
-> {NOT FALSE}
...
}

_h2 3.2) pairs

_p Words are the fundamental data lambdas work on. Pairs will be aggregations of two words.

{pre
'{def CONS {lambda {:a :b :c} {:c :a :b}}}
-> {def CONS {lambda {:a :b :c} {:c :a :b}}}
'{def HEAD {lambda {:p} {:p TRUE}}}
-> {def HEAD {lambda {:p} {:p TRUE}}}
'{def TAIL {lambda {:p} {:p FALSE}}}
-> {def TAIL {lambda {:p} {:p FALSE}}}

'{def P {CONS hello world}} 
-> {def P {CONS hello world}}
'{HEAD {P}}
-> {HEAD {P}}
'{TAIL {P}}
-> {TAIL {P}}
}

_p Note that {code CONS} waits for three values. So {code '{def P {CONS hello world}}} getting only two values is replaced by a partial application returning a function '{lambda {:c} {:c hello world}} waiting for the missing values. When {code '{HEAD {P}}} is invoked, the expression becomes

{pre 
'{{lambda {:p} {:p {lambda {:a :b} :a}}}      // HEAD
 {lambda {:c} {:c hello world}}}             // P
-> '{{lambda {:c} {:c hello world}} {lambda {:a :b} :a}}
-> '{{lambda {:a :b} :a} hello world}
-> hello
}

_p It must be understood that for instance in the FOURTH line {code '{lambda {:a :b} :a}} has been evaluated to a word, the function's reference {b ref}, and it's this word which is replaced in {code '{:c hello world}}, leading to {code '{ref hello world}} then to {code '{{lambda {:a :b} :a} hello world}} and finally to {b hello}. One more time it's not {i magic} it's just text substitution.

_p Pairs can be nested very deeply. As an example we show, without explanations, how with booleans and pairs we have everything required to build a binary numbers based arithmetic, beginning with a 4 bits adder:

{uncover http://rosettacode.org/mw/images/0/0e/4bitsadder.png 100 600 a 4 bits adder}
{pre

'{def halfAdder
 {lambda {:a :b}
  {CONS {AND :a :b} 
        {XOR :a :b}}}}
-> {def halfAdder
 {lambda {:a :b}
  {CONS {AND :a :b} 
        {XOR :a :b}}}}

'{def fullAdder 
 {lambda {:a :b :c}
  {{lambda {:b :ha1}
  {{lambda {:ha1 :ha2}    
           {CONS {OR {HEAD :ha1} {HEAD :ha2}} {TAIL :ha2}}
   } :ha1 {halfAdder {TAIL :ha1} :b}} 
   } :b {halfAdder :c :a}} }}
-> {def fullAdder 
 {lambda {:a :b :c}
  {{lambda {:b :ha1}
  {{lambda {:ha1 :ha2}    
           {CONS {OR {HEAD :ha1} {HEAD :ha2}} {TAIL :ha2}}
   } :ha1 {halfAdder {TAIL :ha1} :b}} 
   } :b {halfAdder :c :a}} }}

'{def 4bitsAdder
 {lambda {:a4 :a3 :a2 :a1 
          :b4 :b3 :b2 :b1}
  {{lambda {:a4 :a3 :a2 :b4 :b3 :b2 :fa1}
  {{lambda {:a4 :a3 :b4 :b3 :fa1 :fa2}
  {{lambda {:a4 :b4 :fa1 :fa2 :fa3}   
  {{lambda {:fa1 :fa2 :fa3 :fa4}
           {HEAD :fa4} {TAIL :fa4} {TAIL :fa3}
                       {TAIL :fa2} {TAIL :fa1}
   } :fa1 :fa2 :fa3 {fullAdder :a4 :b4 {HEAD :fa3}}}
   } :a4 :b4 :fa1 :fa2 {fullAdder :a3 :b3 {HEAD :fa2}}}
   } :a4 :a3 :b4 :b3 :fa1 {fullAdder :a2 :b2 {HEAD :fa1}}}
   } :a4 :a3 :a2 :b4 :b3 :b2 {halfAdder :a1 :b1} 
}}}
-> {def 4bitsAdder
 {lambda {:a4 :a3 :a2 :a1 
          :b4 :b3 :b2 :b1}
  {{lambda {:a4 :a3 :a2 :b4 :b3 :b2 :fa1}
  {{lambda {:a4 :a3 :b4 :b3 :fa1 :fa2}
  {{lambda {:a4 :b4 :fa1 :fa2 :fa3}   
  {{lambda {:fa1 :fa2 :fa3 :fa4}
           {HEAD :fa4} {TAIL :fa4} {TAIL :fa3}
                       {TAIL :fa2} {TAIL :fa1}
   } :fa1 :fa2 :fa3 {fullAdder :a4 :b4 {HEAD :fa3}}}
   } :a4 :b4 :fa1 :fa2 {fullAdder :a3 :b3 {HEAD :fa2}}}
   } :a4 :a3 :b4 :b3 :fa1 {fullAdder :a2 :b2 {HEAD :fa1}}}
   } :a4 :a3 :a2 :b4 :b3 :b2 {halfAdder :a1 :b1} 
}}}

'{4bitsAdder FALSE TRUE TRUE TRUE         //   0111
            FALSE FALSE FALSE TRUE}      // + 0001
-> {4bitsAdder FALSE TRUE TRUE TRUE         
            FALSE FALSE FALSE TRUE}          // = 1000
}

_p Don't be frightened by the apparent complexity of this code. Detail doesn't matter here. Note that everything is reduced to four nested IIFEs. And note that the addition is built without any loop structure, which helps to understand the "static behaviour" of logical gates inside a CPU. In these pages [[4bit_adder]] and [[8bit_adder|?view=4bit_adder2]] is shown how numbers can be added in the range [0..256].

_h2 3.3) lists and recursion

_p Let's add two useful tweened functions

{pre
'{def NIL {lambda {:a} TRUE}}
-> {def NIL {lambda {:a} TRUE}} 
'{def NILP {lambda {:p} {:p {lambda {:a :b} FALSE}}}}
-> {def NILP {lambda {:p} {:p {lambda {:a :b} FALSE}}}}

'{NILP NIL}
-> {NILP NIL}
'{NILP {P}}
-> {NILP {P}}
}

_p It's easy to understand that {code NILP} is a predicate function returning {b TRUE} if given the word {code NIL} and {b FALSE} if given a pair.

_p Let's compose pairs to build lists ending with {code NIL}.

{pre
'{def L {CONS hello
       {CONS brave
       {CONS new
       {CONS world
             NIL}}}}}
-> {def L {CONS hello
       {CONS brave
       {CONS new
       {CONS world
             NIL}}}}}
}

_p Note that a list is just a pair whose second term is a list. It's a first example of {b recursive data structure}. Using the {code HEAD & TAIL} accessors let's get each term and test the {b rest} successively:

{pre 
.  {b get the first                  & test the rest }

'{NILP {L}}
                                    -> {NILP {L}}
'{HEAD {L}}                       & '{NILP {HEAD {L}}}                  
-> {HEAD {L}}                            -> {NILP {TAIL {L}}}

'{HEAD {TAIL {L}}}                & '{NILP {HEAD {L}}}                  
-> {HEAD {TAIL {L}}}                            -> {NILP {TAIL {L}}}

'{HEAD {TAIL {TAIL {L}}}}         & '{NILP {HEAD {TAIL {L}}}}              
-> {HEAD {TAIL {TAIL {L}}}}                              -> {NILP {TAIL {TAIL {L}}}}

'{HEAD {TAIL {TAIL {TAIL {L}}}}}  & '{NILP {HEAD {TAIL {TAIL {L}}}}}          
-> {HEAD {TAIL {TAIL {TAIL {L}}}}}                            -> {NILP {TAIL {TAIL {TAIL {L}}}}}

'{NILP {TAIL {TAIL {TAIL {TAIL {L}}}}}} 
                                    -> {NILP {TAIL {TAIL {TAIL {TAIL {L}}}}}}
}

_p Sounds a recursive process!

_p We now have everything we need to build a function, {code DISP}, {i recursively} diplaying  the content of the list {code L}.

{pre
'{def DISP
 {lambda {:l}
  {{IF {NILP :l}
       {lambda {:l} }
       {lambda {:l} {HEAD :l} {DISP {TAIL :l}}}} :l}}}
-> {def DISP
 {lambda {:l}
  {{IF {NILP :l}
       {lambda {:l} }
       {lambda {:l} {HEAD :l} {DISP {TAIL :l}}}} :l}}}

'{DISP {L}}    
-> {DISP {L}}
}

_p It's funny, it does work, but how does it work?

{blockquote
{center {i This section can be skipped in a first reading.}}

_p Giving a name to the two inner lambdas in {code DISP}

{pre
'{def YES {lambda {:l} }} 
-> {def YES {lambda {:l} }}
'{def NO {lambda {:l} {HEAD :l} {DISP {TAIL :l}}}} 
-> {def NO {lambda {:l} {HEAD :l} {DISP {TAIL :l}}}}
}

_p we can write a shorter and more readable function so called {code SDISP}

{pre
'{def SDISP {lambda {:l} {{IF {NILP :l} YES NO} :l}}}
-> {def SDISP {lambda {:l} {{IF {NILP :l} YES NO} :l}}}

'{SDISP {L}}
-> {SDISP {L}}
}

_p Note the double curly braces before {code IF}. We met it in {b 3.1) booleans} where the chosen lambda YES or NO must be called, here applied to {code :l}. The {code SDISP} function is easy to trace

{pre 
{SDISP {L}}
-> '{{lambda {:l} {{IF {NILP :l} YES NO} :l}} {L}}
-> '{{IF {NILP {L}} YES NO} {L}}             // '{NILP {L}} -> FALSE
-> '{{IF FALSE YES NO} {L}}                  // FALSE -> NO
-> '{NO {L}}
-> '{{lambda {:l} {HEAD :l} {DISP {TAIL :l}}} {L}}
-> '{HEAD {L}} '{DISP {TAIL {L}}}             // '{HEAD {L}} -> hello
-> hello '{DISP {TAIL {L}}}                  // recurse on '{TAIL {L}}
}

_p and repeated until L: is NIL

{pre
-> hello brave new world '{{lambda {:l} {{IF {NILP :l} YES NO} :l}} NIL}
-> hello brave new world '{{IF {NILP NIL} YES NO} NIL}  // '{NILP NIL} -> TRUE
-> hello brave new world '{{IF TRUE YES NO} NIL}        // HEAD -> YES
-> hello brave new world '{YES NIL}
-> hello brave new world '{{lambda {:l} } NIL}          // -> empty
-> hello brave new world                               // stop
}
}

_p In short a recursive function is built on such a following pattern

{pre

'{def RECUR                        // begin function
 {lambda {args}                    // begin lambda
  {                                 // begin future apply
   {IF                               // begin if
       {NILP args}                    // boolean
       {lambda {args} ...}            // then base case
       {lambda {args} {RECUR ...}}    // else recurse
   }                                 // end if
   args                              // apply on args
  }                                 // end apply
 }                                 // end lambda
}                                 // end function

}

_p In short the two inner lambdas are first evaluated to two function's reference. As long as {code '{NILP args}} returns FALSE the {code IF} functionn leads to the second function's ref, the function is applied to {code args} and the {code '{RECUR ...}} recursive block is returned. When {code '{NILP args}} returns FALSE the first function's ref is chosen, applied to {code args} and the {code ...} base case is returned. Using inside lambdas prevents evaluations until the good term is chosen.

_p Now, following the same pattern, we build some more functions working on lists

{pre

'{def REVERSE

{def REVERSE.r                       // recursive part
  {lambda {:a :b}
   {{IF {NILP :a}
    {lambda {:a :b} :b}
    {lambda {:a :b} {REVERSE.r {TAIL :a} {CONS {HEAD :a} :b}}}}
     :a :b}}}

{lambda {:a} {REVERSE.r :a NIL}}}   // init and recurse
-> {def REVERSE
 {def REVERSE.r
  {lambda {:a :b}
   {{IF {NILP :a}
    {lambda {:a :b} :b}
    {lambda {:a :b} {REVERSE.r {TAIL :a} {CONS {HEAD :a} :b}}}}
     :a :b}}}
 {lambda {:a} {REVERSE.r :a NIL}}}

'{DISP {REVERSE {L}}}
-> {DISP {REVERSE {L}}}

'{def APPEND

{def APPEND.r
  {lambda {:a :b}
   {{IF {NILP :b}
    {lambda {:a :b} :a}
    {lambda {:a :b} {APPEND.r {CONS {HEAD :b} :a}
                                    {TAIL :b}}}  } :a :b}}}

{lambda {:a :b} {APPEND.r {REVERSE :a} :b}}} 
-> {def APPEND                            
 {def APPEND.r
  {lambda {:a :b}
   {{IF {NILP :b}
    {lambda {:a :b} :a}
    {lambda {:a :b} {APPEND.r {CONS {HEAD :b} :a}
                                    {TAIL :b}}}  } :a :b}}}
 {lambda {:a :b} {APPEND.r {REVERSE :a} :b}}}

'{DISP {APPEND {L} {REVERSE {L}}}}
-> {DISP {APPEND {L} {REVERSE {L}}}}

'{def LENGTH
 {lambda {:l}
  {{IF {NILP :l}
   {lambda {:l} }
   {lambda {:l} . {LENGTH {TAIL :l}}}} :l}}}
-> {def LENGTH
 {lambda {:l}
  {{IF {NILP :l}
   {lambda {:l} }
   {lambda {:l} . {LENGTH {TAIL :l}}}} :l}}}

'{LENGTH {L}}
-> {LENGTH {L}}   // a primitive notation for the number 4
}

_p The last function, {code LENGTH}, could lead to a list based arithmetic, beginning with the addition - just {b APPEND}ing two lists - and so on. See such an approach in the page [[meta4]]. In this page we will choose another approach sketched in the {b 4.4) arithmetic} section.

_h2 3.4) the Y-combinator

_p It may be interesting to know that all these recursive algorithms can be written without using the second special form, {code def}, as true λ calculus expressions exclusively made of words, abstractions and applications. The trouble is that the body of a recursive function contains its name and we need the {code def} second special form to give a name.
 
_p Here comes the strange {b Y-combinator}!

_p  Let's focus on the {code DISP} function. We add a new argument, {code :f}, acting as a {i fix point} and build a new {i almost recursive} function, {code ADISP}, which will be called by some {i magic} {code Y} combinator acting as a {i bridge}.

{pre
1) adding a new argument, the fix-point:
'{def ADISP
 {lambda {:f :l}
  {{IF {NILP :l}
   {lambda {:f :l} } 
   {lambda {:f :l} {HEAD :l} {:f :f {TAIL :l}}}} :f :l}}}
-> {def ADISP
 {lambda {:f :l}
  {{IF {NILP :l}
   {lambda {:f :l} } 
   {lambda {:f :l} {HEAD :l} {:f :f {TAIL :l}}}} :f :l}}}

2) defining the bridge:
'{def Y {lambda {:f} {:f :f}}}  // :f is applied to itself
-> {def Y {lambda {:f} {:f :f}}}                       p

3) composing boths:
'{{Y ADISP} {L}}                // ADISP is given as the fix point
-> {{Y ADISP} {L}}
}

_p Got it? We have replaced a global definition, {code DISP}, by a local one, {code :f}, and have defined a very small function acting as a bridge, the {b Y-combinator}. Exit the global name. Now we can go further and {i glue} {code Y} and {code ADISP} into a single one {code YDISP}:

{pre
'{def YDISP
 {lambda {:l}
  {{{lambda {:f} {:f :f}} 
   {lambda {:f :l}
    {{IF {NILP :l}
     {lambda {:f :l} } 
     {lambda {:f :l} {HEAD :l} {:f :f {TAIL :l}}}} :f :l}}} :l}}} 
-> {def YDISP
 {lambda {:l}
{{{lambda {:f} {:f :f}} 
{lambda {:f :l}
  {{IF {NILP :l}
   {lambda {:f :l} } 
   {lambda {:f :l} {HEAD :l} {:f :f {TAIL :l}}}} :f :l}}} :l}}}

'{YDISP {L}}
-> {YDISP {L}}
}

_p We can even forget the name {code YDISP}, building an IIFE:

{pre
'{{lambda {:l}
 {{{lambda {:f} {:f :f}} 
  {lambda {:f :l}
   {{IF {NILP :l}
    {lambda {:f :l} } 
    {lambda {:f :l} {HEAD :l} {:f :f {TAIL :l}}}} :f :l}}} :l}}
 {L}} 
-> {{lambda {:l}
{{{lambda {:f} {:f :f}} 
{lambda {:f :l}
  {{IF {NILP :l}
   {lambda {:f :l} } 
   {lambda {:f :l} {HEAD :l} {:f :f {TAIL :l}}}} :f :l}}} :l}}
 {L}} 
}

_p and finally, replacing every names by their lambda expressions recalled below

{pre
'{def TRUE {lambda {:a :b} :a}} 
'{def FALSE {lambda {:a :b} :b}}
'{def IF {lambda {:c :a :b}  {:c :a :b}}}
'{def CONS {lambda {:a :b :c} {:c :a :b}}}
'{def HEAD {lambda {:p} {:p TRUE}}}
'{def TAIL {lambda {:p} {:p FALSE}}}
'{def NIL {lambda {:a} TRUE}}
'{def NILP {lambda {:p} {:p {lambda {:a :b} FALSE}}}}

'{def L {{lambda {:a :b :c} {:c :a :b}} hello
       {{lambda {:a :b :c} {:c :a :b}} brave
       {{lambda {:a :b :c} {:c :a :b}} new
       {{lambda {:a :b :c} {:c :a :b}} world
        {lambda {:a}
        {lambda {:a :b} :a}}}}}}}
}

_p we get this deeply nested expression

{pre
'{{lambda {:l}
 {{{lambda {:f} {:f :f}} 
   {lambda {:f :l}
  {{{lambda {:c :a :b}  {:c :a :b}} 
    {{lambda {:p} {:p 
      {lambda {:a :b} 
       {lambda {:a :b} :b}}}} :l}
        {lambda {:f :l} } 
         {lambda {:f :l} 
         {{lambda {:p} {:p 
           {lambda {:a :b} :a}}} :l} {:f :f 
           {{lambda {:p} {:p 
             {lambda {:a :b} :b}}} :l}}}} :f :l}}} :l}} 
             {{lambda {:a :b :c} {:c :a :b}} hello
             {{lambda {:a :b :c} {:c :a :b}} brave
             {{lambda {:a :b :c} {:c :a :b}} new
             {{lambda {:a :b :c} {:c :a :b}} world
               {lambda {:a} 
                {lambda {:a :b} :a}}}}}}}

-> {{lambda {:l}
 {{{lambda {:f} {:f :f}} 
   {lambda {:f :l}
  {{{lambda {:c :a :b}  {:c :a :b}} 
    {{lambda {:p} {:p 
      {lambda {:a :b} 
       {lambda {:a :b} :b}}}} :l}
        {lambda {:f :l} } 
         {lambda {:f :l} 
         {{lambda {:p} {:p 
           {lambda {:a :b} :a}}} :l} {:f :f 
           {{lambda {:p} {:p 
             {lambda {:a :b} :b}}} :l}}}} :f :l}}} :l}} 
             {{lambda {:a :b :c} {:c :a :b}} hello
             {{lambda {:a :b :c} {:c :a :b}} brave
             {{lambda {:a :b :c} {:c :a :b}} new
             {{lambda {:a :b :c} {:c :a :b}} world
               {lambda {:a} 
                {lambda {:a :b} :a}}}}}}} 
}

_p Nothing but a deeply nested composition of {i abstractions} and {i applications} working on {i words}, in a pure λ-calculus style. And it's not magic, it's just text substitution.

_p {b Note:} According to [[Wikipedia|https://en.wikipedia.org/wiki/Turing_machine]] "A Turing machine is a mathematical model of computation that defines an abstract machine  which manipulates symbols on a strip of tape according to a table of rules."

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

_p I guess that storing the two processes {b abstraction} and {b application} in a Turing's machine table of rules and writing the previous expression on its stripe should display: {b hello brave new world}.

_p You could see how the Universal Turing Machine can be written using plain lambdatalk in this page [[tm]].

_h1 4) applications

_p Until now, bear in mind that we used nothing but {i lambdas & defs}. We defined pairs, lists and a loop mechanism, recursion, to play with.
_p Let's go a little further, reducing explanations to a bare minimum in order to keep this page short and not be buried in details. The goal is to understand how apparently unreachable algorithms - at least at this level - can be defined as a direct application of the powerful pattern we have just defined, the {i recursion}.

_h2 4.1) towers of hanoï

_p A set of {b n} 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, {b "never put a disk on a smaller one "}. The code is built on a doubly recursive function. Because numbers are not defined at this level (see arithmetic later) the set of disks will be represented by the list of 5 items {code L} defined in section 3).

{pre
'{def HANOI
 {lambda {:n :from :to :via}
  {{IF {NILP :n}
   {lambda {:n :from :to :via} }
   {lambda {: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}}}
-> {def HANOI
 {lambda {:n :from :to :via}
  {{IF {NILP :n}
   {lambda {:n :from :to :via} }
   {lambda {: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 {L} A B C} ->     // four disks and three rods
{HANOI {L} A B C}
}

_p Note that the line "{code '{br} move '{l.length :n} from tower :from to tower :to}" contains a constant, {code '{br}}, which is supposed not to be known at this level. It's an HTMLelement used to break lines and produce a readable display. We could forget it.

_h2 4.2) the hilbert's curve

_p This is an example of two mutually recursive functions, {code LEFT} and {code RIGHT}, used to produce a sequence of moves and turns sent to a graphical function {code turtle}, an external device.

{pre
'{def LEFT
 {lambda {:d :n}
  {{IF {NILP :n}
   {lambda {:d :n} }
   {lambda {:d :n} 
               T90      {RIGHT :d {TAIL :n}}
               M:d T-90 {LEFT  :d {TAIL :n}}
               M:d      {LEFT  :d {TAIL :n}}
               T-90 M:d {RIGHT :d {TAIL :n}}
               T90
   }} :d :n}}}
-> {def LEFT
 {lambda {:d :n}
  {{IF {NILP :n}
   {lambda {:d :n} }
   {lambda {:d :n} 
               T90      {RIGHT :d {TAIL :n}}
               M:d T-90 {LEFT  :d {TAIL :n}}
               M:d      {LEFT  :d {TAIL :n}}
               T-90 M:d {RIGHT :d {TAIL :n}}
               T90
   }} :d :n}}}

'{def RIGHT
 {lambda {:d :n}
  {{IF {NILP :n}
   {lambda {:d :n} }
   {lambda {:d :n}
               T-90    {LEFT  :d {TAIL :n}}
               M:d T90 {RIGHT :d {TAIL :n}}
               M:d     {RIGHT :d {TAIL :n}}
               T90 M:d {LEFT  :d {TAIL :n}}
               T-90
  }} :d :n}}}
-> {def RIGHT
 {lambda {:d :n}
  {{IF {NILP :n}
   {lambda {:d :n} }
   {lambda {:d :n}
               T-90    {LEFT  :d {TAIL :n}}
               M:d T90 {RIGHT :d {TAIL :n}}
               M:d     {RIGHT :d {TAIL :n}}
               T90 M:d {LEFT  :d {TAIL :n}}
               T-90
  }} :d :n}}}
}

_p We build a Hilbert curve until the 5{sup th} depth using a list containing 5 dots

{pre
'{def H5 {CONS . {CONS . {CONS . {CONS . {CONS . NIL}}}}}}
-> {def H5 {CONS . {CONS . {CONS . {CONS . {CONS . NIL}}}}}}
}
_p Calling {code '{LEFT 10 {H5}}} produces a sequence of {code 2387} words starting with {code T90 T-90 T90 T-90 T90  M10 T-90  M10  T-90 M10  T90 M10 T90 T-90  M10 T90  M10  T90 M10  T-90 M10 T-90  M10 T90  M10  T90 M10  T-90 T90 M10 T90  M10 T-90  M10  T-90 M10  T90 T-90 M10 T-90 T90 T-90  M10 T90  M10  T90 M10 ...}

_p These words are sent to a SVG graphical "device" which understands {code M & T} as drawing procedures called on numbers {code 10, 90, -90}:

{pre
'{{SVG}
 {curve #000 5 5 0 {LEFT 10 {H5}}}
}

with:

'{def SVG
     svg {@ width="320"          // standard HTML syntax
            height="320"
            style="box-shadow:0 0 8px #000;"}}
-> {def SVG svg {@ width="320" height="320" style="box-shadow:0 0 8px #000;  background:#fff;"}}

'{def curve
 {lambda {:c :s}
   {path {@ d="M {turtle :s}"   // standard SVG syntax
            stroke=":c" 
            stroke-width="1" 
            fill="transparent"}}
}}
-> {def curve
 {lambda {:c :s}
   {path {@ d="M {turtle :s}" stroke=":c" stroke-width="1" fill="transparent"}}
}}

}

_p which displays

{center
{{SVG}
  {curve #000 5 5 0 {LEFT 10 {H5}}}
 }
}

_h2 4.3) fractal trees

{pre
'{def TREE 
 {lambda {:e :s :k :a :b}
  {{IF {NILP :k}
   {lambda {:e :s :k :a :b}
              T-30 M:e T120 M:e T120 M:e T150}
   {lambda {:e :s :k :a :b}
              M:s T:a 
              {TREE :e :s {TAIL :k} :a :b} T-:a T-:b
              {TREE :e :s {TAIL :k} :a :b} T:b M-:s}}
            :e :s :k :a :b}}}
-> {def TREE 
 {lambda {:e :s :k :a :b}
  {{IF {NILP :k}
   {lambda {:e :s :k :a :b} 
               T-30 M:e T120 M:e T120 M:e T150}
   {lambda {:e :s :k :a :b}
          M:s T:a 
          {TREE :e :s {TAIL :k} :a :b}
          T-:a T-:b
          {TREE :e :s {TAIL :k} :a :b}
          T:b M-:s}}
     :e :s :k :a :b}}}
}

_p Calling {code '{tree 10 50 {H5} 45 45}} produces {b 410} words starting with {code M50 T45 M50 T45 M50 T45 M50 T45 M50 T45 T-30 M10 T120 M10 T120 M10 ...}. These words are sent to the SVG graphical "device" which understands {code M & T} as drawing procedures called on numbers {code 50, 45, -30, 10, ...}.

_p And writing

{pre
'{{SVG}
  {curve #f00 150 250 180 {TREE 10 50 {H5} 45 45}}
  {curve #0f0 160 290 180 {TREE 10 60 {H5} 30 50}}
  {curve #00f 140 310 180 {TREE 10 60 {H5} 20 50}}
}}

_p we get

{center
 {{SVG}
  {curve #f00 150 250 180 {TREE 10 50 {H5} 45 45}}
  {curve #0f0 160 290 180 {TREE 10 60 {H5} 30 50}}
  {curve #00f 140 310 180 {TREE 10 60 {H5} 20 50}} 
}}

_p See also [[fern]].

_h2 4.4) arithmetic

_p Note that, until now, except in the outer devices used to display graphics, {b we never used numbers} which don't exist at the λ-calculus level. Let's build them from scratch.

_p This is how Giuseppe Peano defines the infinite set of natural numbers:

{center {pre N = '{0, succ(0), succ(succ(0)), ...}}}

_p How can we implement that? See [[meta5]] for natural numbers implemented as lists. This is how Alonzo Church encodes {b 0} and the {b succ}essor function:

{pre
'{def ZERO FALSE} -> {def ZERO FALSE}
'{def SUCC {lambda {:n :f :x} {:f {:n :f :x}}}} -> {def SUCC {lambda {:n :f :x} {:f {:n :f :x}}}}
}

_p Let's define the first natural numbers

{pre
'{def ONE {SUCC {ZERO}}}
-> {def ONE {SUCC {ZERO}}}
'{def TWO {SUCC {ONE}}}
-> {def TWO {SUCC {ONE}}}
'{def THREE {SUCC {TWO}}}
-> {def THREE {SUCC {TWO}}}
'{def FOUR {SUCC {THREE}}}
-> {def FOUR {SUCC {THREE}}}
'{def FIVE {SUCC {FOUR}}}
-> {def FIVE {SUCC {FOUR}}}
'{def SIX {SUCC {FIVE}}}
-> {def SIX {SUCC {FIVE}}}
...
}

_p Displaying numbers as functions looks like {code _LAMB_xxx} and it's not sexy, so we need a helper function to display Church numbers as decimal integers

{pre
'{def CHURCH {lambda {:n} {:n {lambda {:x} {+ :x 1}} 0}}} 
-> {def CHURCH {lambda {:n} {:n {lambda {:x} {+ :x 1}} 0}}}

'{CHURCH {ZERO}}
-> {CHURCH {ZERO}}
'{CHURCH {ONE}}
-> {CHURCH {ONE}}
...
'{CHURCH {SIX}}
-> {CHURCH {SIX}}
}

_p Note that replacing {code '{lambda {:n} {:n {lambda {:x} {+ :x 1}} 0}}} by {code '{lambda {:n} {:n {lambda {:x} . :x} _}}}, a function which doesn't use javascript maths, (+ 0 1), supposed not to be available at this level, numbers would be displayed as lists of dots with an ending "_". For instance  {b SIX} would be displayed as "{b . . . . . . _}", it's a matter of choice.

_p After the {b SUCC} function we need a function to get the {b PRED}ecessor of a number

{pre
'{def PRED
 {lambda {:n}
  {HEAD {{:n {lambda {:p} {CONS {TAIL :p} {SUCC {TAIL :p}}}}} 
                          {CONS {ZERO} {ZERO}}}}}}               
-> {def PRED
 {lambda {:n}
  {HEAD {{:n {lambda {:p} {CONS {TAIL :p} {SUCC {TAIL :p}}}}} 
  {CONS {ZERO} {ZERO}}}}}}

'{CHURCH {PRED {TWO}}}  
-> {CHURCH {PRED {TWO}}}
'{CHURCH {PRED {ONE}}}  
-> {CHURCH {PRED {ONE}}} 
'{CHURCH {PRED {ONE}}} 
-> {CHURCH {PRED {ONE}}}     // nothing exists before ZERO
}

_p And a predicate function testing if a number is ZERO

{pre
'{def ZEROP {lambda {:n} {:n {lambda {:x} FALSE} TRUE}}}
-> {def ZEROP {lambda {:n} {:n {lambda {:x} FALSE} TRUE}}}

'{ZEROP {ZERO}}
-> {ZEROP {ZERO}}
'{ZEROP {ONE}}
-> {ZEROP {ONE}}
}

_p We can now build a first set of basic operators

{pre
'{def ADD {lambda {:n :m :f :x} {{:n :f} {:m :f :x}}}} 
-> {def ADD {lambda {:n :m :f :x} {{:n :f} {:m :f :x}}}}

'{CHURCH {ADD {TWO} {FIVE}}}
-> {CHURCH {ADD {TWO} {FIVE}}}

'{def SUB {lambda {:m :n} {{:n PRED} :m}}} 
-> {def SUB {lambda {:m :n} {{:n PRED} :m}}}

'{CHURCH {SUB {FIVE} {TWO}}}
-> {CHURCH {SUB {FIVE} {TWO}}}

'{def MUL {lambda {:n :m :f :x} {:n {:m :f} :x}}}      
-> {def MUL {lambda {:n :m :f :x} {:n {:m :f} :x}}}

'{CHURCH {MUL {TWO} {FIVE}}}
-> {CHURCH {MUL {TWO} {FIVE}}}

'{def POW {lambda {:n :m :f :x} {{:m :n :f} :x}}}      
-> {def POW {lambda {:n :m :f :x} {{:m :n :f} :x}}}

'{CHURCH {POW {TWO} {FIVE}}}
-> {CHURCH {POW {TWO} {FIVE}}}

'{def IFAC
 {lambda {:n}
  {TAIL {{:n {lambda {:p}
   {CONS {SUCC {HEAD :p}} {MUL {HEAD :p} {TAIL :p}}}}}
   {CONS {ONE} {ONE}}}}}}   
-> {def IFAC
 {lambda {:n}
  {TAIL {{:n {lambda {:p}
   {CONS {SUCC {HEAD :p}} {MUL {HEAD :p} {TAIL :p}}}}}
   {CONS {ONE} {ONE}}}}}}

'{CHURCH {IFAC {SIX}}}               // 6!
-> 720                         
'{CHURCH {IFAC {MUL {TWO} {FOUR}}}}  // 8!
-> 40320
}

_p Note that pairs are used in the definition of the {code PRED} and {code IFAC} functions, a "trick" due to a student of Alonzo Church, Stephen Cole Kleene. All previous functions are built on iterative processes, {b Church numbers are iterators {i per se}}. 
_p We are going to use recursion to define an alternative version of the factorial, {code RFAC}, the euclidean division {code DIV}, the modulo function {code MOD} and the greater common divisor {code GCD}.

{pre
'{def RFAC
 {lambda {:n}
  {{IF {ZEROP :n}
   {lambda {:n} {ONE}}
   {lambda {:n} {MUL :n {RFAC {PRED :n}}}}} :n}}}
-> {def RFAC
 {lambda {:n}
  {{IF {ZEROP :n}
   {lambda {:n} {ONE}}
   {lambda {:n} {MUL :n {RFAC {PRED :n}}}}} :n}}}

'{CHURCH {RFAC {SIX}}}               // 6!
-> 720
'{CHURCH {RFAC {MUL {TWO} {FOUR}}}}  // 8!
-> 40320

'{def DIV                            
  {lambda {:a :b}
   {{IF {ZEROP {SUB :b :a}}
    {lambda {:a :b} {ADD {ONE} {DIV {SUB :a :b} :b}}}
    {lambda {:a :b} {ZERO}}} :a :b}}}
-> {def DIV                            
  {lambda {:a :b}
   {{IF {ZEROP {SUB :b :a}}
    {lambda {:a :b} {ADD {ONE} {DIV {SUB :a :b} :b}}}
    {lambda {:a :b} {ZERO}}} :a :b}}}

'{CHURCH {DIV {FOUR} {TWO}}}
-> {CHURCH {DIV {FOUR} {TWO}}}
'{CHURCH {DIV {FOUR} {THREE}}}
-> {CHURCH {DIV {FOUR} {THREE}}}

'{def MOD                            
 {lambda {:a :b}
  {SUB :a {MUL {DIV :a :b} :b}}}}
-> {def MOD                            
 {lambda {:a :b}
  {SUB :a {MUL {DIV :a :b} :b}}}}

'{CHURCH {MOD {FOUR} {TWO}}}
-> {CHURCH {MOD {FOUR} {TWO}}}
'{CHURCH {MOD {FOUR} {THREE}}}
-> {CHURCH {MOD {FOUR} {THREE}}}

'{def GCD
 {lambda {:a :b}
  {{IF {ZEROP :b} 
   {lambda {:a :b} :a}
   {lambda {:a :b} {GCD :b {MOD :a :b}}}} :a :b}}}
-> {def GCD
 {lambda {:a :b}
  {{IF {ZEROP :b} 
   {lambda {:a :b} :a}
   {lambda {:a :b} {GCD :b {MOD :a :b}}}} :a :b}}}

'{CHURCH {GCD {IFAC {FIVE}} {THREE}}}
-> 3                      // 1*2*3*4*5 = 120 -> gcd(120,3) = 3
'{CHURCH {GCD {IFAC {FOUR}} {FIVE}}} 
-> 1                      // 1*2*3*4 = 24 -> gcd(24,5) = 1
 
}

_h2 4.5) range, map, reduce

_p A functional progamming language without {code map & reduce} misses something.

{prewrap
'{def RANGE
 {lambda {:a :b}
   {{IF {ZEROP {SUB :b :a}}
    {lambda {:a :b} {CONS :b NIL}}
    {lambda {:a :b} {CONS :a {RANGE {SUCC :a} :b}} }} :a :b}}}
-> {def RANGE
 {lambda {:a :b}
   {{IF {ZEROP {SUB :b :a}}
    {lambda {:a :b} {CONS :b NIL}}
    {lambda {:a :b} {CONS :a {RANGE {SUCC :a} :b}} }} :a :b}}}

'{def MAP
 {lambda {:f :l}
  {{IF {NILP :l}
   {lambda {:f :l} NIL}
   {lambda {:f :l} {CONS {:f {HEAD :l}}
                         {MAP :f {TAIL :l}}}}} :f :l}}}
-> {def MAP
 {lambda {:f :l}
  {{IF {NILP :l}
   {lambda {:f :l} NIL}
   {lambda {:f :l} {CONS {:f {HEAD :l}} {MAP :f {TAIL :l}}}}} :f :l}}}

'{def TEN {MUL {TWO} {FIVE}}} = {def TEN {MUL {TWO} {FIVE}}}

'{DISP {MAP CHURCH {RANGE {ONE} {TEN}}}}
-> {DISP {MAP CHURCH {RANGE {ONE} {TEN}}}}

'{DISP {MAP {lambda {:n} {CHURCH {POW {TWO} :n}}}
           {RANGE {ONE} {SIX}}}}
-> 2 4 8 16 32 64
'{DISP {MAP {lambda {:n} {CHURCH {IFAC :n}}} 
           {RANGE {ONE} {SIX}}}}
-> 1 2 6 24 120 720

'{def REDUCE
 {def REDUCE.r
  {lambda {:f :a :b}
   {{IF {NILP :a}
    {lambda {:f :a :b} :b}
    {lambda {:f :a :b} {:f {HEAD :a} {REDUCE.r :f {TAIL :a} :b}}}} :f :a :b}}}
 {lambda {:f :a}
  {REDUCE.r :f :a {ZERO}}}}
-> {def REDUCE
 {def REDUCE.r
  {lambda {:f :a :b}
   {{IF {NILP :a}
    {lambda {:f :a :b} :b}
    {lambda {:f :a :b} {:f {HEAD :a} {REDUCE.r :f {TAIL :a} :b}}}} :f :a :b}}}
 {lambda {:f :z :a}
  {REDUCE.r :f :a :z}}}

'{CHURCH {REDUCE ADD {ZERO} {RANGE {ONE} {TEN}}}}
-> 55                      // '{+ 1 2 3 4 5 6 7 8 9 10}
'{CHURCH {REDUCE MUL {ONE} {RANGE {ONE} {SIX}}}} 
-> 720                     // '{* 1 2 3 4 5 6}
}

_h2 4.6) the left factorial

_p As an application of {code RANGE, MAP & REDUCE} we compute the left factorial {b !n} defined as the sum of the factorials

{pre 
{center !n = Σ{sub i=0}{sup i=n-1}(i!) = 0! + 1! + 2! + 3! ... + (n-1)}
}

{pre
'{def LFAC
 {lambda {:n}
  {{IF {ZEROP :n}
   {lambda {:n} {ZERO}}
   {lambda {:n} {REDUCE ADD {ONE}
                {MAP {lambda {:n}
                {REDUCE MUL {ONE}
                {RANGE {ONE} :n}}}
                {RANGE {ONE} {PRED :n}}}}}} :n}}}
-> {def LFAC
 {lambda {:n}
  {{IF {ZEROP :n}
   {lambda {:n} {ZERO}}
   {lambda {:n} {REDUCE ADD {ONE} {MAP {lambda {:n}
                          {REDUCE MUL {ONE} {RANGE {ONE} :n}}}
          {RANGE {ONE} {PRED :n}}}}}} :n}}}

'{CHURCH {LFAC {TEN}}}
-> 409114      // 5770ms

'{DISP {MAP CHURCH
      {MAP LFAC 
      {RANGE {ZERO} {TEN}}}}}

-> 0 1 2 4 10 34 154 874 5914 46234 409114 
}

_h1 conclusion

_p The {b read & replace} process implemented in lambdatalk makes its evaluator working close to the raw code, a string. It follows two steps:

_ul 1) {b abstraction}: special forms (lambda, def, ...) are first replaced by words, {i lazily}, for instance:
{pre
'{def hypo {lambda {:x :y} {sqrt {+ {* :x :x} {* :y :y}}}}}
-> '{def hypo LAMB_123} 
-> hypo
}
_ul 2) {b application}: then the remaining expressions are replaced from inside out, {i eagerly}, by words, for instance: 
{pre
'{hypo 3 4}
-> '{{lambda {:x :y} {sqrt {+ {* :x :x} {* :y :y}}}} 3 4}
-> '{sqrt {+ {* 3 3} {* 4 4}}} 
-> '{sqrt {+ 9 16}} 
-> '{sqrt 25} 
-> 5
}

_ul 3) the evaluation stops when the code contains only words.

_p Note that lambdas are also created and evaluated in the application step, in the case of partial applications.

_p During the first step, the raw code (the initial string) is immediately reduced to a smaller sequence of words, some of which are pointers to functions that contain substrings that contain pointers to functions ... and so on, {b recursively}.

_p During the second step, it is in this {b tree of strings and substrings} that the evaluations of normal (nested) forms are carried out {b independently}. It's the reason why the computation of a slow computing extensive function inserted in the middle of a page of one million words is not affected by its length. And since {b functions are really independent of any context} - no lexical context, no closure - one could even think of a parallel evaluation, for instance defining lambdas (at least some of them) as [[web-workers|../lambdaspeech/?view=webworker6]] given for free by web browsers.

_p It's all reminiscent of a {i Turing machine}, with its infinite stripe on which a window comes and goes...

_p And so what?

_p What do we care about a language reduced to a dialect of this brave old λ-calculus nobody on earth would use in real life?

_p {b In real life '{lambda talk} is not lost in an empty space.}

_p He is living in a tiny wiki, '{lambda tank}, {i a dwarf installed on top of shoulders of giants}, the modern web browsers, and takes benefit from the powerful web technologies they bring for free and from the huge eco-system at their fingertips.

_p Lambdatalk comes with a dictionary full of Javascript primitives which can help to break the glass ceiling of the λ-calculus, {code sentences, arrays, math, html/css, ...}. For instance, using pure and basic HTML/CSS, it's straightforward to define a function positionning a colored rectangle in the browser's window

{pre
'{def rgb
 {lambda {:y :x :w :h :c}
  {div
   {@ style="position:absolute;     // standard CSS rules
             top::ypx; left::xpx;
             width::wpx; height::hpx;
             background::c;
             border:5px solid #444;"}}}}
-> {def rgb
 {lambda {:y :x :w :h :c}
  {div
   {@ style="position:absolute;
             top::ypx; left::xpx;
             width::wpx; height::hpx;
             background::c;
             border:5px solid #444;"}}}}
}

_p and call it in a global container

{pre
'{div
  {@ style="position:relative;
            top:0; left:0;
            width:310px; height:310px;
            margin:auto;
            background:#444;"}
 {rgb 10 50 200 200 #f00} 
 {rgb 90 10 200 200 #0f0}
 {rgb 50 90 200 200 #00f}

{rgb 50 90 160 160 #f0f}
 {rgb 90 50 35 120 #ff0} 
 {rgb 215 90 120 35 #0ff}

{rgb 90 90 120 120 #fff}
}

}

_p to display directly in the browser's window the following graphic

{div
  {@ style="position:relative;
            top:0; left:0;
            width:310px; height:310px;
            margin:auto;
            background:#444;"}
 {rgb 10 50 200 200 #f00} 
 {rgb 90 10 200 200 #0f0}
 {rgb 50 90 200 200 #00f}

{rgb 50 90 160 160 #f0f}
 {rgb 90 50 35 120 #ff0} 
 {rgb 215 90 120 35 #0ff}

{rgb 90 90 120 120 #fff}
}
{center {i I think [[Johannes Itten| https://en.wikipedia.org/wiki/Johannes_Itten]] would have liked this composition.}}

_p Lambdatalk is not limited to two special forms, {code [lambda & def]}, the full set contains {b nine special forms} 
{center {pre [ lambda def let if quote macro script style require ]}}

_p The {code '{let { {var val} ... } expression}} special form is a syntactic sugar for this one {code '{{lambda {var ...} expression} val ...}}, which is our well known IIFE, introducing blocks with local variables. 
_p For instance instead of writing this long IIFE

{pre
'{{lambda {:sqr :x :y}                     // applying a lambda
         {sqrt {+ {:sqr :x} {:sqr :y}}}}
 {lambda {:x} {* :x :x}}                  // to an anonymous function
 3 4}                                     // and two values 
-> {{lambda {:sqr :x :y}
         {sqrt {+ {:sqr :x} {:sqr :y}}}}
 {lambda {:x} {* :x :x}} 
 3 
 4
} 
}

_p you should better write

{pre
'{let                                 
 {                                  // 1) define local functions and vars 
   {:sqr {lambda {:x} {* :x :x}}}   // sqr = function(x) { return x*x }
   {:x 3}                           // x = 3
   {:y 4}                           // y = 4
 } {sqrt {+ {:sqr :x} {:sqr :y}}}   // 2) and compute
}
-> {let 
 { 
  {:x 3}
  {:y 4}
  {:sqr {lambda {:x} {* :x :x}}}
 } {sqrt {+ {:sqr :x} {:sqr :y}}}
}
}

_p enlighting two local variables, x & y, and a local function, sqr.

_p The {code '{if bool then one else two}} special form helps to write algorithms more easily and much more efficient, for instance the factorial of a big number:

{prewrap
'{def fac
 {lambda {:n}
 {if {< :n 1}
 then 1
 else {long_mult :n {fac {- :n 1}}}}}}
-> {def fac
 {lambda {:n}
 {if {< :n 1}
 then 1
 else {long_mult :n {fac {- :n 1}}}}}}

'{fac 500}
-> {fac 500} 
}

_p Arrays are powerful data structures added to the lambdatalk's dictionary. The following set of functions uses the {b de casteljau} algorithm

{pre °°
{def CASTEL.interpol {lambda {:p0 :p1 :t}
  {A.new {+ {* {A.get 0 :p0} {- 1 :t}}
            {* {A.get 0 :p1} :t}}
         {+ {* {A.get 1 :p0} {- 1 :t}}
            {* {A.get 1 :p1} :t}} } }}

{def CASTEL.sub {lambda {:arr :acc :t}
 {if {< {A.length :arr} 2}
 then :acc
 else {CASTEL.sub
 {A.rest :arr} 
 {A.addlast! 
 {CASTEL.interpol {A.get 0 :arr}
 {A.get 1 :arr} :t} :acc} :t} }}}

{def CASTEL.split {lambda {:arr :acc :t :lr}
 {if {< {A.length :arr} 1}
 then :acc
 else {CASTEL.split
 {CASTEL.sub :arr {A.new} :t}
 {if :lr
 then {A.addlast! {A.first :arr} :acc}
 else {A.addfirst! {A.last :arr} :acc} } :t :lr} }}}

{def CASTEL.stretch {lambda {:arr :t0 :t1}
  {CASTEL.split
   {CASTEL.split :arr {A.new} :t0 false} {A.new} :t1 true}}}

{def CASTEL.blossom {lambda {:arr :n}
 {if {< :n 1}
 then :arr
 else {A.new {CASTEL.blossom
 {CASTEL.split :arr {A.new} 0.5 true} {- :n 1}}
 {CASTEL.blossom
 {CASTEL.split :arr {A.new} 0.5 false} {- :n 1}} 
}}}}

{def p0 {A.new 50 60}} -> {p0}
{def p1 {A.new 100 200}} -> {p1}
{def p2 {A.new 300 200}} -> {p2}
{def p3 {A.new 200 280}} -> {p3}
°°
}

_p to display these Bézier curves 
   
{center {{svg.frame 320 320}
{polyline {@ points="{tree2svg {CASTEL.blossom {A.new {p0} {p1} {p2} {p3}} 3}}" {svg.stroke #f00 12} }}
{polyline {@ points="{tree2svg {CASTEL.blossom {A.new {p0} {p1} {p2} {p3}} 0}}" {svg.stroke #888 1} }}
{polyline {@ points="{tree2svg {CASTEL.blossom {CASTEL.stretch {A.new {p0} {p1} {p2} {p3}} 0.25 0.85} 3}}" {svg.stroke #ff0 5}}}
{polyline {@ points="{tree2svg {CASTEL.blossom {CASTEL.stretch {A.new {p0} {p1} {p2} {p3}}  -0.1 1.1} 3}}" {svg.stroke #888 2}}}
{polyline {@ points="{tree2svg {CASTEL.blossom {CASTEL.stretch {A.new {p1} {p0} {p2} {p3}}  -0.1 1.1} 3}}" {svg.stroke #888 2}}}
{polyline {@ points="{tree2svg {CASTEL.blossom {CASTEL.stretch {A.new {p0} {p1} {p3} {p2}}  -0.1 1.1} 4}}" {svg.stroke #888 2}}}
{polyline {@ points="{tree2svg {CASTEL.blossom {CASTEL.stretch {A.new {p0} {p2} {p1} {p3}}  -0.1 1.1} 4}}" {svg.stroke #888 2}}}
{svg.dot {p0}} {svg.dot {p1}} {svg.dot {p2}} {svg.dot {p3}}
}}

{{hide} 
{def CASTEL.interpol {lambda {:p0 :p1 :t}
  {A.new {+ {* {A.get 0 :p0} {- 1 :t}}
            {* {A.get 0 :p1} :t}}
         {+ {* {A.get 1 :p0} {- 1 :t}}
            {* {A.get 1 :p1} :t}} } }}

{def CASTEL.sub {lambda {:arr :acc :t}
 {if {< {A.length :arr} 2}
 then :acc
 else {CASTEL.sub
 {A.rest :arr} 
 {A.addlast! {CASTEL.interpol {A.get 0 :arr}
 {A.get 1 :arr} :t} :acc} :t} }}}

{def CASTEL.stretch {lambda {:arr :t0 :t1}
  {CASTEL.split
   {CASTEL.split :arr {A.new} :t0 false} {A.new} :t1 true}}}

{def CASTEL.blossom {lambda {:arr :n}
 {if {< :n 1}
 then :arr
 else {A.new {CASTEL.blossom {CASTEL.split :arr {A.new} 0.5 true} {- :n 1}}
 {CASTEL.blossom {CASTEL.split :arr {A.new} 0.5 false} {- :n 1}} }}}}

{def tree2svg
 {lambda {:arr}
  {S.replace , by space in {S.replace \[|\] by in {A.disp :arr}}}}}

{def svg.frame
 {lambda {:w :h}
  svg {@ width=":w" height=":h" 
    style="border:1px solid #888; background:#fff; box-shadow:0 0 8px;"}}}

{def svg.stroke
 {lambda {:c :e}
  stroke=":c" stroke-width=":e" fill="transparent"}}

{def svg.dot
 {lambda {:p}
  {circle {@ cx="{A.first :p}" cy="{A.last :p}" r="5" 
             {svg.stroke #000 3}}} }}

{def p0 {A.new 50 60}} -> {p0}
{def p1 {A.new 100 200}} -> {p1}
{def p2 {A.new 300 200}} -> {p2}
{def p3 {A.new 200 280}} -> {p3}
}

_p See also in this page [[bezier]] how can be plotted a Bézier curve out of any canvas or svg frame.

_p Finally useful {b libraries} can be created inline (or borrowed from external sources) to do much more:

{uncover http://epsilonwiki.free.fr/ELS_YAW/data/spreadsheet_1.jpg 50 400 S-expressions in a spreadsheet}
{uncover http://lambdaway.free.fr/workshop/data/turtle_tree_2.jpg 50 590 fractal tree}
{uncover http://epsilonwiki.free.fr/lambdaway_2.0/data/lambdaray_20130329/d1.jpg 50 590 ray-tracing}
{uncover http://epsilonwiki.free.fr/alphawiki_2/data/pforms_coons.jpg 50 590 n-gons in curved shapes}
{uncover http://epsilonwiki.free.fr/alphawiki_2/data/mandel_20160104.jpg 50 590 mandelbrot set}

{{hide}
{def uncover
 {lambda {:im :h1 :h2 :txt}
  {img {@ src=":im"
          style="width:100%;
                 height::h1px;
                 object-fit:cover;
                 -webkit-transition: all 1s;  
                    -moz-transition: all 1s;  
                      -o-transition: all 1s;  
                         transition: all 1s;"
          onclick="this.style.height=(this.style.height===':h1px')? ':h2px' : ':h1px';
                   this.nextSibling.style.fontSize=(this.nextSibling.style.fontSize==='0px')? '1.0em' : '0px';
                  "}}{div {@ style="font-size:0px; text-align:center; "}:txt}}}
}

_p You can compare lambdatalk and some other languages, analyzing about 190 {b tasks} in the [[rosettacode.org|http://rosettacode.org/wiki/Category:Lambdatalk]] web site.

_p You could also compare this paper to

_ul 1) [[A Tutorial Introduction to the Lambda Calculus (Raul Rojas)|http://www.inf.fu-berlin.de/lehre/WS03/alpi/lambda.pdf]] or 
_ul 2) [[Le λ-calcul comme modèle de calculabilité|https://www.irif.fr/~carton/Enseignement/Complexite/ENS/Redaction/2009-2010/pablo.rauzy.pdf]] or
_ul 3) [[Perl and the Lambda Calculus |https://perl.plover.com/yak/lambda/samples/]], 
_p and analyze the way are introduced basic concepts, booleans, pairs, recursion, numbers. Your opinion is welcome.

_p Not forgetting that everything was written and evaluated in real time in any modern web browser, via a small engine without any external dependancy, coming as a single 50kb zipped folder easy to install in any web host provider.

_p But it's another story which can be discovered in the '{lambda way} project's [[workshop|?view=start]].

{center
{div {@ style="display:table-cell; width:400px; height:400px; box-shadow:0 0 8px #000; border-radius:200px; text-align:center; font-size:72px; background:#ccc; color:#fff;"}
{div {@ style="display:inline-block; width:250px; height:250px; border:1px solid #000; border-radius:125px; text-align:center; font-size:48px; background:#aaa; color:#fff;"}
{div {@ style="display:inline-block; width:150px; height:150px; border:1px solid #000; border-radius:75px; text-align:center; font-size:24px; background:#888; color:#fff;"}
{div {@ style="display:inline-block; width:75px; height:75px; border:1px solid #000; border-radius:37px; text-align:center; font-size:36px; background:#666; color:#fff; line-height:2.0em"} 
'{λy}}primitives}libraries}'{www}}}

_p {i Alain Marty (2020/03/29 last update 2020/09/06)}

_h1 references

_ul [[https://harryrschwartz.com/2017/07/26/lifting-lambdas-into-supercompilers| https://harryrschwartz.com/2017/07/26/lifting-lambdas-into-supercompilers]]
_ul [[https://en.wikipedia.org/wiki/Combinatory_logic| https://en.wikipedia.org/wiki/Combinatory_logic]]
_ul [[History-of-lambda-calculus-and-combinatory-logic.pdf| https://www.researchgate.net/profile/J_Hindley/publication/228386842_History_of_lambda-calculus_and_combinatory_logic/links/5ac9e3aaaca272abdc6158c4/History-of-lambda-calculus-and-combinatory-logic.pdf?origin=publication_detail]]
_ul [[lambda lifting|https://en.wikipedia.org/wiki/Lambda_lifting]]
_ul [[super combinator|https://wiki.haskell.org/Super_combinator]]
_ul [[github|https://ifl2014.github.io/submissions/ifl2014_submission_13.pdf]]
_ul [[whiteboard problems|https://www.jtolio.com/2017/03/whiteboard-problems-in-pure-lambda-calculus/]]
_ul [[ron garret|http://www.flownet.com/ron/lambda-calculus.html]]

_ul [[A Tutorial Introduction to the Lambda Calculus (Raul Rojas)|http://www.inf.fu-berlin.de/lehre/WS03/alpi/lambda.pdf]]
_ul [[The Lambda Calculus (Don Blaheta)|http://cs.brown.edu/courses/cs173/2001/Lectures/2001-10-25.pdf]]
_ul  [[λ-calculus (wikipedia)|http://en.wikipedia.org/wiki/Lambda_calculus]], 
_ul [[Church_encoding|https://en.wikipedia.org/wiki/Church_encoding]],
_ul [[the-y-combinator-no-not-that-one|https://medium.com/@ayanonagon/the-y-combinator-no-not-that-one-7268d8d9c46]], 
_ul [[lambda-calculus-for-absolute-dummies|http://palmstroem.blogspot.fr/2012/05/lambda-calculus-for-absolute-dummies.html]], 
_ul [[lambda calcul|http://www.mactech.com/articles/mactech/Vol.07/07.05/LambdaCalculus/index.html]], (André van Meulebrouck)
_ul [[simonpj|http://research.microsoft.com/en-us/um/people/simonpj/papers/slpj-book-1987/PAGES/V.HTM]]
_ul [[Y|http://mvanier.livejournal.com/2897.html]]
_ul [[Collected Lambda Calculus Functions|http://jwodder.freeshell.org/lambda.html]]
_ul [[epigrams|http://pu.inf.uni-tuebingen.de/users/klaeren/epigrams.html]]
_ul [[VIGRE|http://www.math.uchicago.edu/~may/VIGRE/VIGRE2006/PAPERS/Chariker.pdf]]
_ul [[palmstroem|http://palmstroem.blogspot.fr/2012/05/lambda-calculus-for-absolute-dummies.html]] 
_ul [[what-is-lambda-calculus-and-why-should-you-care|https://zeroturnaround.com/rebellabs/what-is-lambda-calculus-and-why-should-you-care/]]
_ul [[Show HN: λ-calculus revisited|https://news.ycombinator.com/item?id=22222682]]
_ul [[SHEN|http://www.schoolofinternalalchemy.com/]]
_ul [[pablo rauzy|https://www.irif.fr/~carton/Enseignement/Complexite/ENS/Redaction/2009-2010/pablo.rauzy.pdf]]
_ul [[all-you-need-is-lambda-1-booleans| https://antitypical.com/posts/2020-03-29-all-you-need-is-lambda-1-booleans/]]
_ul ... among some others on the web!

{style 
body { background:#ddd; color:#000; }
#page_frame { border:0; box-shadow:0 0; }  
#page_content { font-family:optima; box-shadow:0 0; border:0; box-shadow:0 0; background:transparent; } 
.page_menu { background:#ddd; opacity:0.8} 
pre { box-shadow:0 0 8px #000; padding:5px; background:#fff; }
}