lambdaway :: digest

5 | list | login |load

| |

{require lib_BN}

{uncover data/camouflage-cameleon.jpg 100 700 '{λ-talk} is a kind of cameleon installed on the web}

_h1 [[french|?view=reflexions_20201219]]| a '{λ-talk}'s digest

_h2 abstract

_ul 1) the kernel
_ul 2) building basic data & control structures
_ul 3) adding syntactic sugar
_ul 4) adding primitives
_ul 5) adding libraries

_p Introducing a programming language is not an easy task and often leaves grey areas suggesting that it is magic that only a few initiates can master. In this essay I look for the most obvious path, not hesitating to go off the beaten track, leading from a very small set of rules to the powerful concepts that make a programming language a great tool to explore the world of algorithms.

_p The key points are introduced without much explanation. For a more detailed presentation please see [[fromroots2canopy]] or [[french|?view=reflexions_20201219]].

_h2 1) the kernel

_p In '{lambda talk} the syntax & evaluation can be sumarized in the following definition of an {b exp}ression:
 
{pre 
exp := word        : any char(s) except '{}    // evaluated to itself
    |  abstraction : (lambda (words) exp)     // evaluated first to a ref
    |  definition  : (def word exp)           // evaluated second to word
    |  application : (exp exp)                // evaluated last (from inside out)
}
_p in other words we can do 3 "things"

{pre
1.1) create an {b anonymous function} 
     using the {b lambda} special form, for instance:

'{lambda {:a :b} {+ :a :b}} -> {lambda {:a :b} {+ :a :b}}  // the function's reference

1.2) name it using the {b def} special form, for instance:

'{def add {lambda {:a :b} {+ :a :b}}} -> {def add {lambda {:a :b} {+ :a :b}}} // an alias of LAMB_0

1.3) and apply it on two any expressions, for instance:

'{add 1 2} -> {add 1 2}
   '{add {add 1 2} {* 3 4}} -> '{add 3 12} -> 15
}

_p Functions are added under the cap to a dictionary initially empty. Finally the evaluation stops when every expressions have been replaced by words.

_h2 2) building basic data & control structures

_p We have two special forms, {b lambda} and {b def}, an ocean of words and we will firstly choose to play with an {b empty dictionary}. What can we do with so little? We can at least replace words in a sentence :

{pre
'{{lambda {:a :b}                  // please, replace :a and :b
          my name is :b, :a :b!   // in this sentence
       } alonzo church}           // by these two words
-> {{lambda {:a :b} my name is :b, :a :b!} alonzo church}
}

_p Using well balanced curly braces, we simply asked the '{lambda talk}'s evaluator to replace two {i variables}, {b :a} and {b :b}, inside the sentence {b my name is :b, :a :b!} by two {i values}, {b alonzo} and {b church}, leading to this result {b my name is church, alonzo church!}.

_p As simple as that! Let's go further and split this rather cumbersome expression using {b def}

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

'{HI alonzo church}
-> {HI alonzo church}
'{HI alan turing}
-> {HI alan turing}
}

_p We simply created a function, added it to the empty dictionary under the name {b HI} and applied it to several couples of words.

_p You are welcome in '{lambda talk}, a programmable programming language.

_p We are going to create lots of functions and build intersting data and control structures.

_h3 2.1) booleans

_p When words come to live. Let's build three simple 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 when {lambda {:a :b :c} {:a :b :c}}}            -> {def when {lambda {:a :b :c} {:a :b :c}}}
}

_p and use them

{pre
'{true alonzo church}
-> {true alonzo church}
'{false alonzo church}
-> {false alonzo church}

'{when true alonzo church}
-> {when true alonzo church}
'{when false alonzo church}
-> {when false alonzo church}
}

_p The words {b true} and {b false} are now bound to functions returning respectively the first and the second of two given words. The word {b when} is bound to a function returning the second word is the first is true else the third. Nothing magic, just text substitutions. Note that {b when} is a function evaluating all terms, we will meet later the special form {b if} which only evaluates the chosen term.

_h3 2.2) pairs

_p When words become data structures. Let's aggregate two words into a {b pair}.

{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 and use it

{pre
'{def P {pair a b}} -> {def P {pair a b}}
'{left {P}}         -> {left {P}}
'{right {P}}        -> {right {P}}
}

_p Let's add two useful functions

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

'{nil? nil}
-> {nil? nil}
'{nil? {P}}
-> {nil? {P}}
}

_p Applied to {b nil} the {b nil?} function returns {b true} and applied to a pair it returns {b false}. The word {b nil} can be seen as a {i false} pair.

_h3 2.3) recursive data structures

_p Terms of a pair can be pairs. For instance

{pre
'{def L {pair a
       {pair b
       {pair c
       {pair d 
       {pair e nil}}}}}} 
-> {def L {pair a {pair b {pair c {pair d {pair e nil}}}}}}
}

_p This is a {b recursive} definition leading to a nested data structure called a {b list} whose last pair is the false one, {b nil}. A list is a {b recursive} data structure. Let' build a recursive function to display its terms

{pre
'{def disp
 {lambda {:l}
  {{when {nil? :l}                      // if :l is nil
         {lambda {:l} }                 // then stop
         {lambda {:l} {left :l}         // else display the first term
                      {disp {right :l}  // do it again on the rest
   }}} :l}                              // then call the function on :l
}}  
-> {def disp
 {lambda {:l}
  {{when {nil? :l}
         {lambda {:l} }
         {lambda {:l} {left :l} {disp {right :l}}}} :l}}}

'{disp {L}} -> {disp {L}}
}

_p You are welcome in the wonderful world of {b recursion}! Now you can play with loops and automatize repetitive processes.

_p Well, the function {b disp} looks rather cumbersome and you can find explanations elsewhere, for instance in [[fromroots2canopy]]. In the following we will just use the same pattern to build new functions to compute for instance the length of a list and to reverse it.

{pre
'{def length
 {lambda {:l}
  {{when {nil? :l}
         {lambda {:l} }
         {lambda {:l} . {length {right :l}}}} :l}}}
-> {def length
 {lambda {:l}
  {{when {nil? :l}
         {lambda {:l} }
         {lambda {:l} . {length {right :l}}}} :l}}}

'{length {L}}
-> {length {L}}   // yes it's the number 4 in a very primitive notation

'{def reverse
 {def reverse.r                       
  {lambda {:a :b}
   {{when {nil? :a}
    {lambda {:a :b} :b}
    {lambda {:a :b} {reverse.r {right :a} {pair {left :a} :b}}}}
     :a :b}}}
 {lambda {:a} {reverse.r :a nil}}}
-> {def reverse
 {def reverse.r                       
  {lambda {:a :b}
   {{when {nil? :a}
    {lambda {:a :b} :b}
    {lambda {:a :b} {reverse.r {right :a} {pair {left :a} :b}}}}
     :a :b}}}
 {lambda {:a} {reverse.r :a nil}}}

'{disp {reverse {L}}}
-> {disp {reverse {L}}}
}

_p Finally, amongst other smart things, we build a double recursive function to solve the {b Towers of Hanoï} game.

{pre
'{def hanoi
 {lambda {:n :from :to :via}
  {{when {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}
  {{when {nil? :n}
   {lambda {:n :from :to :via} }
   {lambda {:n :from :to :via}
    {hanoi {right :n} :from :via :to}
      {div} move {left :n} from tower :from to tower :to 
    {hanoi {right :n} :via :to :from} }}
   :n :from :to :via}}}

'{hanoi {L} A B C}
-> {hanoi {L} A B C}
}

_p Theoretically, it would be possible to go very far by staying at this basic level, but it is sometimes good to put sugar in the coffee.

_h2 3) adding syntactic sugar

_h3 3.1) '{if bool then one else two}

_p This special form allows to replace the previous {b disp} function

{pre
'{def disp
 {lambda {:l}
  {{when {nil? :l}
         {lambda {:l} }
         {lambda {:l} {left :l} {disp {right :l}}}} :l}}}
}

_p by this more readable one

{prewrap

'{def disp2
 {lambda {:l}
  {if {nil? :l}
   then 
   else {left :l} {disp2 {right :l}}}}}
-> {def disp2
 {lambda {:l}
  {if {nil? :l}
   then 
   else {left :l} {disp2 {right :l}}}}}

'{disp2 {L}}
-> {disp2 {L}}
}

_h3 3.2) '{let { {:var val} ...} expression}

_p This special form allows to replace the first example in this page

{pre
'{{lambda {:a :b}
          My name is :b, :a :b!
       } james bond}
-> {{lambda {:a :b} My name is :b, :a :b!} james bond}
}

_p by the following one highlighting the binding between local variables and their values

{pre
'{let { {:a james}                // defining local variables
       {:b bond}                 // :a and :b
     } My name is :b, :a :b!}    // in a local context
-> {let { {:a james}
       {:b bond}
     } My name is :b, :a :b!}
}

_h2 4) adding primitives to the dictionary

_h3 4.1) JS numbers and maths (+, -, *, /, =, ...)

_p We can "do" maths

{pre 
'{+ 1 2}
-> {+ 1 2}
'{sqrt {+ {* 3 3} {* 4 4}}}
-> {sqrt {+ {* 3 3} {* 4 4}}}

'{def φ {/ {+ 1 {sqrt 5}} 2}}
-> {def φ {/ {+ 1 {sqrt 5}} 2}}
'{φ}
-> {φ}

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

'{area 3 4 5}
-> {area 3 4 5}

'{def fac
 {lambda {:n}
  {if {< :n 1}
   then 1
   else {* :n {fac {- :n 1}}}}}}
-> {def fac
 {lambda {:n}
  {if {< :n 1}
   then 1
   else {* :n {fac {- :n 1}}}}}}

'{fac 6}   -> {fac 6}
'{fac 100} -> 9.33262154439441e+157
}

_p The approximative result of {b '{fac 100}}, only 15 digits, will be improved later. For now let's use numbers to improve the {b length} function and introduce a function to index lists

{pre
'{def size 
 {lambda {:l}
  {if {nil? :l}
   then 0
   else {+ 1 {size {right :l}}}}}}
-> {def size 
 {lambda {:l}
  {if {nil? :l}
   then 0
   else {+ 1 {size {right :l}}}}}}

'{size {L}}
-> {size {L}}

'{def get
 {def get.r
  {lambda {:l :n :i}
   {if {= :i :n}
    then {left :l}
    else {get.r {right :l} :n {+ :i 1}}}}}
 {lambda {:l :n}
  {get.r :l :n 0}}}  // should test :n < size(:l), do you see how?
-> {def get
 {def get.r
  {lambda {:l :n :i}
   {if {= :i :n}
    then {left :l}
    else {get.r {right :l} :n {+ :i 1}}}}}
 {lambda {:l :n}
  {get.r :l :n 0}}}

'{get {L} 2}
-> {get {L} 2}
}

_p Indexed lists are inefficient arrays. Happily javascript is under the cap.

_h3 4.2) adding arrays

_p Arrays are indexed sets similar to lists and implemented in a more efficient way.

{pre
'{def A {A.new a b c d}} 
-> {def A {A.new a b c d}} 
'{A.get 2 {A}}
-> {A.get 2 {A}}
'{A.set! 2 hello {A}}
-> {A.set! 2 hello {A}}
}

_p This is how they can be used in "memoïzation". The {b fibonacci} function is well known for bringing the most powerful processors to their knees.

{pre
'{def fib
 {lambda {:n}
  {if {< :n 2}
   then 1
   else {+ {fib {- :n 1}} {fib {- :n 2}}}}}}
-> {def fib
 {lambda {:n}
  {if {< :n 2}
   then 1
   else {+ {fib {- :n 1}} {fib {- :n 2}}}}}}

'{fib 30} 
-> 1346269     // needs about 13800ms on my computer
'{fib 40} 
-> locks it!
}

_p can be efficiently replaced by this memoïzed version

{pre
'{def mfib
 {def mfib.r
  {lambda {:mem :n :i}
   {if {<= :i :n}
    then {mfib.r {A.set! :i 
                         {+ {A.get {- :i 1} :mem}   
                            {A.get {- :i 2} :mem}} 
                         :mem}
                 :n 
                 {+ :i 1}}
    else :mem}}}
 {lambda {:n}
  {A.last {mfib.r {A.new 1 1} :n 2}}}}
-> {def mfib
 {def mfib.r
  {lambda {:mem :n :i}
   {if {<= :i :n}
    then {mfib.r {A.set! :i 
                         {+ {A.get {- :i 1} :mem}   
                            {A.get {- :i 2} :mem}} 
                         :mem}
                 :n 
                 {+ :i 1}}
    else :mem}}}
 {lambda {:n}
  {A.last {mfib.r {A.new 1 1} :n 2}}}}

'{mfib 100} 
-> 573147844013817200000   // about 5ms on my computer
}

_h3 4.3) adding HTML (h1, p, b, ...)

_p You don't like maths? let's play with functions for structuring and styling text.

{pre
'{b hello world} ->
{b hello world}
'{b {i {u hello world}}}
-> {b {i {u hello world}}}

'{def color
 {lambda {:col :txt}
  {span {@ style="color::col;"} :txt}}}
-> {def color
 {lambda {:col :txt}
  {span {@ style="color::col;"} :txt}}}

'{color red hello world}   -> {color red hello world}
'{color green hello world} -> {color green hello world}
'{color blue hello world}  -> {color blue hello world}
}

_p Using pure and basic HTML/CSS, it's straightforward to define a function

{pre
'{def rgb
 {lambda {:y :x :w :h :c}
  {div
   {@ style="position:absolute;     // standard CSS rules
             top::ypx; left::xpx;
             width::wpx; height::hpx;
             background::c;
             border:5px solid #444;"}}}}
-> {def rgb
 {lambda {:y :x :w :h :c}
  {div
   {@ style="position:absolute;
             top::ypx; left::xpx;
             width::wpx; height::hpx;
             background::c;
             border:5px solid #444;"}}}}
}

_p and call it in a {b div} container

{pre
'{div
  {@ style="position:relative;
            top:0; left:0;
            width:310px; height:310px;
            margin:auto;
            background:#444;"}
 {rgb 10 50 200 200 #f00} 
 {rgb 90 10 200 200 #0f0}
 {rgb 50 90 200 200 #00f}

{rgb 50 90 160 160 #f0f}
 {rgb 90 50 35 120 #ff0} 
 {rgb 215 90 120 35 #0ff}

{rgb 90 90 120 120 #fff}
}

}

_p to display directly in the page the following graphic

{div
  {@ style="position:relative;
            top:0; left:0;
            width:310px; height:310px;
            margin:auto;
            background:#444;"}
 {rgb 10 50 200 200 #f00} 
 {rgb 90 10 200 200 #0f0}
 {rgb 50 90 200 200 #00f}

{rgb 50 90 160 160 #f0f}
 {rgb 90 50 35 120 #ff0} 
 {rgb 215 90 120 35 #0ff}

{rgb 90 90 120 120 #fff}
}
{center {i I think [[Johannes Itten| https://en.wikipedia.org/wiki/Johannes_Itten]] would have liked this composition.}}

_h2 5) adding libraries

_p Finally user defined functions and new javascript primitives defined in a {b script} special form can be organised and stored as libraries in some wiki pages. For instance the page [[lib_BN]] contains a set of functions dealing with big numbers and can be included in this page using the {b require} special form.

{prewrap
'{def bigfac
 {lambda {:n}
  {if {< :n 1}
   then 1
   else {BN.* :n {bigfac {- :n 1}}}}}}
-> {def bigfac
 {lambda {:n}
  {if {< :n 1}
   then 1
   else {BN.* :n {bigfac {- :n 1}}}}}}

'{bigfac 6}
-> {bigfac 6}
'{bigfac 500}
->   // quickly outputs:
1220136825991110068701238785423046926253574342803192842192413588385845373153881997605496447502203281863013616477148203584163378722078177200480785205159329285477907571939330603772960859086270429174547882424912726344305670173270769461062802310452644218878789465754777149863494367781037644274033827365397471386477878495438489595537537990423241061271326984327745715546309977202781014561081188373709531016356324432987029563896628911658974769572087926928871281780070265174507768410719624390394322536422605234945850129918571501248706961568141625359056693423813008856249246891564126775654481886506593847951775360894005745238940335798476363944905313062323749066445048824665075946735862074637925184200459369692981022263971952597190945217823331756934581508552332820762820023402626907898342451712006207714640979456116127629145951237229913340169552363850942885592018727433795173014586357570828355780158735432768888680120399882384702151467605445407663535984174430480128938313896881639487469658817504506926365338175055478128640000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
}

_h2 conclusion

_p Currently '{lambda talk} has {b 9} special formss 
{pre lambda, def, if, let, quote, macro, script, style, require
}

_p about 200 primitives

{prewrap
 
{b HTML}: @, div, span, a, ul, ol, li, dl, dt, dd, table, tr, td, h1, h2, h3, h4, h5, h6, p, b, i, u, center, br, hr, blockquote, del, sup, sub, code, img, pre, textarea, audio, video, source, select, option, object, input, iframe, hide, prewrap,

{b GRAPHICS}: canvas, svg, line, rect, circle, ellipse, polygon, polyline, path, text, g, mpath, use, textPath, pattern, image, clipPath, defs, animate, set, animateMotion, animateTransform, title, desc, turtle,

{b MATHS}: +, *, -, /, %, <, >, <=, >=, =, not, or, and, abs, acos, asin, atan, ceil, cos, exp, floor, pow, log, random, round, sin, sqrt, tan, min, max, PI, E, date, long_add, long_mult,

{b WORDS}: W.equal?, W.empty?, W.length, W.get, W.first, W.rest, W.last, W.slice, W.reverse, W.sort, W.lib,

{b SENTENCES}: S.equal?, S.empty?, S.length, S.first, S.rest, S.last, S.get, S.slice, S.serie, S.map, S.reduce, S.replace, S.reverse, S.sort, S.lib,

{b PAIRS & LISTS}: P.new, cons, P.pair?, P.left, car, P.right, cdr, P.disp, P.lib,

{b ARRAYS}: A.new, A.disp, A.join, A.split, A.array?, A.null?, A.empty?, A.in?, A.equal?, A.length, A.get, A.first, A.last, A.rest, A.slice, A.duplicate, A.reverse, A.concat, radic, A.map, A.set!, A.addlast!, A.sublast!, A.addfirst!, A.subfirst!, A.reverse!, A.sort!, A.lib,

and some others ...
}

_p  and ten or so libraries on complex numbers, matrices, 2D/3D graphics, not to mention all those that exist on the web. Enough to make beautiful algorithmic explorations with processes reducible at any time - at least theoretically - to deep text substitutions. The beauty of simple things!

_p {i Alain Marty 2021/01/01}

{style 
pre { box-shadow:0 0 8px #000; padding:10px; }
}