lambdaspeech :: fabric

{pre {@ style="width:600px; margin:auto;
               font:italic 1.5em courier;
               background:transparent;
               -webkit-transform:rotate(-5deg);
                       transform:rotate(-5deg);"}
'{DECIM 
 {{lambda {:n}
  {{lambda {:g :n} {:g :g :n}} 
   {lambda {:g :n}
    {{{NIL? :n} 
     {PAIR {lambda {:g :n} {ONE}}
           {lambda {:g :n}
            {MUL :n {:g :g {PRED :n}}}}
    }} :g :n}} :n}}
 {FIVE}}}
-> {b 120} 
}

{TITLE}

_h2 abstract

_p Wikis are everywhere. In a typical wiki, text is written using simplified syntaxes which are not designed for creating rich and highly structured documents naturally intermixing rich text and active code. In this paper we introduce '{lambda talk}, a small functional language, dialect of the λ-calculus, unifying the markup, styling and scripting, and working in a wiki engine, '{lambda tank}, staying as a light overlay on any modern web browsers.

_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

{hr}
{center {i All code examples in this page are "live", just open the wiki page editor and edit what you want.}} 
{hr}

_h2 introduction

{center « {i There are hundred of wiki engines and hundred of languages! {br}Why yet another wiki and another language nobody will ever want to use?} »}

_p A {b wiki}{ref 1} is {i a web application which allows collaborative modification, extension, or deletion of its content and structure}. Following the first wiki created in 1995 by {b Ward Cunningham}{ref 2} hundred of wikis have moved us from simple consumers to creators of shared informations. The best known of wikis is {b Wikipedia}, full of rich documented pages written by authors supposed to be neither web designers nor coders. Wikis come generally with rather rudimentary and heterogeneous syntaxes to enter, enrich and structure texts. At the lowest level documents are created using HTML & CSS syntaxes. But writing HTML/CSS code being rather complex and at least tiresome, intermediate syntaxes, for instance {b Markdown syntax}{ref 3}, have been created to make things a little bit easier. Everything works well but the code quickly becomes rather obfuscated, difficult to write, read, edit and maintain. In fact, the {b Markdown syntax} is not intended for writing rich documents. Works have been done to build enhanced syntaxes, true languages, in order to unify authoring, styling and coding, for instance CURL{ref 4}, LML{ref 5}, Scribble{ref 6}, SXML{ref 7}, LAML{ref 8}, Pollen{ref 9} ; follow links to get more informations about them. But these tools are definitively devoted to coders, not to web designers and even less to authors, making difficult - if not impossible - a true collaborative work. For instance these tools are built as extensions of existing languages - Lisp, Scheme - where sequences of words must always been "protected" as strings between quotes - say {b '{print "Hello World"}} {ref 20} - and it's definitely unacceptable in the context of a wiki, as it is in a text or spreadsheet editor. Hence '{lambda talk}.

_p '{lambda talk} is a small language working in a wiki engine staying as a light overlay and free of any dependances on any modern web browsers. The wiki engine is nothing but a very rudimentary standard wiki without any original contribution. Its best quality is to be easy to install on any host providers - they generally run PHP - and easy to use: you write text, see the result in real time and save/publish. In the following we forget the wiki and show the "making of" '{lambda talk}, built on a minimal set of rules.

_p Imagine a machine which understands this question:

{pre
{b replace} "fruit" and "unknown" 
     {b in} "The color of fruits is unknwon." 
     {b by} "apple" and "green"
}

_p and returns

{pre
The color of apples is green.
}

_p '{lambda talk} is such a {b replacement machine} waiting for an expression formulated in a slightly different syntax

{pre
'{{lambda {fruit unknown} 
          The color of fruits is unknown.} 
          apple green}
}

_p and progressively evaluated to words

{pre
.  '{{lambda {fruit unknown} The color of fruits is unknown.} apple green}
-> '{{lambda {      unknown} The color of apples is unknown.}       green}
-> '{{lambda {             } The color of apples is green.}              }
-> {b The color of apples is green.}
}

_p It's nothing but {b text substitutions} in a sequence of words. Let's try expressions nesting lambdas

{pre
'{{lambda {z} {z {lambda {x y} x}} {{lambda {x y z} {z x y}} ♥ ♠}}} -> {b ♥}
'{{lambda {z} {z {lambda {x y} y}} {{lambda {x y z} {z x y}} ♥ ♠}}} -> {b ♠}
}

_p These expressions work on a couple of words, [{b ♥ ♠}], and respectively return the first and the second. It's rather easy to follow substitutions in the first expression leading to {b ♥}

{pre °°
.  {{lambda {z} {z {lambda {x y} x}}} {{lambda {x y z} {z x y}} ♥ ♠}}
-> {{lambda {z} {z {lambda {x y} x}}} {{lambda {  y z} {z ♥ y}}   ♠}}
-> {{lambda {z} {z {lambda {x y} x}}} {{lambda {    z} {z ♥ ♠}}    }}
-> {{lambda {z} {z {lambda {x y} x}}}  {lambda {    z} {z ♥ ♠}}     }
-> {{lambda {z} {z ♥ ♠}} {lambda {x y} x}}
-> {{lambda {x y} x} ♥ ♠}
-> ♥
°°}
 
_p We can go further building much more complex replacements using deeply nested lambdas

{pre {@ style="white-space:pre-wrap"} 
'{{lambda {f n} {f f n}} {lambda {f t} {{{{lambda {n} {n {lambda {x} {lambda {z} {z {lambda {x y} y}}}} {lambda {z} {z {lambda {x y} x}}}}} t} {{lambda {x y z} {z x y}} {lambda {f t}} {lambda {f t} {{lambda {z} {z {lambda {x y} x}}} t} {f f {{lambda {z} {z {lambda {x y} y}}} t}}}}} f t}} {{lambda {x y z} {z x y}} apple {{lambda {x y z} {z x y}} banana {{lambda {x y z} {z x y}} lemon {{lambda {x y z} {z x y}} orange {lambda {f x} x}}}}}}

-> {b apple banana lemon orange}
}

_p Following the cascade of replacements in such a convoluted expression is far to be obvious! The amazing fact is that, as we will discover in the following section, this expression made of words, lambdas and curly braces, hides two data structures, a {b pair}, a {b list} and a control structure, the {b recursion}, which are the {i Maxwell's Equations} of functional computing. In fact we have in hands anything we need to reverse, append and sort lists, count their elements, build numbers and their related operators, compute the factorial of a number, play with the Towers of Hanoï, and so on. Theoretically {i ad libitum}.

_h2 1. foundation

_p The foundation of '{lambda talk} is the {b λ-calculus} language, created in the 1930s by {b Alonzo Church} {ref 10} ten years before the era of computers. Following the initial paper, numerous introductions have been proposed, for instance [[A Tutorial Introduction to the Lambda Calculus|http://www.inf.fu-berlin.de/lehre/WS03/alpi/lambda.pdf]] by {b Raul Rojas} and  [[The Lambda Calculus|http://cs.brown.edu/courses/cs173/2001/Lectures/2001-10-25.pdf]] by Don Blaheta. This is how Raul Rojas introduces the λ-calculus: « {i The  central  concept in λ-calculus is the “expression”. A “name”, also  called a “variable”, is an identifier which, for our purposes, can be any of the letters a,b,c,... An expression is defined recursively as follows}

{pre
< expression >  := < name > | < function > | < application >
< function >    := λ < name >.< expression >
< application > := < expression >< expression >
}

_p On this reduced set of rules Raul Rojas shows {i « how to perform some arithmetical computations using the λ calculus and how to define recursive functions.} »

_p Don Blaheta starts with « {i We’ve seen that Scheme is, as languages go, pretty small. There are just a few keywords, and most of the utility of the language is inherent in its minimal, unornamented structure, unlike, say, “public static void main” Java. We can come up with a short list of fundamental Scheme concepts} »
{pre {center
( ) lambda define if true false
cons car cdr numbers arithmetic
}}

_p « {i Without motivating it too deeply, let’s consider how we could reduce this list further, by implementing some of these features in terms of others.}

_p Even if these short introductions are supposed to be understandable by average people, they become quickly convoluted, labyrinthic, obfuscated. « {i After all, it's λ calculus, man!} »  It's the reason why, in this paper, concepts are introduced via the "making of" a language, progressively adding to the initial set of rules small user defined functions, data and control structures, then a set of primitives, special forms and libraries to reach the level of a true functional programming language. In order to make code easier to read, following Lisp/Scheme, we will use a systematic parenthesis prefixed notation. More precisely, being in a wiki context, parenthesis will be replaced by curly braces.

_h3 '{lambda talk}'s minimal set of rules

_p At the lowest level {b expressions} are made of {b words, abstractions & applications} recursively evaluated to {b words}:

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

_p More precisely

_ul a {b word} is a group of any characters except spaces and curly braces '{}, and stands for itself, ie is its own value,

_ul an {b application} determines if {b expression1} is bound to a {b function} then evaluates {b expression2} into {b words2}, applies that function to words2 and returns other {b words},

_ul an {b abstraction} is evaluated into a {b word} bound to an anonymous function selecting words (arguments) in expression (body) to be replaced by some future given words (values).

_p The evaluation stops when the code is reduced to words without any curly braces. These words are sent to the browser's engine for anymore evaluations - HTML/CSS/SVG,... - and the final display.

_p For convenience we will add a second special form, {b definition}, with which users can create constants and give a name to anonymous functions

{pre
4) definition is {b '{def word expression}}
}

_p More precisely

_ul a {b definition} is a special form which evaluates expression - the body -, binds word - the name - to a function returning body and returns the name. Definitions are evaluated after lambdas and before applications.

_p That's all!

_h2 2. implementation

_p A language can't be understood in deep, without any shadow zone, any mysterious behaviour, if the main part of its implementation is not revealed. It happens that '{lambda talk} is not implemented on a standard AST approach - {b evaluate( build_tree( tokenize( code )))} - but on an original approach based on Regular Expressions {ref 11}.

_p The heart of '{lambda talk} is an Immeditely Invoked Function Expression (IIFE). This is its minimal shape

{pre
var {b LAMBDATALK} = (function() '{
  return { 
    DICT: {}                      // the dictionary is initially empty
    evaluate:function(s) { ... }  // a single public function
  }
})();
}

_h3 2.1. the main function

_p Each key entry in the wiki - or in a simple HTML interface - calls the function {b LAMBDATALK.evaluate( code )}

{pre 
var {b evaluate} = function(s) °°{°°
    var bal = balance(s);
    if (bal.left === bal.right) °°{°°
      {span {@ style="color:grey;"}s = preprocessing(s);}
      s = eval_special_forms(s);
      s = eval_forms(s);
      {span {@ style="color:grey;"}s = postprocessing(s);}
    °°}°°
    return °°{val:s, bal:bal}°°;
°°}°°;

}

_p The evaluator catches special forms first, abstracted from the main string, then evaluates the rest, simple nested forms.

_h3 2.2. nested forms evaluation

_p Simple forms are nested expressions evaluated after special forms and from inside out. The process is built on a single line of Javascript running a single regular expression over and over the input string, replacing '{first rest} terminal expressions - the leaves - until there are no more changes {ref 12}.

{pre 
var {b eval_forms} = function(s) °°{°°
    var regexp = {b °°/\{([^\s{}]*)(?:[\s]*)([^{}]*)\}/g;°°}
    while (s !== (s = s.replace( regexp, eval_form ))) ;
    return s;
°°}°°;

var {b eval_form} = function() °°{°°
    var {b first} = arguments[1] || "", {b rest} = arguments[2] || "";
    return DICT.hasOwnProperty({b first})
      ? DICT[{b first}].apply(null, [{b rest}]) : "[" + {b first} + " " + {b rest} + "]";
°°}°°;
}

_p The fact that it is repeated application of the same transformation makes the process effective. Repeated application of Regular Expressions can perform Turing Complete computations {ref 13}. This works because the "needed state" is in the partially evaluated text itself.

_p Initially the dictionary, DICT, is empty. As an example, this is how we could add an {b add} operator waiting for two numbers:

{pre °°
DICT['add'] = function() {                       // {* 3 4}
  var args = supertrim( arguments[0] ).split(' ');  // [3,4]
  return args[0] * args[1];                      // 3*4
};
°°}

_h3 2.3. special forms evaluation

{pre 
var {b eval_special_forms} = function(s, flag) °°{°°
    {span {@ style="color:grey;"}while (s !== (s = form_replace(s, "quote",  eval_quote)));} 
    {span {@ style="color:grey;"}while (s !== (s = form_replace(s, "let",    eval_let)));}
    {b while (s !== (s = form_replace(s, "lambda", eval_lambda)));}
    {span {@ style="color:grey;"}while (s !== (s = form_replace(s, "def",    eval_def, flag)));}
    {span {@ style="color:grey;"}while (s !== (s = form_replace(s, "if",     eval_if)));}
    return s;
°°}°°;
}

_p In the following we will forget any special form except lambdas, which are the heart of '{lambda talk} and have the following properties

_ul lambdas are first class, essentially they can be called as arguments, returned as values and created at run-time,
_ul lambdas brings some {i laziness} in an applicative order evaluation process,
_ul lambdas can be nested,
_ul lambdas accept vals' number < args' number, functions accept partial calls, memorizing the given values and returning a new function waiting for the rest,
_ul lambdas accept vals' number > args' number, extra values are simply gathered in the last argument,
_ul lambdas are pure functions, like mathematical functions the list of arguments determines the local working environment, there is no access to any external variables, no closure, no free variables, no side effects,

_ul lambdas abstract from the main code {i long} string a set of {i short} sub-strings in which anymore evaluations can be quickly performed. The code string has been transformed into a tree of strings before the evaluation starts.

_p Everything is done in the {b eval_lambda()} function:

{pre 
  var {b eval_lambda} = function(s) °°{°° 
    {b s = eval_special_forms(s);}  // recursive call
    var index = s.indexOf("°°)°°"),
      argStr = supertrim(s.substring(1, index)),
      {b args} = argStr === "" ? [] : argStr.split(" "),
      {b body} = s.substring(index + 2).trim(),
      {b name} = "_LAMB_" + LAMB_num++,
      {b reg_args} = [];
    for (var i = 0; i < args.length; i++)
      reg_args[i] = RegExp(args[i], "g");
    {b body = eval_special_forms( body );}
    {b DICT[name]} = function() °°{°°
      var valStr = supertrim(arguments[0]);
      var {b vals} = valStr === "" ? [] : valStr.split(" ");
      return (function(bod) °°{°°
        {i bod = eval_conds(bod, reg_args, vals);} // if sepcial forms
        {b if (vals.length < args.length)} °°{°°   // partial call
          for (var i = 0; i < vals.length; i++)
            bod = bod.replace(reg_args[i], vals[i]);
          var _args_ = args.slice(vals.length).join(" ");
          bod = eval_lambda("°°{" + _args_ + "}°° " + bod);
        °°}°° {b else if ( vals.length === args.length)} °°{°° // total call
          for (var i=0; i < args.length; i++)
          bod = bod.replace( reg_args[i], vals[i] );
        °°}°° {b else} °°{°° // extra vals are gathered in the last arg                
          var _vals_ = vals.slice(0,args.length);
          _vals_[args.length-1] = 
          vals.slice(args.length-1,vals.length).join(' ');
          for (var i=0; i < args.length; i++)
            bod = bod.replace( reg_args[i], _vals_[i] ); 
        °°}°°
        return {b eval_forms(bod);}
      °°}°°)(supertrim(body));
    °°}°°;
    return name;  // _LAMB_n
  °°}°°; 
}

_p What can be done with so little?

_h2 3. first steps

_p Words are not evaluated. As in any text or spreadsheet editor {i quoting} sequences of words is useless .

{pre
Hello World 
-> Hello World
}

_p Sequences of words can be given a name
{pre
'{def HI Hello World} -> {def HI Hello World}
HI, I just say '{HI} 
-> HI, I just say {HI} 
}

_p Note that writing {b HI} displays {b HI}. You must write {b '{HI}} to get its value, {b {HI}}. In spreadsheets - which are wonderful examples of functional programming - writing {b PI} displays {b PI}, and you must write {b = PI()} to get the value, {b {PI}}.

_p Anonymous functions can be created and immediately called 
{pre
'{{lambda {fruit unknown}
  The color of fruits is unknown.} apple green} 
-> {{lambda {fruit unknown}
  The color of fruits is unknown.} apple green}
}

_p Anonymous functions can be given a name
{pre
'{def AFFIRMATION {lambda {fruit unknown} The color of fruits is unknown.}} 
-> {def AFFIRMATION
 {lambda {fruit unknown}
  The color of fruits is unknown.}}

'{AFFIRMATION apple green} 
-> {AFFIRMATION apple green}
'{AFFIRMATION banana yellow} 
-> {AFFIRMATION banana yellow} 
}

_h2 4. data & control structures

_p In order to understand how the long and {i unreadable} expression given in the introductive section can be composed, we are going to build it from a set of smaller compositions of lambdas.

_p First we define 3 functions, [{b PAIR, LEFT, RIGHT}]

{pre
'{def PAIR {lambda {:x :y :z} {:z :x :y}}} 
-> {def PAIR {lambda {:x :y :z} {:z :x :y}}}
'{def LEFT {lambda {:z} {:z {lambda {:x :y} :x}}}} 
-> {def LEFT {lambda {:z} {:z {lambda {:x :y} :x}}}}
'{def RIGHT {lambda {:z} {:z {lambda {:x :y} :y}}}} 
-> {def RIGHT {lambda {:z} {:z {lambda {:x :y} :y}}}}
}

_p We have just defined a fundamental {b data structure}. Something close to the [{b cons, car cdr}] construction well known in the LISP/SCHEME world {ref 14}{ref 15}. Thanks to this data structure we can aggregate two words with {b PAIR} and access each of them with {b LEFT} and {b RIGHT}

{pre
'{def ♥♠ {PAIR ♥ ♠}} 
-> {def ♥♠ {PAIR ♥ ♠}}  
'{LEFT {♥♠}} 
-> {LEFT {♥♠}} 
'{RIGHT {♥♠}} 
-> {RIGHT {♥♠}}
}

_p We define two associated functions, [{b NIL, NIL?}], where {b NIL?} is a predicate function returning {b LEFT} if applied on {b NIL} or {b RIGHT} if applied on a pair.

{pre
'{def NIL? {lambda {:n} {:n {lambda {:x} RIGHT} LEFT}}} 
-> {def NIL? {lambda {:n} {:n {lambda {:x} RIGHT} LEFT}}}
'{def NIL {lambda {:f :x} :x}} 
-> {def NIL {lambda {:f :x} :x}} 
 
'{NIL? NIL} 
-> {NIL? NIL} 
'{NIL? {♥♠}} 
-> {NIL? {♥♠}}
}

_p We can compose PAIRs to build lists terminating with {b NIL}

{pre
'{def FRUITS {PAIR apple {PAIR banana {PAIR lemon {PAIR orange NIL}}}}} 
-> {def FRUITS
 {PAIR apple
  {PAIR banana
   {PAIR lemon
    {PAIR orange NIL}}}}}
}

_p and access each of their elements with {b LEFT} and {b RIGHT}

{pre
'{LEFT {FRUITS}} 
-> {LEFT {FRUITS}} 
'{LEFT {RIGHT {FRUITS}}} 
-> {LEFT {RIGHT {FRUITS}}}
'{LEFT {RIGHT {RIGHT {FRUITS}}}} 
-> {LEFT {RIGHT {RIGHT {FRUITS}}}}
'{LEFT {RIGHT {RIGHT {RIGHT {FRUITS}}}}} 
-> {LEFT {RIGHT {RIGHT {RIGHT {FRUITS}}}}}
'{RIGHT {RIGHT {RIGHT {RIGHT {FRUITS}}}}} 
-> {RIGHT {RIGHT {RIGHT {RIGHT {FRUITS}}}}}
}

_p Playing with the {b NIL?} predicate function

{pre
'{NIL? {FRUITS}} 
-> {NIL? {FRUITS}}
'{NIL? {RIGHT {FRUITS}}} 
-> {NIL? {RIGHT {FRUITS}}}
'{NIL? {RIGHT {RIGHT {FRUITS}}}} 
-> {NIL? {RIGHT {RIGHT {FRUITS}}}}
'{NIL? {RIGHT {RIGHT {RIGHT {FRUITS}}}}} 
-> {NIL? {RIGHT {RIGHT {RIGHT {FRUITS}}}}}
'{NIL? {RIGHT {RIGHT {RIGHT {RIGHT {FRUITS}}}}}} 
-> {NIL? {RIGHT {RIGHT {RIGHT {RIGHT {FRUITS}}}}}}
}

_p enlights a "pattern" leading to a {b recursive function} displaying the list

{pre
'{def LIST.DISP {lambda {:l}
  {{{NIL? :l}
   {PAIR {lambda {:l} }
         {lambda {:l} {LEFT :l} {LIST.DISP {RIGHT :l}} } }} :l}}} 
-> {def LIST.DISP
 {lambda {:l}
  {{{NIL? :l}
   {PAIR {lambda {:l} }
         {lambda {:l} {LEFT :l}
                      {LIST.DISP {RIGHT :l}} } }} :l}}}

'{LIST.DISP {FRUITS}} 
-> {LIST.DISP {FRUITS}}
}

_p Let's trace the definition and the evaluation of '{LIST.DISP {FRUITS}}. We rewrite this definition using 2 helper functions, [{b one, two}] in order to enlight the process of delaying and forcing evaluation:

_ul first {u delaying} {b one & two} with lambdas
_ul then {u forcing} {b one OR two} depending on {b bool}

{pre
'{def one {lambda {:l} }} 
-> {def one {lambda {:l} }}
'{def two {lambda {:l} {LEFT :l} {LIST.DISP {RIGHT :l}} }} 
-> {def two {lambda {:l} {LEFT :l} {LIST.DISP {RIGHT :l}} }}
'{def LIST.DISP {lambda {:l} {{{NIL? :l} {PAIR one two}} :l} }} 
-> {def LIST.DISP {lambda {:l} {{{NIL? :l} {PAIR one two}} :l} }}
}

_p So

{pre
'{LIST.DISP {FRUITS}}
-> '{{lambda {:l} {{{NIL? :l} {PAIR one two}} :l}} {FRUITS}}
-> '{{{NIL? {FRUITS}} {PAIR one two}} {FRUITS}}
-> '{{RIGHT {PAIR one two}} {FRUITS}}
-> '{two {FRUITS}}
-> '{{lambda {:l} {LEFT :l} {LIST.DISP {RIGHT :l}}} {FRUITS}}
-> '{LEFT {FRUITS}} '{LIST.DISP {RIGHT {FRUITS}}}
-> apple '{LIST.DISP {RIGHT {FRUITS}}}
and so on, recursively
-> apple banana '{LIST.DISP {RIGHT {RIGHT {FRUITS}}}}
-> apple banana lemon '{LIST.DISP {RIGHT {RIGHT {RIGHT {FRUITS}}}}}
-> apple banana lemon orange '{LIST.DISP {RIGHT {RIGHT {RIGHT {RIGHT {FRUITS}}}}}}
-> apple banana lemon orange '{LIST.DISP NIL}
until the end case
-> apple banana lemon orange '{{lambda {:l} {{{NIL? :l} {PAIR one two}} :l}} NIL}
-> apple banana lemon orange '{{{NIL? NIL} {PAIR one two}} NIL}
-> apple banana lemon orange '{{LEFT {PAIR one two}} NIL}
-> apple banana lemon orange '{one NIL}
-> apple banana lemon orange '{{lambda {:l} } NIL}
-> apple banana lemon orange
}

_p So, the obfuscated expression given in the introductive section and the LIST.DISP user defined recursive function lead to the same result. We still have to demonstrate that they are equivalent. The problem is that a recursive function calls its name in its body and so must be named. We have to eliminate names - we have to forget the second special form {b def} - to get a chance to find an expression exclusively made of words and lambdas. A known solution is to split the recursive function into some {b Y-combinator} and an {i almost recursive} function {i which doesn't call its name in its body}

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

'{def ALMOST {lambda {:f :l}
 {{{NIL? :l}
   {PAIR {lambda {:f :l} }
         {lambda {:f :l} {LEFT :l} {:f :f {RIGHT :l}} } }} :f :l}}} 
-> {def ALMOST
{lambda {:f :l}
 {{{NIL? :l}
   {PAIR {lambda {:f :l} }
         {lambda {:f :l} {LEFT :l}
                         {:f :f {RIGHT :l}} } }} :f :l}}}

'{Y ALMOST {FRUITS}} 
-> {Y ALMOST {FRUITS}}
}

_p Finally, replacing in {b '{Y ALMOST {FRUITS}}} all user defined names, {b  PAIR, LEFT, RIGHT, NIL, NIL?, Y, ALMOST, FRUITS}, by their lambda definitions, we get an expression exclusively made of words and lambdas, in a pure {b λ-calculus} style

{pre {@ style="white-space:pre-wrap"}
'{{lambda {:f :n} {:f :f :n}} {lambda {:f :t} {{{{lambda {:n} {:n {lambda {:x} {lambda {:z} {:z {lambda {:x :y} :y}}}} {lambda {:z} {:z {lambda {:x :y} :x}}}}} :t} {{lambda {:x :y :z} {:z :x :y}} {lambda {:f :t}} {lambda {:f :t} {{lambda {:z} {:z {lambda {:x :y} :x}}} :t} {:f :f {{lambda {:z} {:z {lambda {:x :y} :y}}} :t}}}}} :f :t}} {{lambda {:x :y :z} {:z :x :y}} apple {{lambda {:x :y :z} {:z :x :y}} banana {{lambda {:x :y :z} {:z :x :y}} lemon {{lambda {:x :y :z} {:z :x :y}} orange {lambda {:f :x} :x}}}}}}
-> apple banana lemon orange 
}

_p To sum up, with nothing but 3 rules, {b words, abstractions, applications}, we have built two data structures, {b pairs & lists}, and a control structure, {b recursion}. Let's give some more examples of application.

_p For instance we can reverse and append lists

{pre
'{def LIST.REVERSE
 {def LIST.REVERSE.r {lambda {:a :b}
   {{{NIL? :a}
   {PAIR {lambda {:a :b} :b}
         {lambda {:a :b} {LIST.REVERSE.r {RIGHT :a} {PAIR {LEFT :a} :b}}} }} :a :b}}}
 {lambda {:a} {LIST.REVERSE.r :a NIL}}} 
-> {def LIST.REVERSE
 {def LIST.REVERSE.r
  {lambda {:a :b}
   {{{NIL? :a}
   {PAIR {lambda {:a :b} :b}
         {lambda {:a :b}
          {LIST.REVERSE.r
           {RIGHT :a} {PAIR {LEFT :a} :b}}}
   }} :a :b}}}
 {lambda {:a} {LIST.REVERSE.r :a NIL}}}

'{def LIST.APPEND
 {def LIST.APPEND.r
  {lambda {:a :b}
   {{{NIL? :b}
    {PAIR {lambda {:a :b} :a}
          {lambda {:a :b} {LIST.APPEND.r {PAIR {LEFT :b} :a} {RIGHT :b}}}
  }} :a :b}}}
 {lambda {:a :b}
  {LIST.APPEND.r :a {LIST.REVERSE :b}}}} 
-> {def LIST.APPEND
 {def LIST.APPEND.r
  {lambda {:a :b}
   {{{NIL? :b}
    {PAIR {lambda {:a :b} :a}
          {lambda {:a :b} {LIST.APPEND.r {PAIR {LEFT :b} :a} {RIGHT :b}}}
  }} :a :b}}}
 {lambda {:a :b}
  {LIST.APPEND.r :a {LIST.REVERSE :b}}}}

'{LIST.DISP {LIST.REVERSE {FRUITS}}} 
-> {LIST.DISP {LIST.REVERSE {FRUITS}}}

'{LIST.DISP {LIST.APPEND {FRUITS} {LIST.REVERSE {FRUITS}}}}
-> {LIST.DISP {LIST.APPEND {FRUITS} {LIST.REVERSE {FRUITS}}}}
}

_p We can define and display trees

{pre
'{def TREE.DISP
 {lambda {:p}
  {{{NIL? {RIGHT :p}}
   {PAIR {lambda {:p} {LEFT :p}}
         {lambda {:p} ({TREE.DISP {LEFT :p}}
                       {TREE.DISP {RIGHT :p}})}}} :p}}}
-> {def TREE.DISP
 {lambda {:p}
  {{{NIL? {RIGHT :p}}
   {PAIR {lambda {:p} {LEFT :p}}
         {lambda {:p} ({TREE.DISP {LEFT :p}}
                       {TREE.DISP {RIGHT :p}})}}} :p}}}

'{def TREE
 {PAIR
  {PAIR
   {PAIR
    {PAIR A NIL}
    {PAIR B NIL}}
   {PAIR
    {PAIR C NIL}
    {PAIR D NIL}}
  } 
  {PAIR
   {PAIR
    {PAIR E NIL}
    {PAIR F NIL}}
   {PAIR
    {PAIR G NIL}
    {PAIR H NIL}}
}}}
-> {def TREE
 {PAIR
  {PAIR
   {PAIR
    {PAIR A NIL}
    {PAIR B NIL}}
   {PAIR
    {PAIR C NIL}
    {PAIR D NIL}}
  } 
  {PAIR
   {PAIR
    {PAIR E NIL}
    {PAIR F NIL}}
   {PAIR
    {PAIR G NIL}
    {PAIR H NIL}}
}}}

'{TREE.DISP {TREE}}
-> {TREE.DISP {TREE}}
}

_p Instead of displaying each term of a list we could display, for instance, a pipe {b |}

{pre
'{def LIST.LENGTH {lambda {:l}
  {{{NIL? :l}
   {PAIR {lambda {:l} }
         {lambda {:l} | {LIST.LENGTH {RIGHT :l}}} }} :l}}} 
-> {def LIST.LENGTH
 {lambda {:l}
  {{{NIL? :l}
   {PAIR {lambda {:l} }
         {lambda {:l} | {LIST.LENGTH {RIGHT :l}}}
   }} :l}}}

'{LIST.LENGTH {FRUITS}} 
-> {LIST.LENGTH {FRUITS}}
}

_p Ok, we have got the length of the list displayed as four pipes but, obviously, we need a more modern display of numbers! It's time to build the set of natural numbers.

_h2 5. numbers

_p The set of natural numbers uses to be defined as ZERO and its successors. Alonzo CHURCH defined a number {b N} as a function iterating N times the application of a function {b f} on a variable {b x}. We will choose another way and define natural numbers as lists of any word, for instance a {b pipe |}. We will define ZERO as NIL, ONE will be the pair '{PAIR | NIL}, TWO will be the pair '{PAIR | {PAIR | NIL}} and so on. But we have seen that computing the length of a list displays a sequence of pipes, a very old numeral system. In order to display results in a modern decimal notation we will display numbers using this function

{pre
'{def DECIM
 {lambda {:n}
  {{{NIL? :n}
   {PAIR {lambda {:n} 0}
         {lambda {:n} {+ 1 {DECIM {RIGHT :n}}}}}} :n}}}
-> {def DECIM
 {lambda {:n}
  {{{NIL? :n}
   {PAIR {lambda {:n} 0}
         {lambda {:n} {+ 1 {DECIM {RIGHT :n}}}}}} :n}}}
}

_p forgetting that we are not allowed to use JS numbers and their associate operators. And to make things easier let's also define the SUCCessor operator

{pre
'{def SUCC {lambda {:n} {PAIR | :n}}}
-> {def SUCC {lambda {:n} {PAIR | :n}}}

'{def ZERO NIL}             -> {def ZERO NIL}    '{DECIM {ZERO}}  -> {DECIM {ZERO}}
'{def ONE {SUCC {ZERO}}}    -> {def ONE {SUCC {ZERO}}}     '{DECIM {ONE}}   -> {DECIM {ONE}}  
'{def TWO {SUCC {ONE}}}     -> {def TWO {SUCC {ONE}}}     '{DECIM {TWO}}   -> {DECIM {TWO}}
'{def THREE {SUCC {TWO}}}   -> {def THREE {SUCC {TWO}}}   '{DECIM {THREE}} -> {DECIM {THREE}}  
'{def FOUR {SUCC {THREE}}}  -> {def FOUR {SUCC {THREE}}}    '{DECIM {FOUR}}  -> {DECIM {FOUR}}
'{def FIVE {SUCC {FOUR}}}   -> {def FIVE {SUCC {FOUR}}}    '{DECIM {FIVE}}  -> {DECIM {FIVE}}  
'{def SIX {SUCC {FIVE}}}    -> {def SIX {SUCC {FIVE}}}     '{DECIM {SIX}}   -> {DECIM {SIX}}
'{def SEVEN {SUCC {SIX}}}   -> {def SEVEN {SUCC {SIX}}}   '{DECIM {SEVEN}} -> {DECIM {SEVEN}}  
'{def EIGHT {SUCC {SEVEN}}} -> {def EIGHT {SUCC {SEVEN}}}   '{DECIM {EIGHT}} -> {DECIM {EIGHT}}
'{def NINE {SUCC {EIGHT}}}  -> {def NINE {SUCC {EIGHT}}}    '{DECIM {NINE}}  -> {DECIM {NINE}}  
'{def TEN {SUCC {NINE}}}    -> {def TEN {SUCC {NINE}}}     '{DECIM {TEN}}   -> {DECIM {TEN}}
}

_p and the PREDecessor operator

{pre
'{def PRED {lambda {:n} {{{NIL? :n} {PAIR NIL {RIGHT :n}}}}}}
-> {def PRED {lambda {:n} {{{NIL? :n} {PAIR NIL {RIGHT :n}}}}}}

'{DECIM {PRED {THREE}}} 
-> {DECIM {PRED {THREE}}}
'{DECIM {PRED {TWO}}}   
-> {DECIM {PRED {TWO}}}
'{DECIM {PRED {ONE}}}   
-> {DECIM {PRED {ONE}}}
'{DECIM {PRED {ZERO}}}  
-> {DECIM {PRED {ZERO}}} // the predecessor of ZERO is ZERO
}

_p On these two fundamental operators we build the arithmetic operators, [ADD, SUB, MUL, POW], as recursive processes

{pre
'{def ADD {lambda {:a :b}
  {{{NIL? :b}
   {PAIR {lambda {:a :b} :a}
         {lambda {:a :b} {ADD {SUCC :a} {PRED :b}}} }} :a :b}}} 
-> {def ADD
 {lambda {:a :b}
  {{{NIL? :b}
   {PAIR {lambda {:a :b} :a}
         {lambda {:a :b} {ADD {SUCC :a} {PRED :b}}}
   }} :a :b}}}

'{def SUB {lambda {:a :b}
  {{{NIL? :b}
   {PAIR {lambda {:a :b} :a}
         {lambda {:a :b} {SUB {PRED :a} {PRED :b}}} }} :a :b}}} 
-> {def SUB
 {lambda {:a :b}
  {{{NIL? :b}
   {PAIR {lambda {:a :b} :a}
         {lambda {:a :b} {SUB {PRED :a} {PRED :b}}}
   }} :a :b}}}

'{def MUL
 {def MUL.rec {lambda {:a :b :c}
   {{{NIL? :b}
    {PAIR {lambda {:a :b :c} :a}
          {lambda {:a :b :c} {MUL.rec {ADD :a :c} {PRED :b} :c}} }} :a :b :c}}}
 {lambda {:a :b} {MUL.rec :a {PRED :b} :a}}} 
-> {def MUL
 {def MUL.rec
  {lambda {:a :b :c}
   {{{NIL? :b}
    {PAIR
     {lambda {:a :b :c} :a}
     {lambda {:a :b :c} {MUL.rec {ADD :a :c} {PRED :b} :c}}
    }} :a :b :c}}}
 {lambda {:a :b} {MUL.rec :a {PRED :b} :a}}}

'{def POW
 {def POW.rec {lambda {:a :b}
   {{{NIL? :b}
    {PAIR {lambda {:a :b} :a}
          {lambda {:a :b} {POW.rec {ADD :a :a} {PRED :b}}} }} :a :b}}}
 {lambda {:a :b} {POW.rec :a {PRED :b}}}} 
-> {def POW
 {def POW.rec
  {lambda {:a :b}
   {{{NIL? :b}
    {PAIR
     {lambda {:a :b} :a}
          {lambda {:a :b} {POW.rec {ADD :a :a} {PRED :b}}}
    }} :a :b}}}
 {lambda {:a :b} {POW.rec :a {PRED :b}}}}

'{DECIM {ADD {TWO} {THREE}}} 
-> 5
'{DECIM {SUB {THREE} {TWO}}} 
-> 1
'{DECIM {MUL {TWO} {THREE}}} 
-> 6
'{DECIM {POW {TWO} {THREE}}} 
-> 8
}

_p To define the {b DIV, MOD} operators we use the Euclid algorithm {b a = b*q+r}

{pre
'{def EUCLID
 {def EUCLID.r {lambda {:a :b :q :r}
   {{{NIL? {SUB {MUL :b :q} :a}}
    {PAIR {lambda {:a :b :q :r} {EUCLID.r :a :b {SUCC :q} {SUB :a {MUL :b :q}}}}
          {lambda {:a :b :q :r} {PAIR {PRED :q} :r} } }} :a :b :q :r}}}
 {lambda {:a :b}
  {EUCLID.r :a :b {ZERO} :b}}} 
-> {def EUCLID
 {def EUCLID.r
  {lambda {:a :b :q :r}
    {{{NIL? {SUB {MUL :b :q} :a}}
       {PAIR
        {lambda {:a :b :q :r}
           {EUCLID.r :a :b {SUCC :q} {SUB :a {MUL :b :q}}}}
        {lambda {:a :b :q :r} {PAIR {PRED :q} :r} }  
     }} :a :b :q :r}}}
 {lambda {:a :b} {EUCLID.r :a :b {ZERO} :b}}}

'{def DIV {lambda {:a :b} {LEFT {EUCLID :a :b}}}}  
-> {def DIV {lambda {:a :b} {LEFT {EUCLID :a :b}}}}
'{def MOD {lambda {:a :b} {RIGHT {EUCLID :a :b}}}} 
-> {def MOD {lambda {:a :b} {RIGHT {EUCLID :a :b}}}}

'{DECIM {DIV {FIVE} {TWO}}} 
-> 2
'{DECIM {MOD {FIVE} {TWO}}} 
-> 1
'{DECIM {DIV {SIX} {TWO}}}  
-> 3
'{DECIM {MOD {SIX} {TWO}}}  
-> 0
}

_p Computing the factorial function {b n! = 1*2*3* ... *n = n*(n-1)!} is straightforward

{pre
'{def FAC {lambda {:n}
  {{{NIL? :n}
   {PAIR {lambda {:n} {ONE}}
         {lambda {:n} {MUL :n {FAC {PRED :n}}}} }} :n}}} 
-> {def FAC
 {lambda {:n}
  {{{NIL? :n}
   {PAIR {lambda {:n} {ONE}}
         {lambda {:n} {MUL :n {FAC {PRED :n}}}}
   }} :n}}}

'{DECIM {FAC {SIX}}} 
-> 720
}

_p But the implementation of numbers as lists and operators as recursive processes has severe limits, computing becomes very very slow and long lists may exceed the stack capacity. In the real world numbers must be implemented differently. More later ...

_p Let's define two useful functions, {b MAP} and {b SERIE}

{prewrap
'{def MAP
 {def MAP.r {lambda {:f :l :acc}
   {{{NIL? :l}
    {PAIR {lambda {:f :l :acc} :acc}
          {lambda {:f :l :acc} 
                     {MAP.r :f {RIGHT :l} {PAIR {:f {LEFT :l}} :acc}}} }} :f :l :acc}}}
 {lambda {:f :l} {MAP.r :f :l NIL}}} 
-> {def MAP
 {def MAP.r
  {lambda {:f :l :acc}
   {{{NIL? :l}
    {PAIR
     {lambda {:f :l :acc} :acc}
      {lambda {:f :l :acc} 
      {MAP.r :f {RIGHT :l} {PAIR {:f {LEFT :l}} :acc}}}}} 
   :f :l :acc}}}
 {lambda {:f :l} {MAP.r :f :l NIL}}}

'{def SERIE
 {def SERIE.r {lambda {:a :b :l}
   {{{NIL? {SUB :b :a}}
    {PAIR {lambda {:a :b :l} {PAIR :b :l}}
          {lambda {:a :b :l} {SERIE.r {SUCC :a} :b {PAIR :a :l}}} }} :a :b :l}}}
 {lambda {:a} {SERIE.r {ONE} :a NIL}}} 
-> {def SERIE
 {def SERIE.r
  {lambda {:a :b :l}
   {{{NIL? {SUB :b :a}}
    {PAIR {lambda {:a :b :l} {PAIR :b :l}}
          {lambda {:a :b :l} {SERIE.r {SUCC :a} :b {PAIR :a :l}}}}} :a :b :l}}}
 {lambda {:a} {SERIE.r {ONE} :a NIL}}}

'{LIST.DISP {MAP DECIM {SERIE {TEN}}}}
-> 1 2 3 4 5 6 7 8 9 10
'{LIST.DISP {MAP {lambda {:n} {DECIM {POW {TWO} :n}}} {SERIE {TEN}}}} 
-> 2 4 8 16 32 64 128 256 512 1024
}

_p As a last example this is a doubly recursive function, HANOI

{pre
'{def HANOI
 {lambda {:n :from :to :via}
  {{{NIL? :n}
   {PAIR {lambda {:n :from :to :via} }
         {lambda {:n :from :to :via}
            {HANOI {PRED :n} :from :via :to}
            {br} move disc from :from to :to 
            {HANOI {PRED :n} :via :to :from} }}}
   :n :from :to :via}}}
-> {def HANOI
 {lambda {:n :from :to :via}
  {{{NIL? :n}
   {PAIR {lambda {:n :from :to :via} }
         {lambda {:n :from :to :via}
            {HANOI {PRED :n} :from :via :to}
            {br} move disc from :from to :to 
            {HANOI {PRED :n} :via :to :from} }}}
   :n :from :to :via}}}

'{HANOI {THREE} A B C} ->
{HANOI {THREE} A B C}
}

_p At this point '{lambda talk} is still supposed to be reduced to a couple of special forms [{b lambda, def}] working on {b words}, an empty dictionary and this set of user defined functions

{pre {@ style="white-space:pre-wrap"}
[ HI, AFFIRMATION, PAIR, LEFT, RIGHT, ♥♠, FRUITS, NIL, NIL?, LIST.DISP, Y, ALMOST, LIST.REVERSE, LIST.APPEND, LIST.LENGTH, DECIM, ZERO, ONE, TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT, NINE, TEN, SUCC, PRED, ADD, SUB, MUL, POW, EUCLID, DIV, MOD, FAC, MAP, SERIE, HANOI ]
}

_p Theoretically it's endless, practically not. It's time to enter the real life!

_h2 6. a dwarf on the shoulders of giants

{center 
{img {@ src="http://lambdaway.free.fr/workshop/data/brussels/browsers_icons.jpg" height="100px"}}
{img {@ src="http://lambdaway.free.fr/workshop/data/brussels/braces.png" height="100px"}}
}

_p '{lambda talk} is not lost in an empty space and can take benefit of modern web browsers it stays on. Thanks to their powerful functionalities - HTML/CSS/SVG parsers, the DOM, Javascript - we can build superstructures making coding easier and computing efficient.

_h3 6.1. special forms

_p In its final state '{lambda talk} comes with 9 special forms, [{b lambda, def, if, quote|', let, macros, script, style, require}]

{pre 
1: '{lambda {args} body}                -> anonymous function
2: '{def name expression}               -> add a name to the dictionary
3: '{quote expression} or ''{expression} -> unevaluated expression
4: '{if bool then one else two}         -> standard control structure
5: '{let { {arg val} ...} body}         -> '{{lambda {args} body} vals}
6: '{macro regexp to talk exp}        -> add syntaxic sugar
7: '{script JS expressions}             -> add JS scripts to your page
8: '{style CSS expressions}             -> edit CSS rules of your page
9: '{require page_1 page_2 ...}         -> include code from other wiki pages 
}

_h3 6.2. primitives

_p Currently '{lambda talk} provides an extendable set of more than 150 built-in primitives

{prewrap
{b STRINGS}
equal?, empty?, chars, charAt, substring, length, first, rest, last, nth, replace, serie, map, reduce, 
{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, 
{b ARRAYS}
#.new, #.disp, #.array?, #.null?, #.empty?, #.in?, #.length, #.get, #.first, #.last, #.rest, #.slice, #.concat, #.split, #.join, 
#.set!, #.addlast!, #.push!, #.sublast!, #.pop!, #.addfirst!, #.unshift!, #.subfirst!, #.shift!, #.reverse!, #.sort!, 
{b PAIRS, LISTS}
pair, cons, pair?, nil?, left, list.first, car, right, list.rest, cdr, pair.disp, list.new, list.disp, 
{b HTML/CSS}
@, 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, sup, sub, del, code, img, pre, prewrap, textarea, audio, video, source, select, option, object, canvas, 
{b SVG}
svg, line, rect, circle, ellipse, polygon, polyline, path, text, g, mpath, use, textPath, pattern, image, clipPath, defs, animate, set, animateMotion, animateTransform, title, desc, 
{b MISC}
lib, input, iframe, hide, turtle, drag, localStorage.display, localStorage.removeItem, localStorage.getItem, localStorage.clear, 
}

_h3 6.3. applications

_p Four examples are now given to illustrate how these "superstructures" make '{lambda talk} a useful language.

_h4 6.3.1. big numbers

_p We have seen in the previous section that computing the factorial of a number beyond 7 was an inaccessible dream with the minimal implementation based on words, applications and abstractions. With the JS numbers and their associated operators the dream becomes reality!

{pre
'{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 50}  
-> {fac 50}
'{fac 171} 
-> Infinity
}

_p But JS numbers are limited in precision and we can see that '{fac 50} returns a float number limited to 15 digits and not the exact value. Calling an appropriate library stored in the wiki, {b [[lib_BN]]}, written by a smart coder, xxx, we can overcome the limitations of JavaScript numbers and build a '{lambda talk} code computing the exact value of the factorial of big numbers in a few milliseconds.

{{hide} {require lambdatalk::lib_BN}}

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

'{bigfac {BN.new 50}} 
-> 30414093201713378043612608166064768844377641568960512000000000000

'{bigfac {BN.new 500}} 
-> 1220136825991110068701238785423046926253574342803192842192413588385845373153881997605496447502203281863013616477148203584163378722078177200480785205159329285477907571939330603772960859086270429174547882424912726344305670173270769461062802310452644218878789465754777149863494367781037644274033827365397471386477878495438489595537537990423241061271326984327745715546309977202781014561081188373709531016356324432987029563896628911658974769572087926928871281780070265174507768410719624390394322536422605234945850129918571501248706961568141625359056693423813008856249246891564126775654481886506593847951775360894005745238940335798476363944905313062323749066445048824665075946735862074637925184200459369692981022263971952597190945217823331756934581508552332820762820023402626907898342451712006207714640979456116127629145951237229913340169552363850942885592018727433795173014586357570828355780158735432768888680120399882384702151467605445407663535984174430480128938313896881639487469658817504506926365338175055478128640000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
}

_h4 6.3.2. de casteljau algorithm

_p A Bézier curve {ref 16} is defined by a set of control points, {b [p0 p1  ... pn]}. The de Casteljau’s algorithm {ref 17} takes the control points and finds the midpoints along each line, then joins these midpoints. After that, it takes the midpoints along the newly drawn lines and finds the midpoints again, then draws a line connecting these. By doing this until we are down to only one point, we can approximate the Bézier curve. This is a schema of the de Casteljau algorithm for a cubic curve controled by 4 points {b [p0 p1 p2 p3]} and leading to the point at t=1/2:

{pre
.     [{b p0}  p1  p2  {b p3}]     the control polygon
        [{b q0}  q1  {b q2}]       q{sub i} = (p{sub i}+p{sub i+1})/2  i in [0,1,2]
          [{b r0}  {b r1}]         r{sub i} = (q{sub i}+q{sub i+1})/2  i in [0,1]
            [{b s0}]           s{sub 1} = (r{sub i}+r{sub i+1})/2  i in [0]
}

_p This process is recursively done on the left and right control polygons {b [p0 q0 r0 s0]} and {b [s0 r1 q2 p3]}. The depth of recursion is controlled either by a "flatness/smoothness" condition or by a number, the choice taken in this page. The result is a {b binary tree} of polygon controls translated in a sequence of points, {b x0 y0 x1 y1 .... xp yp}, expected by the SVG polyline's {b points:"..."} attribute.

_p The main function is {b '{CASTEL.blossom pol n}} which returns a level {b n} binary tree of polygon controls, {b [[x0,y0],...,[xp,yp]]}. The curve is defined in the interval {b [0,1]}. The second {b '{CASTEL.stretch pol t0 t1}} function returns a new equivalent control polygon stretched to any other interval {b [t0,t1]}. In order to display the curve, we define a third {b '{svg.points pol}} function replacing the 3 characters {b "[",",","]"} by spaces in the array expression of the control polygon and returning a sequence of SVG formated points {b x0 y0 x1 y1 ... xp yp}.

{pre 
'{def CASTEL.interpol {lambda {:p0 :p1 :t}
  {#.new {+ {* {#.get :p0 0} {- 1 :t}} {* {#.get :p1 0} :t}}
         {+ {* {#.get :p0 1} {- 1 :t}} {* {#.get :p1 1} :t}} } }} 
-> {def CASTEL.interpol {lambda {:p0 :p1 :t}
  {#.new {+ {* {#.get :p0 0} {- 1 :t}}
            {* {#.get :p1 0} :t}}
         {+ {* {#.get :p0 1} {- 1 :t}}
            {* {#.get :p1 1} :t}} } }}

'{def CASTEL.sub {lambda {:arr :acc :t}
  {if {< {#.length :arr} 2}
   then :acc
   else {CASTEL.sub {#.rest :arr} {#.addlast! :acc
        {CASTEL.interpol {#.get :arr 0} {#.get :arr 1} :t} } :t} }}} 
-> {def CASTEL.sub {lambda {:arr :acc :t}
  {if {< {#.length :arr} 2}
   then :acc
   else {CASTEL.sub
         {#.rest :arr} 
         {#.addlast! :acc
         {CASTEL.interpol {#.get :arr 0}
                          {#.get :arr 1} :t} } :t} }}}

'{def CASTEL.split {lambda {:arr :acc :t :lr}
  {if {< {#.length :arr} 1}
   then :acc
   else {CASTEL.split
         {CASTEL.sub :arr {#.new} :t}
         {if :lr
          then {#.addlast! :acc {#.first :arr}}
          else {#.addfirst! :acc {#.last :arr}} } :t :lr} }}} 
-> {def CASTEL.split {lambda {:arr :acc :t :lr}
  {if {< {#.length :arr} 1}
   then :acc
   else {CASTEL.split
         {CASTEL.sub :arr {#.new} :t}
         {if :lr
          then {#.addlast! :acc {#.first :arr}}
          else {#.addfirst! :acc {#.last :arr}} } :t :lr} }}}

'{def CASTEL.stretch {lambda {:arr :t0 :t1}
  {CASTEL.split
   {CASTEL.split :arr {#.new} :t0 right} {#.new} :t1 left}}}
-> {def CASTEL.stretch {lambda {:arr :t0 :t1}
  {CASTEL.split
   {CASTEL.split :arr {#.new} :t0 right} {#.new} :t1 left}}}

'{def CASTEL.blossom {lambda {:arr :n}
  {if {< :n 1}
   then :arr
   else {array 
    {CASTEL.blossom {CASTEL.split :arr {array} 0.5 true} {- :n 1}}
    {CASTEL.blossom {CASTEL.split :arr {array} 0.5 false} {- :n 1}} }}}}
-> {def CASTEL.blossom {lambda {:arr :n}
  {if {< :n 1}
   then :arr
   else {#.new {CASTEL.blossom {CASTEL.split :arr {#.new} 0.5 left} {- :n 1}}
               {CASTEL.blossom {CASTEL.split :arr {#.new} 0.5 right} {- :n 1}} }}}}

'{def svg.points {lambda {:arr} 
 {replace (\[|\]|,) by space in {#.disp :arr}}}} -> {def svg.points {lambda {:arr}
  {replace (\[|\]|,) by space in {#.disp :arr}}}}

'{def svg.stroke {lambda {:c :e}
 stroke=":c" stroke-width=":e" fill="transparent"}} -> {def svg.stroke {lambda {:c :e} stroke=":c" stroke-width=":e" fill="transparent"}}

'{def svg.dot {lambda {:p}
  {circle {@ cx="{#.first :p}" cy="{#.last :p}" r="5"
  {svg.stroke #000 3}}} }} -> {def svg.dot {lambda {:p}
  {circle {@ cx="{#.first :p}" cy="{#.last :p}" r="5" {svg.stroke #000 3}}} }}
}

_p Using these functions, we can feed the SVG polyline's points:"..." attributes

{pre
{def p0 {#.new 50 60}} -> {p0}
{def p1 {#.new 100 200}} -> {p1}
{def p2 {#.new 300 200}} -> {p2}
{def p3 {#.new 200 280}} -> {p3}
}

{pre °°
{svg {@ width="320" height="320"}
{polyline {@ points="{svg.points {CASTEL.blossom 
 {#.new {p0} {p1} {p2} {p3}} 4}}" {svg.stroke #f00 12} }}
{polyline {@ points="{svg.points {CASTEL.blossom
 {#.new {p0} {p1} {p2} {p3}} 0}}" {svg.stroke #888 1} }}
{polyline {@ points="{svg.points {CASTEL.blossom {CASTEL.stretch
 {#.new {p0} {p1} {p2} {p3}} 0.25 0.85} 3}}" {svg.stroke #ff0 5}}}
{polyline {@ points="{svg.points {CASTEL.blossom {CASTEL.stretch
 {#.new {p0} {p1} {p2} {p3}}  -0.1 1.1} 4}}" {svg.stroke #888 2}}}
{polyline {@ points="{svg.points {CASTEL.blossom {CASTEL.stretch
 {#.new {p1} {p0} {p2} {p3}}  -0.1 1.1} 4}}" {svg.stroke #888 2}}}
{polyline {@ points="{svg.points {CASTEL.blossom {CASTEL.stretch
 {#.new {p0} {p1} {p3} {p2}}  -0.1 1.1} 4}}" {svg.stroke #888 2}}}
{polyline {@ points="{svg.points {CASTEL.blossom {CASTEL.stretch
 {#.new {p0} {p2} {p1} {p3}}  -0.1 1.1} 4}}" {svg.stroke #888 2}}}

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

{center {svg {@ width="320" height="320"}
{polyline {@ points="{svg.points {CASTEL.blossom {#.new {p0} {p1} {p2} {p3}} 4}}" {svg.stroke #f00 12} }}
{polyline {@ points="{svg.points {CASTEL.blossom {#.new {p0} {p1} {p2} {p3}} 0}}" {svg.stroke #888 1} }}
{polyline {@ points="{svg.points {CASTEL.blossom {CASTEL.stretch {#.new {p0} {p1} {p2} {p3}} 0.25 0.85} 3}}" {svg.stroke #ff0 5}}}
{polyline {@ points="{svg.points {CASTEL.blossom {CASTEL.stretch {#.new {p0} {p1} {p2} {p3}}  -0.1 1.1} 4}}" {svg.stroke #888 2}}}
{polyline {@ points="{svg.points {CASTEL.blossom {CASTEL.stretch {#.new {p1} {p0} {p2} {p3}}  -0.1 1.1} 4}}" {svg.stroke #888 2}}}
{polyline {@ points="{svg.points {CASTEL.blossom {CASTEL.stretch {#.new {p0} {p1} {p3} {p2}}  -0.1 1.1} 4}}" {svg.stroke #888 2}}}
{polyline {@ points="{svg.points {CASTEL.blossom {CASTEL.stretch {#.new {p0} {p2} {p1} {p3}}  -0.1 1.1} 4}}" {svg.stroke #888 2}}}
{svg.dot {p0}} {svg.dot {p1}} {svg.dot {p2}} {svg.dot {p3}}
}}

_h4 6.3.3. Lindenmeier L-system

_p With the browser's SVG functions and the '{lambda talk} primitive turtle, we can define a tree using the Lindenmeier, L-system {ref 18}, and call it in a SVG container. We define a function {b tree} depending on 5 parameters which will gather the {b points} attribute of a polyline in a SVG container. In the first picture we play with {b :a :b} equal to 45° and increase initial sizes to increase complexity, {b :k :e} being constant. The red tree defines the generative pattern. The green, blue and grey trees are generated by the recursive application of this pattern at the end of the branchs for different initial sizes. In the second picture the angles {b :a :b} are freely choosen to distord the trees.

{pre  
'{def tree 
 {lambda {:e :s :k :a :b}
  {if {< :s :e}
   then T-30 M:s T120 M:s T120 M:s T150
   else M:s T:a
        {tree :e {* :k :s} :k :a :b}
        T-{+ :a :b}
        {tree :e {* :k :s} :k :a :b} 
        T:b M-:s }}} 
-> {def tree 
 {lambda {:e :s :k :a :b}
  {if {< :s :e}
   then T-30 M:s T120 M:s T120 M:s T150
   else M:s T:a
        {tree :e {* :k :s} :k :a :b}
        T-{+ :a :b}
        {tree :e {* :k :s} :k :a :b}
        T:b M-:s    }}}
}

{center {table {@ style="width:100%"} {tr
 {td {pre
'{tree 25 50 {/ 2 3} 45 45}  -> grey tree
'{tree 25 100 {/ 2 3} 45 45} -> blue tree 
'{tree 25 150 {/ 2 3} 45 45} -> green tree
'{tree 25 200 {/ 2 3} 45 45} -> red tree}}
 {td {pre
'{tree 5 200 {/ 2 3} 40 4}  -> red tree
'{tree 5 180 {/ 2 3} 40 10} -> green tree
'{tree 5 180 {/ 2 3} 4 20}  -> blue tree
'{tree 5 150 {/ 2 3} 4 50}  -> black tree
}}}}}

{center
{img {@ src="http://lambdaway.free.fr/workshop/data/turtle_tree_1.jpg" width="49%"}}
{img {@ src="http://lambdaway.free.fr/workshop/data/turtle_tree_2.jpg" width="49%"}}
}

°°°
{svg 
 {@ width="600px" height="600px" 
    style="border:1px solid #888; margin-left:-12px"}

{polyline 
  {@ points="{turtle 300 590 180
             {tree 25 200 {/ 2 3} 45 45}}"
     fill="transparent" stroke="grey" stroke-width="1"}}

{polyline 
  {@ points="{turtle 300 590 180
             {tree 25 150 {/ 2 3} 45 45}}"
     fill="transparent" stroke="blue" stroke-width="2"}}

{polyline 
  {@ points="{turtle 300 590 180
             {tree 25 100 {/ 2 3} 45 45}}"
     fill="transparent" stroke="green" stroke-width="3"}}

{polyline 
  {@ points="{turtle 300 590 180
             {tree 25 50 {/ 2 3} 45 45}}"
     fill="transparent" stroke="red" stroke-width="4"}}

}
°°°

°°°
{svg 
 {@ width="600px" height="600px" 
    style="border:1px solid #888; margin-left:-12px;"}

{polyline 
  {@ points="{turtle 340 590 180
             {tree 5 200 {/ 2 3} 40 4}}"
     fill="transparent" stroke="red" stroke-width="1"}}

{polyline 
  {@ points="{turtle 340 590 180
             {tree 5 180 {/ 2 3} 40 10}}"
     fill="transparent" stroke="green" stroke-width="1"}}

{polyline 
  {@ points="{turtle 340 590 180
             {tree 5 180 {/ 2 3} 4 20}}"
     fill="transparent" stroke="blue" stroke-width="1"}}

{polyline 
  {@ points="{turtle 340 590 180 
             {tree 5 150 {/ 2 3} 4 50}}"
     fill="transparent" stroke="black" stroke-width="1"}}
}
°°°

_h4 6.3.4. HTML/CSS

_p As a last example of application, with HTML/CSS built-in primitives we have tools for building rich documents intermixing pure text and code and produce PDF files. Being a dialect of lambda calculus doesn't prevent '{lambda talk} to be useful.

_p The {b current wiki page} was built on a handfull of small '{lambda talk} user functions and CSS rules. '{lambda talk} keeps writing rich structured and dynamic web documents {b Small & Simple}. First you, the author, insert your ideas, what you think, as it comes to you. Yes it's not exactly WYSIWYG, {i you can't select words with the mouse and click on some button {b [B]} to boldify them}. You have to write code in a text editor frame and see the result in a viewer frame. But it's in real time and you code at a minimal level, with a handful of simple textual commands closely related to standard HTML/CSS. Later you will be able to enrich the document by yourself or helped by a cute web designer or a smart coder.

_p This {b collaborative creation} is made possible because the author, the web designer and the coder share the {b same consistent code}. The coder will define on demand new functions to make things easier, closer to your needs and web design requirements. And so your documents will always be sustainable, easy to edit, improve and publish, from everywhere, on every systems and every devices, free from any proprietary or/and obfuscated tools.

_p And it's exactly how the current wiki page was created and the (2Mb) ACM formated [[PDF paper|http://b2b3.free.fr/lambdatalk/data/fabric_new_20180902.pdf]] directly generated from the browser.

_h2 conclusion

_p The heart of '{lambda talk} is built on a 30kb PHP file and a 60kb JS file free of any external dependancies. And more, the single function, {b talk}, contained in the JS file can be used in any other wiki. The code is small and can be read, edited and improved by any coder, it's just plain Javascript. '{lambda talk} is a free software under the {b GNU GPL} licence, and its {b 25kb} archive is easy to [[download & install|?view=talk]] on any web host provider running PHP. Or can be freely tested in the website [[lambdatalk|http://b2b3.free.fr/lambdatalk/]].

_p It is said that John McCarthy's lamented the W3C's choice of SGML as the basis for HTML : « {i An environment where the markup, styling and scripting is all s-expression based would be nice.} »

_p '{lambda talk} could be an answer, small and simple.

_p {i Alain Marty -- last update 2018/09/02}

_h2 references
{pre 
{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} Markdown Syntax: [[https://help.github.com/articles/basic-writing-and-formatting-syntax/|https://help.github.com/articles/basic-writing-and-formatting-syntax/]]
{back_ref 4} [[http://epsilonwiki.free.fr/lambdaway/?view=curl|http://epsilonwiki.free.fr/lambdaway/?view=curl]]
{back_ref 5} [[http://epsilonwiki.free.fr/lambdaway/?view=LML|http://epsilonwiki.free.fr/lambdaway/?view=LML]]
{back_ref 6} [[http://docs.racket-lang.org/scribble/|http://docs.racket-lang.org/scribble/]]
{back_ref 7} [[http://epsilonwiki.free.fr/lambdaway/?view=SXML|http://epsilonwiki.free.fr/lambdaway/?view=SXML]] 
{back_ref 8} [[http://people.cs.aau.dk/~normark/laml/papers/web-programming-laml.pdf|http://people.cs.aau.dk/~normark/laml/papers/web-programming-laml.pdf]]
{back_ref 9} [[http://docs.racket-lang.org/pollen|http://docs.racket-lang.org/pollen/]]
{back_ref 10} 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 11} S. C. Kleene, “Representation of events in nerve nets and finite automata”, in: C. Shannon and J. McCarthy, (eds.) Automata Studies, Princeton University Press, NJ, 1956, 3–41.
{back_ref 12} Regular Expressions: [[http://blog.stevenlevithan.com/archives/reverse-recursive-pattern|http://blog.stevenlevithan.com/archives/reverse-recursive-pattern]]
{back_ref 13} Turing machines implemented in JavaScript  [[http://www.turing.org.uk/book/update/tmjavar.html|http://www.turing.org.uk/book/update/tmjavar.html]]
{back_ref 14} 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 15} SCHEME: Arold Abelson and Gerald J. Sussman. 1996. Structure and Interpretation of Computer Programs (2nd ed.). MIT Press, Cambridge, MA, USA.
{back_ref 16} Bézier curve: [[href="https://www.scratchapixel.com/lessons/advanced-rendering/bezier-curve-rendering-utah-teapot"|href="https://www.scratchapixel.com/lessons/advanced-rendering/bezier-curve-rendering-utah-teapot"]]
{back_ref 17} de Casteljau: [[https://en.wikipedia.org/wiki/De_Casteljau%27s_algorithm|https://en.wikipedia.org/wiki/De_Casteljau%27s_algorithm]]
{back_ref 18} Lindenmeier L-system: [[https://en.wikipedia.org/wiki/L-system|https://en.wikipedia.org/wiki/L-system]]
{back_ref 19} MathML 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 20} Rosetta: [[https://www.rosettacode.org/wiki/Hello_world/Text|https://www.rosettacode.org/wiki/Hello_world/Text]]
}

{{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{br}
 Villeneuve de la Raho, France{br}
 marty•alain © free•fr{br}
 [[http://b2b3.free.fr/lambdatalk/|http://b2b3.free.fr/lambdatalk/]]
}}}

{def ref {lambda {:i}
  {a {@ name="_:i" href="#:i"} [:i]} }}
{def back_ref {lambda {:i}
  {b {a {@ name=":i" href="#_:i"}[:i]}} }}
{def space {span {@ style="padding:0 10pt"}}}

}

{style 
body { background:#fff; }

.menu { display:block; opacity:0.5; border:0}

#frame {
 background:#fff; width:95%; border:0; margin:0; padding:0;
}

#content {
 font:normal 1.0em Times Roman; 
/* font:normal 9pt Times Roman; */
 width:750px; /* 650px 750px 100% */
 margin:auto;
 padding:0;
 border:0;
 box-shadow:0 0 0;
}
p {
 margin:10px 0;
 text-indent:0px;
}
h2 {
 font:bold 2.0em Times Roman; 
/*font:bold 12pt Times Roman;*/
 text-transform: uppercase; color:#000;
} 
h3 {
 font:bold 1.5em Times Roman; color:#000; 
/*font:italic 12pt Times Roman; color:#000;*/
} 
h4, h5, h6 { 
 font:italic 1.0em Times Roman; color:#000; 
/*font:italic 11pt Times Roman; color:#000;*/
} 
pre {
 word-wrap: break-word; 
 white-space:pre-wrap; 
 background:#eee; color:#000;
 font:normal 1.0em courier new;
 border-top:0px solid #ccc;
 border-bottom:0px solid #ccc;
 margin:2px 0; 
}

}