lambdaway :: lambda

2 | list | login |load

| |

_h1 lambdas in '{lambda talk}

{center {i There is a life out of closures}}

_p In this page we quickly introduce the {b lambda} special form and explore its behaviour regarding (un)closure, partial application, variadicity and recursion.

_h2 1) syntax & evaluation

_p A lambdatalk expression is defined as follows
{center {pre expression := words | abstractions | applications | definitions }}

_p where

{pre
word        := any chars except spaces and '{}   evaluated to itself
abstraction := '{lambda {words} expression}      evaluated to a word (ref)       
application := '{abstraction expression}         evaluated to words
definition  := '{def word expression}            evaluated to a word (name)   
}

_p Note that the character "{code s}" ending {code words, abstractions, applications & definitions} means {b a sequence of}. The evaluator doesn't translate the code string into a tree of tokens, but does its work inside the string iself, going back and forth in a sequence of textual substitutions resulting in a sequence of words.

_p The implementation of '{lambda talk} insures that evaluations are done in this order: 1) first {b abstractions}, 2) then {b definitions}, 3) and finally {b applications}. The result is a sequence of words sent to the web browser which evaluates any existing HTML/CSS/JS code and outputs the result to the browser's window.

_h2 2) lambda

_p The command
{pre
{b replace}   :a{sub 0} :a{sub 1} ... a{sub n-1}
     {b in}   expression containing some occurences of :a{sub i}
     {b by}   v{sub 0} v{sub 1} ... v{sub p-1}
}

_p rewritten in a prefixed parenthesized form

{pre
°°{{°°lambda °°{°°:a{sub 0} :a{sub 1} ... a{sub n-1}°°}°°
          expression containing some occurences of :a{sub i}
        °°}°° v{sub 0} v{sub 1} ... v{sub p-1}°°}°°
}

_p so called {b IIFE} (Immediately Invoked Function Expression), defines an anonymous function containing a sequence of n arguments {code :a{sub i}}, immediately invoked on a sequence of p values {code v{sub i}}, and returning the expression in its body as so modified:
_p 1) if p < n 
_ul20 the occurrences of the p first arguments are replaced in the function's body by the corresponding p given values,
_ul20 a function waiting for missing n-p values is created,
_ul20 and its reference is returned.
_ul20 example:
{pre
'{{lambda {:x :y} ... :y ... :x ...} hello} 
-> '{lambda {:y} ... :y ... hello ...} // replaces :x by hello
-> LAMB_123 // the new functions's reference
}
_ul20 called with the value world this function will return ... world ... hello ...
_p 2) if p = n 
_ul20 the occurences of the n arguments are replaced in the function's body by the corresponding p given values, 
_ul20 the body is evaluated and the result is returned.
_ul20 example
{pre
'{{lambda {:x :y} ... :y ... :x ...} hello world}
-> '{{lambda {:y} ... :y ... hello ...} world} // replaces :x by hello
-> '{{lambda {} ... world ... hello ...} } // replaces :y by world
-> ... world ... hello ... // the value
}
_p 3) if p > n 
_ul20 the occurrences of the n-1 first arguments are replaced in the function's body by the corresponding n-1 given values, 
_ul20 the occurrences of the last argument are replaced in the body by the sequence of p-n supernumerary values, 
_ul20 the body is evaluated and the result is returned.
_ul20 example:
{pre
'{{lambda {:x :y} ... :y ... :x ...} hello world good morning}
-> '{{lambda {:y} ... :y ... hello ...} world good morning} 
-> '{{lambda {} ... world good morning ... hello ...}} 
-> ... world good morning ... hello ... // the value
}

_h2 3) def

_p IIFEs can be nested, for instance

{pre
'{{lambda {:z}           
 {:z {lambda {:x :y} :x}}}
  {{lambda {:x :y :z}
   {:z :x :y}} Hello World
}}
-> {{lambda {:z}           
 {:z {lambda {:x :y} :x}}}
  {{lambda {:x :y :z}
   {:z :x :y}} Hello World
}}

'{{lambda {:z}              
 {:z {lambda {:x :y} :y}}}
  {{lambda {:x :y :z}
   {:z :x :y}} Hello World
}}
-> {{lambda {:z}              
 {:z {lambda {:x :y} :y}}}
  {{lambda {:x :y :z}
   {:z :x :y}} Hello World
}}
}

_p and we could follow the replacement process and understand how these expressions get the first and the second word of {b Hello World}. But things can quickly become completely unreadable, for instance

{pre
'{{lambda {k}
 {{lambda {f k} {f f k}}
   {lambda {f k}
 {{{{lambda {z} {z
    {{lambda {x y} x}
      {lambda {z} {z
       {lambda {x y} y}}}}
        {lambda {z} {z
         {lambda {x y} x}}}}} k}
         {{lambda {x y z} {z x y}}
           {lambda {f k} }
            {lambda {f k}
            {{lambda {z} {z 
              {lambda {x y} x}}} k} {f f 
              {{lambda {z} {z 
                {lambda {x y} y}}} k}} } }} f k}} k}} 
                {{lambda {x y z} {z x y}} hello
                {{lambda {x y z} {z x y}} brave
                {{lambda {x y z} {z x y}} new 
                {{lambda {x y z} {z x y}} world
                 {lambda {x y} y}}}}}}
-> hello brave new world
}

_p We therefore introduce an optional but useful second special form

{pre
'{def name expression}
}

_p which will greatly simplify writing and reading code. For instance, using names, the long unreadable previous expression will be reduced to

{pre 
'{D {L}}
-> hello brave new world           // explanations in section 4) ...
}

_p This second special form {code def} simply evaluates {code expression}, stores the result in a dictionary (initially empty) and returns {code name} as a reference.

_p The constants thus defined are global and immutable. Examples:

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

HI               // words are not evaluated
-> HI            // writing PI in a worksheet displays "PI"
'{HI}             // bracketed words are evaluated
-> {HI}   // writing =PI() in a worksheet displays {PI}

'{def swap {lambda {:x :y} :y :x}} 
-> {def swap {lambda {:x :y} :y :x}}

'{swap hello world} 
-> {swap hello world}
}

_p Bear in mind that the last expression is nothing but an other way to write this IIFE:

{pre
'{{lambda {:x :y} :y :x} hello world}
-> world hello
}

_h2 4) living without closure

_p A lambdatalk function has access to globals - user defined constants and functions and eventual built-in primitives - but is totally independent of the context and has no side effect. At the time of the invocation, the occurrences of the arguments defined in the list {b and they alone} are replaced in the body of the function by the values provided. The variables of the possible outer function are inaccessible. Their use assumes that they are {i manually} redefined in the list of arguments of the inner function and that they receive their values through an IIFE.

_p For instance, the area of any triangle of sides[a,b,c] is 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 If the intermediate variable {code s} is provided alone in an IIFE, like this :

{pre
'{def area1 {lambda {:a :b :c}
  {{lambda {:s}             // it's an IIFE where :s will be replaced ...
           {sqrt {* :s {- :s :a} {- :s :b} {- :s :c}}}    // ... here ...
   } {/ {+ :a :b :c} 2}}}}             // ... by this value computed once              
-> {def area1 {lambda {:a :b :c}
  {{lambda {:s}
           {sqrt {* :s {- :s :a} {- :s :b} {- :s :c}}}
   } {/ {+ :a :b :c} 2}}}}

'{area1 3 4 5}
-> {area1 3 4 5}                                                  // Not a Number
}

_p it doesn't work, simply because {code [:a :b :c]} are not in the inner function's arguments list and a function knows nothing about its context. It is necessary to {i manually} add the arguments of the calling function

{pre
'{def area2 {lambda {:a :b :c}
  {{lambda {:a :b :c :s}        // :a :b :c are redefined ...
           {sqrt {* :s {- :s :a} {- :s :b} {- :s :c}}}
   } :a :b :c                   // ... get values from the outer func ...
     {/ {+ :a :b :c} 2}}        // ... and from the new computed value
}} 
-> {def area2 {lambda {:a :b :c}
  {{lambda {:a :b :c :s}
           {sqrt {* :s {- :s :a} {- :s :b} {- :s :c}}}
   } :a :b :c {/ {+ :a :b :c} 2}}}}

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

}

_p As this practice is frequent, there is a more meaningful alternative form

{pre 
'{let                      // begin local context
     {                      // defining and assigning local variables 
       {:a0 v0}                   // :a0 = v0
       {:a1 v1}                   // :a1 = v1
        ...
       {:an-1 vn-1}               // :an-1 = vn-1
      }                     // end defining and assigning
     ...
       expressions containing local vars :ai   
     ...
}                        // end local context
}

_p a {i syntactic sugar} equivalent to this IIFE

{pre
'{{lambda {:a0 :a1 ... :an}
          expression containing :ai
  } v0 v1 ... vn}
}

_p which has the advantage of highlighting {i local variables}. So we can write

{pre
'{def area3
 {lambda {:a :b :c}
  {let { {:a :a}                    // in fact, it's a hidden lambda
         {:b :b}                    // we must redefine the arguments
         {:c :c}                    // of the outer lambda
         {:s {/ {+ :a :b :c} 2}}    // and add the new computed variable
       } {sqrt {* :s {- :s :a} {- :s :b} {- :s :c}}}  everything is known
}}}
-> {def area3
 {lambda {:a :b :c}
  {let { {:a :a} {:b :b} {:c :c} {:s {/ {+ :a :b :c} 2}} }
       {sqrt {* :s {- :s :a} {- :s :b} {- :s :c}}}
}}}
'{area3 3 4 5}
-> {area3 3 4 5}
}

_p Such a code reminds definitions/assignations blocks found in imperative languages, for instance in javascript:

{pre
var area = function (a,b,c) '{
  var a = a,              // we could redefine a, b, c
      b = b,              // but it is useless in javascript
      c = c,              // thanks to closure
      s = (a+b+c)/2; 
  return Math.sqrt( s*(s-a)*(s-b)*(s-c) );
};

console.log( area(3,4,5) );

}

_p Even if it is not theoretically required the {code '{let { {:args values} } body}} special form is very useful to write {i in real life} much more easily complex algorithms as it can be seen in this wiki, for instance in [[ADD & MUL|?view=ADD_MUL2]], [[FFT]], [[horner_newton]], ... See also [[closure]].

_h2 5) partial application

_p Let's analyze the well known [{code cons car cdr}] pair structure as it could be defined using Lisp or Scheme.

{pre
(def cons (lambda (x y) (lambda (z) (z x y))))         // closure on x y
(def car (lambda (z) (z (lambda (x y) x))))
(def cdr (lambda (z) (z (lambda (x y) y))))

(def P (cons 'hello 'world))      // in Lisp/Scheme words must be quoted
(car P) -> hello
(cdr P) -> world
}

_p The {code cons} function gets two values, stores them in a local environment {code [x,y]} and returns a function of {code z}. The {code car} function gets this function and, thanks to the closure, returns the first value stored in the local environment {code [x,y]}. We can't do that in lambdatalk. This is how we could build these functions, replacing {b c} by {b k} to avoid conflicts with the built-in {code [cons, car, cdr]} primitives

{pre 
'{def kons {lambda {:x :y :z} {:z :x :y}}}     
-> {def kons {lambda {:x :y :z} {:z :x :y}}}     
'{def kar {lambda {:z} {:z {lambda {:x :y} :x}}}}  
-> {def kar {lambda {:z} {:z {lambda {:x :y} :x}}}} 
'{def kdr {lambda {:z} {:z {lambda {:x :y} :y}}}}  
-> {def kdr {lambda {:z} {:z {lambda {:x :y} :y}}}}

'{def P {kons hello world}}   // partial application
-> {def P {kons hello world}}                         // returning '{lambda {:z} {:z hello world}}           
'{kar {P}}                    // '{:z {lambda {:x :y} :x}} gets the first
-> {kar {P}}          
'{kdr {P}}                    // '{:z {lambda {:x :y} :y}} gets the second
-> {kdr {P}}     
}

_p The {code kons} function gets two values, it's a partial application, stores them in its body and returns a function waiting for {code z}. The {code kar} function gets this function and returns the value bound to the first argument. 
_p Let's go a little further, defining 3 new useful functions

{pre
'{def ø {lambda {:x :y} :y}}    
-> {def ø {lambda {:x :y} :y}}
'{def ø? {lambda {:z} {:z {{lambda {:x :y} :x} kdr} kar}}}  
-> {def ø? {lambda {:z} {:z {{lambda {:x :y} :x} kdr} kar}}}
'{def D
 {lambda {:z}
  {{{ø? :z}
   {kons {lambda {:z} }
         {lambda {:z} {kar :z} {D {kdr :z}}}}} :z}}}
-> {def D
 {lambda {:z}
  {{{ø? :z}
   {kons {lambda {:z} }
         {lambda {:z} {kar :z} {D {kdr :z}}}}} :z}}}
}

_p Now we can build a {b list} of words ending with {b ø} and automatically display its elements

{pre
'{def L {kons hello {kons brave {kons new {kons world ø}}}}}
-> {def L {kons hello {kons brave {kons new {kons world ø}}}}}
'{D {L}}
-> {D {L}}
}

_p It's how can be built a recursive algorithm using nothing but lambdas, their {i lazy behaviour} and native partial application. More explanations in ...

_h2 5) variadicity

_p Functions defined with a given number of arguments can accept any number of values.

{pre
'{def add {lambda {:x :y} {+ :x :y}}} 
-> {def add {lambda {:x :y} {+ :x :y}}}                           // a diadic function
'{add 1 2}
-> {add 1 2}

'{add {S.serie 1 10}}               // accepts any number of values
-> {add {S.serie 1 10}}
}

_p here thanks to the variadicity of +. But that's not required, we could instead write

{pre
'{S.reduce add {S.serie 1 10}}
-> {S.reduce add {S.serie 1 10}}
}

_p A diadic function can be converted to a monodic one via an IIFE and used in a loop:

{pre
'{S.map {{lambda {:x :y} {pow :x :y}} 2} {S.serie 1 10}}
-> {S.map {{lambda {:x :y} {pow :x :y}} 2} {S.serie 1 10}}
}

_p This is a last one very useful in a wiki context

{pre
'{def color
 {lambda {:col :text}
  {span {@ style="color::col"}:text}}}
-> {def color
 {lambda {:col :text}
  {span {@ style="color::col"}:text}}}

'{color #f00 hello world}
-> {color #f00 hello world}
'{color #0ff hello brave new world}
-> {color #0ff hello brave new world}
}

_p And so on.

_h2 conclusion

_p As a conclusion, the way lambdatalk has been implemented enlights the uniqueness of lambdas, everything can be reduced to a deep composition of pure functions replacing words by another ones. No shadow areas, optional {i syntactic sugars} like {code (def, let, if)} and {i nebulous concepts} like {code (closure, partial application, variadicity, laziness, recursion)} are {b demystified}, thanks to the simple and evident behaviour of lambdas which are nothing but text replacement processes. Nothing but words, abstractions and applications. Words, Yin & Yang. The TAO of functional programming.

_p Just kidding? Once again:

_p The {b read & replace} implementation of lambdatalk makes its evaluator work in direct contact with the raw code and in two steps:

_ul 1) abstraction: special forms (lambda def if let ...) are replaced by words, eg: '{def add {lambda {x y} {+ x y}}} -> '{def add LAMB_123} -> add

_ul 2) application: normal (nested) forms are replaced "from inside out" by words, eg: '{sqrt {+ {* 3 3} {* 4 4}}} -> '{sqrt {+ 9 16}} -> '{sqrt 25} -> 5

_ul and the evaluation stops when the code contains only words.

_p Note that lambdas (first class) are also created and evaluated in the application step, in the case of partial applications.

_p During the first step, the raw code (the initial string) is immediately reduced to a smaller sequence of words, some of which are pointers to functions that contain substrings that contain pointers to functions ... and so on, recursively.

_p During the second step, it is in this {b tree of strings and substrings} that the evaluations of normal (nested) forms are carried out independently. It's the reason why the computation of a Fibonacci function inserted in the middle of a page of one million words is not affected by its length. And since functions are really independent of any context - no lexical context, no closure - one could even think of a parallel evaluation, for instance defining lambdas (at least some of them) as [[web-workers|../lambdaspeech/?view=webworker6]].

_p I think it all looks like the stripe and running window of a {i Turing machine}. But I must admit that I never followed to the end the explanations on how a Turing machine works, except maybe in this page [[tm]] ... What do you think about that?

_p I could never get an answer on that aspect. That's probably a stupid question.

_p {i Alain Marty 2020/02/07}

{style 
pre { box-shadow:0 0 8px; padding:5px; }
}