{λ way

user:anonymous

{TITLE}

{div {@ style="column-count:2;
          -moz-column-count:2;
       -webkit-column-count:2;"}

_h2 Abstract

_p The '{lambda way} project is a web application built on two engines, '{lambda talk} and '{lambda tank}. '{lambda talk} is a purely functional language unifying authoring, styling and scripting in a single and coherent Lisp-like syntax, working in '{lambda tank}, a tiny wiki built as a thin overlay on top of any web browser. In this paper we forget '{lambda tank}, mainly a PHP engine managing text files on the server side, and progressively introduce '{lambda talk}, a Javascript engine evaluating code in realtime on the client side. The making of '{lambda talk} is done in three stages:

_ul 1) we define the minimal set of rules making '{lambda talk} a programming language, {i complete even if unusable},
_ul 2) we progressively add numbers, operators, data and control structures making '{lambda talk} {i more usable},  
_ul 3) we finally build on the browsers' full functionalities a set of {i libraries} making '{lambda talk} {i usable and much more efficient}.

_p As a guilding line, at each stage, we compute with a total precision the factorial of {b 5} and {b 50}:
{pre
5!  = 120
50! = 30414093201713378043612608166064
      768844377641568960512000000000000
}

_p In a last section, APPENDICE, some explanations are given on the '{lambda talk}'s Javascript implementation.

_h2 Keywords

_ul Information systems~Wikis
_ul Theory of computation~Regular languages
_ul Theory of computation~Lambda calculus
_ul Software and its engineering~Functional languages
_ul Software and its engineering~Extensible Markup Language (XML)

_h2 introduction

_p '{lambda talk} expressions are written in an editor frame, evaluated in real time and displayed in the wiki's viewer frame, then saved and published on the WEB. « {i A wiki is a web application which allows collaborative modification, extension, or deletion of its content and structure.}{ref 1} » The father of this concept, Ward Cunningham{ref 2}, gives a simple and clear introduction to '{lambda talk}:

_ul {b 1)} Away from curly braces '{} {i words are just words}:
{pre
Hello World!
-> Hello World!
}
_ul {b 2)} Expressions are written in a {i prefix notation}:

{pre
2+3 is equal to '{b {+ 2 3}}
-> 2+3 is equal to {b {+ 2 3}}
}

_ul {b 3)} Functions are created with {i lambda} and named with {i def}:
{pre
'{def SMART_ADD
 {lambda {:a :b}
  :a+:b is equal to {b {+ :a :b}}}} 
-> {def SMART_ADD {lambda {:a :b} :a+:b is equal to {b {+ :a :b}}
}}

'{SMART_ADD 2 3} 
-> {SMART_ADD 2 3}
}

_p These examples use the "{code +}" Math operator, the "{code b}" HTML/CSS markup operator and Javascript numbers. In the following we want to introduce '{lambda talk} built upon the {i deepest foundation} possible, {i simple words}, and we will ignore everything but words until the third section.

_h2 1. words

_p We present the structure and evaluation of a '{lambda talk} expression.

_h3 1.1. expressions

_p '{lambda talk} is mainly built on three rules freely inspired by the {i λ-calculus}{ref 3}. An expression is defined recursively as follows:

{center {pre expression is [word|abstraction|application]* }}

_p where

{pre 
1) word         is [^\s'{}]* 
2) abstraction  is '{lambda {word*} expression}
3) application  is '{abstraction expression}
}

_p An expression is made of {code words}, {code abstractions} and {code applications} where 1) a {code word} is any character except spaces "{code \s}" and curly braces "{code '{}"}, 2) an {code abstraction} is the "process" (called a {i function}) selecting a sequence of {code words} (called {i arguments}) in an {code expression} (called {i body}), 3) an {code application} is the "process" calling an {code abstraction} to replace selected {code words} by some other {code words} (called {i values}).

_p The evaluation follows these rules:

{ol 
{li words are not evaluated,}
{li abstractions are evaluated before applications,}
{li an abstraction is evaluated to a single word, a reference to an anonymous a function stored in a global dictionary, initially empty,}
{li an application is progressively evaluated from inside out, to a sequence of words,}
{li the evaluation stops when all expressions have been reduced to a sequence of words.}
}

_p What can we do with that?

_h4 1.1.1. words 
{pre 
Hello World 
-> Hello World
}
_p Words are not evaluated and are displayed as they are.

_h4 1.1.2. abstraction 
{pre
'{lambda {o a} oh happy day!} 
-> {lambda {o a} oh happy day!}
}
_p The abstraction selects {code o} and {code a} as characters whose occurences in the expression {code oh happy day!} are to be replaced by some future values, and returns the reference to an anonymous function.

_h4 1.1.3. application {sup (1)}
{pre
'{{lambda {o a} oh happy day!} oOOOo aaAAaa} 
-> {{lambda {o a} oh happy day!} oOOOo aaAAaa}  
}
_p The abstraction is defined and immediately called. The abstraction is first evaluated to a word, say {code _LAMB_10}, the application {code '{_LAMB_10 oOOOo aaAAaa}} gets the given values, calls the abstraction which makes the substitution and returns the result, {code oOOOoh haaAAaappy daaAAaay!}.

_h4 1.1.4. application {sup (2)} 
{pre
'{{lambda {z}
 {z {lambda {x y} x}}}
  {{lambda {x y z}
   {z x y}} Hello World}} 
-> Hello

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

_p These expressions return respectively the first and the second words of {code Hello World}. This is very similar to a pair and its accessors. Let's trace the evaluation leading to Hello:

_ul 1) Nested lambdas are first evaluated:

{pre
1: '{{lambda {z} {z {lambda {x y} x}}}
    {{lambda {x y z} {z x y}} Hello World}}
2: '{{lambda {z} {z _LAMB_1}}
    {_LAMB_2 Hello World}}
3: '{_LAMB_3 {_LAMB_2 Hello World}}
where
  _LAMB_1 replaces '{lambda {x y} x}
  _LAMB_2 replaces '{lambda {x y z} {z x y}}
  _LAMB_3 replaces '{lambda {z} {z f1}}
}

_ul 2) Then simple forms are evaluated:

{pre
1: '{_LAMB_3 {_LAMB_2 Hello World}}
2: '{_LAMB_3 {{lambda {x y z} {z x y}} Hello World}} 
}

_p {code '{{lambda {x y z} {z x y}} Hello World}} is a {i partial application} replacing "x" and "y" by "Hello" and "World", creating a new lambda waiting for the third value, {code '{lambda {z} {z Hello World}}}, and returning a reference, {code _LAMB_4}.

{pre
3: '{_LAMB_3 _LAMB_4}
4: '{{lambda {z} {z _LAMB_1}} _LAMB_4}
5: '{_LAMB_4 _LAMB_1}
6: '{{lambda {z} {z Hello World}} _LAMB_1}
7: '{_LAMB_1 Hello World}
8: '{{lambda {x y} x} Hello World}
9: Hello
}

_p To sum up on lambdas:

_ul {code 1) lambdas} are {i first class} functions,
_ul {code 2) lambdas} accept {i partial function application}:  a lambda called with a number of values lesser than their arity memorizes the given values and returns a new lambda waiting for the rest.
_ul {code 3) lambdas} {i don't create closures}, inner lambdas have no access to outer lambdas' arguments, there is no lexical scoping, no nested environments, no free variables. 
_p Lambdas are pure black boxes, independant of any context, as are mathematical functions.

_h4 1.1.5. application {sup (3)}

{pre {WRAP}
'{{lambda {n} {{lambda {g n} {g g n}} {lambda {g n} {{lambda {p t f g n} {{{p n} {{lambda {x y z} {z x y}} t f}} g n}} {lambda {n} {{lambda {n} {n {lambda {x} {lambda {z} {z {lambda {x y} y}}}} {lambda {z} {z {lambda {x y} x}}}}} n}} {lambda {g n} {{lambda {n f x} {f {{n f} x}}} {lambda {f x} x}}} {lambda {g n} {{lambda {n m f} {m {n f}}} n {g g {{lambda {n} {{lambda {z} {z {lambda {x y} x}}} {{n {lambda {p} {{lambda {x y z} {z x y}} {{lambda {z} {z {lambda {x y} y}}} p} {{lambda {n f x} {f {{n f} x}}} {{lambda {z} {z {lambda {x y} y}}} p}}}}} {{lambda {x y z} {z x y}} {lambda {f x} x} {lambda {f x} x}}}}} n}}}} g n}} n}} {lambda {f x} {f {f {f {f {f x}}}}}}}
-> _LAMB_167
}

_p At this point, {i you should believe} that this unreadble expression evaluated to an anonymous function {i is} the factorial of {b 5}, {b 5! = 120}, computed using its recursive definition:

{pre
 {center fac(n) = 1 if n == 0 else fac(n) = n*fac(n-1)
}}

_h3 1.2. names

_p In order to make code more readable we introduce a second special form {code '{def word expression}}, with which we will populate the {i global dictionary} with {i constants} and give {i names} to anonymous functions. Let's rewrite with names the previous examples.

_h4 1.2.1. words

_p Any sequence of words can be given a name:
{pre
'{def HI Hello World} 
-> {def HI Hello World}

HI '{HI} 
-> HI {HI} 
}

_p Note that the word {code HI} is not evaluated out of curly braces '{}. Remember that, in a spreadsheet, one write {code =PI()} to get the value associated to {b PI}.

_h4 1.2.2. abstractions

_p An anonymous functions can be given a name:

{pre
'{def GOOD_DAY {lambda {:o :a} :oh h:appy day!}} 
-> {def GOOD_DAY {lambda {:o :a} :oh h:appy day!}}
}

_h4 1.2.3. application {sup (1)}

_p making applications easier:

{pre

'{GOOD_DAY oOOOo aaAaa} 
-> oOOOoh haaAaappy day!

'{GOOD_DAY ♠ ♥}
-> ♠h h♥ppy day!
}

_p {b Note:} arguments and their occurences in the function's body have been prefixed with a colon "{b :}". Doing so prevents unintentional substitutions in the function's body, for instance the word {b day} hasn't been replaced by {b daaAaay} or {b d♥y}. Escaping/marking arguments, for instance prefixing them with a colon "{code :}", is highly recommended if not always mandatory. {b We will do it systematically} and we add this constraint to the previous rules: « {i In lambda expressions arguments {code arg} must at least be tagged by some {i escaping} character, for instance {code :arg}, or for a better security, bracketted between two, for instance {code :arg:}.}

_h4 1.2.4. application {sup (2)}

{pre
'{def CONS {lambda {:x :y :z} {:z :x :y}}}
-> {def CONS {lambda {:x :y :z} {:z :x :y}}} 
'{def CAR  {lambda {:z} {:z {lambda {:x :y} :x}}}}
-> {def CAR  {lambda {:z} {:z {lambda {:x :y} :x}}}}
'{def CDR  {lambda {:z} {:z {lambda {:x :y} :y}}}}
-> {def CDR  {lambda {:z} {:z {lambda {:x :y} :y}}}}

'{CAR {CONS Hello World}}  
-> Hello
'{CDR {CONS Hello World}} 
-> World
}
_p In fact we just have built and used a {i pair} and its {i accessors}. Where LISP{ref 4} and SCHEME{ref 5} use a closure to define {code cons}

{pre
(def cons (lambda (x y) (lambda (z) (z x y))))
(def car  (lambda (z)   (z (lambda (x y) x))))
(def cdr  (lambda (z)   (z (lambda (x y) y))))
}

_p '{lambda talk} uses partial application. There is no outer environment storing accessible values, values are stored inside lambdas.

_h4 1.2.5. application {sup (3)}

_p We rewrite the example 1.1.5. using two names:

{pre  {WRAP}
'{def FOO {lambda {:n} {{lambda {:g :n} {:g :g :n}} {lambda {:g :n} {{lambda {:b :t :f :g :n} {{{:b :n} {{lambda {:x :y :z} {:z :x :y}} :t :f}} :g :n}} {lambda {:n} {{lambda {:n} {:n {lambda {:x} {lambda {:z} {:z {lambda {:x :y} :y}}}} {lambda {:z} {:z {lambda {:x :y} :x}}}}} :n}} {lambda {:g :n} {{lambda {:n :f :x} {:f {{:n :f} :x}}} {lambda {:f :x} :x}}} {lambda {:g :n} {{lambda {:n :m :f} {:m {:n :f}}} :n {:g :g {{lambda {:n} {{lambda {:z} {:z {lambda {:x :y} :x}}} {{:n {lambda {:p} {{lambda {:x :y :z} {:z :x :y}} {{lambda {:z} {:z {lambda {:x :y} :y}}} :p} {{lambda {:n :f :x} {:f {{:n :f} :x}}} {{lambda {:z} {:z {lambda {:x :y} :y}}} :p}}}}} {{lambda {:x :y :z} {:z :x :y}} {lambda {:f :x} :x} {lambda {:f :x} :x}}}}} :n}}}} :g :n}} :n}} }
-> FOO

'{def BAR
 {lambda {:f :x} {:f {:f {:f {:f {:f :x}}}}}}}
-> {def BAR {lambda {:f :x} {:f {:f {:f {:f {:f :x}}}}}}}

'{FOO BAR }
-> _LAMB_8
}

_p We notice that {code FOO} is applied to {code BAR}, an anonymous function applying {i 5 times} {code :f} to {code :x}. We can now better understand that the result is a reference to an anonymous function which could be associated to the factorial of {b 5}. And we guess that applying {b 50 times} {code :f} to {code :x} would lead to an anonymous function associated to the factorial of {b 50} ... provided we had a huge memory and thousands years before us!

_p Concluding this first section we note that, until now, '{lambda talk} knows nothing but text substitution and that the dictionary contains no built-in primitive. In the following section, {i still without using any Javascript Math object}, we progressively build {b numbers}, {b operators}, {b data} and {b control structures} to compute {b 5!} and {b 50!}.

_h2 2. numbers

_p Following {i "Collected Lambda Calculus Functions"}{ref 6} we progressively add numbers, operators, data and control structures.

_h3 2.1. numbers

_p We define the so-called {i Church numbers}:

{pre
'{def ZERO  {lambda {:f :x} :x}} 
-> {def ZERO  {lambda {:f :x} :x}}
'{def ONE   {lambda {:f :x} {:f :x}}} 
-> {def ONE   {lambda {:f :x} {:f :x}}}
'{def TWO   {lambda {:f :x} {:f {:f :x}}}} 
-> {def TWO   {lambda {:f :x} {:f {:f :x}}}}
'{def THREE {lambda {:f :x} {:f {:f {:f :x}}}}} 
-> {def THREE {lambda {:f :x} {:f {:f {:f :x}}}}}
'{def FOUR  {lambda {:f :x} {:f {:f {:f {:f :x}}}}}} 
-> {def FOUR  {lambda {:f :x} {:f {:f {:f {:f :x}}}}}}
'{def FIVE  {lambda {:f :x} {:f {:f {:f {:f {:f :x}}}}}}} 
-> {def FIVE  {lambda {:f :x} {:f {:f {:f {:f {:f :x}}}}}}}
}

_p Applied to a couple of any words, we get strange things:

{pre
'{ZERO . .} -> .
'{ONE  . .} -> (. .)
'{TWO  . .} -> (. (. .))
'{FIVE . .} -> (. (. (. (. (. .)))))
}

_p We define the function {code CHURCH} which translates Church numbers in a more familiar shape:

{pre
'{def CHURCH
 {lambda {:n}
  {{:n {lambda {:x} {+ :x 1}}} 0}}}
-> {def CHURCH {lambda {:n} {{:n {lambda {:x} {+ :x 1}}} 0}}}
'{CHURCH ZERO} -> 0
'{CHURCH ONE}  -> 1
'{CHURCH FIVE} -> 5
}

_p {b Note:} the {code CHURCH} function is built on a primitive function, {b '+'} and on the Javascript number primitive, which are not supposed to exist at this point. Consider that it's only for readability.

_h3 2.2. operators

_p Based on Church numbers, which are {b iterators by themselves}, we can easily define and test a first set of operators:

{pre
'{def SUCC {lambda {:n :f :x} {:f {{:n :f} :x}}}} 
-> {def SUCC {lambda {:n :f :x} {:f {{:n :f} :x}}}}
'{def ADD {lambda {:n :m :f :x} {{:n :f} {{:m :f} :x}}}} 
-> {def ADD {lambda {:n :m :f :x} {{:n :f} {{:m :f} :x}}}}  
'{def MUL {lambda {:n :m :f} {:m {:n :f}}}} 
-> {def MUL {lambda {:n :m :f} {:m {:n :f}}}}
'{def POWER {lambda {:n :m} {:m :n}}} 
-> {def POWER {lambda {:n :m} {:m :n}}}

'{CHURCH {SUCC ZERO}}       -> 1
'{CHURCH {SUCC ONE}}        -> 2
'{CHURCH {SUCC THREE}}      -> 3
'{CHURCH {ADD TWO THREE}}   -> 5  // 2+3
'{CHURCH {MUL TWO THREE}}   -> 6  // 2*3
'{CHURCH {POWER THREE TWO}} -> 9  // 3^2 
}

_p Building "opposite" functions like {code PRED, SUBTRACT, DIVIDE} is not so easy - and Church himself  avoided them in the primitive version of λ-calculus. The answer was given by Stephen Cole Kleene{ref 7}, the father of Regular Expressions: {i Church numbers can be used to {b iterate} and pairs to {b aggregate}}. This is how:

_ul we define a function {code PRED.PAIR} getting a pair {code [a,a]} and returning a pair {code [a,a+1]},

_ul the function {code PRED} computes {code n} iterations of {code PRED.PAIR} starting on the pair {code [0,0]} and leading to the pair {code [n-1,n]} and  returns the first, {code n-1}:

{pre
'{def PRED.PAIR {lambda {:p}
 {CONS {CDR :p} {SUCC {CDR :p}}}}} 
-> {def PRED.PAIR {lambda {:p}
 {CONS {CDR :p} {SUCC {CDR :p}}}}}
'{def PRED {lambda {:n}
 {CAR {{:n PRED.PAIR} {CONS ZERO ZERO}}}}} 
-> {def PRED {lambda {:n} {CAR {{:n PRED.PAIR} {CONS ZERO ZERO}}}}}

'{CHURCH {PRED FIVE}}
-> 4
}

_h3 2.3. « To Iterate is Human, ...

_p We already have all what is needed to evaluate complex expressions like {b 1*2*3*...*n}. Inspired by the {code PRED} operator:

_ul we define a function {code ITER.PAIR} getting a pair {code [a,b]} and returning a pair {code [a+1,a*b]},
_ul the function {code ITER} computes {code n} iterations of {code ITER.PAIR}, starting on the pair {code [1,1]} and leading to the pair {code [n,n!]} and returns the second, {code n!}

{pre
'{def ITER  
 {def ITER.PAIR
  {lambda {:p}
   {CONS {SUCC {CAR :p}}
         {MUL {CAR :p} {CDR :p}}}}}
 {lambda {:n}
  {CDR {{:n ITER.PAIR} {CONS ONE ONE}}}}}
-> {def ITER 
 {def ITER.PAIR
  {lambda {:p}
   {CONS {SUCC {CAR :p}} {MUL {CAR :p} {CDR :p}}}}}
 {lambda {:n}
  {CDR {{:n ITER.PAIR} {CONS ONE ONE}}}}}

'{CHURCH {ITER TWO}}   -> 2     
'{CHURCH {ITER THREE}} -> 6
'{CHURCH {ITER FOUR}}  -> 24
'{CHURCH {ITER FIVE}}  -> 120    
}

_h3 2.4. ... to Recurse, Divine »{ref 8}

_p We want to define the factorial using its recursive mathematical definition:

{pre {center
fac(n) = 1 if n == 0 else fac(n) = n*fac(n-1)
}}

_p We need a few boolean operators:

{pre
'{def TRUE {lambda {:z} {:z {lambda {:x :y} :x}}}} 
-> {def TRUE {lambda {:z} {:z {lambda {:x :y} :x}}}}
'{def FALSE {lambda {:z} {:z {lambda {:x :y} :y}}}} 
-> {def FALSE {lambda {:z} {:z {lambda {:x :y} :y}}}}
'{def IF {lambda {:x :y :z} {:z :x :y}}} 
-> {def IF {lambda {:x :y :z} {:z :x :y}}}
'{def ISZERO {lambda {:n}
  {:n {lambda {:x} FALSE} TRUE}}} 
-> {def ISZERO  {lambda {:n} {:n {lambda {:x} FALSE} TRUE}}}
}

_p Note that {code TRUE, FALSE, IF} are aliases to {code CAR, CDR, CONS}.

_p {b Here is the tricky part!} We remember that all expressions except abstractions are evaluated {i eagerly}: functions' arguments are {i called by value} and not {i called by name}. Inside the {code IF} function every arguments are evaluated before the call and this would lead to an {i infinite loop} in a recursive process. A workaround is to use abstraction to introduce {i manually} some kind of lazyness. This is an answer:

{pre
'{def FAC
 {lambda {:n}
  {{lambda {:bool :true :false :n}
   {{{:bool :n}               // compute bool
     {IF :true :false}}       // choose now
     :n}}                     // force now
    {lambda {:n} {ISZERO :n}} // delay
    {lambda {:n} {SUCC ZERO}} // delay
    {lambda {:n} {MUL :n {FAC {PRED :n}}}}
    :n                        // for n
}}} 
-> {def FAC
 {lambda {:n}
  {{lambda {:b :t :f :n}
   {{{:b :n} {IF :t :f}} :n} }
    {lambda {:n} {ISZERO :n}}
    {lambda {:n} {SUCC ZERO}} 
    {lambda {:n} {MUL :n {FAC {PRED :n}}}}
    :n }}}

'{CHURCH {FAC FIVE}}
-> {b 120}
}

_p Let's introduce some {b Y-combinator} making recursive an almost recursive function:

{pre
'{def Y {lambda {:g :n} {:g :g :n}}} -> {def Y {lambda {:g :n} {:g :g :n}}}

'{def IFTHENELSE {lambda {:b :t :f :g :n}
  {{{:b :n} {IF :t :f}} :g :n} }} 
-> {def IFTHENELSE {lambda {:b :t :f :g :n}
  {{{:b :n} {IF :t :f}} :g :n} }}

'{def ALMOST_FAC {lambda {:g :n}
  {IFTHENELSE
   {lambda {:n} {ISZERO :n}}
   {lambda {:g :n} {SUCC ZERO}} 
   {lambda {:g :n} {MUL :n {:g :g {PRED :n}}}}
   :g :n }}} 
-> {def ALMOST_FAC {lambda {:g :n}
  {IFTHENELSE
   {lambda {:n} {ISZERO :n}}
   {lambda {:g :n} {SUCC ZERO}} 
   {lambda {:g :n} {MUL :n {:g :g {PRED :n}}}}
   :g :n }}}

'{CHURCH {Y ALMOST_FAC FIVE}} 
-> {b 120}
}

_p Let's mix the both:

{pre
'{def YFAC {lambda {:n}
 {{lambda {:g :n} {:g :g :n}}
 {lambda {:g :n}
  {IFTHENELSE
   {lambda {:n} {ISZERO :n}}
   {lambda {:g :n} {SUCC ZERO}} 
   {lambda {:g :n} {MUL :n {:g :g {PRED :n}}}}
   :g :n}}
   :n}}}
-> {def YFAC {lambda {:n}
 {{lambda {:g :n} {:g :g :n}}
 {lambda {:g :n}
  {IFTHENELSE
   {lambda {:n} {ISZERO :n}}
   {lambda {:g :n} {SUCC ZERO}} 
   {lambda {:g :n} {MUL :n {:g :g {PRED :n}}}}
   :g :n}}
   :n}}}
  
'{CHURCH {YFAC FIVE}} 
-> {b 120} 
}

_p Throwing away the name, let's define and immediately call the lambda on the value {b 5}:

{pre
'{CHURCH 
 {{lambda {:n} {{lambda {:g :n} {:g :g :n}}
  {lambda {:g :n}
   {IFTHENELSE
    {lambda {:n} {ISZERO :n}}
    {lambda {:g :n} {SUCC ZERO}} 
    {lambda {:g :n} {MUL :n {:g :g {PRED :n}}}}
    :g :n}} :n}} FIVE}}
-> {b 120}
}

_p Finally, let's replace all constants by their lambda based values to get a pure λ-calculus expression made of {code words, abstractions} and {code applications}:

{pre {@ style="word-wrap: break-word; white-space:pre-wrap;"}

'{CHURCH {{lambda {:n} {{lambda {:g :n} {:g :g :n}} {lambda {:g :n} {{lambda {:b :t :f :g :n} {{{:b :n} {{lambda {:x :y :z} {:z :x :y}} :t :f}} :g :n}} {lambda {:n} {{lambda {:n} {:n {lambda {:x} {lambda {:z} {:z {lambda {:x :y} :y}}}} {lambda {:z} {:z {lambda {:x :y} :x}}}}} :n}} {lambda {:g :n} {{lambda {:n :f :x} {:f {{:n :f} :x}}} {lambda {:f :x} :x}}} {lambda {:g :n} {{lambda {:n :m :f} {:m {:n :f}}} :n {:g :g {{lambda {:n} {{lambda {:z} {:z {lambda {:x :y} :x}}} {{:n {lambda {:p} {{lambda {:x :y :z} {:z :x :y}} {{lambda {:z} {:z {lambda {:x :y} :y}}} :p} {{lambda {:n :f :x} {:f {{:n :f} :x}}} {{lambda {:z} {:z {lambda {:x :y} :y}}} :p}}}}} {{lambda {:x :y :z} {:z :x :y}} {lambda {:f :x} :x} {lambda {:f :x} :x}}}}} :n}}}} :g :n}} :n}} {lambda {:f :x} {:f {:f {:f {:f {:f :x}}}}}}}}
-> {b 120}     
}

_p Concluding this section, using nothing but words and text replacement processes, forgetting limitations of Javascript numbers and so theoretically regardless of its size and with a total precision, we could compute the factorial of any natural number. But if computing {b 5!} is {i relatively} fast - about 50ms on a recent computer - computing {b 50!} would still be too long ! It's time to remember that we can use the power of modern browsers to make things easier and much more faster!

_h2 3. '{lambda talk}

_p In this section Church numbers and their related operators built as user defined functions are {i forgotten} and replaced by primitive functions built on the browser's foundations. We use Javascript's numbers, Math operators and functions, HTML tags, CSS rules, SVG and more. We add {i aggregate datas} like {code pairs, lists, arrays} and some others specific to the wiki context. We add new special forms, {code [if, let, quote, macro]}. Note that there is no {code set!} special form, '{lambda talk} is purely functional. This is the current dictionary:

{blockquote
{lib}
}

_p where can be seen the user defined functions starting at  {code SMART_ADD}, the first constant created for the current document.

_p In order to illustrate some of these new capabilities we will write effective recursive factorials, compute big numbers, play with tabular data in a spreadsheet, explore intensive computing with javascripts, build regular expressions based macros.

_h3 3.1. recursion

_p In the previous section we have seen how tricky it was to write a recursive algorithm. We had to write {i manually} a lazy behaviour. Using the third {code '{if bool then one else two}} special form and its built-in {i lazy evaluation} the way is opened to efficient recursive algorithms. It's now possible to write the factorial function following its mathematical definition:

{pre
'{def FACT
 {lambda {:n}
  {if {< :n 0}
   then {b n must be positive!}
   else {if {= :n 0} then 1
   else {* :n {FACT {- :n 1}}}}}}} 
-> {def FACT
 {lambda {:n}
  {if {< :n 0}
   then {b n must be positive!}
   else {if {= :n 0}
   then 1
   else {* :n {FACT {- :n 1}}}}}}}

'{FACT -1} -> {b n must be positive!}
'{FACT 0}  -> 1
'{FACT 5}  -> 120
'{FACT 50} -> 3.0414093201713376e+64
}

_p Let's write the tail-recursive version:

{pre
'{def TFAC
 {def TFAC.rec
  {lambda {:a :n}
   {if {< :n 0}
    then {b n must be positive!}
    else {if {= :n 0} then :a 
    else {TFAC.rec {* :a :n} {- :n 1}}}}}}
 {lambda {:n} {TFAC.rec 1 :n}}} 
-> {def TFAC
 {def TFAC.rec
  {lambda {:a :n}
   {if {< :n 0} then {b n must be positive!}
    else {if {= :n 0} then :a 
    else {TFAC.rec {* :a :n} {- :n 1}}}}}}
 {lambda {:n} {TFAC.rec 1 :n}}}

'{TFAC 5}  -> 120
'{TFAC 50} -> 3.0414093201713376e+64
}

_p The recursive part is called by a {i helper function} introducing the accumulator "{code :a}". '{lambda talk} doesn't know lexical scoping - the {code TFAC.rec} inner function is global - and this leads to some pollution of the dictionary. The {i Y-combinator} mentionned above, {i making recursive an almost-recursive function}, will help us to discard this helper function. The {i Y-combinator} and the almost-recursive function can be defined and used like this:

{pre
'{def Y {lambda {:f :a :n} {:f :f :a :n}}} 
-> {def Y {lambda {:f :a :n} {:f :f :a :n}}}

'{def ALMOST_FAC
 {lambda {:f :a :n}
  {if {< :n 0}
   then {b n must be positive!}
   else {if {= :n 0} then :a
   else {:f :f {* :a :n} {- :n 1}}}}}} 
-> {def ALMOST_FAC
 {lambda {:f :a :n}
  {if {< :n 0} then {b the number must be positive!}
   else {if {= :n 0} then :a
   else {:f :f {* :a :n} {- :n 1}}}}}}

'{Y ALMOST_FAC 1 5} 
-> 120
}

_p We can do better. Instead of applying the Y combinator to the almost recursive function we can define a function composing both:

{pre {WRAP} 
'{def YFAC {lambda {:n}
 {{lambda {:f :a :n}
  {:f :f :a :n}} 
   {lambda {:f :a :n}
    {if {< :n 0}
     then {b n must be positive!}
     else {if {= :n 0} then :a
     else {:f :f {* :a :n} {- :n 1}}}}} 1 :n}}}
-> {def YFAC {lambda {:n}
  {{lambda {:f :a :n} {:f :f :a :n}} 
   {lambda {:f :a :n}
    {if {< :n 0} then {b the number must be positive!}
     else {if {= :n 0} then :a
     else {:f :f {* :a :n} {- :n 1}}}}} 1 :n}}}

'{YFAC 5} 
-> 120
'{YFAC 50} 
-> 3.0414093201713376e+64   
}

_p We can {code map} this function to a sequence of numbers:

{pre
'{map YFAC {serie 0 20}}
-> 1 1 2 6 24 120 720 5040 40320 362880 3628800 39916800 479001600 6227020800 87178291200 1307674368000 20922789888000 355687428096000 6402373705728000 121645100408832000 2432902008176640000  
}

_p It's much fast but there is a last point to fix: {code '{FAC 50}}, {code '{TFAC 50}} and {code '{YFAC 50}} return a rounded value {b 3.0414093201713376e+64} which is obvioulsly not the exact value. We must go a little further and build some tools capable of processing big numbers.

_h3 3.2. big numbers

_p The way the Javascript Math object is implemented puts the limit of natural numbers to {b 2{sup 54}}. Beyond this limit last digits are rounded to zeros, for instance, as we will demonstrate later, the four last digits of {b 2{sup 64} = '{pow 2 64} = {pow 2 64}} should be {b 1616} and are rounded to {b 2000}. And beyond {b {b 2{sup 69}}} natural numbers are replaced by float numbers with a maximum of 15 valid digits. In order to overcome this limitation we come back to the definition of a natural number: {i A natural number a{sub 0}a{sub 1}...a{sub n} is the value of a polynomial Σ{sub i=0}{sup n}a{sub i}x{sup i} for some value of x, called the base}. For instance {i 12345 = 1*10{sup 4}+2*10{sup 3}+3*10{sup 2}+4*10{sup 1}+5*10{sup 0}}. We build a set of user defined functions defining addition, multiplication of polynomials and some helper functions:

{pre
'{def BI.bigint2pol
 {def BI.bigint2pol.rec
  {lambda {:n :p :i}
   {if {< :i 0}
    then :p
    else {BI.bigint2pol.rec 
          :n
          {cons {charAt :i :n} :p} {- :i 1}}}}}
 {lambda {:n}
  {BI.bigint2pol.rec :n nil {- {chars :n} 1}}}}
-> {def BI.bigint2pol
 {def BI.bigint2pol.rec
  {lambda {:n :p :i}
   {if {< :i 0}
    then :p
    else {BI.bigint2pol.rec 
          :n {cons {charAt :i :n} :p} {- :i 1}}}}}
 {lambda {:n} {BI.bigint2pol.rec :n nil {- {chars :n} 1}}
}}

'{def BI.pol2bigint
 {def BI.pol2bigint.rec
  {lambda {:p :n}
   {if {equal? :p nil}
    then :n
    else {BI.pol2bigint.rec
           {cdr :p} {car :p}:n}}}}
 {lambda {:p}
  {let { {:q {list.reverse :p}} }
   {BI.pol2bigint.rec {cdr :q} {car :q}}}}}
-> {def BI.pol2bigint
 {def BI.pol2bigint.rec
  {lambda {:p :n}
   {if {equal? :p nil} then :n
    else {BI.pol2bigint.rec {cdr :p} {car :p}:n} }}}
 {lambda {:p}
  {let { {:q {list.reverse :p}} }
   {BI.pol2bigint.rec {cdr :q} {car :q}}} }}

'{def BI.simplify
 {def BI.simplify.rec
  {lambda {:p :q :r}
   {if {and {equal? :p nil} {= :r 0}}
    then :q
    else {if {equal? :p nil} then {cons :r :q}
    else {BI.simplify.rec
          {cdr :p} 
          {cons {+ {% {car :p} 10} :r} :q}
          {floor {/ {car :p} 10}} }} }}}
 {lambda {:p}
  {BI.simplify.rec {list.reverse :p} nil 0}}} 
-> {def BI.simplify
 {def BI.simplify.rec
  {lambda {:p :q :r}
   {if {and {equal? :p nil} {= :r 0}}
    then :q
    else {if {equal? :p nil} then {cons :r :q}
    else {BI.simplify.rec
          {cdr :p} 
          {cons {+ {% {car :p} 10} :r} :q}
          {floor {/ {car :p} 10}} }} }}}
 {lambda {:p}
  {BI.simplify.rec {list.reverse :p} nil 0} }}

'{def BI.pk
 {lambda {:k :p} 
  {if {equal? :p nil}
   then nil
   else {cons {* :k {car :p}}
              {BI.pk :k {cdr :p}}} }}}
-> {def BI.pk
 {lambda {:k :p} 
  {if {equal? :p nil}
   then nil
   else {cons {* :k {car :p}} {BI.pk :k {cdr :p} }} }}}

'{def BI.p+
 {lambda {:p1 :p2}
  {if {and {equal? :p1 nil} {equal? :p2 nil}}
   then nil
   else {if {equal? :p1 nil} then :p2
   else {if {equal? :p2 nil} then :p1
   else {cons {+ {car :p1} {car :p2}} 
              {BI.p+ {cdr :p1} {cdr :p2} }}}}}}}
-> {def BI.p+
 {lambda {:p1 :p2}
  {if {and {equal? :p1 nil} {equal? :p2 nil}}
   then nil
   else {if {equal? :p1 nil} then :p2
   else {if {equal? :p2 nil} then :p1
   else {cons {+ {car :p1} {car :p2}} 
              {BI.p+ {cdr :p1} {cdr :p2} }}}} }}}

'{def BI.p*
 {lambda {:p1 :p2}
  {if {or {equal? :p1 nil} {equal? :p2 nil}}
   then nil
   else {if {not {cons? :p1}}
   then {BI.pk :p1 :p2}
   else {BI.p+ {BI.pk {car :p1} :p2}
               {cons 0 {BI.p* {cdr :p1} :p2}}}}}}}
-> {def BI.p*
 {lambda {:p1 :p2}
  {if {or {equal? :p1 nil} {equal? :p2 nil}}
   then nil
   else {if {not {cons? :p1}}
   then {BI.pk :p1 :p2}
   else {BI.p+ {BI.pk {car :p1} :p2}
               {cons 0 {BI.p* {cdr :p1} :p2}}}} }}}
}

_p Using this set of functions we can now compute the factorial of natural numbers of any size with an exact precision:

{pre {WRAP} 
'{def BI.tfac
 {def BI.tfac.r {lambda {:n :p}
   {if {< :n 1}
    then :p
    else {BI.tfac.r {- :n 1}
         {BI.simplify
          {BI.p* {BI.bigint2pol :n} :p}}}}}}
 {lambda {:n}
  {BI.pol2bigint
   {BI.simplify
    {BI.tfac.r :n {BI.bigint2pol 1}}}}}}
-> {def BI.tfac
 {def BI.tfac.r {lambda {:n :p}
   {if {< :n 1}
    then :p
    else {BI.tfac.r {- :n 1}
         {BI.simplify
          {BI.p* {BI.bigint2pol :n} :p}}}}}}
 {lambda {:n}
  {BI.pol2bigint
   {BI.simplify
    {BI.tfac.r :n {BI.bigint2pol 1}} }}}}

'{BI.tfac 50}
-> 304140932017133780436126081660647
   68844377641568960512000000000000
}

_p We finally reached the goal: with the subset of special forms {code [lambda, def, if]}, the {code cons} and {code lists} structures, a few Math operators and {i without any external library} we have computed the exact value of {b 50!} But we need to go a little further.

_h3 3.3. when '{lambda talk} calls Javascript

_p Until now user defined functions were exclusively created in the '{lambda talk} syntax. With a large speed penalty when comes intensive computation. We can write new functions in the Javascript syntax inside '{script ... Javascript code ...} forms.

_p When a set of user defined functions written in '{lambda talk} or Javascript syntaxes increazes in size, it's better to externalize it in some other wiki page used as a {b library} and called via a {{span}require library_name}. This helps '{lambda talk} to stay minimal, coherent, orthogonal, and any user to create, add and maintain his own specific {b library}. In the following we illustrate some of these capabilities.

_h4 3.3.1. the lib_bignum library

_p Jonas Raoni Soares Silva{ref 9} has written a small (150 lines) and smart Javascript library, {code BigNumber}, ready to be called via '{lambda talk} wrapping functions, everything being stored in another wiki page, {code lib_bignum}. We just write the factorial function using the multiplicate operator {code BN.*} redefined for big numbers:

{require lib_bignum}
{pre {WRAP}
'{def BN.fac
 {lambda {:n}
  {if {= :n 0}
   then 1
   else {BN.* :n {BN.fac {- :n 1}}}}}}
-> {def BN.fac
 {lambda {:n}
  {if {= :n 0}
   then 1
   else {BN.* :n {BN.fac {- :n 1}}}}}}

}

_p and call it on the number {b 50}:

{pre {WRAP}
'{BN.fac 50}   
-> 304140932017133780436126081660647
   68844377641568960512000000000000
}

_p Obviously it's the fastest and best choice!

_p {b Note:} Using this library, we can control that the value of {i 2{sup 64}} given by the Javascript Math object, {i '{pow 2 64} = {pow 2 64}} is not its exact value {i '{BN.pow 2 64} = {BN.pow 2 64}}!

_h3 3.3.2. the lib_spreadsheet library

_p A spreadsheet is a good illustration of functional languages, (Simon Peyton-Jones {ref 10}). A spreadsheet is an interactive computer application for organization, analysis and storage of data in tabular form. The basic idea is that each cell contains the input - {i words and expressions} - and displays the output. Calling a set of Javascript and '{lambda talk} functions stored in a wiki page, {code lib_spreadsheet}, and writing '{spreadsheet 4 5} displays the following table of 5 rows and 4 columns of editable cells:

{center {@ style="white-space:normal;"}  
 {spreadsheet 4 5}     
}

_p  Two specific functions are added for linking cells:
_ul  {code '{LC i j}} returns the value of the cell {code L{sub i}C{sub j}} as an {i absolute reference},
_ul  {code '{IJ i j}} returns the value of the cell {code L{sub [i]}C{sub [j]}} as a {i relative reference}. For instance writing {code '{IJ -1 -1}} in {code L2C2} will return the value of {code L1C1}.

_p Datas are stored in the browser's {i localStorage}. Let's test: click on the {b [local storage]} button, copy the code in the frame below, paste it in the local storage frame, click on the {b editor -> storage} button, confirm the action and analyze the spreadsheet's cells.

{pre {WRAP} °°
["{b NAME}","{b QUANT}","{b UNIT PRICE}","{b PRICE}","Item 1","10","2.1","{* {IJ 0 -2} {IJ 0 -1}}","Item 2","20","3.2","{* {IJ 0 -2} {IJ 0 -1}}","Item 3","30","4.3","{* {IJ 0 -2} {IJ 0 -1}}","","","{b TOTAL PRICE}","{+ {IJ -3 0} {IJ -2 0} {IJ -1 0}}","4"]
°°}

_h3 3.3.3. graphics

_p The {b de Casteljau} recursive algorithm{ref 11} allows drawing Bezier curves of any degree, i.e controlled by any number of points. Defining points as pairs and control polylines as lists, we build a small set of '{lambda talk} user defined functions feeding the points attributes of SVG polylines:

{pre
'{def castel.interpol {lambda {:p0 :p1 :t}
 {cons {+ {* {car :p0} {- 1 :t}}
          {* {car :p1} :t}} 
       {+ {* {cdr :p0} {- 1 :t}}
          {* {cdr :p1} :t}}
}}}
-> {def castel.interpol {lambda {:p0 :p1 :t}
 {cons {+ {* {car :p0} {- 1 :t}} {* {car :p1} :t}} 
       {+ {* {cdr :p0} {- 1 :t}} {* {cdr :p1} :t}}}}}
 
'{def castel.sub {lambda {:l :t}
 {if {equal? {cdr :l} nil}
  then nil
  else {cons
   {castel.interpol {car :l} {car {cdr :l}} :t} 
   {castel.sub {cdr :l} :t}}}}}
-> {def castel.sub {lambda {:l :t}
 {if {equal? {cdr :l} nil}
  then nil
  else {cons {castel.interpol {car :l} {car {cdr :l}} :t} 
             {castel.sub {cdr :l} :t}}}}}

'{def castel.point {lambda {:l :t}
 {if {equal? {cdr :l} nil}
  then {car {car :l}} {cdr {car :l}} 
  else {castel.point {castel.sub :l :t} :t}}}}
-> {def castel.point {lambda {:l :t}
 {if {equal? {cdr :l} nil}
  then {car {car :l}} {cdr {car :l}} 
  else {castel.point {castel.sub :l :t} :t}}}}

'{def castel.build {lambda {:l :a :b :d}
 {map {castel.point :l} {serie :a :b :d}}}}   
-> {def castel.build {lambda {:l :a :b :d}
 {map {castel.point :l} {serie :a :b :d}}}}

'{def svg.dot {lambda {:p}
 {circle {@ cx="{car :p}" cy="{cdr :p}" r="5" 
            stroke="black" stroke-width="3"
            fill="rgba(255,0,0,0.5)"}}}}
-> {def svg.dot {lambda {:p}
 {circle {@ cx="{car :p}" cy="{cdr :p}" r="5" 
            stroke="black" stroke-width="3"
            fill="rgba(255,0,0,0.5)"}}}}
}

_p For instance the following code:

{pre
'{def p0 {cons 150 80}}  -> {def p0 {cons 150 80}}
'{def p1 {cons 200 150}} -> {def p1 {cons 200 150}}
'{def p2 {cons 50 250}}  -> {def p2 {cons 50 250}}
'{def p3 {cons 200 250}} -> {def p3 {cons 200 250}}
'{def red_curve {castel.build   
  {list {p0} {p1} {p2} {p3}}
   -0.3 1.1 {pow 2 -5}}}
-> {def red_curve {castel.build   
  {list {p0} {p1} {p2} {p3}} -0.3 1.1 {pow 2 -5}}}
'{def green_curve {castel.build
  {list {p2} {p1} {p3}}
   -0.1 0.6 {pow 2 -5}}}
-> {def green_curve {castel.build
  {list {p2} {p1} {p3}} -0.1 0.6 {pow 2 -5}}}

'{svg.dot {p0}}
'{svg.dot {p1}}
'{svg.dot {p2}}
'{svg.dot {p3}}

'{polyline {@ points="{red_curve}" 
  stroke="red" fill="transparent"
  stroke-width="3"}} 
'{polyline {@ points="{green_curve}"    
  stroke="green" fill="transparent"
  stroke-width="3"}} 
}
 
_p draws a cute {b λ} in an SVG frame:

{center {svg {@ width="300px" height="300px"}  
 {svg.dot {p0}}
 {svg.dot {p1}}
 {svg.dot {p2}}
 {svg.dot {p3}}

{polyline {@ points="{red_curve}" 
  stroke="red" fill="transparent" stroke-width="3"}} 
 {polyline {@ points="{green_curve}"    
  stroke="green" fill="transparent" stroke-width="3"}} 
}}

_h3 3.3.4. intensive computing

_p For intensive computing, it's obvioulsly more efficient to call the underlying language, Javascript. These are screenshots of '{lambda tank}'s pages dedicated to {b ray-tracing,{ref 12} curved shapes modeling{ref 13}, fractals{ref 14}, turtle graphics drawing{ref 15}}.

{center
{img {@ src="data/brussels/d1.jpg" height="150" title="Ray tracing" style="border:1px solid #ccc"}}
{img {@ src="data/brussels/pforms_coons.jpg" height="150" title="Coons patches built on 6 cubic spline curves with embedded regular polygons" style="border:1px solid #ccc"}}
{br}
{img {@ src="data/brussels/mandel_20160104.jpg" height="140" title="The MandelBrot set"  style="border:1px solid #ccc"}}
{img {@ src="data/brussels/turtle_20161105.jpg" height="140" title="Turtle graphics with Lindenmeier, L-system"  style="border:1px solid #ccc"}}  
}

_h3 3.3.5. mathML

{div {@ style="font:italic 1.2em georgia; text-align:center;"}
i{del h}{QUOTIENT 20 ∂ψ ∂t} (x,t) = {PAREN 3 (}mc{sup 2}α{sub 0} - i{del h}c {SIGMA 20 j=1 3} α{sub j}{QUOTIENT 20 ∂ ∂x{sub j}} {PAREN 3 )} ψ(x,t)
}
{center {i The Dirac equation in the form originally proposed by Dirac}}

_p '{lambda talk} forgets the {b MathML} markup set which is not implemented in Google Chrome{ref 16}. A set of functions, exclusively built on standard HTML and CSS rules, can be defined to render Math Symbols. For instance the above {b Dirac equation} is not a picture but the result of the code below:

{pre °°
i{del h}{QUOTIENT 30 ∂ψ ∂t}(x,t) = {PAREN 3 (}
mc{sup 2}α{sub 0} - i{del h}c {SIGMA 30 j=1 3} α{sub j}
{QUOTIENT 30 ∂ ∂x{sub j}} {PAREN 3 )} ψ(x,t)
°°}

_p calling three user defined '{lambda talk} functions: 
{pre
'{def QUOTIENT
 {lambda {:s :num :denom}
  {table
   {@ style="width::spx;
             display:inline-block;
             vertical-align:middle;
             text-align:center;"}
 {tr {td {@ style="border:0 solid; 
                   border-bottom:1px solid;"}:num}}
 {tr {td {@ style="border:0 solid;"}:denom}} }}}
-> {def QUOTIENT {lambda {:s :num :denom}
{table {@ style="width::spx; display:inline-block; vertical-align:middle; text-align:center;"}
 {tr {td {@ style="border:0 solid; border-bottom:1px solid;"}:num}}
 {tr {td {@ style="border:0 solid;"}:denom}}
}}}

'{def SIGMA
 {lambda {:s :one :two}
  {table
   {@ style="width::spx;
             display:inline-block;
             vertical-align:middle;
             text-align:center;"}
 {tr {td {@ style="border:0 solid;"}:two}}
 {tr {td {@ style="border:0 solid;
                   font-size:2em;
                   line-height:0.7em;"}Σ}}
 {tr {td {@ style="border:0 solid;"}:one}} }}}
-> {def SIGMA {lambda {:s :one :two}
{table {@ style="width::spx; display:inline-block; vertical-align:middle; text-align:center;"}
 {tr {td {@ style="border:0 solid;"}:two}}
 {tr {td {@ style="border:0 solid; font-size:2em; line-height:0.7em;"}Σ}}
 {tr {td {@ style="border:0 solid;"}:one}}
}}}

'{def PAREN
 {lambda {:s :p} 
  {span {@ style="font:normal :sem arial;
                  vertical-align:-0.15em;"}:p}}}
-> {def PAREN {lambda {:s :p} 
 {span {@ style="font:normal :sem arial; vertical-align:-0.15em;"}:p}}}
}

_h3 3.4. what about macros?

_p A language without macros is not a "true" language, isnt'it? '{lambda talk} macros bring (a little bit of) the power of regular expressions directly in the language.

_h4 3.4.1. make it variadic
_p '{lambda talk} comes with some variadic primitives, for instance [{code +, -, *, /, list, ...}]. But at first sight, user functions can't be defined variadic, for instance:

{pre
'{def mul {lambda {:x :y} {* :x :y}}} -> {def mul {lambda {:x :y} {* :x :y}}}
'{* 1 2 3 4 5}   -> 120      // * is variadic
'{mul 1 2 3 4 5} -> 2        // 3, 4, 5 are ignored
}

_p In order to make {code mul} variadic we glue values in a list and define an helper function, {code variadic}:

{pre
'{def variadic 
 {lambda {:f :args}
  {if   {equal? {cdr :args} nil}
   then {car :args}
   else {:f {car :args}
            {variadic :f {cdr :args}}}}}} 
-> variadic

'{variadic mul {list 1 2 3 4 5}} 
-> 120
}

_p But it's ugly and doesn't follow a standard call. We can do better using a macro:

{pre
1) defining:
'{macro {mul* (.*?)} 
    to {variadic mul {list €1}}}

2) using:
'{mul* 1 2 3 4 5} 
-> 120
}

_p Now {code mul*} is a variadic function which can be used as any other primitive or user function, except that it's not a first class function, as in most Lisps.

_h4 3.4.2. titles, paragraphs & links

_p As a last example, '{lambda talk} comes with a predefined small set of macros allowing writing without curly braces titles, paragraphs, list items, links:
{pre
_{span}h1 TITLE ¬            
  stands for: '{h1 TITLE}

_{span}p Some paragraph ... ¬
  stands for: '{p Some paragraph ...}

[{span}[PIXAR|http://www.pixar.com/]{span}]
  stands for: '{a {@ href="http://www.pixar.com/"}PIXAR}

[{span}[sandbox]{span}]
  stands for: '{a {@ href="?view=sandbox"}sandbox}
}

_p These simplified alternatives, avoiding curly braces as much as possible, are fully used in the current document.

_h2 conclusion

_p '{lambda talk} takes benefit from the extraordinary power of modern web browsers, simply adding a coherent and unique syntax, {i without re-inventing the wheel}, just using existing tools, HTML/CSS, the DOM and Javascript. {i Standing on the shoulders of such giants},  '{lambda talk} can be built as a minimal regexp based implementation of the λ-calculus, where the repeated substitutions inside the code string overcomes limitations of regular language, where the lack of closure is balanced by the built-in partial application, where a dictionary initially empty can be extended "inline" via user defined libraries. More can be seen in the following APPENDICE.

_p The '{lambda way} project is a thin overlay - under 100kb - built upon any modern browser, proposing a small interactive development environment, '{lambda tank}, and a coherent language, '{lambda talk}, without any external dependencies and thereby easy to download and install on a web account provider running PHP. From any web browser on any system, complex web pages can be created, enriched, structured and (algorithms) tested in real time on the web. The current document has been created in this wiki page, {code [[http://lambdaway.free.fr/lambdaway/?view=oxford|http://lambdaway.free.fr/lambdaway/?view=oxford]]} then directly printed from the browser as a PDF document.

_p .
_ol12 {i Alain Marty,  2017/06/12}

_h2 APPENDICE

_p In this section we present the minimal set of JavaScript functions necessary and sufficient to implement {code abstractions}, {code applications}, {code definitions} and the {code ifthenelse} control structure.

_h3 1. evaluation
_p Working on the client side the '{lambda talk} evaluator is a Javascript {b IIFE} (Immediately Invoked Function Expression), {code LAMBDATALK}, returning the public function  {code eval()}. This function is called at every keyboard entry and replaces the string code by its evaluation, without building any Abstract Syntaxic Tree.

{pre 
°°
var LAMBDATALK = (function() {
var eval = function(str) {
  str = pre_processing(str);
  str = abstract_lambdas(str); // abstraction
  str = abstract_defs(str);    // abstraction
  // some other special forms
  str = eval_forms(str);       // application
  str = post_processing(str);
  return str;
};
return {eval:eval}
})();
°°}

_h3 2. application
_p In a single loop, using a single regular expression{ref 17}, simple forms {code '{first rest}} are recursively evaluated from the leaves to the root and replaced by words. The evaluator stops when simple forms are reduced to a sequence of words, actually a valid {b HTML code} sent to the browser's engine for the final evaluation and display. Using a {i regular expression} based window, the evaluator literally {i loops over the code string}, skips the words and progressively replaces {b in situ} forms by words. {b The repeated substitutions inside the code string overcomes limitations of regular language}. A kind of Turing machine{ref 18} ...

{pre °° 
var eval_forms = function( str ) {
  while (str != (str=str.replace(leaf,eval_leaf))) 
    ; // does nothing!
  return str
};
var leaf = /\{([^\s{}]*)(?:[\s]*)([^{}]*)\}/g;
var eval_leaf = function(_,f,r) {
  return (DICT.hasOwnProperty(f)) ? 
          DICT[f].apply(null,[r]) : '('+f+' '+r+')' 
};
var DICT = {}; // initially empty
°°}

_h3 3. abstraction
_p Special forms {code '{lambda {arg*} body}} are matched and evaluated {b before} simple forms and replaced by a reference to an anonymous function added to the dictionary. The following code demonstrates that:

_ul {b 1) lambdas} are {b first class} functions,

_ul {b 2) lambdas} accept {b partial function application},  when called with a number of values lesser than their arity, they memorize the given values and return a lambda waiting for the rest,

_ul {b 3) lambdas} {b don't create closures}, inner lambdas have no access to outer lambdas' arguments, there is no lexical scoping, no environment, no free variables. Like mathematical functions {b lambdas} are pure black boxes. 
 
{pre °°
var abstract_lambdas = function(str) {
  while ( str !== ( str = 
    form_replace(str,'{lambda', abstract_lambda)));
  return str
};

{pre °°
var form_replace = function(str,sym,func,flag){
  sym += ' ';
  var s = catch_form( sym, str );
  return (s==='none')?
     str:str.replace(sym+s+'}',func(s,flag))
};

_h3 4. definition
_p Special forms {code '{def name expression}} are matched and evaluated {b before} simple forms and replaced by {code name} as a reference to {code expression} added to the dictionary.

{pre °°
var abstract_defs = function(str, flag) {
  while ( str !== ( str = 
    form_replace( str, '{def', abstract_def, flag ))) ;
  return str
};
var abstract_def = function (s, flag) {
  flag = (flag === undefined)? true : false;
  s = abstract_defs( s, false );
  var index = s.search(/\s/), // match spaces
      name  = s.substring(0, index).trim(),
      body  = s.substring(index).trim(); 
  if (body.substring(0,6) === '_LAMB_') {
    DICT[name] = DICT[body];
    delete DICT[body];
  } else {
     body = eval_forms(body);
     DICT[name] = function() { return body };
  }
  return (flag)? name : '';
};

°°}

_h3 5. ifthenelse
_p Special forms {code '{if bool then one else two}} are matched in lambda's bodies and replaced by the reference to an array {code [bool, one, two]}. When the lambda is called with some values, {code one} or {code two} is returned according to the {b bool} value.

{pre °°
var abstract_ifs = function(str) {
  while ( str !== ( str =
    form_replace( str, '{if', abstract_if ))) ;
  return str
};
var abstract_if = function(s){
  s = eval_ifs( s );
  var name = '_COND_' + COND_num++;
  var index1 = s.indexOf( 'then' ),
      index2 = s.indexOf( 'else' ),
      bool = s.substring(0,index1).trim(),
      one = s.substring(index1+5,index2).trim(),
      two = s.substring(index2+5).trim();
  COND[name] = [bool,one,two];
  return name;
};
var eval_ifs = function(bod, reg_args, vals) {  
   var m = bod.match( /_COND_\d+/ );
   if (m === null) { 
     return bod
   } else {
     var name = m[0];
     var cond = COND[name]; 
     if (cond === undefined) return bod;
     var bool=cond[0], one=cond[1], two=cond[2];
     if (reg_args !== undefined) {
      for (var i=0; i < vals.length; i++) {
       bool = bool.replace(reg_args[i], vals[i]); 
       one = one.replace(reg_args[i], vals[i]); 
       two = two.replace(reg_args[i], vals[i]); 
      }
     }
     var boolval = (eval_forms(bool)==='true')? 
                   one : two;
     bod = bod.replace( name, boolval );
     return eval_ifs( bod, reg_args, vals )
   }
};
°°}

_h2 references

{pre {WRAP}

{back_ref 1} The Wiki way: [[http://dl.acm.org/citation.cfm?id=375211|http://dl.acm.org/citation.cfm?id=375211]]
{back_ref 2} Ward_Cunningham: [[http://ward.asia.wiki.org/view/testing-microtalk|http://ward.asia.wiki.org/view/testing-microtalk]] 
{back_ref 3} A Tutorial Introduction to the Lambda Calculus (Raul Rojas): [[http://www.inf.fu-berlin.de/lehre/WS03/alpi/lambda.pdf|http://www.inf.fu-berlin.de/lehre/WS03/alpi/lambda.pdf]]
{back_ref 4} Lisp: [[http://www.cs.utexas.edu/~cannata/cs345/Class%20Notes/06%20Lisp.pdf|http://www.cs.utexas.edu/~cannata/cs345/Class%20Notes/06%20Lisp.pdf]]
{back_ref 5} Scheme: [[https://mitpress.mit.edu/sicp/full-text/book/book.html|https://mitpress.mit.edu/sicp/full-text/book/book.html]]
{back_ref 6} Collected Lambda Calculus Functions: [[http://jwodder.freeshell.org/lambda.html|http://jwodder.freeshell.org/lambda.html]]
{back_ref 7} Stephen_Cole_Kleene: [[https://en.wikipedia.org/wiki/Stephen_Cole_Kleene|https://en.wikipedia.org/wiki/Stephen_Cole_Kleene]]
{back_ref 8} L. Peter Deutsch [[https://fr.wikipedia.org/wiki/L._Peter_Deutsch|https://fr.wikipedia.org/wiki/L._Peter_Deutsch]] [[https://sites.google.com/a/gertrudandcope.com/info/Publications/Patterns/C--Report/SpaceIII|https://sites.google.com/a/gertrudandcope.com/info/Publications/Patterns/C--Report/SpaceIII]]
{back_ref 9} Jonas Raoni Soares Silva [[http://jsfromhell.com/classes/bignumber|http://jsfromhell.com/classes/bignumber]]
{back_ref 10} Simon_Peyton_Jones: [[https://www.microsoft.com/en-us/research/people/simonpj/#|https://www.microsoft.com/en-us/research/people/simonpj/#]]
{back_ref 11} De_Casteljau's_algorithm: [[http://www.malinc.se/m/DeCasteljauAndBezier.php|http://www.malinc.se/m/DeCasteljauAndBezier.php]]
{back_ref 12} raytracing: [[http://lambdaway.free.fr/lambdaway/?view=raytracing|http://lambdaway.free.fr/lambdaway/?view=raytracing]]
{back_ref 13} pForms: [[http://lambdaway.free.fr/lambdaway/?view=pforms|http://lambdaway.free.fr/lambdaway/?view=pforms]]
{back_ref 14} fractal: [[http://lambdaway.free.fr/lambdaway/?view=mandel|http://lambdaway.free.fr/lambdaway/?view=mandel]] 
{back_ref 15} turtle: [[http://lambdaway.free.fr/lambdaway/?view=lambdatree|http://lambdaway.free.fr/lambdaway/?view=lambdatree]] 
{back_ref 16} google-subtracts-mathml-from-chrome: [[https://www.cnet.com/news/google-subtracts-mathml-from-chrome-and-anger-multiplies/|https://www.cnet.com/news/google-subtracts-mathml-from-chrome-and-anger-multiplies/]]
{back_ref 17} Regular Expressions: [[http://blog.stevenlevithan.com/archives/reverse-recursive-pattern|http://blog.stevenlevithan.com/archives/reverse-recursive-pattern]]
{back_ref 18} Turing machines implemented in JavaScript  [[http://www.turing.org.uk/book/update/tmjavar.html|http://www.turing.org.uk/book/update/tmjavar.html]]
}

} ;; end of columns

;; the following should be externalized

{script °°
var SHEET = (function () {

// BUTTONS

var storage2editor = function() {
  getId('local_storage').value = 
     localStorage.getItem('myCells');
};

var editor2storage = function() {
  if (!confirm('Are you sure?')) return;
  localStorage.setItem('myCells', 
     getId('local_storage').value);
  storage2cells(); 
};

var storage_clear = function() {
  if (!confirm('Are you sure?')) return;
  localStorage.removeItem('myCells');
  getId('local_storage').value = '';

var edits = document.getElementsByClassName('edit');
  var disps = document.getElementsByClassName('disp');
  for (var i = 0; i < edits.length; i++) {
    edits[i].value = '';
    disps[i].innerHTML = '.';
  }
};

return {
  cell_open:cell_open,
  cells_eval:cells_eval,
  storage2cells:storage2cells,
  storage2editor:storage2editor,
  editor2storage:editor2storage,
  storage_clear:storage_clear 
};

})();

°°}

{{hide}

{def spreadsheet 
 {lambda {:m :n}
  {div {@ style="position:relative;"}
   {span
    {@ id="M" style="visibility:hidden"}:m}
   {span
    {@ id="cell_num"
       style="font:bold 0.9em courier;"}}
   {sheet.new sheet.input :m :n}
   {sheet.new {sheet.output :m} :m :n}
   {br}
   [{note_start local_editor local storage}]
   {note_end {@ id="local_editor"} 
   {input 
    {@ type="button" value="storage -> cells"
       onclick="SHEET.storage2cells()"}}

{input
    {@ type="button" value="storage -> editor"
       onclick="SHEET.storage2editor()"}}

{input
    {@ type="button" value="editor -> storage"
       onclick="SHEET.editor2storage()"}}

{input 
    {@ type="button" value="clear storage" 
       onclick="SHEET.storage_clear()"}}

{br}
   {textarea
    {@ id="local_storage"
       placeHolder="This is the frame in which can be copied, pasted and edited the sheet's content."
       style="width:98%;"}}
  }

}}}

{def sheet.new 
 {lambda {:f :m :n}
  {map {{lambda {:f :m :n}
   {br}{map {:f :n}
    {serie 1 :m}}} :f :m}
     {serie 1 :n}
}}}

{def sheet.input 
 {lambda {:i :j}
  {textarea
   {@ id=":i|:j" class="edit"
      onkeyup="SHEET.cells_eval()"
      title="Enter words and/or lambdatalk expressions"
      style="height:20px; padding:0 5px;
             background:#eee; color:#f00;
             display:none;             
             border:0;"
}}}}

{def sheet.output       
 {lambda {:m :i :j}
  {div 
   {@ id="_:i|:j_" class="disp"
      onclick="SHEET.cell_open(:i,:j)"
      title="click to edit the cell."
      style="display: inline-block;
             vertical-align:top;
             width: {round {/ 90 :m}}%; margin:2px 0;
             text-align: center;
             background: #ccc; color: #000;
             border: 0;"}
   .
}}}

}

{{hide}
{def TITLE 
{center 
 {@ style="border-bottom:1px solid #ccc;
           margin:15px 0; padding:15px 0"}      
 {div {@ style="font:bold 18pt arial"} '{lambda talk}}    
 {div {@ style="font:normal 12pt arial"} Alain Marty Engineer Architect} 
 {div {@ style="font:normal 10pt arial"} Villeneuve de la Raho, France}
 {div {@ style="font:normal 12pt arial"} marty.alain@free.fr}
}
}
{def WRAP 
 {@ style="word-wrap: break-word; white-space:pre-wrap;"}}
{def ref {lambda {:i}
  {a {@ name="_:i" href="#:i"}{sup [:i]}} }}
{def back_ref {lambda {:i}
  {b {a {@ name=":i" href="#_:i"}[:i]}} }}
{def space {span {@ style="padding:0 10pt"}}}
}

{style °°
body { background:#fff; }
#title { display:none; }
#frame_view {
 font:normal 9pt Times Roman;
 width:650px; 
 width:100%; 
 margin:auto;
 padding:0;
 border:0;
 box-shadow:0 0 0;
}
p {
 margin:10px 0;
 text-indent:0px;
}
h2 {
 font:bold 12pt Times Roman;
 text-transform: uppercase; color:#000;
} 
h3 {
 font:italic 12pt Times Roman; color:#000;
} 
h4, h5, h6 { 
 font:italic 11pt Times Roman; color:#000;
} 
pre {
 white-space:pre-wrap; background:#fff; color:#000;
 border-top:0px solid #ccc;
 border-bottom:0px solid #ccc;
 margin:2px 0; 
}
a { color:#000; }
°°}

°°° 
{style °°
#title { display:block; }
#frame_view {
  width:700px;
  font-size:1.0em;
  border:0;
  background:#fff;
  box-shadow:0 0 0;
}
.call:hover { opacity:0.5; }
.call img   { box-shadow:0 0 4px #000; }
pre {
  font:normal 1.0em courier; 
  /* box-shadow:0 0 8px #000; */
  background:#ffe;
}
°°}
°°°