lambdaway :: oops

5 | list | login |load

| |

_h3 [[coding]] | oops | [[oops3]] | [[oops4]] | [[oops5]] | [[oops6]] | [[oops7]] | [[tromp]]
  
{{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 computation as rewriting

{center {pre
Perfection is achieved,
not when there is nothing more to add,
but when there is nothing left to take away.
(Antoine de Saint-Exupery)
}}

_p In this paper we explore {i the making of a programming language} in term of more or less {i complex combinations} of a very {i simple process}, {b [[term rewriting|https://users.dimi.uniud.it/~pietro.digianantonio/slides_didattica/rewriting_systems.pdf]]}.

_p Examples of code, ({i which are evaluated in real time in this page, and can be edited and tested}), will be written using [[lambdatalk|?view=coding]], the programming language used in this wiki, reduced to two special forms, {b lambda} and {b def}, working on a unique type of data, {b words} ; the {b dictionary} will be supposed to be {b empty}, with a few exceptions for illustrative purposes.

_p We will build fundamental data and control structures, {b booleans}, {b pairs, trees, lists} and {b recursion}. On the way we will explore how {b binary numbers} can be added, we will sketch a {b Binary Search Tree}, we will sketch the set of {b natural numbers} and some of their related operators, we will introduce {b map & reduce}, and we will conclude with the algorithm solving the {b Towers of Hanoï} and written as a {b [[λ-calculus|https://arxiv.org/pdf/1503.09060.pdf]]} expression. So as not to forget the foundations of programming languages.

_p See a detailed presentation of the {b lambdaway project} : [[λ-calc|?view=coding]], [[λ-talk|?view=coding2]], [[λ-tank|?view=coding3]], and a short presentation of {b IIFE}s in this page [[coding with iifes|?view=iife]].

_h4 Document map:
 
_ul introduction
_ul20 lambda & def
_ul20 booleans
_ul20 pairs
_ul40 trees
_ul60 a binary search tree
_ul40 lists
_ul60 numbers as lists of dots
_ul60 range, map & reduce
_ul60 numbers as boolean lists
_ul20 the towers of Hanoï
_ul conclusion

_p {i Alain Marty 2021/09/10}
}

{{block}
{uncover http://lambdaway.free.fr/workshop/data/brussels/nef.jpg 100 350 the Familia Sagrada, Antonio Gaudi, Barcelona{br}a frozen waterfall of parabolas}

_h2 introduction

_p Consider the following words replacement command, asked in plain english

{pre
{i replace} : {b foo} {i and} {b bar}
     {i in} : My first name is {b foo} and my last name is {b bar}.  
     {i by} : James {i and} Bond
}

_p To be understood by a computer, we rewrite it in a shorthand notation, a codified syntax, here for instance as a [[lambdatalk|?view=start]] parenthesized expression

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

_p where 
_ul {b lambda} stands for the verb {b replace}, more to see in [[coding]],
_ul colon characters {b :} prefixing {b foo} and {b bar} are for the blue color marking words to be replaced, 
_ul and a set of judiciously balanced {b curly braces} avoiding the need for the {b and}, {b in} and {b by} conjunctions.

_p Given to the lambdatalk evaluator, this 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 it's what could be awaited!

_p The general form of such an expression is

{pre 
'{{lambda {words} expression} words}
}

_p and we will call it an "{b I}mmediately {b I}nvoked {b F}unction {b E}xpression", or {b [[IIFE|https://en.wikipedia.org/wiki/Immediately_invoked_function_expression]]}, following the name coined by [[Ben Alman|http://benalman.com/news/2010/11/immediately-invoked-function-expression/]] for javascript in which such an expression would be written

{pre
(function(foo,bar) '{ 
  return "My first name is " + foo + "and my last name is " + bar +"." 
})("james","bond")
}

_p ... a syntax which does not shine by its great clarity!

_p Everything that follows in this paper could be fully expressed as a cascade of IIFEs. But obviously, even in the lambdatalk syntax, {b IIFE}s are not easy to read and write.
}

{{block}
{uncover https://images.techhive.com/images/article/2017/05/lambda_calculus_900x600-100721981-large.jpg 100 350 the λ way}

_h2 lambda & def

_p In order to make things easier, we will split an {b IIFE} into 3 steps:

_ul 1) use the {b '{lambda {var} body}} expression as an {b anonymous function},
_ul 2) give it a {b name} inside a '{def name function} expression,
_ul 3) and apply this function to values, {b (name values)}.

_p And so, we split the initial {b IIFE} into

_ul 1) a function immediately called {b HI}

{pre 
'{def HI
 {lambda {:foo :bar} 
          My first name is :foo and my last name is :bar.
}}
-> {def HI
 {lambda {:foo :bar} 
          My first name is :foo and my last name is :bar.
}}
}

_ul 2) and followed by an invocation

{pre
'{HI James Bond} 
-> {HI James Bond}
}

_p As a more useful example let's define a function swapping two words

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

_p and let's use it

{pre
'{SWAP James Bond}
-> {SWAP James Bond}
}

_p {b Note:} {i It may be useful to know that the lambdatalk implementation of lambdas does not make them {b closures}, there is no lexical context, but makes them accept automatic {b partial application}, compensating for the lack of closure, as can be seen in the "pair" section. More about this technical point in the page [[coding]].}

_p With these two special forms, {b lambda & def}, we are going to build an extendable set of user defined functions, which for efficiency use to be promoted as primitives. And so, we will define booleans, data structures (pairs, trees, lists), and a fundamental control structure, the recursion.

_p Let's go.
}

{{block}
{uncover https://www.computerhope.com/jargon/t/true-or-false.jpg 100 500 Binary logic}

_h2 booleans

_p The {b SWAP} function returns two given words swapped, let's define two functions, called {b TRUE} and {b FALSE}, returning either the first or the second

{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}}

'{TRUE hello world}
-> {TRUE hello world}
'{FALSE hello world}
-> {FALSE hello world}
}

_p Sounds like a {i choice process}, we add an optional function, {b IF}, to make things clearer.

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

'{IF TRUE hello world}
-> {IF TRUE hello world}
'{IF FALSE hello world}
-> {IF FALSE hello world}
}

_p The 3 functions {b IF, TRUE, FALSE} are called {b booleans operators} allowing to say " {i if something is true then take the first term else the second} ".

_p Here are four useful boolean 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 Unexpectedly it seems that it is not possible at this stage to construct predicate functions, for example a function testing the equality between two words. In this paper we will wait for the section "numbers as lists" to do so. 
}

{{block}
{uncover https://www.wolfram.com/system-modeler/industry/compact/examples/electrical-engineering/8-bit-adder/images/output1.png 100 300 a 8-bits additioner}

_h2 pairs

_p We can soon aggregate words using {b def} - remember the {b HI} constant - but yet we have no tool to acces each of them. Let's take another way and define a {b fundamental data structure}, so called a {b PAIR}.

{pre
P = [hello world]
}

_p in other words

{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}}}
}

_p Using {b PAIR} we aggregate two words in an ordered set and using {b LEFT} or {b RIGHT} we acces the left or the right one.

{pre
'{def P {PAIR hello world}}
-> {def P {PAIR hello world}}
'{LEFT {P}}
-> {LEFT {P}}
'{RIGHT {P}}
-> {RIGHT {P}}
}

_p More details about pairs can be seen in [[coding]].

_h3 a 4bits additioner

_p Thanks to pairs we can add booleans. Here is for instance a 4bits 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}          //   1000
}

_p We have built a process adding booleans, in other words {b 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.

_p The 8bits adder is detailed [[here|?view=4bit_adder2]]. See also a [[recursive n-bit-adder|?view=oops3]] implemented as pire lambda expressions.
 
_h3 to be or not to be?

_p Before going further we need to test if a value is a PAIR or not, and we will define two functions:
_ul {b NIL} always returning TRUE, and
_ul {b NIL?} returning TRUE if the given value is {b NIL} or FALSE if it's a {b PAIR}.

{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}}}}
°°°
'{def NIL {lambda {} TRUE}}
-> {def NIL {lambda {} TRUE}}
'{def NIL? {lambda {:c} {:c {lambda {} FALSE}}}}
-> {def NIL? {lambda {:c} {:c {lambda {} FALSE}}}}   
 
'{NIL? NIL}
-> {NIL? NIL}
'{NIL? {P}}
-> {NIL? {P}}
}

_p We now have everything we need to create powerful {b recursive} data an control structures. 
}

{{block}
{uncover https://s-media-cache-ak0.pinimg.com/736x/c2/6f/9b/c26f9bfdd74a186a8f17926f091c0175.jpg 100 500 tree}

_h2 trees

_p The interesting part of a pair structure is that {b each term can be either a word or a pair}, leading to a new {b recursive} data structure, the {b tree}. A tree is a pair whose terms can be either a word or a pair or NIL. For instance let's redefine the {b HI} constant as a binary tree

{pre
[  
 [
  [hello •] 
  [brave •] 
 ]
 [
  [new •] 
  [world •]
 ]
]
}

_p in other words

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

_p Each term of a tree can be accessed using {b LEFT} and {b RIGHT}

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

_h3 displaying a tree

_p We can deduce, here without further explanation, a function displaying all the terms of the tree

{pre
'{def T.DISP
 {lambda {:t}
  {{IF {NIL? {RIGHT :t}}
   {lambda {:t} {LEFT :t}}
   {lambda {:t} {T.DISP {LEFT :t}}
                {T.DISP {RIGHT :t}}}} :t}}}
-> {def T.DISP
 {lambda {:t}
  {{IF {NIL? {RIGHT :t}}
   {lambda {:t} {LEFT :t}}
   {lambda {:t} {T.DISP {LEFT :t}}
                {T.DISP {RIGHT :t}}}} :t}}}

'{T.DISP {T}}
-> {T.DISP {T}}
}

_p {b T.DISP} is a function calling itself twice in its body, it's a {b doubly recursive} function and the first example of a fundamental control structure, {b recursion}, we will use in this paper {b to repeat an action until some condition becomes true}. Detailled explanations about the behaviour of the recursive algorithm can be seen in the page [[coding]].

_h3 reversing a tree

{pre
'{def T.REV
 {lambda {:t}
  {{IF {NIL? {RIGHT :t}}
   {lambda {:t} {LEFT :t}}
   {lambda {:t} {T.REV {RIGHT :t}}
                {T.REV {LEFT :t}}}} :t}}}
-> {def T.REV
 {lambda {:t}
  {{IF {NIL? {RIGHT :t}}
   {lambda {:t} {LEFT :t}}
   {lambda {:t} {T.REV {RIGHT :t}}
                {T.REV {LEFT :t}}}} :t}}}

'{T.REV {T}}
-> {T.REV {T}}
}

_h3 the size of a tree

_p Even if at this stage the language doesn't know anything about numbers we can get a "representation" of the number of leaves of a tree
{pre
'{def T.LENGTH
 {lambda {:t}
  {{IF {NIL? {RIGHT :t}}
   {lambda {:t} •}
   {lambda {:t} {T.LENGTH {RIGHT :t}}
                {T.LENGTH {LEFT :t}}}} :t}}}
-> {def T.LENGTH
 {lambda {:t}
  {{IF {NIL? {RIGHT :t}}
   {lambda {:t} •}
   {lambda {:t} {T.LENGTH {RIGHT :t}}
                {T.LENGTH {LEFT :t}}}} :t}}}

'{T.LENGTH {T}}
-> {T.LENGTH {T}}

}

_p And so on...
}

{{block}
{uncover http://zestedesavoir.com/media/galleries/2214/c24c4cfa-706a-4940-a648-e76959b09d5b.jpg.960x960_q85.jpg 100 650 [[BST|https://zestedesavoir.com/tutoriels/558/les-arbres-binaires-de-recherche-1/]]}

_h2 a Binary Search Tree

_p We are going to build a BST data structure equivalent to the picture on top of this section. Let's first define some useful functions, creating nodes and accessing their content.

{pre
'{def BT.node {lambda {:d :l :r} {PAIR :d {PAIR :l :r}}}}
-> {def BT.node {lambda {:d :l :r} {PAIR :d {PAIR :l :r}}}}
'{def BT.data  {lambda {:t} {LEFT :t}}}
-> {def BT.data  {lambda {:t} {LEFT :t}}}
'{def BT.left  {lambda {:t} {LEFT {RIGHT :t}}}}
-> {def BT.left  {lambda {:t} {LEFT {RIGHT :t}}}}
'{def BT.right {lambda {:t} {RIGHT {RIGHT :t}}}}
-> {def BT.right {lambda {:t} {RIGHT {RIGHT :t}}}}
}

_p The picture on top of this section can be defined this way:

{pre
'{def BT
 {BT.node 10 
      {BT.node 5
           {BT.node 2 NIL NIL}
           {BT.node • NIL NIL}
      }
      {BT.node 12 
           {BT.node • NIL NIL}  
           {BT.node 15 
                {BT.node 13 NIL NIL}
                {BT.node 17 NIL NIL}
           }
      }
}}
-> {def BT
 {BT.node 10 
      {BT.node 5
           {BT.node 2 NIL NIL}
           {BT.node • NIL NIL}
      }
      {BT.node 12 
           {BT.node • NIL NIL}  
           {BT.node 15 
                {BT.node 13 NIL NIL}
                {BT.node 17 NIL NIL}
           }
      }
}}
}

_p Using this function

{prewrap
'{def BT.disp
 {lambda {:t}
  {{IF {NIL? :t}
   {lambda {:t} }
   {lambda {:t} {BT.disp {BT.left :t}}
                {BT.data :t}
                {BT.disp {BT.right :t}}}} :t}}}
-> {def BT.disp
 {lambda {:t}
  {{IF {NIL? :t}
   {lambda {:t} }
   {lambda {:t} {BT.disp {BT.left :t}}
                {BT.data :t}
                {BT.disp {BT.right :t}}}} :t}}}
}

_p we display the nodes

{pre
'{BT.disp {BT}}
-> {BT.disp {BT}}
}

_p Note that the tree has been "carefully" built to be displayed in an "apparently" increasing order. But until now numbers are nothing but words and no relation of order has been defined. Or if we want to add a node to an existing tree we need some relation of order and, to go further in this example, we will assume that exist two primitives, {b EQU?} and {b INF?}, on which we can build the {b BT.add} function

{{hide}
{def EQU? {lambda {:a :b} {if {W.equal? :a :b} then TRUE else FALSE} }}
{def INF? {lambda {:a :b} {if {< :a :b} then TRUE else FALSE} }}
}

{pre
'{def BT.add
 {lambda {:x :t}
  {{IF {NIL? :t}
   {lambda {:x :t} {BT.node :x NIL NIL}}
   {lambda {:x :t}
    {{IF {EQU? :x {BT.data :t}}
     {lambda {:x :t} :t}
     {lambda {:x :t}
      {{IF {INF? :x {BT.data :t}}
       {lambda {:x :t} {BT.node {BT.data :t} 
                                {BT.add :x {BT.left :t}}
                                {BT.right :t}} }
       {lambda {:x :t} {BT.node {BT.data :t} 
                                {BT.left :t}
                                {BT.add :x {BT.right :t}} }
  }} :x :t}
  }} :x :t}
  }} :x :t}
}}
-> {def BT.add
 {lambda {:x :t}
  {{IF {NIL? :t}
   {lambda {:x :t} {BT.node :x NIL NIL}}
   {lambda {:x :t}
    {{IF {EQU? :x {BT.data :t}}
     {lambda {:x :t} :t}
     {lambda {:x :t}
      {{IF {INF? :x {BT.data :t}}
       {lambda {:x :t} {BT.node {BT.data :t} 
                                {BT.add :x {BT.left :t}}
                                {BT.right :t}} }
       {lambda {:x :t} {BT.node {BT.data :t} 
                                {BT.left :t}
                                {BT.add :x {BT.right :t}}} }
   } :x :t}
  }} :x :t}
  }} :x :t}
}}

'{BT.disp {BT.add 6 {BT}}}
-> {BT.disp {BT.add 6 {BT}}}
}

_p The tree has now a new node, {b 6}, at the right place. Thanks to this function it becomes possible to build an entire BST from a "random" sequence of nodes addition. Left as an exercise ...

_p For information, note that using natural numbers as they are defined later in the section "numbers as lists", we could replace the {b EQU?} and {b INF?} "impure" primitives by two user defined functions, {b N.EQ?} and {b N.LT?}. I thought it best for the presentation not to wait for their definitions later in the page. 
}

{{block}
{uncover https://history-computer.com/ModernComputer/Software/images/McCarthy.jpg 100 350 John McCarthy, the father of LISP}

_h2 lists

_p A {b list} is a special case of a tree whose left term is always a word and the right term is a pair or {b NIL}, for instance

{pre
T = [hello [brave [new [world •]]]]
}

_p in other words

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

_p We can successively get each term of the list using the {b LEFT} accessor function

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

_h3 displaying a list

_p As we did for trees

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

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

_h3 reversing a list

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

'{L.DISP {L.REV {L}}}
-> {L.DISP {L.REV {L}}}
}

_h3 the length of a list

_p As we did for a tree

{pre 
'{def L.LENGTH
 {lambda {:l}
  {{IF {NIL? :l}
   {lambda {:l} }
   {lambda {:l} • {L.LENGTH {RIGHT :l}}}} :l}}}
-> {def L.LENGTH
 {lambda {:l}
  {{IF {NIL? :l}
   {lambda {:l} }
   {lambda {:l} • {L.LENGTH {RIGHT :l}}}} :l}}}

'{L.LENGTH {L}}
-> {L.LENGTH {L}}
}

_p Sounds like numbers, isnt'it?

}

{{block}
{uncover data/LISP-inbinary.jpg 100 500 LISP}

_h2 numbers as lists

_p As an example of application of lists, we define natural numbers, [ {b 0 1 2 ... n} ], as lists of dots, {b •}, displayed using the {b N.DISP} function, very close to {b L.DISP}. Begining with {b NIL} as the number {b zéro}, we build the {b next} and the {b previous} functions, then some of standard arithmetical operators, 
{pre [ {b N.ADD N.SUB N.MULT N.POW N.FAC N.DIV N.MOD N.GCD N.EQ? N.LT? N.GT? ... } ]}

_h3 next & prev

{prewrap

'{def N.DISP
 {lambda {:l}
  {{IF {NIL? :l}
   {lambda {:l} }
   {lambda {:l} •{N.DISP {RIGHT :l}}}} :l}}}
-> {def N.DISP
 {lambda {:l}
  {{IF {NIL? :l}
   {lambda {:l} }
   {lambda {:l} •{N.DISP {RIGHT :l}}}} :l}}}

'{def N.NEXT {lambda {:n} {PAIR • :n}}}
-> {def N.NEXT {lambda {:n} {PAIR • :n}}}

'{def N.PREV                         
 {lambda {:n}
  {{IF {NIL? :n}                    
   {lambda {:n} NIL}                
   {lambda {:n} {RIGHT :n}}} :n}}}
-> {def N.PREV                         
 {lambda {:n}
  {{IF {NIL? :n}                    
   {lambda {:n} NIL}                
   {lambda {:n} {RIGHT :n}}} :n}}}

'{def ONE {N.NEXT NIL}}
-> {def ONE {N.NEXT NIL}} 
'{def TWO {N.NEXT {ONE}}}  
-> {def TWO {N.NEXT {ONE}}}
'{def THREE {N.NEXT {TWO}}}  
-> {def THREE {N.NEXT {TWO}}}
'{def FOUR {N.NEXT {THREE}}}
-> {def FOUR {N.NEXT {THREE}}}
'{def FIVE {N.NEXT {FOUR}}}
-> {def FIVE {N.NEXT {FOUR}}}
'{def SIX {N.NEXT {FIVE}}}
-> {def SIX {N.NEXT {FIVE}}}

'{N.DISP NIL}
-> // nothing
'{N.DISP {ONE}}
-> {N.DISP {ONE}}
'{N.DISP {TWO}}
-> {N.DISP {TWO}}
'{N.DISP {THREE}}
-> {N.DISP {THREE}}

'{N.DISP {N.PREV {ONE}}}
-> {N.DISP {N.PREV {ONE}}} // nothing
'{N.DISP {N.PREV {TWO}}}
-> {N.DISP {N.PREV {TWO}}}
'{N.DISP {N.PREV {THREE}}}
-> {N.DISP {N.PREV {THREE}}}
}

_h3 addition

{prewrap
'{def N.ADD
 {lambda {:a :b}
  {{IF {NIL? :a}
   {lambda {:a :b} :b}
   {lambda {:a :b} {N.ADD {N.PREV :a} {N.NEXT :b}}}}
    :a :b}}}
-> {def N.ADD
 {lambda {:a :b}
  {{IF {NIL? :a}
   {lambda {:a :b} :b}
   {lambda {:a :b} {N.ADD {N.PREV :a} {N.NEXT :b}}}} :a :b}}}

'{N.DISP {N.ADD {TWO} {THREE}}}
-> {N.DISP {N.ADD {TWO} {THREE}}}
}

_h3 subtraction

{prewrap
'{def N.SUB
 {lambda {:a :b}
  {{IF {NIL? :b}
   {lambda {:a :b} :a}
   {lambda {:a :b} {N.SUB {N.PREV :a} {N.PREV :b}}}}
    :a :b}}}
-> {def N.SUB
 {lambda {:a :b}
  {{IF {NIL? :b}
   {lambda {:a :b} :a}
   {lambda {:a :b} {N.SUB {N.PREV :a} {N.PREV :b}}}} :a :b}}}

'{N.DISP {N.SUB {FOUR} {TWO}}} 
-> {N.DISP {N.SUB {FOUR} {TWO}}}
}

_h3 inequality and equality

_p With the subtraction we can compare numbers with 3 predicate functions "lesser than", "greater than" and "equal to".

{pre
'{def N.LT? {lambda {:a :b} {NIL? {N.SUB :a :b}}}}
-> {def N.LT? {lambda {:a :b} {NIL? {N.SUB :a :b}}}}
'{def N.GT? {lambda {:a :b} {NIL? {N.SUB :b :a}}}}
-> {def N.GT? {lambda {:a :b} {NIL? {N.SUB :b :a}}}}
'{def N.EQ? {lambda {:a :b} {AND {NIL? {N.SUB :a :b}} 
                                {NIL? {N.SUB :b :a}}}}}
-> {def N.EQ? {lambda {:a :b} {AND {NIL? {N.SUB :a :b}} {NIL? {N.SUB :b :a}}}}}

'{N.LT? {THREE} {TWO}}   -> {N.LT? {THREE} {TWO}}
'{N.LT? {TWO} {THREE}}   -> {N.LT? {TWO} {THREE}}
'{N.GT? {THREE} {TWO}}   -> {N.GT? {THREE} {TWO}}
'{N.GT? {TWO} {THREE}}   -> {N.GT? {TWO} {THREE}}
'{N.EQ? {THREE} {THREE}} -> {N.EQ? {THREE} {THREE}}
'{N.EQ? {TWO} {THREE}}   -> {N.EQ? {TWO} {THREE}}
'{N.EQ? {THREE} {TWO}}   -> {N.EQ? {THREE} {TWO}}
}

_p Note that {b LT?} is equivalent to {b <=} and {b GT?} to {b >=}, theese are not strict inequalities.

_h3 multiplication

{prewrap
'{def N.MULT
 {def N.MULT.r
  {lambda {:a :b :c}
   {{IF {NIL? :b}
    {lambda {:a :b :c} :c}
    {lambda {:a :b :c} {N.MULT.r :a {N.PREV :b} {N.ADD :c :a}}}}
     :a :b :c}}}
 {lambda {:a :b}
  {N.MULT.r :a :b NIL}}}
-> {def N.MULT
 {def N.MULT.r
  {lambda {:a :b :c}
   {{IF {NIL? :b}
    {lambda {:a :b :c} :c}
    {lambda {:a :b :c} {N.MULT.r :a {N.PREV :b} {N.ADD :c :a}}}} :a :b :c}}}
 {lambda {:a :b}
  {N.MULT.r :a :b NIL}}}

'{N.DISP {N.MULT {THREE} {THREE}}}
-> {N.DISP {N.MULT {THREE} {THREE}}}
}

_h3 power

{prewrap
'{def N.POW   
 {def N.POW.r       
 {lambda {:a :b :c}
  {{IF {NIL? :b}
       {lambda {:a :b :c} :c}
       {lambda {:a :b :c} {N.POW.r :a
                                   {N.PREV :b}
                                   {N.MULT :a :c} }}}
                :a :b :c}}}
 {lambda {:a :b}
  {N.POW.r :a :b {ONE}}}} 
-> {def N.POW   
 {def N.POW.r       
 {lambda {:a :b :c}
  {{IF {NIL? :b}
       {lambda {:a :b :c} :c}
       {lambda {:a :b :c} {N.POW.r :a
                                   {N.PREV :b}
                                   {N.MULT :a :c} }}}
                :a :b :c}}}
 {lambda {:a :b}
  {N.POW.r :a :b {ONE}}}}

'{N.DISP {N.POW {TWO} {N.MULT {FOUR} {THREE}}}}    // 2{sup 7} = 128
-> ••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••  
}

;; note that, contrary to all the previuous expressions
;; the last one is not actually computed and is replaced by the result, a sequence of dots
;; you can uncomment the preceding line to test the algorithm
;; in order to let the whole page computed in a reasonable time, ie < 100ms,
;; it will be the same later when computing tims is too long

_h3 factorial

{prewrap
'{def N.FAC  
 {lambda {:a :b}
  {{IF {NIL? :b}
   {lambda {:a :b} :a}
   {lambda {:a :b} {N.FAC {N.MULT :a :b} {N.PREV :b}}}}
   :a :b}}}
-> {def N.FAC
 {lambda {:a :b}
  {{IF {NIL? :b}
   {lambda {:a :b} :a}
   {lambda {:a :b} {N.FAC {N.MULT :a :b} {N.PREV :b}}}} :a :b}}}

'{N.DISP {N.FAC {ONE} {N.ADD {THREE} {TWO}} }}        // 5! = 120
-> ••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••  // 120 dots
}

_h3 div, mod, gcd

{prewrap
'{def N.DIV                            
  {lambda {:a :b}
   {{IF {NIL? {N.SUB :b :a}}
    {lambda {:a :b} {N.ADD {ONE} {N.DIV {N.SUB :a :b} :b}}}
    {lambda {:a :b} NIL}}
     :a :b}}}
-> {def N.DIV                            
  {lambda {:a :b}
   {{IF {NIL? {N.SUB :b :a}}
    {lambda {:a :b} {N.ADD {ONE} {N.DIV {N.SUB :a :b} :b}}}
    {lambda {:a :b} NIL}} :a :b}}}

'{N.DISP {N.DIV {FOUR} {TWO}}}
-> {N.DISP {N.DIV {FOUR} {TWO}}}
'{N.DISP {N.DIV {FOUR} {THREE}}}
-> {N.DISP {N.DIV {FOUR} {THREE}}}

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

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

'{def N.GCD
 {lambda {:a :b}
  {{IF {NIL? :b} 
   {lambda {:a :b} :a}
   {lambda {:a :b} {N.GCD :b {N.MOD :a :b}}}}
    :a :b}}}
-> {def N.GCD
 {lambda {:a :b}
  {{IF {NIL? :b} 
   {lambda {:a :b} :a}
   {lambda {:a :b} {N.GCD :b {N.MOD :a :b}}}} :a :b}}}
 
'{N.DISP {N.GCD {FOUR} {TWO}}}
-> {N.DISP {N.GCD {FOUR} {TWO}}}
'{N.DISP {N.GCD {FOUR} {THREE}}} 
-> {N.DISP {N.GCD {FOUR} {THREE}}}
}

_p More can be seen in [[coding]].
}

{{block}
{uncover https://www.udacity.com/blog/wp-content/uploads/2020/12/Python-Functions_Blog-scaled.jpeg.webp 100 500 map & reduce}

_h2  range, map & reduce

_p Could you imagine a functional programming language without the {b map} and {b reduce} functions introducing a kind of iteration in a recursive world?
_p  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 {NIL? {N.SUB :b :a}}
    {lambda {:a :b} {PAIR :b NIL}}
    {lambda {:a :b} {PAIR :a {RANGE {N.NEXT :a} :b}} }
   } :a :b}}} 
-> {def RANGE
 {lambda {:a :b}
   {{IF {NIL? {N.SUB :b :a}}
    {lambda {:a :b} {PAIR :b NIL}}
    {lambda {:a :b} {PAIR :a {RANGE {N.NEXT :a} :b}} }
   } :a :b}}}

'{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}}}

'{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}}}

'{L.DISP {MAP N.DISP {RANGE {ONE} {FIVE}}}}
-> •••••••••••••••
'{N.DISP {REDUCE N.ADD NIL {RANGE {ONE} {FIVE}}}}   // 15
-> •••••••••••••••
'{N.DISP {REDUCE N.MULT {ONE} {RANGE {ONE} {FIVE}}}}  // 120
-> ••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••
}

_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 {NIL? :n}
   {lambda {:n} NIL}
   {lambda {:n}
    {REDUCE N.ADD
            {ONE}
            {MAP {lambda {:n} {REDUCE N.MULT
                                      {ONE}
                                      {RANGE {ONE} :n}}}
            {RANGE {ONE} {N.PREV :n}}} }}
  } :n}}}
-> {def LFAC
 {lambda {:n}
  {{IF {NIL? :n}
   {lambda {:n} NIL}
   {lambda {:n} {REDUCE N.ADD {ONE} {MAP {lambda {:n}
                {REDUCE N.MULT {ONE} {RANGE {ONE} :n}}}
          {RANGE {ONE} {N.PREV :n}}}}}} :n}}}

'{N.DISP {LFAC {SIX}}}   // !6 = 154
-> ••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••  
}

_p Obviously, {b in real life}, such user defined function doing "iteration" should be promoted as primitives, and it's the case in the full lambdatalk language. 
}

{{block}
{uncover https://www.researchgate.net/profile/Michael-Flynn-7/publication/2575879/figure/fig4/AS:669436306542623@1536617461905/By-applying-the-basic-three-input-adder-in-a-recursive-manner-any-number-of.png 100 500 recursive binary addition}

_h2 recursive binary addition

_p In the previous sections we have represented numbers as lists of points. The number 1000 is therefore a list of one thousand points, and we are confronted with the stack overflow. By representing numbers in binary notation, for example {b 0, 1, 10, 11, 100, ...} we push the limit much further. For example the binary number

{pre 
100000000000000000000000000000000000000
 00000000000000000000000000000000000000
}

_p is represented by a list of {b 64} characters, {b O, 1}, corresponding to the decimal number {b 2{sup 64} = 18446744073709551616}. We are going to write the addition of two binary numbers represented as lists of characters {b TRUE, FALSE}.

_h3 the B.ADD function

{pre

'{def B.ADD
 {lambda {:a :b}
  {L.REV 
   {B.ADD.rec {L.REV :a}
              {L.REV :b} FALSE}}}}
-> {def B.ADD
 {lambda {:a :b}
  {L.REV 
   {B.ADD.rec {L.REV :a}
              {L.REV :b} FALSE}}}}

'{def B.ADD.rec
 {lambda {:a :b :c}
  {{IF {NIL? :a}
   {lambda {:a :b :c} {PAIR {PAIR :c NIL} NIL}}
   {lambda {:a :b :c}
    {PAIR {LEFT {B.ADD.bit {LEFT :a}
                           {LEFT :b}
                           :c}}
          {B.ADD.rec {RIGHT :a}
                     {RIGHT :b}
                     {RIGHT {B.ADD.bit {LEFT :a}
                                       {LEFT :b}
                                       :c} }}}} } :a :b :c}}}  
-> {def B.ADD.rec
 {lambda {:a :b :c}
  {{IF {NIL? :a}
   {lambda {:a :b :c} {PAIR {PAIR :c NIL} NIL}}
   {lambda {:a :b :c}
    {PAIR {LEFT {B.ADD.bit {LEFT :a} {LEFT :b} :c}}
          {B.ADD.rec {RIGHT :a} {RIGHT :b}
                     {RIGHT {B.ADD.bit {LEFT :a} {LEFT :b} :c} }}}}} :a :b :c}}}

'{def B.ADD.bit
 {lambda {:x :a :b}
  {PAIR {B.ADD.bit.sum :x :a :b}
        {B.ADD.bit.carry :x :a :b}}}}
-> {def B.ADD.bit
 {lambda {:x :a :b}
  {PAIR {B.ADD.bit.sum :x :a :b} {B.ADD.bit.carry :x :a :b}}}}

'{def B.ADD.bit.sum
 {lambda {:x :a :b}
  {XOR :x {XOR :a :b}}}}
-> {def B.ADD.bit.sum
 {lambda {:x :a :b}
  {XOR :x {XOR :a :b}}}}

'{def B.ADD.bit.carry
 {lambda {:x :a :b}
  {OR {AND :a :b}
      {OR {AND :x :a}
          {AND :x :b}}}}}
-> {def B.ADD.bit.carry
 {lambda {:x :a :b}
  {OR {AND :a :b}
      {OR {AND :x :a}
          {AND :x :b}}}}}
}

_h3 testing 7+1

{pre
'{def 111+001
 {B.ADD {PAIR TRUE {PAIR TRUE {PAIR TRUE NIL}}}      // 111   = 7
        {PAIR FALSE {PAIR FALSE {PAIR TRUE NIL}}}}}  // 001   = 1
-> {def 111+001 {B.ADD {PAIR TRUE {PAIR TRUE {PAIR TRUE NIL}}}
                 {PAIR FALSE {PAIR FALSE {PAIR TRUE NIL}}}}}

'{L.DISP {LEFT {111+001}}} -> {L.DISP {LEFT {111+001}}}                   // carry = 1
'{L.DISP {RIGHT {111+001}}} -> {L.DISP {RIGHT {111+001}}}     // sum = 000

and so 111+001 = 1000 which is 8
}

_p At this point {b B.ADD} is a pure composition of lambda expressions, exclusively. Binary numbers are nothing but lists of TRUE and FALSE values. As it is obvious that manipulating numbers as lists of FALSE and TRUE boleans, in real life we will use functions to work with binary numbers in their usual form. Note in [[oops3]] how it becomes possible to calculate the sum of {b 2{sup 64}-1} and {b 1} :

{pre
'{bool2bin
 {B.ADD
  {bin2bool 1111111111111111111111111111111111111111111111111111111111111111}
  {bin2bool 0000000000000000000000000000000000000000000000000000000000000001}}}
-> 10000000000000000000000000000000000000000000000000000000000000000
}

_p which is {b 2{sup 64} = 18446744073709551616}. 
_p Now we can break the glass ceiling of stack overflow ...

}

{{block}
{uncover https://upload.wikimedia.org/wikipedia/commons/8/8d/Iterative_algorithm_solving_a_6_disks_Tower_of_Hanoi.gif 100 250 The Towers of Hanoï}

_h2 the towers of Hanoï

_p This is an example of double recursive function applied on a list. 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}
      {br} move {LEFT :n} from tower :from to tower :to 
    {HANOI {RIGHT :n} :via :to :from} }}
   :n :from :to :via}}}

'{def DISKS
 {PAIR DISK_1
 {PAIR DISK_2
 {PAIR DISK_3
 {PAIR DISK_4
 {PAIR DISK_5
 {PAIR DISK_6
 {PAIR DISK_7 NIL}}}}}}}}
-> {def DISKS
 {PAIR DISK_1
 {PAIR DISK_2
 {PAIR DISK_3
 {PAIR DISK_4
 {PAIR DISK_5
 {PAIR DISK_6
 {PAIR DISK_7 NIL}}}}}}}}

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

_p With 7 disks we need {b {- {pow 2 7} 1}} moves, with 64 disks we should need {b {- {pow 2 64} 1}}, it's a great number!
}

{{block}
{uncover https://upload.wikimedia.org/wikipedia/commons/a/a5/Tsunami_by_hokusai_19th_century.jpg 100 440 A frozen waterfall of lambdas}

_h2 conclusion

_p Remembering that we began with {b IIFES}s we will end this exploration with the Towers of Hanoï written as an {b IIFE}. It's to say that we have to replace all the names used by the {b HANOI} function and the {b DISKS} list by their lambda expressions.

_p We have seen that the {b HANOI} function is recursive, it calls its name, {b HANOI} must be given a name and so the {b def} special form seems to be a "must-have". Fortunately there is a workaround, a very simple one, thanks to a new function called the {b Ω-combinator}, acting as a bridge, defined this way

{pre
'{def Ω {lambda {:g} {:g :g}}}
-> {def Ω {lambda {:g} {:g :g}}}
}

_p First, let's rewrite the HANOI function

_p as a new one called {b A_HANOI}, {i an almost recursive function}, whose body doesn't contain the name anymore, but whose argument's list contains a new argument, {b :g}, acting as a fix point, as a memory of the function's reference

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

'{{Y A_HANOI} {DISKS} A B C}
}

_p Applying the Ω-combinator to {b A_HANOI} and {b DISKS} works fine. Now let's compose the Ω-combinator and A_HANOI into a new function {b Ω_HANOI}

{pre
'{def Ω_HANOI
 {lambda {:n :from :to :via}
  {{{lambda {:g} {:g :g}} 
   {lambda {:g :n :from :to :via}
    {{IF {NIL? :n}
     {lambda {:g :n :from :to :via} }
     {lambda {:g :n :from :to :via}
      {:g :g {RIGHT :n} :from :via :to}
       {br} move {LEFT :n} from tower :from to tower :to 
      {:g :g {RIGHT :n} :via :to :from} }}
     :g :n :from :to :via}
  }} :n :from :to :via}}}
-> {def Ω_HANOI
 {lambda {:n :from :to :via}
  {{{lambda {:g} {:g :g}} 
   {lambda {:g :n :from :to :via}
    {{IF {NIL? :n}
     {lambda {:g :n :from :to :via} }
     {lambda {:g :n :from :to :via}
      {:g :g {RIGHT :n} :from :via :to}
       {br} move {LEFT :n} from tower :from to tower :to 
      {:g :g {RIGHT :n} :via :to :from} }}
     :g :n :from :to :via}
  }} :n :from :to :via}}}
 
'{Ω_HANOI {DISKS} A B C}
}

_p Now let's forget the name and build an IIFE

{pre
'{{lambda {:n :from :to :via}
  {{{lambda {:g} {:g :g}} 
   {lambda {:g :n :from :to :via}
    {{IF {NIL? :n}
     {lambda {:g :n :from :to :via} }
     {lambda {:g :n :from :to :via}
      {:g :g {RIGHT :n} :from :via :to}
       {br} move {LEFT :n} from tower :from to tower :to 
      {:g :g {RIGHT :n} :via :to :from} }}
     :g :n :from :to :via}
  }} :n :from :to :via}} {DISKS} A B C}
}

_p Finally replacing all the names by their lambda definitions, [NIL?, LEFT, RIGHT, ...] leads to a frozen waterfall of nested lambdas

{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} {br} 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 :b :c} {:c :a :b}} DISK_6
               {{lambda {:a :b :c} {:c :a :b}} DISK_7
                 {lambda {:a}
                  {lambda {:a :b} :a}}}}}}}}} A B C} 
}

_p A true {b [[lambda-calculus|https://arxiv.org/pdf/1503.09060.pdf]]} expression made of words, lambda expressions and applications, leading to the result displayed in the previous section.

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

_p Don't worry, in the true life {b [[lambdatalk|http://lambdaway.free.fr/lambdaspeech]]} is a true homemade programming language coming with a set of {b 9} special forms, [{b lambda, def, if, let, macro, quote, script, style, require}] and more than 200 primitives, [{b maths, arrays, html, ...}], allowing to write efficient code. 
_p For instance, thanks to the {b if then else} special form and numbers and math functions properly implemented, the {b HANOI} function could be easier to write

{pre
'{def hanoi          
 {lambda {:n :from :to :via}
  {if {> :n 0}
   then {hanoi {- :n 1} :from :via :to}
        {br} move disk :n from tower :from to tower :to 
        {hanoi {- :n 1} :via :to :from}
   else }}}
}

_p and simply called like this

{pre
'{hanoi 5 A B C}
}

_p To conclude, it is sometimes useful to remember the "making of" a language, its deepest foundations, the founding seed: {b '{{λ {w} x} x}}. I just hope you enjoyed the trip and I welcome your feedback.

_p {i alain marty | marty•alain_at_free•fr | 2021/09/10 - 2022/03/12}

_p [[HN|https://news.ycombinator.com/item?id=28427040]] | [[HN|https://news.ycombinator.com/item?id=28479791]]

_p {i Note: This page is written using the lambdatalk syntax and computed in less than 0.1 second on my powerbookk and iPad pro, all expressions are evaluated except a few ones, too time consuming: factorial, map, reduce.}

}

{{hide}
{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:8200px; 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; }

a[href^="https://"]:after { content: " ➚"; } 
}