lambdaway :: book

3 | list | login |load

| |

{{block intro}
{uncover http://colette.cerda.free.fr/coco.c/data/e_aok1.jpg 100 500 AOK.1{br}encre monotype sur papier 10x15cm}
_h1 coding | [[λ-calc|?view=coding]] | [[λ-talk|?view=coding2]] | [[λ-tank|?view=coding3]]

_h2 introduction

_p We give a gentle introduction to coding, highlighting the unicity of the mechanism used to evaluate expressions, a simple {b text rewriting} process.

_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
_ul 9) back to lambdas
_ul conclusion

_p Let's go!
}

{{block 1}
{uncover http://colette.cerda.free.fr/coco.c/data/e_aok2.jpg 100 500 AOK.3{br}encre monotype sur papier 10x15cm} 
_h2 1) lambda

_p The following command

{pre
replace marked words
     in this sentence 
     by other words
}
_p is rewritten, in a shorthand notation, as

{pre
'{{lambda {:words} sentence} words}
}

_p and used for instance like this

{pre
'{{lambda {:a :b} My name is :b, :a :b!} James Bond} 
-> {{lambda {:a :b} My name is :b, :a :b!} James Bond}
}

_p Smart people call this expression an {b IIFE}, an ({b I}mmediately {b I}nvoked {b F}unction {b E}xpression). Let's forget about it for now! It's just {b text rewriting}.
}

{{block 2}
{uncover http://colette.cerda.free.fr/coco.c/data/e_aok2.jpg 100 500 AOK.3{br}encre monotype sur papier 10x15cm}
_h2 2) def

_p Naming expressions will help to write and read code in a more pleasant way.

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

'{HI}
-> {HI}

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

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

_p We have built our first user defined constant, {b HI}, and our first user defined function, {b SWAP}.

_p In lambdatalk {b HI} can be seen as a "pointer" to some value and {b '{HI}} as the bounded value. For your information this is how two strings are swapped using "pointers" in the C language:

{pre {@ style="transform:rotate(-2deg); font-style:italic;"}
°°

#include < stdio.h >
  
/* Swaps strings by swapping pointers */ 
void swap (char **str1_ptr, char **str2_ptr) {
  char *temp = *str1_ptr;
  *str1_ptr = *str2_ptr;
  *str2_ptr = temp;
}  
   
int main() {
  char *str1 = "geeks";
  char *str2 = "forgeeks";
  swap(&str1, &str2);
  printf("str1 is %s, str2 is %s", str1, str2);
  getchar();
  return 0;
} 
°°}

_p Two different worlds.

}

{{block 3}
{uncover http://colette.cerda.free.fr/coco.c/data/e_d1.jpg 100 500 SUD d1{br}encre monotype sur papier 10x15cm}
_h2 3) boolean

_p Booleans are 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 IF} and {b TRUE} by their lambda definitions in {b '{IF TRUE yes no}}, go on and be convinced that the sequence of replacements will lead to {b yes}. Let's trace:

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

{{block 4}
{uncover http://colette.cerda.free.fr/coco.c/data/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 geeks 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 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. Smart people call such a thing {b partial application}. As simple as that!
}

{{block 5}
{uncover http://colette.cerda.free.fr/coco.c/data/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 {} TRUE}}
-> {def NIL {lambda {} TRUE}}
'{def NIL? {lambda {:c} {:c {lambda {} FALSE}}}}
-> {def NIL? {lambda {:c} {:c {lambda {} FALSE}}}}

'{NIL? NIL}
-> {NIL? NIL}
'{NIL? {WIKI}}
-> {NIL? {WIKI}}
}

_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. Be patient too, the gift is at the end of the road.

}

{{block 6}
{uncover http://colette.cerda.free.fr/coco.c/data/e_fon.jpg 100 500 fon{br}encre monotype sur papier 10x15cm}
_h2 6) list

_p A list is a pair whose first term is a word and second term is a list or NIL. Such a composed composition is said a {b data recursive structure}. And it's powerful!

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

_p We can 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 automatically all the terms of the list. Before that 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}} and again until {b '{NIL? list}} returns {b TRUE}.

}

{{block 7}
{uncover http://colette.cerda.free.fr/coco.c/data/e_fon2.jpg 100 500 fon2{br}encre monotype sur papier 10x15cm}
_h2 7) recursion

_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 ONE {lambda {:l} }} -> {def ONE {lambda {:l} }}
'{def TWO {lambda {:l} {LEFT :l} {DISP {RIGHT :l}}}} -> {def TWO {lambda {:l} {LEFT :l} {DISP {RIGHT :l}}}}
}

_p the {b DISP} function becomes easier to read

{pre
'{def DISP {lambda {:l} {{IF {NIL? :l} ONE TWO} :l}}}
}

_p Now let's apply {b DISP} to {b '{LIST}},

{pre
'{DISP {LIST}}
-> '{{lambda {:l} {{IF {NIL? :l} ONE TWO} :l}} {LIST}}
-> '{{IF {NIL? {LIST}} ONE TWO} {LIST}}
-> '{TWO {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. 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} ONE TWO} :l}} {LIST}}
-> '{{IF {NIL? {LIST}} ONE TWO} {LIST}}
-> '{ONE {LIST}}  // because '{NIL? {LIST}} is TRUE
-> '{{lambda {:l} } {LIST}}
->       // nothing because '{lambda {:l} } always returns nothing
-> stop
}

_p Finally {b '{DISP {LIST}}} has returned {b hello brave new world}.

_p Done! 
}

{{block 8}
{uncover http://colette.cerda.free.fr/coco.c/data/e_fon3.jpg 100 500 fon3{br}encre monotype sur papier 10x15cm}
_h2 8) some applications

_p Having understood how the recursive process works, we can go on playing with this powerful pattern.

_p First, let's rewrite {b DISP} as {b LENGTH}, displaying dots {b •} instead of list's terms

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

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

_p Let's play with text, reversions, concatenations, ...

{pre
'{def LOOP
 {lambda {:l1 :l2}
  {{IF {NIL? :l1}
       {lambda {:l1 :l2} :l2}
       {lambda {:l1 :l2} {LOOP {RIGHT :l1}
                               {PAIR {LEFT :l1} :l2}}}}
                :l1 :l2}}}
-> {def LOOP
  {lambda {:l1 :l2}
  {{IF {NIL? :l1}
       {lambda {:l1 :l2} :l2}
       {lambda {:l1 :l2} {LOOP {RIGHT :l1} {PAIR {LEFT :l1} :l2}}}} :l1 :l2}}}

'{def REVERSE {lambda {:l} {LOOP :l NIL}}}
-> {def REVERSE {lambda {:l} {LOOP :l NIL}}}

'{def CONCAT {lambda {:l1 :l2} {LOOP {REVERSE :l1} :l2}}}
-> {def CONCAT {lambda {:l1 :l2} {LOOP {REVERSE :l1} :l2}}}

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

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

_p and also

{pre
'{LENGTH {CONCAT {LIST} {LIST}}}
-> {LENGTH {CONCAT {LIST} {LIST}}}        // 4+4 -> 8, a primitive addition
}

_p Following this way we could build an {b arithmetic} full of operators, [{b ADD, MUL, SUB, DIV, MOD, FAC, ...}]. Such a way is detailed in the page [[coding]].

_p And finally this is an example of double recursion with a taste of infinite.

{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 {LENGTH :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 {LENGTH :n} from tower :from to tower :to 
    {HANOI {RIGHT :n} :via :to :from} }}
   :n :from :to :via}}}

'{HANOI {LIST} A B C}    // 4 disks and 3 towers
-> {HANOI {LIST} A B C} 
}

_p With {b 64} discks this function would write {b 2{sup 64}-1 = 18446744073709551615} lines. See more in [[hanoi]].
}

{{block 9}
{uncover http://colette.cerda.free.fr/coco.c/data/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, PAIR, LEFT, RIGHT, WIKI, NIL, NIL?, LIST, DISP, LENGTH, LOOP, REVERSE, CONCAT, 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. Are you ready? Yes? Let's go...
_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.

_p First, let's rewrite the {b DISP} function as a new one, {b ADISP}, adding a new argument, {b :f}.

{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 And now the "magic part", let's apply {b ADISP} to itself and to the list.

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

_p It works but we can do better thanks to a new function called the {b Ω-combinator}, acting as a bridge.

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

'{{Ω ADISP} {LIST}}
-> {{Ω ADISP} {LIST}}
}

_p Going further let's compose {b Ω} and {b ADISP} into a new function {b ΩDISP}

{pre
'{def ΩDISP
 {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 ΩDISP
 {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}}}

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

_p And finally let's forget the name and build 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}}
-> {{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 Left as an exercice, replacing all the names by their lambda definitions, [{b NIL?, LEFT, RIGHT, ABCD}] leads to this "cascade" of lambdas

{pre
'{{lambda {:l}
{{{lambda {:f} {:f :f}} 
   {lambda {:f :l}
  {{{lambda {:a :b :c} {:a :b :c}}
    {{lambda {:c} {:c 
      {lambda {} 
       {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 {}
                {lambda {:a :b} :a}}}}}}}
-> {{lambda {:l}
{{{lambda {:f} {:f :f}} 
   {lambda {:f :l}
  {{{lambda {:a :b :c} {:a :b :c}}
    {{lambda {:c} {:c 
      {lambda {} 
       {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 {}
                {lambda {:a :b} :a}}}}}}}
}

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

{{block conclu}
{uncover http://colette.cerda.free.fr/coco.c/data/e_est.jpg 100 500 EST{br}encre monotype sur papier 10x15cm}
_h2 conclusion
_p We could go much further, building a real programming language, but that is not the purpose of this page. We go further and explore the factory of a text editor, {b lambdatank}, coming with a programming language, {b lambdatalk}, in three other pages:
 
_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 You are welcome in the '{lambda way} project.

_p marty.alain at free.fr (2021/05/17 - 2022/06/17)
_p [[HN|https://news.ycombinator.com/item?id=31779873]]
}

{{hide}
{def block 
 {lambda {:id} 
  div {@ style="display:inline-block; width:600px; vertical-align:top; padding:5px; "}
  {a {@ name=":id"}}
}}

}

{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; }
.page_menu { background:transparent; color:#fff;}
a {color:red}
pre { box-shadow:0 0 8px #000; padding:5px; background:#444; color:#fff; font:normal 1.0em courier; }
b { color:cyan; }
}