lambdaway :: scratch

5 | list | login |load

| |

_h1 λscratch  (1 | [[2|?view=scratch2]] | [[3|?view=scratch3]])

{{column}

_h2 introduction
_p This is how the factorial function is introduced to kids using the [[SCRATCH|https://tutorialscircle.com/scratch-tutorials]] or [[SNAP|https://snap.berkeley.edu/]] or [[λSNAP|http://progopedia.com/implementation/snap/]] programming language.

_img http://epsilonwiki.free.fr/alphawiki_2/data/snap_fac_1.jpg

_p Mathematicians use to compute the product of natural numbers from {code n} to {code 1}, {code n*(n-1)*(n-2)*...*3*2*1}, introducing the factorial function like this:

{pre
factorial(n) = n*factorial(n-1)
factorial(1) = 1
}

_p Using Python we would write

{pre
def factorial(n): 
    if n==1:
        return 1
    else
        return n*factorial(n-1)
}

_p Using the prefixed parenthesized expressions syntax of [[lambdatalk|?view=start]], a small homemade language working in {b lambdatank}, a tiny wiki (30kb zipped) working in any web browser, we would write

{pre
'{def factorial                       // define factorial
 {lambda {:n}                        // as the function of n 
  {if {= :n 1}                       // if n==1 
   then 1                            // then return 1
   else {* :n {factorial {- :n 1}}}  // else return n*factorial(n-1)
  }                                  // end if
 }                                   // end function
}                                    // end define
-> factorial

'{factorial 5}                        // calling factorial of 5
-> 120
}

_p We must admit that blocks are easier to visualize than parentheses, using visual tools is probably a good idea to follow, at least for kids. The question is « {i Could that be done without the big machinery coming with SCRATCH?} »

_p This is a first sketch of an answer using {b [[lambdatalk|?view=start]]} inside {b lambdatank}.

{pre
{{define} {{user} factorial} as
{{replace} {{var} :n} in  
{{iff} {{prim} = {{var} :n} {{val} 1}}
then {{val} 1}
else {{prim} * {{var} :n} {{user} factorial {{prim} - {{var} :n} {{val} 1}}} }}
by }} 1) a function waiting for a value
-> factorial    
{{user} factorial {{val} 5}}                        2) giving a value to the function
-> 120        
}

_p where nested blocks highlight {b values, variables, primitive functions, user defined functions, definitions, replacements, conditional structures} and {b local contexts}.

_p Let's go further, defining the syntax more precisely and giving more examples.
}

{{column}
_h2 1) syntax

_p This syntax -- let's call it {b lambdascratch} -- could be defined using this small set of {b lambdatalk} functions

{pre
{b value}:                  '{{val} hello}     
                        -> {{val} hello}         
                            '{{val} 123}
                        -> {{val} 123}

{b variable}:               '{{var} :x}
                        -> {{var} :x}

{b primitive function}:     '{{prim} max}
                        -> {{prim} max}

{b user defined function}:  '{{user} myfunc}
                        -> {{user} myfunc}

{b define}:                 '{{define} {{user} name} as ...}
                        -> {{define} {{user} name} as ...}

{b replace}:                '{{replace} {{var} :x}
                          in ...
                          by}
                        -> {{replace} {{var} :x}
in ... 
by}

{b if then else}:           '{{iff} {{prim} bool} // or {{user} bool}
                          then ...
                          else ...}
                        -> {{iff} {{prim} bool}
then ... 
else ...}

{b let}:                    '{{lett} {{var} x1} = {{val} v1}
                                {{var} x2} = {{val} v2} 
                        in ...}  
                        -> {{lett} {{var} x1} = {{val} v1}
    {{var} x2} = {{val} v2} 
in ...}
}

_p This is how the factorial's colored {b lambdascratch} code is generated using this syntax

{pre
'{{define} {{user} factorial} as
{{replace} {{var} :n} in 
{{iff} {{prim} = {{var} :n} {{val} 1}}
then {{val} 1}
else {{prim} * {{var} :n} 
               {{user} factorial {{prim} - {{var} :n} {{val} 1}}} }}
by }} // a function waiting for a value
-> factorial    
'{{user} factorial {{val} 5}}  // applying the function
-> 120      
}

_p One could imagine a courageous teacher writing such a code generating colored blocks for kids. Why not?
_p The factorial example is not the simplest one. Let's go on with more simple things.

}

{{column}
_h2 2) words

_h3 2.1) words are evaluated to themselves

_p Words and sentences are written as they are, without quoting them, as in a standard HTML document, {i which was the first requirement in the development of lambdatalk}.

{pre                                                          
{{val} My name is Bond, James Bond!}                                       
-> My name is Bond, James Bond!              
}

_h3 2.2) abstraction

_p We can abstract {b James} and {b Bond} from the previous sentence, using an anonymous function of two variables, {b :a} and {b :b}, defined and immediately applied to two words

{pre 
{{replace} {{var} :a :b} in
{{val} My name is {{var} :b}, {{var} :a} {{var} :b}!} 
by {{val} James Bond}}    
-> {{val} My name is {{val} Bond}, {{val} James} {{val} Bond}!}
-> My name is Bond, James Bond! 
}

_p Using lambdatalk we would write 
{pre 
'{{lambda {:a :b}
          My name is :b, :a :b!
        } James Bond}
}

_p Lambda is used instead of "replace" for historical reasons and ... to get attention in the salons.

_h3 2.3) definition

_p To make things easier we can give a name to the previous anonymous function

{pre
{{define} {{user} HI} 
{{replace} {{var} :a :b} in 
{{val} My name is {{var} :b}, {{var} :a} {{var} :b}!} 
by}}  
-> HI
}
_p Using lambdatalk we would write 
{pre 
'{def HI
 {lambda {:a :b} My name is :b, :a :b!
}}
}

_h3 2.4) application

_p We can now apply this name to several couple of names
{pre
{{user} HI {{val} James} {{val} Bond}}                                                    
-> My name is Bond, James Bond!

{{user} HI {{val} Ward} {{val} Cunningham}}                                               
-> My name is Cunningham, Ward Cunningham!
}
_p Using lambdatalk we would write 
{pre 
'{HI James Bond} 
'{HI Ward Cunningham}
}

_h3 2.5) swapping

_p Here is more useful function used to swap two words

{pre 
{{define} {{user} swap} 
{{replace} {{var} :a :b} in 
       {{var} :b} {{var} :a} 
by}}  
-> swap

{{user} swap {{val} Monica} {{val} Bellucci}}
-> Bellucci Monica
}
_p Using lambdatalk we would write 
{pre 
'{def swap
 {lambda {:a :b}
  :b :a
}} 
-> {def swap
 {lambda {:a :b}
  :b :a
}}

'{swap Monica Bellucci}
-> {swap Monica Bellucci}
}

_p It's interesting to know that {b words, abstractions} & {b applications} can be combined to build the fondamental objects of programming languages, {b data & control structures}, for example lists and loops. See [[scratch2]] for a little more. 
}

{{column}
_h2 3) numbers

_h3 3.1) numbers are evaluated to themselves

_p Numbers are special words on which a set of functions [{code +,-,*,/,%,..., sqrt,...}] can do mathematical operations.

{pre
{{val} 123}                                                                
-> 123
}

_h3 3.2) applying some primitive to two numbers

{pre
{{prim} / {{val} 3} {{val} 4}}                                                              
-> {/ 3 4}
}
_p Using lambdatalk we would write 
{pre 
'{/ 3 4}
-> {/ 3 4}
}

_p Of course primitive and user defined functions can be combined

{pre
{{prim} / {{user} swap {{val} 3} {{val} 4}}}
-> {/ {swap 3 4}}

}

_h3 3.3) evaluating a nested expression

_p For instance: hypo = √{b {@ style="border-top:1px solid #fff"}3*3+4*4}

{pre 
{{prim} sqrt 
{{prim} + {{prim} * {{val} 3} {{val} 3}} 
  {{prim} * {{val} 4} {{val} 4}}}}                         
-> {{prim} sqrt 
{{prim} + {{val} 9} {{val} 16}}}                                                 
-> {{prim} sqrt {{val} 25}}                                                          
-> {{val} 5}                                                                
-> 5                                                                
}
_p Using lambdatalk we would write 
{pre 
'{sqrt {+ {* 3 3} {* 4 4}}}
-> 5
}

_p You can notice here the close similarity between the nested blocks and the nested prefixed parenthesized expressions, {i loved by Lispers and hated by the rest of the world}. It would even come to the point that writing {b '{sqrt {+ {* 3 3} {* 4 4}}}} could become more {i natural} than writing {b √{b {@ style="border-top:1px solid #fff"}3*3+4*4}}, mixing prefix and infix notations, of such a nature as to disgust kids with mathematics for a long time. IMHO.

_p Now if you try to evaluate an expression like this one

{pre 
{{prim} sqrt {{prim} + {{prim} * {{var} :x} {{var} :x}} {{prim} * {{var} :y} {{var} :y}}}}                                                            
}

_p you get {b NaN}, {i Not a Number}, as you can guess, until {b x} and {b y} get a value. It's time to {i procrastinate} using the {b replace} block.

_h3 3.4) and the answer is...

_p As we did before we can define an anonymous function and immediately apply to two numbers

{pre 
{{replace} {{var} :x :y} in 
{{prim} sqrt {{prim} + {{prim} * {{var} :x} {{var} :x}} {{prim} * {{var} :y} {{var} :y}}}} 
by {{val} 3 4}}        
-> {{prim} sqrt {{prim} + {{prim} * {{val} 3} {{val} 3}} {{prim} * {{val} 4} {{val} 4}}}}                      
-> 5                                                               
}
_p Using lambdatalk we would write
 {pre 
'{{lambda {:x :y}
         {sqrt {+ {* :x :x} {* :y :y}}}
         } 3 4}}

_h3 3.5) naming an anonymous function

_p Giving a name to the previous anonymous function will make things easier.
{pre 
{{define} {{user} hypo} 
{{replace} {{var} :x :y} in 
{{prim} sqrt {{prim} + {{prim} * {{var} :x} {{var} :x}} {{prim} * {{var} :y} {{var} :y}}}} 
by}}    
-> hypo
}

_p Using lambdatalk we would write 
{pre 
'{def hypo
 {lambda {:x :y}
  {sqrt {+ {* :x :x} {* :y :y}}}}}
}

_h3 3.6) applying this name to two numbers
{pre
{{user} hypo {{val} 3} {{val} 4}}
-> {{replace} {{var} :x :y} in 
{{prim} sqrt {{prim} + {{prim} * {{var} :x} {{var} :x}} {{prim} * {{var} :y} {{var} :y}}}}
by {{val} 3 4}}                                                        
-> 5

{{user} hypo {{val} 1} {{val} 1}}                                                          
-> {sqrt 2} 
}
_p Using lambdatalk we should write {code '{hypo 3 4}} and {code '{hypo 1 1}}.

_h3 3.7) defining a constant

{pre
{{define} {{user} Φ} as
{{prim} / {{prim} + {{val} 1} {{prim} sqrt {{val} 5}}} {{val} 2}}}
-> Φ

{{user} Φ}
-> {/ {+ 1 {sqrt 5}} 2}
}

_p Written {code '{/ {+ 1 {sqrt 5}} 2}} in lambdatalk.

_p We can do much more ...
}

{{column}
_h2 4) and more...

_h3 4.1) creating a local context

_p Instead of writing an anonymous function immediately applied to values, as we did in section 3.4), we can use a {b syntactic sugar}, the {b let} block, wich creates a local context highlighting the binding between variables and their values.
{pre
{{lett} {{var} :x} = {{val} 3}
    {{var} :y} = {{val} 4}
in {{prim} sqrt {{prim} + {{prim} * {{var} :x} {{var} :x}} {{prim} * {{var} :y} {{var} :y}}}} 
}
-> 5
}

_p As a useful application here is how to compute the area of a triangle of sides [a,b,c] given by the formula
 
{pre {center
 area = √{span {@ style="border-top:1px solid #888"}s*(s-a)*(s-b)*(s-c)} where s = (a+b+c)/2
}}

_p The temporary variable {b s} is computed once and used four times in the formula. Here is the equivalent using lambdascratch.

{pre
{{define} {{user} area}
{{replace} {{var} :a :b :c} in
{{lett} {{var} :x} = {{var} :a}
    {{var} :y} = {{var} :b}
    {{var} :z} = {{var} :b}
    {{var} :s} = {{prim} / {{prim} + {{var} :a} {{var} :b} {{var} :c}} {{val} 2}}
in {{prim} 
sqrt {{prim} * {{var} :s}
  {{prim} - {{var} :s} {{var} :x}}
  {{prim} - {{var} :s} {{var} :y}}
  {{prim} - {{var} :s} {{var} :z}}} 
}}
by
}}
-> area

{{user} area {{val} 3 4 5}}
-> 6
}

_p which is equivalent to this lambdatalk code

{pre
'{def area
 {lambda {:a :b :c}
  {let { {:x :a}
         {:y :b}
         {:z :c}
         {:s {/ {+ :a :b :c} 2}} }
       {sqrt {* :s {- :s :x} {- :s :y} {- :s :z}}}}}}
-> area

'{area3 3 4 5}
-> 6
}

_p Note for lispers: In lambdatalk neither lambdas nor lets can have free variables. In the local context defined by {b let} all variables must be redefined and reassigned. Changing the name as it's done in {b '{:x :a}} is not required, one could simply write {b '{:a :a}}.

_p Here is a last example of the {b let} special form used in the scary [[Fast Fourier Transformation|?view=FFT]] algorithm whose main function is given below, without more explanations:

{pre
{{define} {{user} fft} as
{{replace} {{var} :s :x} 
in {{iff} {{prim} = {{prim} A.length {{var} :x} {{val} 1}}}
then {{var} :x}
else {{lett} {{var} :s} = {{var} :s}
    {{var} :ev} = {{user} fft {{var} :s} {{user} evens {{var} :x}}}
    {{var} :od} = {{user} fft {{var} :s} {{user} odds {{var} :x}}}
in  {{lett} {{var} :ev} = {{var} :ev}
    {{var} :t} = {{user} rotate {{var} :s} {{var} :od} {{prim} A.length {{var} :od}}}
in  {{prim} A.concat {{user} apply {{prim} C.add} {{var} :ev} {{var} :t}}
         {{user} apply {{prim} C.add} {{var} :ev} {{var} :t}}} 
}}}}} 
-> '{def fft   
 {lambda {:s :x}
  {if {= {A.length :x} 1}
   then :x
   else {let { {:s :s}
               {:ev {fft :s {evens :x}} }
               {:od {fft :s {odds  :x}} } }
               {let { {:ev :ev}
                      {:t {rotate :s :od 0 {A.length :od}}} }
                    {A.concat {apply C.add :ev :t}
                              {apply C.sub :ev :t}} }}}}}
where
1) A.length, A.concat, C.add and C.sub are primitive functions 
   for Arrays and Complex numbers
2) fft, evens, odds, rotate and apply are user defined functions
}

_p Fortunately it's more easy and more funny to resolve the {b Towers of Hanoi} game.

_h3 4.2) the towers of hanoi

_p For explanations about this game see the page [[hanoi]]. Here we just show how the {b lambdascratch} code is translated into {b lambdatalk} and evaluated. 
_p So, buidling these blocks

{pre
{{define} {{user} hanoi} as
{{replace} {{var} :n :from :to :via} in 
{{iff} {{prim} = {{var} :n} {{val} 0}}
then exit
else {{user} hanoi {{prim} - {{var} :n} {{val} 1}} :from :via :to}  
      '{br}move :n from :from to :to
     {{user} hanoi {{prim} - {{var} :n} {{val} 1}} :from :via :to} } 
by {i ... the future values.}}}

{{user} hanoi {{val} 5 A B C}}
}

_p leads to this {b lambdatalk} code

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

'{hanoi 5 A B C}
}

_p generating the answer:

{pre
{hanoi 5 A B C}
}

_p Et voilà !

_p I leave it to you to translate other algorithms, found for example in [[coding]] and [[prime_pattern]]. Detailed explanations on recursion can be seen in [[scratch2]].
}

{{column}
_h2 conclusion

_p The visual nesting of the lambdascratch blocks fits perfectly with that of the lambdatalk braces, further justifying the LISP-style parenthetical prefix syntax. There is no such match between SCRATCH blocks and C-style syntax.

_p Using visual colored blocks we have easily introduced a first set of concepts used in programming languages, blocks, values, constants, primitive functions, user defined functions, variables, local contexts, conditionnal structures and loops using recursion. In [[scratch2]] we even go further, reaching the very foundations, the lambda-calculus level.

_p A smart coder could write the lambdascratch interface allowing kids to code via drag & drops of nested colored blocks, and behind the curtain generating the lambdatalk code sent to the evaluator. I'am too lazy to do that, and probably not smart enough.

_p In fact, I think that representing code as nested blocks is just good enough to introduce the very first algorithms ... {b before switching to pure text}, using a {u systematic} nested prefixed parenthesized expressions. Yes, following this old brave LISP, reduced to its fundamentals and dressed in nested pretty colored blocks, which are nothing but a more visual representation of nested parentheses.

_p Finally I think that kids are able to jump the gap between blocks and parentheses, their imagination doing the rest. I even think that writing code is much better than drag & dropping blocks, that it helps for fighting against {b infobesity} and for the development of intelligence. I believe that their [[future]] is in the KISS attitude.

_p This is at least a subject that could be discussed.

_p {i alain marty | 2022/03/20 - 2022/04/03}
_p [[HN|https://news.ycombinator.com/item?id=33580760]]
}

;; coder's corner

{{hide}
{def column 
  div {@ style="display:inline-block; width:700px; vertical-align:top; padding:5px; "}}

{def define div  {@ class="bloc" style="background:#ff0; color:#000;"}define}
{def replace div {@ class="bloc" style="background:#0ff; color:#000;"}replace}
{def iff div     {@ class="bloc" style="background:#f0f; color:#000;"} if} 
{def lett div    {@ class="bloc" style="background:#ccc; color:#000;"} let}

{def prim div    {@ class="bloc" style="background:#f00; color:#fff;"}}
{def user div    {@ class="bloc" style="background:#f80; color:#000;"}}

{def var div     {@ class="bloc" style="background:#000; color:#fff; padding:0 5px;"}}
{def val div     {@ class="bloc" style="background:#fff; color:#000; padding:0 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:4500px; box-shadow:0 0 0; font:normal 1.0em  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 new; }
b { color:cyan; }
h1 { font-size:4.0em; margin-left:0; }
h2 { font-size:3.0em; }
h3 { font-size:1.5em; }
table {background:#fff; color:#000; }

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

.bloc { 
  display: inline-block;
  border: 0px solid #888;
  box-shadow:0px 0px 4px #000;
  border-radius: 9px;
  padding: 0 2px;
  margin: 3px;
  color:#000;
  vertical-align:middle;
} 
}