lambdascratch

http://code.fed.wiki/assets/pages/lambda-talk-in-a-frame/repl.html HEIGHT 1000

_h1 λscratch _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 or 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 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 « Could that be done without the big machinery coming with SCRATCH? » _p This is a first sketch of an answer using {b lambdatalk} inside {b lambdatank}, a small (30kb zipped) wiki working in any web browser. {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 where nested blocks highlight {b values, variables, primitive functions, user defined functions, definitions, replacements, ifthenelse structures} and {b local contexts}. _p Let's go further, defining the syntax more precisely and giving more examples. _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? _h2 2) other examples _p The factorial example is not the simplest one. Let's go on with more simple things. _h3 2.1) words _h4 2.1.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! } _h4 2.1.2) abstraction _p We can abstract {b James} and {b Bond} from the previous sentence, using an anonymous function defined and immediately applied to two variables, {b :a} and {b :b} {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} } _h4 2.1.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!}} } _h4 2.1.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} } _h4 2.1.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}} '{swap Monica Bellucci} } _p It's interesting to know that {b words, abstractions} & {b applications} can be combined to build the basic objects of a programming language, the data structures and the control structures, for example lists and loops. See scratch2 for a little more. _h3 2.2) numbers _h4 2.2.1) numbers are special words and are evaluated to themselves {pre {{val} 123} -> 123 } _h4 2.2.2) applying the {b +} primitive to two numbers {pre {{prim} + {{val} 1} {{val} 2}} -> 3 } _p Using lambdatalk we would write {pre '{+ 1 2} -> 3 } _h4 2.2.3) evaluating a nested expression 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. _h4 2.2.4) an anonymous function is defined and immediately applied 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 Written {code '{{lambda {x y} {sqrt {+ {* x x} {* y y}}}} 3 4}} using lambdatalk. Lambda is used instead of "replace" for historical reasons and ... to get attention in the salons. _h4 2.2.5) giving a name to the previous anonymous function {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 Written {code '{def hypo {lambda {x y} {sqrt {+ {* x x} {* y y}}}}}} using lambdatalk _h4 2.2.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}}. _h4 2.2.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. _h4 2.2.8) creating a local context _p Instead of writing an anonymous function immediately applied to values, as we did in section 2.2.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 usedul 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. _h2 3) 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} {br}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. _h2 conclusion _p Using visual colored blocks we have introduced a first set of concepts used in programming languages, values, constants, primitives, functions, variables, local contexts, if then else and loops using recursion. _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/02} _p HN|https://news.ycombinator.com/item?id=30848382 ;; coder's corner {{hide} {def define div {@ class="bloc" style="background:#ff0;"}define} {def replace div {@ class="bloc" style="background:#0ff;"}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;"}} {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 .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; } pre { padding:10px; background:#fff; box-shadow:0 0 8px #000; font-size:0.8em; } }