lambdaway :: coding

3 | list | login |load

| |

_h1 λ{sup calc} | [[λ{sup talk}|?view=coding2]] | [[λ{sup tank}|?view=coding3]] | [[•••|?view=oops]]

{{block}
{uncover https://toysondor.files.wordpress.com/2020/05/corpus-hypercubus-salvador-dali.jpg 100 800 [[Corpus Hypercubus|https://arxiv.org/pdf/1512.02086.pdf]] | Salvador Dali & Gala{br}Teacher trying to explain λ-calculus to a hairdresser}

_h2 introduction

_p We are going to explore the factory of a text editor, {b lambdatank}, coming with a programming language, {b lambdatalk}, following three steps:
 
_ul 1) {b [[λ{sup calc}|?view=coding]], the core}: using only an extremely reduced core of its features, (words, abstractions, applications), and an empty dictionary, (no primitives, no numbers, nothing), we will build and progressively discover some essential data structures, (booleans, pairs, lists, numbers), as well as a tool to deal with them, {b recursion} ;

_ul 2) {b [[λ{sup talk}|?view=coding2]], special forms & primitives}: we will introduce a list of {b 9} special forms, (lambda, def, if, let, quote, macro, script, style, require), making the code faster and easier to write, as well as a set of about {b 200} primitives, (words, numbers, arrays, html, svg, ...), and a first set of libraries, (big numbers, complex numbers, ...), opening the language to the rich ecosystem provided for free by web browsers ;

_ul 3) {b [[λ{sup tank}|?view=coding3]], the environment}: and finally we will present the IDE, interactive development environment, the wiki {b lambdatank} and its installation on any web browser, as a {i dwarf on the shoulders of giants}.

_p During the first step the goal is to give a gentle introduction to coding, highlighting the unicity of a mechanism used to evaluate expressions, which is nothing but a simple {b text replacement process}. On the way we will meet useful concepts like functions, names, booleans, pairs, predicates, lists and recursive loops. Avoiding as far as it can be shadow areas, magic tools, building everything on text replacement processes, which can be tricky but are always understandable, with a little help of patience and curiosity.

_ul intoduction
_ul 1) lambda
_ul 2) def
_ul 3) boolean
_ul 4) pair
_ul 5) nil
_ul 6) list
_ul 7) recursion
_ul 8) applications
_ul20 8.1) concat & reverse
_ul20 8.2) a bit of arithmetic
_ul20 8.3) the towers of Hanoï 
_ul 9) back to lambdas
_ul conclusion

_p Let's go!

_p {b Note:} A slightly different presentation can be seen in [[coding as rewriting|?view=oops]] and how big numbers can be used at the λ-calculs level in [[n{sup bit} arithmetic|?view=oops6]].
_p See also [[Why is programming fun?|https://news.ycombinator.com/item?id=30517221]]
}

{{block}
{uncover {COCO}/t2_orchestre3.jpg 100 500 ORCHESTRE.3{br}encre monotype sur papier 18x24cm} 
_h2 1) lambda

_p The following text replacement command

{pre
replace : {b foo} {b bar}
     in : My first name is {b foo} and my last name is {b bar}.  
     by : James Bond
}
_p is rewritten, in a shorthand notation, as a parenthesized expression

{pre
'{{lambda {:foo :bar} 
          My first name is :foo and my last name is :bar.
        } James Bond} 
}

_p where {b lambda} is for the verb {b replace}, the colons {b :} prefixing {b foo} and {b bar} are for the blue color marking words to be replaced, and the balanced {b curly braces} avoid the need for the {b in} and {b by} conjunctions.

_p This being done, the expression is, {i in a magical way}, replaced by

{pre
{{lambda {:foo :bar} 
          My first name is :foo and my last name is :bar.
        } James Bond} 
}

_p and leads us to the definition of {b lambdatalk} - ({i not to be confused with ze lambada dance}) - a dialect of the λ-calculus created by Alonso Church in the thirties, a Turing complete functional language working in a tiny IDE, {b lambdatank}, installed on any web browser, {i as a dwarf on the shoulders of giants}.

_h3 syntax & evaluation

_p Here lambdatalk is supposed reduced to the previous expression written in its most general form

{center {pre 
'{{lambda {w} x} w} -> w
}}

_p where {b x} and {b w} are expressions and words defined this way

{center {pre 
x := w | '{lambda {w} x} | '{x x}
}}

_p  In other words expressions, {b x}, are reduced to words, {b w}, lambda forms, {b '{lambda {w} x}},  and applications, {b '{x x}}. Lambdatalk is implemented so that
_ul 1) {b words} are {b not evaluated}, they are simply skipped by the evaluator, 
_ul 2) {b applications} are normal forms evaluated {b from inside out} to a word or a sequence of words, 
_ul 3) {b lambdas} are special forms evaluated to a single word - a function's reference added to a dictionary, initially empty - and follow these 3 rules:
_ul20 3.1) called on a number of words {b lesser} than the number of arguments, a lambda memorizes the given words and returns a new lambda waiting for missing words,
_ul20 3.2) called on a number of words {b equal} to the number of arguments a lambda returns a word or a sequence of words,
_ul20 3.3) called on a number of words {b greater} than the number of arguments, the last one gets the exceeding words and the lambda returns a word or a sequence of words.
_ul 4) {b lambdas} are evaluated {b first}, {b applications} are evaluated {b last}.

_p Regarding rule {b 3.1)} specialists talk about {b partial application} or {b currying}. About rule {b 3.3)} they talk about {b variadicity}. In lambdatalk lambdas can't get values from the context, a behaviour called {b closure} by specialists. Happily the rule {b 3.1)} helps to work arounds this weakness. As we will find out in the following.

_p At this level lambdatalk knows nothing about data structures (booleans, pairs, lists, ...), control structures (if then else), numbers, math operators or whatever else. Nothing. The dictionary is empty! We are going to feed it, with the help of a second useful special form, {b def}.

_p {b Note:} Lambdatalk doesn't know closures and it can be seen as a severe weakness. {b Lambdacode} is a variant built on a standard evaluator dealing with closures. which should be more satisfying for aficionados of pure Lisp/Scheme code. But it turns out that lambdatalk, even without closures, is more appropriate in a wiki context where (enriched and structured) text is king, and there are a few workarounds to the absence of closures, when it is felt. It's all a matter of context ... See details in [[lambdacode5]] and [[lambdacode]]. 
}

{{block}
{uncover {COCO}/e_aok2.jpg 100 500 AOK.3{br}encre monotype sur papier 10x15cm}
_h2 2) def

_p The special form {b '{lambda {:words} expression}} is the heart of the text replacement process and could be used alone everytime. In order to write and read code in a more pleasant way, we introduce a second special form to {b def}ine names bounded to expressions

{pre '{def name expression}}

_p {b expression} is first evaluated to one or several words and {b '{def words}} is replaced by {b name}.

_p Examples

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

'{HI}                       
-> {HI}

HI, I just say «'{HI}»!
-> HI,  I just say «{HI}»!     
}

_p Note that outside curly braces words are not evaluated, simply skipped by the evaluator. Think to Excel where writing {b 1+2} in a cell displays {b 1+2} and writing {b =1+2} displays {b 3}.

{pre
'{def SWAP {lambda {:a :b} :b :a}}   
-> {def SWAP {lambda {:a :b} :b :a}}

'{SWAP james bond}                 
-> {SWAP james bond}   
            
'{SWAP ward cunningham}                 
-> {SWAP ward cunningham} 
}

_p We have built our first user defined constant, {b HI}, and function, {b SWAP}. In what follows, exclusively using {b lambda} and {b def}, we will build from scratch the tools that will lead us to a full-fledged programming language.
}

{{block}
{uncover {COCO}/e_d1.jpg 100 500 SUD d1{br}encre monotype sur papier 10x15cm}
_h2 3) boolean

_p We begin with logical operators, {b TRUE | FALSE | IF}, which are obviously vital in a binary world, but the most important thing here will be to understand the mechanism of text replacements.

{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 {:a :b :c} {:a :b :c}}}
-> {def IF {lambda {:a :b :c} {:a :b :c}}}

'{IF TRUE yes no}
-> {IF TRUE yes no}
'{IF FALSE yes no}
-> {IF FALSE yes no} 
}

_p Replace {b TRUE} by its lambda definition in {b '{IF TRUE yes no}}, go on and be convinced that the sequence of replacements will lead to {b yes}. Let's do it:

{pre
'{IF TRUE yes no}
-> '{{lambda {:a :b :c} {:a :b :c}} TRUE yes no}
-> '{TRUE yes no}
-> '{{lambda {:a :b} :a} yes no}
-> yes
}

_p Once more it's essential to understand that it's nothing but text replacement. And don't forget that a name is nothing but an alias to the bounded expression. For instance {b TRUE} is equivalent to {b '{lambda {:a :b} :a}}, both are interchangeable.

_p Left as an exercice, you could play with the following functions

{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 TRUE}   -> {AND TRUE TRUE}
'{AND TRUE FALSE}  -> {AND TRUE FALSE}
'{AND FALSE TRUE}  -> {AND FALSE TRUE}
'{AND FALSE FALSE} -> {AND FALSE FALSE}
}

_p And so on.

}

{{block}
{uncover {COCO}/e_pf1.jpg 100 500 SUD pf1{br}encre monotype sur papier 10x15cm}
_h2 4) pair

_p A pair is a couple of words, the simplest of what specialists call a {b data structure}, with a constructor and two accessors.

{pre
'{def PAIR {lambda {:a :b :c} {:c :a :b}}}
-> {def PAIR {lambda {:a :b :c} {:c :a :b}}}
'{def LEFT {lambda {:c} {:c TRUE}}}
-> {def LEFT {lambda {:c} {:c TRUE}}}
'{def RIGHT {lambda {:c} {:c FALSE}}}
-> {def RIGHT {lambda {:c} {:c FALSE}}}

'{def WIKI {PAIR ward cunningham}}
-> {def WIKI {PAIR ward cunningham}}
'{LEFT {WIKI}} 
-> {LEFT {WIKI}}
'{RIGHT {WIKI}} 
-> {RIGHT {WIKI}}
}

_p Here are the sequences of replacements are more tricky, let's trace them:

{pre
'{LEFT {WIKI}}
-> '{{lambda {:c} {:c TRUE}} {WIKI}}
-> '{{WIKI} TRUE}
-> '{{PAIR ward cunningham} TRUE}
-> '{{{lambda {:a :b :c} {:c :a :b}} ward cunningham} TRUE}
-> '{{lambda {:c} {:c ward cunningham}} TRUE}
-> '{TRUE ward cunningham}
-> ward
}

_p The tricky part is in this transformation

{pre
'{{lambda {:a :b :c} {:c :a :b}} ward cunningham} 
-> '{lambda {:c} {:c ward cunningham}}
}

_p The lambda is waiting for three values and is only given two. Don't worry, it memorises them and returns a new lambda waiting for the missing one. Geeks call such a thing {b partial application}. As simple as that!

_h3 displaying a pair

{pre
'{def P.DISP
 {lambda {:p}
  ({LEFT :p} {RIGHT :p})}}
-> {def P.DISP
 {lambda {:p}
  ({LEFT :p} {RIGHT :p})}}

'{P.DISP {PAIR Alan Turing}}
-> {P.DISP {PAIR Alan Turing}}
}

_h3 swapping in a pair

{pre
'{def P.SWAP
 {lambda {:p}
  {PAIR {RIGHT :p} {LEFT :p}}}}
-> {def P.SWAP
 {lambda {:p}
  {PAIR {RIGHT :p} {LEFT :p}}}}

'{P.DISP {P.SWAP {PAIR Alonzo Church}}}
-> {P.DISP {P.SWAP {PAIR Alonzo Church}}}
}

_h3 a 4 bits adder

_p With booleans and pairs we can build an additioner

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

'{def fullAdder 
 {lambda {:a :b :c}
  {{lambda {:b :ha1}
  {{lambda {:ha1 :ha2}    
           {PAIR {OR {LEFT :ha1} {LEFT :ha2}} {RIGHT :ha2}}
   } :ha1 {halfAdder {RIGHT :ha1} :b}} 
   } :b {halfAdder :c :a}} }}
-> {def fullAdder 
 {lambda {:a :b :c}
  {{lambda {:b :ha1}
  {{lambda {:ha1 :ha2}    
           {PAIR {OR {LEFT :ha1} {LEFT :ha2}} {RIGHT :ha2}}
   } :ha1 {halfAdder {RIGHT :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}
           {LEFT :fa4} {RIGHT :fa4} {RIGHT :fa3}
                       {RIGHT :fa2} {RIGHT :fa1}
   } :fa1 :fa2 :fa3 {fullAdder :a4 :b4 {LEFT :fa3}}}
   } :a4 :b4 :fa1 :fa2 {fullAdder :a3 :b3 {LEFT :fa2}}}
   } :a4 :a3 :b4 :b3 :fa1 {fullAdder :a2 :b2 {LEFT :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}
           {LEFT :fa4} {RIGHT :fa4} {RIGHT :fa3}
                       {RIGHT :fa2} {RIGHT :fa1}
   } :fa1 :fa2 :fa3 {fullAdder :a4 :b4 {LEFT :fa3}}}
   } :a4 :b4 :fa1 :fa2 {fullAdder :a3 :b3 {LEFT :fa2}}}
   } :a4 :a3 :b4 :b3 :fa1 {fullAdder :a2 :b2 {LEFT :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}          //  01000
}

_p {b Notes:}

_ul Don't worry if yo can't trace all that stuff. At this point you have understood the principle, it is about longer and longer sequences of text replacements, and hereafter we will keep that in mind without going too deeply into the details.
_ul We have built a process adding binary numbers (here from {b 0} to {b 1111, ie 15}), using a "{b frozen wave}" of lambdas, without any loop structure, highlighting the "{b static behaviour}" of digital hardwired gates.

_img https://upload.wikimedia.org/wikipedia/commons/a/a5/Tsunami_by_hokusai_19th_century.jpg 
 
}

{{block}
{uncover {COCO}/e_g3.jpg 100 500 g3{br}encre monotype sur papier 10x15cm}
_h2 5) nil

_p The question is « {b To be or not to be a pair?} » Two twinned functions are built to answer such a question, {b NIL} and {b NIL?}.

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

'{NIL? NIL}
-> {NIL? NIL}
'{NIL? {WIKI}}       // WIKI is '{PAIR ward cunningham}
-> {NIL? {WIKI}}            // and so is not NIL
}

_p Let's trace

{pre
'{NIL? NIL}
-> '{{lambda {:c} {:c {lambda {:a :b} FALSE}}} NIL} 
-> '{NIL {lambda {:a :b} FALSE}}
-> '{{lambda {:a} TRUE} {lambda {:a :b} FALSE}} 
-> TRUE

'{NIL? {WIKI}} 
-> '{{lambda {:c} {:c {lambda {:a :b} FALSE}}} {WIKI}}
-> '{{{lambda {:a :b :c} {:c :a :b}} ward cunningham} 
                                       {lambda {:a :b} FALSE}}  
-> '{{lambda {:c} {:c ward cunningham}} {lambda {:a :b} FALSE}} 
-> '{{lambda {:a :b} FALSE} ward cunningham} 
-> FALSE
}

_p It took me a long time to figure this out, I'm still struggling to retrieve from memory the code for the {b NIL?} function.

_p Be patient too, the gift is at the end of the road.
}

{{block}
{uncover {COCO}/e_fon.jpg 100 500 fon{br}encre monotype sur papier 10x15cm}
_h2 6) list

_p {b PAIRS} can be nested, for instance into a {b tree} recursively defined this way

{pre
tree = '{PAIR PAIR|word PAIR|word}  where | means OR
}

{pre
'{def MYTREE
 {PAIR
  {PAIR a b}
   {PAIR c 
    {PAIR d e}}}} 
-> {def MYTREE
 {PAIR {PAIR a b}
       {PAIR c {PAIR d e}}}}

'{LEFT {LEFT {MYTREE}}}   -> {LEFT {LEFT {MYTREE}}}
'{RIGHT {LEFT {MYTREE}}}  -> {RIGHT {LEFT {MYTREE}}}
'{LEFT {RIGHT {MYTREE}}}  -> {LEFT {RIGHT {MYTREE}}}
'{LEFT {RIGHT {RIGHT {MYTREE}}}}  -> {LEFT {RIGHT {RIGHT {MYTREE}}}}
'{RIGHT {RIGHT {RIGHT {MYTREE}}}} -> {RIGHT {RIGHT {RIGHT {MYTREE}}}}
}

_p We will be interested in a very particular type of tree, the {b list}, defined this way

{pre
list = '{PAIR word PAIR|NIL} where | means OR
}

_p For instance:

{pre
'{def LIST
 {PAIR hello
  {PAIR brave
   {PAIR new
    {PAIR world NIL}}}}} 
-> {def LIST {PAIR hello {PAIR brave {PAIR new {PAIR world NIL}}}}}
}

_p {b Note:} The full lambdatalk comes with primitives dealing with sentences we could use to simplify lists' definitions

{pre
'{def L.NEW
 {lambda {:s}
  {PAIR {S.first :s}
   {if {S.empty? {S.rest :s}}
    then NIL 
    else {L.NEW {S.rest :s}}}}}}
-> {def L.NEW
 {lambda {:s}
  {PAIR {S.first :s}
   {if {S.empty? {S.rest :s}}
    then NIL 
    else {L.NEW {S.rest :s}}}}}}

'{L.NEW a b c}
-> '{PAIR a {PAIR b {PAIR c NIL}}}
}

_p But we won't have to use such an ugly {b L.NEW} function in the following. Forget!

_p Let's extract successively all the terms of the list

{pre
'{LEFT {LIST}} -> {LEFT {LIST}}
'{LEFT {RIGHT {LIST}}} -> {LEFT {RIGHT {LIST}}}
'{LEFT {RIGHT {RIGHT {LIST}}}} -> {LEFT {RIGHT {RIGHT {LIST}}}}
'{LEFT {RIGHT {RIGHT {RIGHT {LIST}}}}} -> {LEFT {RIGHT {RIGHT {RIGHT {LIST}}}}}
}

_p Obviously we need a "mechanism" to display easily all the terms of the list. Let's question {b LIST} at each step

{pre
'{NIL? {LIST}} -> {NIL? {LIST}}
'{NIL? {RIGHT {LIST}}} -> {NIL? {RIGHT {LIST}}}
'{NIL? {RIGHT {RIGHT {LIST}}}} -> {NIL? {RIGHT {RIGHT {LIST}}}}
'{NIL? {RIGHT {RIGHT {RIGHT {LIST}}}}} -> {NIL? {RIGHT {RIGHT {RIGHT {LIST}}}}}
'{NIL? {RIGHT {RIGHT {RIGHT {RIGHT {LIST}}}}}} -> {NIL? {RIGHT {RIGHT {RIGHT {RIGHT {LIST}}}}}}
}

_p We can now imagine a process which takes the left part of the list, {b '{LEFT list}}, and does it again on the right part of the list, {b '{RIGHT list}} until {b '{NIL? list}} returns {b TRUE}.

}

{{block}
{uncover {COCO}/e_fon2.jpg 100 500 fon2{br}encre monotype sur papier 10x15cm}
_h2 7) recursion

_h3 7.1) DISP

_p Here is the function displaying all the terms of {b LIST}

{pre
'{def DISP
 {lambda {:l}
  {{IF {NIL? :l}
       {lambda {:l} }
       {lambda {:l} {LEFT :l}
                    {DISP {RIGHT :l}}}} :l}}}
-> {def DISP
 {lambda {:l}
  {{IF {NIL? :l}
       {lambda {:l} }
       {lambda {:l} {LEFT :l} {DISP {RIGHT :l}}}} :l}}}

'{DISP {LIST}}
-> {DISP {LIST}}
}

_p Note that {b DISP} calls {b DISP}, it's called a {b recursive process} with which we will {b loop} over recursive data structures. We are going to trace the sequence of replacements in the call {b '{DISP {LIST}}}. Giving a name to the two inside lambdas

{pre
'{def STOP {lambda {:l} }} 
-> {def STOP {lambda {:l} }}
'{def RECURSE {lambda {:l} {LEFT :l} {DISP {RIGHT :l}}}} 
-> {def RECURSE {lambda {:l} {LEFT :l} {DISP {RIGHT :l}}}}
}

_p the {b DISP} function becomes easier to read

{pre
'{def DISP {lambda {:l} {{IF {NIL? :l} STOP RECURSE} :l}}}
}

_p Now let's apply {b DISP} to {b '{LIST}} and do text substitutions

{pre
'{DISP {LIST}}
-> '{{lambda {:l} {{IF {NIL? :l} STOP RECURSE} :l}} {LIST}}
-> '{{IF {NIL? {LIST}} STOP RECURSE} {LIST}}
-> '{RECURSE {LIST}}  // because '{NIL? {LIST}} is FALSE
-> '{{lambda {:l} {LEFT :l} {DISP {RIGHT :l}}} {LIST}}
-> '{LEFT {LIST}} '{DISP {RIGHT {LIST}}}
-> {LEFT {LIST}} '{DISP {RIGHT {LIST}}}
}

_p At this point the first term of the list, {b hello}, is displayed and {b '{DISP {RIGHT {LIST}}}} says "do it again with the rest of the list". Obviously we will get successively {b brave}, {b new}, {b world} and then the list will be empty.

_p Let's see what happens when the liste is empty, in other words when {b '{NIL? {LIST}}} is {b TRUE}

{pre
'{DISP {LIST}}
-> '{{lambda {:l} {{IF {NIL? :l} STOP RECURSE} :l}} {LIST}}
-> '{{IF {NIL? {LIST}} STOP RECURSE} {LIST}}
-> '{STOP {LIST}}  // because '{NIL? {LIST}} is TRUE
-> '{{lambda {:l} } {LIST}}
-> // nothing end stop
}

_p Finally {b '{DISP {LIST}}} has returned {b hello brave new world}. Funny isnt'it?

_p Having understood how the recursive process works, let's apply it to concatening two lists and reversing a list.

_h3 7.2) CONCAT & REVERSE

_p Following the same pattern we write the {b CONCAT} function waiting for two lists

{pre
'{def CONCAT
 {lambda {:a :b}
  {{IF {NIL? :a}
   {lambda {:a :b} :b}
   {lambda {:a :b}
    {PAIR {LEFT :a} {CONCAT {RIGHT :a} :b}}} } :a :b}}}
-> {def CONCAT
 {lambda {:a :b}
  {{IF {NIL? :a}
   {lambda {:a :b} :b}
   {lambda {:a :b}
    {PAIR {LEFT :a} {CONCAT {RIGHT :a} :b}}} } :a :b}}}

'{def A {PAIR a {PAIR b {PAIR c NIL}}}}
-> {def A {PAIR a {PAIR b {PAIR c NIL}}}} = {DISP {A}}
'{def B {PAIR d {PAIR e {PAIR f {PAIR g NIL}}}}}
-> {def B {PAIR d {PAIR e {PAIR f {PAIR g NIL}}}}} = {DISP {B}}
'{DISP {CONCAT {A} {B}}}
-> {DISP {CONCAT {A} {B}}}
}

_p The {b REVERSE} function needs an helper function for a right initialization

{pre
'{def REVERSE
 {def REVERSE.r
  {lambda {:a :b}
   {{IF {NIL? :a}
    {lambda {:a :b} :b}
    {lambda {:a :b} {REVERSE.r {RIGHT :a} {PAIR {LEFT :a} :b}}}} :a :b}}}
 {lambda {:a}
  {REVERSE.r :a NIL}}}
-> {def REVERSE
 {def REVERSE.r
  {lambda {:a :b}
   {{IF {NIL? :a}
    {lambda {:a :b} :b}
    {lambda {:a :b} {REVERSE.r {RIGHT :a} {PAIR {LEFT :a} :b}}}} :a :b}}}
 {lambda {:a}
  {REVERSE.r :a NIL}}}

'{DISP {REVERSE {A}}}
-> {DISP {REVERSE {A}}}
}

_h3 7.3) HANOÏ

_p This is an example of {b double recursion} with a taste of infinite.

_p A set of 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.

{pre
'{def HANOI          
 {lambda {:n :from :to :via}
  {{IF {NIL? :n}
   {lambda {:n :from :to :via} }
   {lambda {:n :from :to :via}
    {HANOI {RIGHT :n} :from :via :to}
      {br} move {LEFT :n} from tower :from to tower :to 
    {HANOI {RIGHT :n} :via :to :from} }}
   :n :from :to :via}}}
-> {def HANOI          
 {lambda {:n :from :to :via}
  {{IF {NIL? :n}
   {lambda {:n :from :to :via} }
   {lambda {:n :from :to :via}
    {HANOI {RIGHT :n} :from :via :to}
      {div} move {LEFT :n} from tower :from to tower :to 
    {HANOI {RIGHT :n} :via :to :from} }}
   :n :from :to :via}}} 
}

_p The set of disks is defined as a list of words, {b Disk_1, Disk_2, ...}

{pre
'{def DISKS
 {PAIR Disk_1
 {PAIR Disk_2
 {PAIR Disk_3
 {PAIR Disk_4
 {PAIR Disk_5 NIL}}}}}}
-> {def DISKS {PAIR Disk_1 {PAIR Disk_2 {PAIR Disk_3 {PAIR Disk_4 {PAIR Disk_5 NIL}}}}}}
}

{pre
'{HANOI {DISKS} A B C}
-> {HANOI {DISKS} A B C} 
}

_p With 5 disks we have {b 2{sup 5}-1 = {pow 2 5}} moves. With {b 64} disks this function would write {b 2{sup 64}-1 = 18446744073709551615} moves, a very very big number.
}

{{block}
{uncover {COCO}/e_fon3.jpg 100 500 fon3{br}encre monotype sur papier 10x15cm}
_h2 8) arithmetic

_p We are going to build a bit of {b arithmetic} where numbers are defined as lists of anything, say dots. This is how we could display a list containing four dots, using a close variant of the {b DISP} function:

{pre
'{def NDISP
 {lambda {:l}
  {{IF {NIL? :l}
       {lambda {:l} }
       {lambda {:l} •{NDISP {RIGHT :l}}}} :l}}}
-> {def NDISP
 {lambda {:l}
  {{IF {NIL? :l}
       {lambda {:l} }
       {lambda {:l} •{NDISP {RIGHT :l}}}} :l}}}

'{def 4dots {PAIR • {PAIR • {PAIR • {PAIR • NIL}}}}}
-> {def 4dots {PAIR • {PAIR • {PAIR • {PAIR • NIL}}}}}
'{NDISP {4dots}}
-> {NDISP {4dots}}
}

_p We can do better than this very primitive system of numeration.

_h3 8.1) LENGTH

_p We choose to rewrite {b DISP} as {b LENGTH}, returning the count of the elements of the list, using a small bit of javascript's maths, but only for display convenance.

{pre
'{def LENGTH
 {lambda {:l}
  {{IF {NIL? :l}
       {lambda {:l} }
       {lambda {:l} {+ 1 {LENGTH {RIGHT :l}}}}} :l}}}
-> {def LENGTH
 {lambda {:l}
  {{IF {NIL? :l}
       {lambda {:l} 0}
       {lambda {:l} {+ 1 {LENGTH {RIGHT :l}}}}} :l}}}

'{LENGTH {LIST}}
-> {LENGTH {LIST}} 
}

_h3 8.2) ZERO & alii

_p We are going to define a constant, {b ZERO}, and three functions, [{b ZERO?, SUCC & PREV}] which will be the fundamental bricks of this small arithmetic.

{pre
'{def ZERO NIL}               
-> {def ZERO NIL}

'{def ZERO? {lambda {:n} {NIL? :n}}}
-> {def ZERO? {lambda {:n} {NIL? :n}}}

'{def SUCC {lambda {:n} {PAIR . :n}}} 
-> {def SUCC {lambda {:n} {PAIR . :n}}}

'{def PREV {lambda {:n} {IF {NIL? :n} NIL {RIGHT :n}}}}
-> {def PREV {lambda {:n} {IF {NIL? :n} NIL {RIGHT :n}}}}   // nothing below ZERO
}

_h3 8.3) natural positive numbers

_p Here are the first numbers built using {b ZERO} and {b SUCC}

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

'{LENGTH {PREV {SIX}}}      -> {LENGTH {PREV {SIX}}}
'{LENGTH {PREV {ONE}}}      -> {LENGTH {PREV {ONE}}}    // ZERO
'{LENGTH {PREV {ZERO}}}     -> {LENGTH {PREV {ZERO}}}    // nothing below ZERO
}

_p Don't forget that numbers are nothing but lists of dots and we have to use {b LENGTH} to display them.

_h3 8.4) The {b ADD}ition {b a+b}

{pre
'{def ADD
 {lambda {:n1 :n2}
  {{IF {ZERO? :n1}
       {lambda {:n1 :n2} :n2}
       {lambda {:n1 :n2} {ADD {PREV :n1}
                              {SUCC :n2}}}}
                :n1 :n2}}}
-> {def ADD
 {lambda {:n1 :n2}
  {{IF {ZERO? :n1}
       {lambda {:n1 :n2} :n2}
       {lambda {:n1 :n2} {ADD {PREV :n1}
                              {SUCC :n2}}}}
                :n1 :n2}}}

'{LENGTH {ADD {THREE} {FOUR}}} 
-> {LENGTH {ADD {THREE} {FOUR}}}    
}

_h3 8.5) The {b SUB}straction, {b a-b}

{pre
'{def SUB
 {lambda {:n1 :n2}
  {{IF {ZERO? :n2}
       {lambda {:n1 :n2} :n1}
       {lambda {:n1 :n2} {SUB {PREV :n1}
                              {PREV :n2}}}}
                :n1 :n2}}}
-> {def SUB
 {lambda {:n1 :n2}
  {{IF {ZERO? :n2}
       {lambda {:n1 :n2} :n1}
       {lambda {:n1 :n2} {SUB {PREV :n1}
                              {PREV :n2}}}} 
                :n1 :n2}}}

'{LENGTH {SUB {FOUR} {TWO}}}
-> {LENGTH {SUB {FOUR} {TWO}}} 
}

_h3 8.6) The {b MULT}iplication, {b a*b}, in two steps

{prewrap
'{def MULT  // initialize and call the recursive part
 {lambda {:n1 :n2}
  {MULT.rec :n1 :n2 NIL}}}
-> {def MULT
 {lambda {:n1 :n2}
  {MULT.rec :n1 :n2 NIL}}}

'{def MULT.rec       // the recurse part
 {lambda {:n1 :n2 :n3}
  {{IF {ZERO? :n2}
       {lambda {:n1 :n2 :n3} :n3}
       {lambda {:n1 :n2 :n3} {MULT.rec :n1
                                       {PREV :n2}
                                       {ADD :n1 :n3}}}}
                :n1 :n2 :n3}}}
-> {def MULT.rec
 {lambda {:n1 :n2 :n3}
  {{IF {ZERO? :n2}
       {lambda {:n1 :n2 :n3} :n3}
       {lambda {:n1 :n2 :n3} {MULT.rec :n1
                                       {PREV :n2}
                                       {ADD :n1 :n3}}}}
                :n1 :n2 :n3}}}

'{def EIGHT {MULT {TWO} {FOUR}}}
-> {def EIGHT {MULT {TWO} {FOUR}}}
'{LENGTH {EIGHT}}
-> {LENGTH {EIGHT}}    // 2*4 = 8 
}

_h3 8.7) The {b POW}er function, {b a{sup b}}, in two steps

{prewrap
'{def POW    // initialize and call the recursive part
 {lambda {:n1 :n2}
  {POW.rec :n1 :n2 {ONE}}}}
-> {def POW
 {lambda {:n1 :n2}
  {POW.rec :n1 :n2 {ONE}}}}

'{def POW.rec               // the recurse part
 {lambda {:n1 :n2 :n3}
  {{IF {ZERO? :n2}
       {lambda {:n1 :n2 :n3} :n3}
       {lambda {:n1 :n2 :n3} {POW.rec :n1
                                      {PREV :n2}
                                      {MULT :n1 :n3} }}}
                :n1 :n2 :n3}}}
-> {def POW.rec
 {lambda {:n1 :n2 :n3}
  {{IF {ZERO? :n2}
       {lambda {:n1 :n2 :n3} :n3}
       {lambda {:n1 :n2 :n3} {POW.rec :n1
                                      {PREV :n2}
                                      {MULT :n1 :n3} }}}
                :n1 :n2 :n3}}}

'{def n256 {POW {TWO} {EIGHT}}}      // 2{sup 8}
-> {def n256 {POW {TWO} {EIGHT}}}

'{LENGTH {n256}}
-> '{LENGTH {n256}}
}

_h3 8.8) The {b DIV}, {b MOD} and {b GCD} operators

{prewrap
'{def DIV                            
  {lambda {:a :b}
   {{IF {ZERO? {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 {ZERO? {SUB :b :a}}
    {lambda {:a :b} {ADD {ONE} {DIV {SUB :a :b} :b}}}
    {lambda {:a :b} {ZERO}}} :a :b}}}

'{LENGTH {DIV {FOUR} {TWO}}}
-> {LENGTH {DIV {FOUR} {TWO}}}    // 4 = 2*2 + 0
'{LENGTH {DIV {FOUR} {THREE}}}
-> {LENGTH {DIV {FOUR} {THREE}}}     // 4 = 3*1 + 1

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

'{LENGTH {MOD {FOUR} {TWO}}}
-> {LENGTH {MOD {FOUR} {TWO}}}      // 4 = 2*2 + 0
'{LENGTH {MOD {FOUR} {THREE}}}
-> {LENGTH {MOD {FOUR} {THREE}}}     // 4 = 3*1 + 1

'{def GCD
 {lambda {:a :b}
  {{IF {ZERO? :b} 
   {lambda {:a :b} :a}
   {lambda {:a :b} {GCD :b {MOD :a :b}}}} :a :b}}}
-> {def GCD
 {lambda {:a :b}
  {{IF {ZERO? :b} 
   {lambda {:a :b} :a}
   {lambda {:a :b} {GCD :b {MOD :a :b}}}} :a :b}}}
 
'{LENGTH {GCD {FOUR} {TWO}}}
-> {LENGTH {GCD {FOUR} {TWO}}}
'{LENGTH {GCD {FOUR} {THREE}}}
-> {LENGTH {GCD {FOUR} {THREE}}}
}

_h3 8.9) The {b FAC}torial function, {b n!}

{prewrap
'{def FAC
 {lambda {:n1 :n2}
  {{IF {ZERO? :n2}
       {lambda {:n1 :n2} :n1}
       {lambda {:n1 :n2} {FAC {MULT :n1 :n2}
                              {PREV :n2}}}}
                :n1 :n2}}} 
-> {def FAC
 {lambda {:n1 :n2}
  {{IF {ZERO? :n2}
       {lambda {:n1 :n2} :n1}
       {lambda {:n1 :n2} {FAC {MULT :n1 :n2}
                              {PREV :n2}}}}
                :n1 :n2}}}

'{LENGTH {FAC {ONE} {FIVE}}}  // 5! = 120
-> {LENGTH {FAC {ONE} {FIVE}}} 
}

_h3 8.10) The {b FIBO}nacci function, {b F(n)}

{prewrap
'{def FIBO
 {lambda {:a :b :n}
  {{IF {ZERO? :n}
   {lambda {:a :b :n} :a}
   {lambda {:a :b :n} {FIBO {ADD :a :b} :a {PREV :n}}}}
   :a :b :n}}}
-> {def FIBO
 {lambda {:a :b :n}
  {{IF {ZERO? :n}
   {lambda {:a :b :n} :a}
   {lambda {:a :b :n} {FIBO {ADD :a :b} :a {PREV :n}}}} :a :b :n}}}

'{LENGTH {FIBO {ZERO} {ONE} {ADD {FIVE} {FIVE}}}} // F(10)=55 
->  {LENGTH {FIBO {ZERO} {ONE} {ADD {FIVE} {FIVE}}}}
}

_h3 8.11) RANGE, MAP, REDUCE

_p Could you imagine a functional programming language without the {b map} and {b reduce} structures introducing a kind of iteration in a recursive world? We introduce 
_ul 1) {b RANGE} generating a list of increasing numbers, 
_ul 2) {b MAP} applying a function to every elements of a list and returning a list, and 
_ul 3) {b REDUCE} applying a function to every elements of a list and returning the accumulation.

{prewrap
'{def RANGE
 {lambda {:a :b}
   {{IF {ZERO? {SUB :b :a}}
    {lambda {:a :b} {PAIR :b NIL}}
    {lambda {:a :b} {PAIR :a {RANGE {SUCC :a} :b}} }
   } :a :b}}}
-> {def RANGE
 {lambda {:a :b}
   {{IF {ZERO? {SUB :b :a}}
    {lambda {:a :b} {PAIR :b NIL}}
    {lambda {:a :b} {PAIR :a {RANGE {SUCC :a} :b}} }} :a :b}}}

'{DISP {MAP LENGTH {RANGE {ONE} {SIX}}}}
-> {DISP {MAP LENGTH {RANGE {ONE} {SIX}}}}

'{def MAP
 {lambda {:f :l}
  {{IF {NIL? :l}
   {lambda {:f :l} NIL}
   {lambda {:f :l} {PAIR {:f {LEFT :l}}
                         {MAP :f {RIGHT :l}}}}
  } :f :l}}}
-> {def MAP
 {lambda {:f :l}
  {{IF {NIL? :l}
   {lambda {:f :l} NIL}
   {lambda {:f :l} {PAIR {:f {LEFT :l}}
                         {MAP :f {RIGHT :l}}}}} :f :l}}}

'{DISP {MAP {lambda {:n} {LENGTH :n}}
           {RANGE {ONE} {SIX}}}} 
-> {DISP {MAP {lambda {:n} {LENGTH :n}} {RANGE {ONE} {SIX}}}}

'{DISP {MAP {lambda {:n} {LENGTH {POW {TWO} :n}}}
           {RANGE {ONE} {SIX}}}}
-> {DISP {MAP {lambda {:n} {LENGTH {POW {TWO} :n}}}
           {RANGE {ONE} {SIX}}}}

'{def REDUCE
  {lambda {:op :acc :list}
   {{IF {NIL? :list}
    {lambda {:op :acc :list} :acc}
    {lambda {:op :acc :list}
            {REDUCE :op 
                   {:op {LEFT :list} :acc}
                   {RIGHT :list}}}
   } :op :acc :list}}}
-> {def REDUCE
  {lambda {:op :acc :list}
   {{IF {NIL? :list}
    {lambda {:op :acc :list} :acc}
    {lambda {:op :acc :list}
            {REDUCE :op 
                   {:op {LEFT :list} :acc}
                   {RIGHT :list}}}}
             :op :acc :list}}}

'{LENGTH {REDUCE ADD {ZERO} {RANGE {ONE} {FIVE}}}}  
-> {LENGTH {REDUCE ADD {ZERO} {RANGE {ONE} {FIVE}}}}
'{LENGTH {REDUCE MULT {ONE} {RANGE {ONE} {FIVE}}}} 
-> {LENGTH {REDUCE MULT {ONE} {RANGE {ONE} {FIVE}}}}
}

_h3 8.12) 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)}
}

{prewrap
'{def LFAC
 {lambda {:n}
  {{IF {ZERO? :n}
   {lambda {:n} {ZERO}}
   {lambda {:n} {REDUCE ADD {ONE} {MAP {lambda {:n}
                {REDUCE MULT {ONE} {RANGE {ONE} :n}}}
          {RANGE {ONE} {PREV :n}}}}}} :n}}}
-> {def LFAC
 {lambda {:n}
  {{IF {ZERO? :n}
   {lambda {:n} {ZERO}}
   {lambda {:n} {REDUCE ADD {ONE} {MAP {lambda {:n}
                          {REDUCE MULT {ONE} {RANGE {ONE} :n}}}
          {RANGE {ONE} {PREV :n}}}}}} :n}}}

'{LENGTH {LFAC {SIX}}}
-> {LENGTH {LFAC {SIX}}} 
 
}

_p {b Note:} Naïvely defining numbers at the [[λ-calculus|?view=lambda_calculus]] level as lists of dots is easy to understand and explore, but is highly inefficient and quickly leading to a stack overflow. Defining numbers as {b binary numbers of variable length} it becomes possible to break the glass ceiling quickly found, as it can be seen in [[oops6]] and compute big numbers, for instance:

{center {pre
fibonacci(100) = 354224848179262000000
factorial(22) = 1124000727777607680000
}}

}

{{block}
{uncover {COCO}/e_fon4.jpg 100 500 fon4{br}encre monotype sur papier 18x24cm}
_h2 9) back to lambdas

_p Using nothing but the {b lambda} and {b def} special forms, we have built an extensible set of user defined constants and functions.

{prewrap
HI, SWAP, TRUE, FALSE, IF, AND, OR, NOT, XOR, PAIR, LEFT, RIGHT, WIKI, P.DISP, P.SWAP, halfAdder, fullAdder, 4bitsAdder, NIL, NIL?, MYTREE, LIST, DISP, STOP, RECURSE, CONCAT, REVERSE, LENGTH, ZERO, ZERO?, SUCC, PREV, ONE, TWO, THREE, FOUR, FIVE, SIX, ADD, SUB, MULT, MULT.rec, EIGHT, POW, POW.rec, n256, DIV, MOD, GCD, FAC, FIBO, RANGE, MAP, REDUCE, LFAC, HANOI
}

_p At this point we have explored the foundations of coding, trying to understand them as simple text replacements processes.

_p We can go deeper forgetting the second {b def} special form.
_p We have seen that the {b DISP} function is recursive, it calls its name, {b DISP} must be given a name and so {b def} seems to be a "must-have". Fortunately there is a workaround, a very simple one, thanks to a new function called the {b Y-combinator}, acting as a bridge.

{pre
'{def Y {lambda {:f} {:f :f}}}
-> {def Y {lambda {:f} {:f :f}}}
}

_p First, let's rewrite the {b DISP} function

{pre
'{def DISP
 {lambda {:l}
  {{IF {NIL? :l}
       {lambda {:l} }
       {lambda {:l} {LEFT :l}
                    {DISP {RIGHT :l}}}} :l}}}
}

_p as a new one, {b ADISP}, where is added a new argument acting as a fix point

{pre
'{def ADISP
 {lambda {:f :l}
  {{IF {NIL? :l}
       {lambda {:f :l} }
       {lambda {:f :l} {LEFT :l}
                       {:f :f {RIGHT :l}}}} :f :l}}}
-> {def ADISP
 {lambda {:f :l}
  {{IF {NIL? :l}
       {lambda {:f :l} }
       {lambda {:f :l} {LEFT :l}
                       {:f :f {RIGHT :l}}}} :f :l}}}
}

_p Applying the {b Y-combinator} to {b ADISP} and {b LIST} works fine.

{pre
'{{Y ADISP} {LIST}}
-> {{Y ADISP} {LIST}}
}

_p Now let's compose {b Y} and {b ADISP} into a new function {b YDISP}

{pre
'{def YDISP
 {lambda {:l}
  {{{lambda {:f} {:f :f}}
   {lambda {:f :l}
    {{IF {NIL? :l}
         {lambda {:f :l} }
         {lambda {:f :l} {LEFT :l}
                         {:f :f {RIGHT :l}}}} :f :l}}} :l}}}
-> {def YDISP
 {lambda {:l}
  {{{lambda {:f} {:f :f}}
   {lambda {:f :l}
    {{IF {NIL? :l}
         {lambda {:f :l} }
         {lambda {:f :l} {LEFT :l}
                         {:f :f {RIGHT :l}}}} :f :l}}} :l}}}

'{YDISP {LIST}}
-> {YDISP {LIST}}
}

_p Let's combine the definition and the call in an {b IIFE}

{pre
'{{lambda {:l}
  {{{lambda {:f} {:f :f}}
   {lambda {:f :l}
    {{IF {NIL? :l}
         {lambda {:f :l} }
         {lambda {:f :l} {LEFT :l}
                         {:f :f {RIGHT :l}}}} :f :l}}} :l}}
 {LIST}}
}

_p Finally replacing all the names by their lambda definitions, [{b NIL?, LEFT, RIGHT, LIST, ...}] leads to this "cascade" of nested lambdas

{pre
'{{lambda {:l}
 {{{lambda {:f} {:f :f}} 
   {lambda {:f :l}
  {{{lambda {:a :b :c} {:a :b :c}} 
    {{lambda {:c} {:c 
      {lambda {:a :b} 
       {lambda {:a :b} :b}}}} :l}
        {lambda {:f :l} }
         {lambda {:f :l}
         {{lambda {:c} {:c
           {lambda {:a :b} :a}}} :l} {:f :f 
            {{lambda {:c} {:c 
              {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 {:a :b :c} {:a :b :c}} 
    {{lambda {:c} {:c 
      {lambda {:a :b} 
       {lambda {:a :b} :b}}}} :l}
        {lambda {:f :l} }
         {lambda {:f :l}
         {{lambda {:c} {:c
           {lambda {:a :b} :a}}} :l} {:f :f 
            {{lambda {:c} {:c 
              {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 Left as an exercice this is the double recursive code for {b the Towers of Hanoï} rewritten as a single lambda-expression with {b 5} disks and {b 3} towers

{pre
'{{lambda {:n :from :to :via}
{{{lambda {:g} {:g :g}} 
   {lambda {:g :n :from :to :via}
  {{{lambda {:a :b :c} {:a :b :c}}
    {{lambda {:c} {:c 
      {lambda {:a :b} 
       {lambda {:a :b} :b}}}} :n}
        {lambda {:g :n :from :to :via} }
         {lambda {:g :n :from :to :via} {:g :g 
         {{lambda {:c} {:c 
           {lambda {:a :b} :b}}} :n} :from :via :to} {div} move 
           {{lambda {:c} {:c 
             {lambda {:a :b} :a}}} :n} 
                         from tower :from to tower :to {:g :g
             {{lambda {:c} {:c 
               {lambda {:a :b} :b}}} :n} :via :to :from} }}
                 :g :n :from :to :via}}} :n :from :to :via}}
               {{lambda {:a :b :c} {:c :a :b}} Disk_1
               {{lambda {:a :b :c} {:c :a :b}} Disk_2
               {{lambda {:a :b :c} {:c :a :b}} Disk_3
               {{lambda {:a :b :c} {:c :a :b}} Disk_4 
               {{lambda {:a :b :c} {:c :a :b}} Disk_5 
                 {lambda {:a}
                  {lambda {:a :b} :a}}}}}}} A B C}  
-> {{lambda {:n :from :to :via}
 {{{lambda {:g} {:g :g}} 
  {lambda {:g :n :from :to :via}
{{{lambda {:a :b :c} {:a :b :c}}
  {{lambda {:c} {:c 
    {lambda {:a :b} 
     {lambda {:a :b} :b}}}} :n}
      {lambda {:g :n :from :to :via} }
       {lambda {:g :n :from :to :via} {:g :g 
       {{lambda {:c} {:c 
         {lambda {:a :b} :b}}} :n} :from :via :to} {div} move 
         {{lambda {:c} {:c 
           {lambda {:a :b} :a}}} :n} from tower :from to tower :to {:g :g
           {{lambda {:c} {:c 
             {lambda {:a :b} :b}}} :n} :via :to :from} }} :g :n :from :to :via}}}  :n :from :to :via}}
             {{lambda {:a :b :c} {:c :a :b}} Disk_1
             {{lambda {:a :b :c} {:c :a :b}} Disk_2
             {{lambda {:a :b :c} {:c :a :b}} Disk_3
             {{lambda {:a :b :c} {:c :a :b}} Disk_4 
             {{lambda {:a :b :c} {:c :a :b}} Disk_5 
               {lambda {:a}
                {lambda {:a :b} :a}}}}}}} A B C} 
}

_p Nothing but sequences of text replacements, with all due respect to [[Alonzo Church|https://en.wikipedia.org/wiki/Alonzo_Church]].

_p Still here? Congratulations, you deserve a lullaby.

{audio
 {@ controls style="width:100%; height:20px;"}
 {source
  {@ src="http://b2b3.free.fr/musique/Wiegenlied.m4a" 
 }}
 {p Your browser does not support HTML5 audio.} 
}
{center {pre
Traüme, traüme, du mein sûsses Leben
Von dem Himmel, der die Blumen bringt
Blüten schimmern da, die leben
Von dem Lied, das deine Mutter singt

Traüme, traüme Knospe meiner Sorgen,
Von dem Tage, da die Blume spross
Von dem hellen Blütenmorgen
Da dein Seelchen sich der Welt erschloss

Traüme, traüme, Blüte meiner Liebe
Von der stillen, von der heil'gen Nacht
Da die Blume seiner Liebe
Diese Welt, zum Himmel mir gemacht.

Wiegenlied Opus 41-n°1
Richard Strauss (1864/1949)
}} 
}

{{block}
{uncover {COCO}/e2_bvl232.jpg 100 500 bleu profond{br}EXTREME LENTEUR DANS L.ESPACE{br}encre monotype sur papier 18x24cm}
_h2 conclusion
_p We could go much further, building a real programming language, but that is not the purpose of this page. The following [[λ{sup talk}|?view=coding2]] page gives the full set of {b 9 special forms}

{pre {center {b lambda def if let quote macro script style require}}}

_p and the extendable set of primitives on {b Math, HTML/CSS, DOM, JS, ...} as well as some libraries (bignumbers, complex numbers, graphics, ...), thanks to the web technologies coming for free with the web browsers and rising the syntax presented here to a full-fledged programming language. As a foretaste here are a handful of examples that may give you the desire to [[go further|?view=coding2]].

_h4 1) a big factorial

_p As a first example, here is the code for the {b FAC}torial presented in section {b 8.2 NUMBERS} applied to a big number

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

'{fac 400}
-> {fac 400}
}

_h4 2) curves

_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 The kind of curves which can be found everywhere in the Sagrada Familia, Barcelona, created by Antoni Gaudi, catalan architect. Architecture and coding are part of the same thought process. Abstractions, applications, Shapes/Verbs.

{uncover http://www.apartime.com/images/Curved%20lines.jpg 100 500 La Sagrada Familia, Barcelona, Antoni Gaudi}

_h4 3) the dragon curve

{pre
'{def dcr 
 {lambda {:step :length}
  {let { {:step {- :step 1}}
         {:length {/ :length 1.41421}}
       } {if {> :step 0}
          then T45 
               {dcr :step :length} 
               T-90 
               {dcl :step :length} 
               T45
          else T45 M:length T-90 M:length T45} 
}}}
-> {def dcr 
 {lambda {:step :length}
  {let { {:step {- :step 1}}
         {:length {/ :length 1.41421}}
       } {if {> :step 0}
          then T45 {dcr :step :length} T-90 {dcl :step :length} T45
          else T45 M:length T-90 M:length T45} }}}

'{def dcl {lambda {:step :length}
  {let { {:step {- :step 1}}
         {:length {/ :length 1.41421}}
       } {if {> :step 0}
          then T-45 
               {dcr :step :length} 
               T90 {dcl :step :length} 
               T-45
          else T-45 M:length T90 M:length T-45} 
}}}
-> {def dcl {lambda {:step :length}
  {let { {:step {- :step 1}}
         {:length {/ :length 1.41421}}
       } {if {> :step 0}
          then T-45 {dcr :step :length} T90 {dcl :step :length} T-45
          else T-45 M:length T90 M:length T-45} }}}
}
 
_p The call {code '{dcr 10 360}} produces a sequence of {b 4093} words begining with 
{prewrap T45 T45 T45 T45 T45 T45 T45 T45 T45 T45 M11.250283388970585 T-90 M11.250283388970585 T45 T-90 T-45 M11.250283388970585 T90 M11.250283388970585 ...
}

_p which, given to a graphic device, the {b turtle} function, draws a SVG {b dragon curve}.

{center
{svg 
 {@ width="580px" height="580px" style="box-shadow:0 0 8px #888;"}
 {path {@ d="M {turtle 230 130 0 {dcr 12 360}}" fill="transparent" stroke="#888" stroke-width="1"}}
}}

_h4 4) colors

_p 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 Finally, don't forget that {b this wiki page is itself written according to the same syntax}, and in particular the very simple code ensuring a pleasant display in blocks developing horizontally, the active code of the examples evaluated in real time in the page, all accessible on the web and/or printable as a PDF file from the web browser. {b lambdatalk} is a functional programming language working in a wiki, {b lambdatank}, easy to instal on top of any web browser, allowing to produce rich documents on the web.

_p You are welcome in the {b lambdaway project}.

_p Paintings are from [[colette|http://colette.cerda.free.fr/coco.c/]], except the first one from Salvador Dali.

_p {i marty.alain at free.fr (2021/05/17-26)}

}

{{hide}
{def COCO http://colette.cerda.free.fr/coco.c/data}
{def block 
  div {@ style="display:inline-block; width:600px; vertical-align:top; padding:5px; "}}
}

{style 
body { background:#444; } 
#page_frame { border:0; background:#444; width:600px; margin-left:0; }
#page_content { background:transparent; color:#fff; border:0; width:7000px; box-shadow:0 0 0; font-family:papyrus, optima; }
.page_menu { background:transparent; color:#fff; }
a { color:#f80; }
pre { box-shadow:0 0 8px #000; padding:5px; background:#444; color:#fff; font:normal 1.0em courier; }
b { color:cyan; }
h1 { font-size:4.0em; margin-left:0; }
h2 { font-size:3.0em; }
h3 { font-size:1.5em; }
}