lambdaway :: meta5

1 | list | login |load

| |

{center [[fromroots2canopy]] | meta5 | [[coding]]}

{uncover http://lambdaway.free.fr/workshop/data/dancing_minions.gif 30 300 papaya, banana, cucaracha y lambada}

_h1 kids don't need tools for kids!

_img http://epsilonwiki.free.fr/alphawiki_2/data/snap_fac_1.jpg
{center See also [[future]], [[teaching|http://lambdaway.free.fr/lambdaspeech/index.php?view=teaching]], [[kiddle|https://kids.kiddle.co/Lambda_calculus]]...}

_p This is how, among other useful concepts in programming, {b recursion} is introduced to children using the [[Scratch|https://fr.wikipedia.org/wiki/Scratch_(langage)]] language. With advancing age I return to childhood and still curious about the hidden workings of the tools, this [[overly sweet|https://snap.berkeley.edu/]] approach does not suit me. {i I don't want your fish, give me a fishing rod}. I don't want to be a consumer, I want to be an actor. I want to understand things by myself and from ... scratch.

_p I have noticed that I only understand what I can code in a language without shadow zones. That this language is not the best, that it has few features, that its ecosystem is almost nonexistent is basically irrelevant. What matters is that its foundations are reduced to a handful of clear axioms and that its syntax is simple and systematic. This choice also has the enormous advantage of making the expression evaluator easy to implement, even for the amateur that I am.

_p That's why I built my own language, [[lambdatalk|?view=coding]], on the simplest foundation I know, {b text rewriting}, as it appeared in the 1930s with the λ-calculus and on the simple and uniform syntax popularized by {b LISP}. {b lambdatalk} is a tiny functional language working, {i as a dwarf on the shoulders of giants}, in a tiny IDE, lambdatank, allowing anyone to {b edit and test algorithms} in any web browser.

_p I feel that this type of language is a good tool to offer to a child to approach computer science concepts. Far from the sweet candy baskets, pure text manipulation can even accompany a child in learning to read, write and code. And avoid the brain dulling generated by the overconsumption of too sweet interfaces.

_p Let's introduce this minimalist toolkit.

_h2 1) find & replace

_p A simple find & replace request

{pre

{b find & replace these words} :a & :b
          {b in this sentence} My name is :b, :a :b !
             {b by these ones} James & Bond 
}

_p is rewritten as a prefixed parenthesized expression

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

_p and evaluated in real time to

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

_p It works as awaited, the two words {b :a} and {b :b} inside the sentence have been replaced by the given words, {b James} and {b Bond} and the process is easy to understand. Now, in order to make things more readable, let's rewrite this expression in three steps:

_ul 1. The inner expression (called "anonymous function" by specialists)

{pre
'{lambda {:a :b}      // arguments are prefixed with a colon 
         My name is :b, :a :b !}
}

_ul 2. is given a global name, say {b HI},

{pre
'{def HI
 {lambda {:a :b}      
         My name is :b, :a :b !
}}      
-> {def HI {lambda {:a :b} My name is :b, :a :b !}}
}

_ul 3. more easy to use on demand

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

'{HI Ward Cunningham}
-> {HI Ward Cunningham} 
}

_p It's just {b text rewriting}. Let's define a more useful function

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

'{SWAP Hello World} 
-> {SWAP Hello World}
}

_p That's all, using exclusively {b lambda} and {b def} we have built a new function, {b SWAP}. An we can do it again and again.

_p Before going on, here is a quick technical introduction which can be read in a second time.

{div {@ style="transform:rotate(-2.5deg); border:1px solid grey; padding:10px; "}

_p Reduced to the minimum {b lambdatalk} can be defined like this:

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

_p where:
_ul expressions are reduced to words, lambdas, definitions and applications, 
_ul {b words} are not evaluated, simply skipped by the evaluator, 
_ul {b lambdas} are special forms evaluated first to a function and return a reference,
_ul {b definitions} are then evaluated from inside out and return the given name,
_ul {b applications} are normal forms evaluated last, from inside out,
_ul the {b dictionary} is initially empty of any primitive,
_p A lambda is an anonymous function, first class, callable as a value and returned as a value, partially applicable, memorizing the given values and returning a new lambda waiting for the missing ones.

_p At this level lambdatalk knows nothing about data structures (pairs, trees, lists, ...), about control structures (if then else), about numbers, math operators, HTML/CSS, DOM, ... the dictionary is empty!

_p Only {b lambdas} and {b defs}.
}

_p {b Note:} {i Obviously more explanations should be given around the following examples. This page should be considered as a skeleton used for a guided exploration.}

_p So let's start the journey. In a few lines we will discover booleans, pairs, lists, recursive processes, numbers and more.

_h2 2) booleans

_p Let's define logical functions

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

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

_p Let's follow replacements in {b '{IF TRUE hello world}}:

{pre
0: '{IF TRUE hello world}
1: '{{lambda {:a :b :c} {:a :b :c}} TRUE hello world}
2: '{TRUE hello world}
3: '{{lambda {:a :b} :a} hello world}
4: hello
}

_p Here are three standard logical gates, without more explanations

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

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

_p It's a good exercice to follow the words replacements. Boring but systematic. See how a [[λ-calculus using binary numbers of variable length|?view=oops6]] could be built using these logical gates.

_h2 3) pairs, trees, lists

_p Let's define a data structure, i.e. 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}}}
}

_p A {b pair} is made of two words, P = (word1 , word2)

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

_p Full explanations in [[coding]].

_p Let's build a {b binary tree}, T = (pair , pair)

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

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

_p We will have to answer to this question: « To be or not to be » a {b pair}?

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

'{ISNIL NIL}     -> {ISNIL NIL}
'{ISNIL {P}}     -> {ISNIL {P}}
}

_p A {b list} is a pair whose the left element is a word and the right one is a pair or {b NIL}, L = (word , pair or NIL)

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

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

_p It sounds like a recursive process...

_h2 4) recursion

_p Testing with the {b ISNIL} function the previous sequence

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

_p leads to a recursive function displaying every elements to the list

{pre
'{def DISP
 {lambda {:l}
  {                         // postpone the application ...
   {IF            // remember that IF is not a special form
    {ISNIL :l}                  // it's the end of the list
     {lambda {:l} }                            // then stop 
     {lambda {:l} {LEFT :l}   // else display the left term
                  {DISP {RIGHT :l}}}    // recurse on right
  } :l}                   // ... of the chosen lambda on :l
}}  
-> {def DISP
 {lambda {:l}
  {{IF {ISNIL :l}   
       {lambda {:l} }
       {lambda {:l} {LEFT :l} {DISP {RIGHT :l}}}} :l}}}

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

_p Full explanations in [[coding]]. The important thing is that, using nothing but text rewriting, we have quickly built a powerful concept, {b recursion}, that will accompany us during the rest of the trip.

{uncover http://lambdaway.free.fr/workshop/data/dancing_minions.gif 30 300 Larga vida a la recursividad sin Y-combinador!}

_h2 5) reverse, append, length, ...

_p Using the same pattern we can build some more useful functions

{pre

'{def REVERSE

{def REVERSE.r                 // recursive part
  {lambda {:a :b}
   {{IF {ISNIL :a}   
    {lambda {:a :b} :b}
    {lambda {:a :b} {REVERSE.r {RIGHT :a}
                               {PAIR {LEFT :a} :b}}}} :a :b}}} 
 {lambda {:l}
  {REVERSE.r :l NIL}}}          // init and recurse
-> {def REVERSE
 {def REVERSE.r
  {lambda {:a :b}
   {{IF {ISNIL :a}   
    {lambda {:a :b} :b}
    {lambda {:a :b} {REVERSE.r {RIGHT :a} {PAIR {LEFT :a} :b}}}} :a :b}}} 
 {lambda {:l}
  {REVERSE.r :l NIL}}}

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

'{def APPEND

{def APPEND.r                  // recursive part
  {lambda {:a :b}
   {{IF {ISNIL :b}
    {lambda {:a :b} :a}
    {lambda {:a :b} {APPEND.r {PAIR {LEFT :b} :a}
                              {RIGHT :b}}}} :a :b}}}
 {lambda {:a :b}
  {APPEND.r :a {REVERSE :b}}}}  // init and recurse
-> {def APPEND
 {def APPEND.r
  {lambda {:a :b}
   {{IF {ISNIL :b}
    {lambda {:a :b} :a}
    {lambda {:a :b} {APPEND.r {PAIR {LEFT :b} :a} {RIGHT :b}}}} :a :b}}}
 {lambda {:a :b}
  {APPEND.r :a {REVERSE :b}}}}

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

'{def LENGTH
 {lambda {:l}
  {{IF {ISNIL :l}   
       {lambda {:l} }
       {lambda {:l} .{LENGTH {RIGHT :l}}}} :l}}}
-> {def LENGTH
 {lambda {:l}
  {{IF {ISNIL :l}   
       {lambda {:l} }
       {lambda {:l} .{LENGTH {RIGHT :l}}}} :l}}}

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

_h2 6) a little bit of arithmetic

_p So, let's define natural numbers as lists of dots, begining with {b NIL}.

{pre
'{def ONE {PAIR . NIL}}
-> {def ONE {PAIR . NIL}}
'{LENGTH {ONE}}
-> {LENGTH {ONE}}

'{def FIVE
 {PAIR .
  {PAIR . 
   {PAIR . 
    {PAIR . 
     {PAIR . NIL}}}}}}
-> {def FIVE {PAIR . {PAIR . {PAIR . {PAIR . {PAIR . NIL}}}}}}

'{LENGTH {FIVE}}
-> {LENGTH {FIVE}}
}

_p {b ADD}ing two numbers {b m+n} is similar to {b APPEND}ing two lists of {b m & n} dots

{pre 
'{def ADD                  
 {lambda {:a :b}
  {{IF {ISNIL :b}
   {lambda {:a :b} :a}
   {lambda {:a :b} {ADD {PAIR . :a} 
                        {RIGHT :b}}}} :a :b}}}
-> {def ADD               
 {lambda {:a :b}
  {{IF {ISNIL :b}
   {lambda {:a :b} :a}
   {lambda {:a :b} {ADD {PAIR . :a}  
                        {RIGHT :b}}}} :a :b}}}

'{LENGTH {ADD {FIVE} {FIVE}}}   // 5+5=10
-> {LENGTH {ADD {FIVE} {FIVE}}}
}

_p {b MUL}tiplying two numbers {b m*n} is {b ADD}ing {b m} times {b n} to zéro.

{pre
'{def MUL

{def MUL.r              // recursive part
  {lambda {:a :b :c}
   {{IF {ISNIL :b}
    {lambda {:a :b :c} :c}
    {lambda {:a :b :c} {MUL.r :a {RIGHT :b} {ADD :a :c}}}} 
    :a :b :c}}}
{lambda {:a :b}
 {MUL.r :a :b NIL}}}     // init and recurse
-> {def MUL
 {def MUL.r
  {lambda {:a :b :c}
   {{IF {ISNIL :b}
    {lambda {:a :b :c} :c}
    {lambda {:a :b :c} {MUL.r :a {RIGHT :b} {ADD :a :c}}}} :a :b :c}}}
{lambda {:a :b}
 {MUL.r :a :b NIL}}}

'{LENGTH {MUL {FIVE} {FIVE}}}   // 5*5=25
-> {LENGTH {MUL {FIVE} {FIVE}}}
}

_p The {b FAC}torial of a number {b n} is {b :n} times the {b FAC}torial of {b n-1}

{prewrap
'{def FAC
 {lambda {:a}
  {{IF {ISNIL :a}
   {lambda {:a} {ONE}}
   {lambda {:a} {MUL :a {FAC {RIGHT :a}}}}} :a}}}
-> {def FAC
 {lambda {:a}
  {{IF {ISNIL :a}
   {lambda {:a} {ONE}}
   {lambda {:a} {MUL :a {FAC {RIGHT :a}}}}} :a}}}

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

_p See how a [[λ-calculus using binary numbers of variable length|?view=oops6]] could deal with big numbers.

_h2 7) the towers of hanoï

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

_p The code is built on a doubly recursive function. See explanations [[here|?view=hanoi]].

{pre

'{def HANOI
 {lambda {:n :from :to :via}
  {{IF {ISNIL :n}
   {lambda {:n :from :to :via} }          // then stop
   {lambda {:n :from :to :via}            // else 
    {HANOI {RIGHT :n} :from :via :to}     // move(n-1) from A to C 
     {br}move DISK {LENGTH :n}            // // move DISK n
          from :from to :to               // from A to B
    {HANOI {RIGHT :n} :via :to :from} }}  // move(n-1) from C to B
   :n :from :to :via}}}
-> {def HANOI
 {lambda {:n :from :to :via}
  {{IF {ISNIL :n}
   {lambda {:n :from :to :via} }
   {lambda {:n :from :to :via}
    {HANOI {RIGHT :n} :from :via :to}
     {br}move DISK {LENGTH :n} from :from to :to 
    {HANOI {RIGHT :n} :via :to :from} }}
   :n :from :to :via}}}

'{HANOI {FIVE} A B C}                      // five disks
-> {HANOI {FIVE} A B C}
}

_p Detailed explanations, full functionalities and more examples can be seen in [[coding]] and numerous other pages of this workshop, for instance [[FFT]], [[quicksort]], [[decasteljau]], [[hilbert]], ...

_p And don't forget that lambdatalk is not lost in an empty space, the {b WWW} and its huge library is at its fingertips!

_h2 conclusion

_p I remember this child who was given a big present for Christmas, which he unwrapped with enthusiasm, and then played with the box all morning. If I was employed in an IT company I would probably use a real language like C, Python or Javascript to answer the question as quickly as possible. As I get older, I have no more obligations, I just want to learn, understand and play ... like a kid. For instance like [[Romane|http://lambdaway.free.fr/lambdaspeech/index.php?view=teaching]].

_p Kids don't need tools for kids!

{div {@ style="transform:rotate(-2.5deg); border:1px solid grey; padding:10px; "}
_p To [[HN|https://news.ycombinator.com/item?id=30671422]] folks:
_p This is not a statement, but a question. And yes, I love SCRATCH and I admire its creators. I'm just saying that there can be another way, just as accessible, with minimalist tools, including the one I use, but not only. 
_p I am interested in your opinion.
_p [...]
_p I find it so sad that 99% of the 160 comments are an entre soi between SCRATCH worshippers, of which I am one, and have no relation to the substance of my question. But what else could I expect, everyone stays in their own domain, me first, I guess. I like the presentation of the lambda-calculus made here [[kiddle|https://kids.kiddle.co/Lambda_calculus]], which confirms me in the idea that the children could find profit there, far from the certainties of the adults. 
}

_p {i Alain Marty | marty.alain at free.fr | 2022/03/13}

{uncover http://lambdaway.free.fr/workshop/data/dancing_minions.gif 30 600 Yo entendí todo !}

{macro \/\/ ([^\n]*)\n to <span style="color:yellow">// €1</span></br>}

{style 
@font-face {
  font-family: 'Quicksand';
  src: url(data/quicksand.woff) format('woff');
}
body {
 background:#444;
}
#page_frame, #page_content, .page_menu {
 background:#444;
 color:#fff;
 border:0;
 box-shadow:0 0 0 #000;
 font-family:Quicksand; 
}
pre {
 box-shadow:0 0 8px #000;
 background:#444;
 padding:10px; 
 font-family:courier new;
}
b { color:#fff; }
#page_content a { color:#0ff; }
}