workshop

user:anonymous

{MENU}
{{hide} {def DISPLAY block}}

{SPLASH_SCREEN}
{hr}
{center --- {{note.call introduction} START} ---}

{{note.content introduction}
_h2 introduction

_p Computer languages are generally introduced from a long enumeration of their syntaxic rules, several objects and their associated functions - strings, numbers, arrays, ... - and via numerous examples and applications. We can learn how to resolve problems, it's useful, but not to understand the way languages have been conceived. There remains a great deal of mystery which can only be lifted by those who have had access to the {b making of}.

_p So, we are going to create a language from the most elementary bricks. A handful of rules, no grey area, no magical functions, no abstract concepts. Nothing but words to assemble/compose, which could {i theoretically} be manipulated by hand, without any computer. {i Practically}, we need a pre-existing environment to do so and we will choose the '{lambda way} project, a {b workshop} built on a {b wiki}, '{lambda tank}, coming with a true functional programming {b language}, '{lambda talk}.

_h6 But why?
_p « {i There are hundred of wiki engines and hundred of languages! Why not Java, Python, C or whateverelse existing language with a true IDE? Why yet another wiki and another language nobody will ever want to use?} »

_p Let's speak about that!

_h5 1. a wiki is a text editor on the web
_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.

_h5 2. the Markdown syntax is not a language
_p 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.

_h5 3. the quest of a language
_p 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} ... 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. Hence the '{lambda way} project!

_h5 4. the '{lambda way} project
_p Built on two engines, '{lambda tank}, a tiny {b wiki} easy to install as a thin overlay on top of any web browser, and '{lambda talk}, a small {b functional language} unifying authoring, styling and scripting in a single and coherent prefixed notation, the '{lambda way} project proposes an answer making easy the {b collaborative creation} of rich documents by authors, web designers and coders.
_p '{lambda tank} gives everyone the same small and local IDE to write code in an editor window, control the result in real time in a view window, the wiki page, save it in the distant server and make it immediately visible on the web:

{img {@ src="data/wiki_session.png" width="100%"}}

{center The {b KISS} attitude: {b K}eep {b I}t {b S}imple & {b S}mall}

_h5 5. content of this presentation

_p So, upon a solid {b infrastructure} made of a reduced set of substitution rules, we will add progressively some {b data & control structures}, give an idea of the {b implementation} and, taking benefit of the powerful functionalities of the modern web browsers, build {b superstructures} leading to useful {b applications}, making '{lambda talk} a true programming language on the web.

{center --- {{note.call foundations} foundations} ---}
}

{{note.content foundations}

_img data/brussels/mies_pav.jpg

_h2 1. foundations

{center {b « Où l'on montre comment une vieille théorie absconse{br}datant des années 30 peut aider à construire{br}un langage moderne et cohérent pour le web ! »}}

_p Imagine a {i machine} understanding this question

{pre
{i replace}: "x" and "y"
     {i in}: "« x brave new y! »"
     {i by}: "Hello" and "World"
}

_p and answering

{pre
« Hello brave new World! »
}

_p '{lambda talk} is such a {i replacement machine} where the question is formulated using a slightly different syntax '{{lambda {args} body} values}

{pre
'{{lambda {x y}                                // replace
          « x brave new y! »}                 // in
          Hello World}                        // by

-> {{lambda {x y} « x brave new y! »} Hello World}
}
   
_p This {i strange syntax} - a kind of shorthand/stenography - is freely inspired by the [[{b λ-calculus}|http://www.inf.fu-berlin.de/lehre/WS03/alpi/lambda.pdf]] created in the 1930s by {b Alonzo Church} and uses the {b LISP} S-expressions introduced by {b John McCarthy} in the 1950s.

_h5 syntax

_p At the foundation level, valid '{lambda talk} expressions are made of a reduced set of nested terms, [{b words, applications, abstractions}] and are evaluated to {b words}.

{pre {quote 
expression := 
|   word        := [^\s{}]*
|   application := {expression1 expression2}      -> words
|   abstraction := {lambda {words} expression}    -> word
}}

_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).

_h5 evaluation

_p The implementation of '{lambda talk} insures that

_ul {b words} are not evaluated,
_ul {b abstractions} are {u special forms} evaluated to words {b before} applications,
_ul {b applications} are {u nested forms} evaluated to words from inside out, from the leaves to the root.

_h5 lambdas

_p Lambdas are the heart of '{lambda talk} and have the following properties

_ul {b first class}: essentially they can be called as arguments, returned as values and created at run-time,
_ul {b no closure}: the list of arguments determines the local working environment, there is no access to any external variables, no free variables,
_ul {b no side effects}: like mathematical functions, '{lambda talk} functions are pure and free of any input/output side effects, 
_ul {b accept partial calls}: functions accept partial calls, memorizing the given values and returning a new function waiting for the rest.

_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 evaluation and display.

_h5 that's it!

_p But what can be done with so little? We can now understand that

{pre
'{{lambda {x y} « x brave new y! »} Hello World}
}

_p is an Immediately Invoked Function Expression  ({b IIFE}), 
{pre '{{lambda {args} body} values}}

_p which replaces successively in its body {b x} by {b Hello} and {b y} by {b World}

{pre
0: '{{lambda {x y} « x brave new y! »} Hello World}
1: '{{lambda {y} « Hello brave new y! »} World}
2: '{{lambda {} « Hello brave new World! »}}
}

_p until the list of arguments is empty and finally returns its body

{pre « Hello brave new World! »}

_h5 definitions

_p For convenience we add a second special form {b '{def word expression}}, first evaluating {b expression} into words then binding {b word} to these words. With this special form, evaluated {b after} the abstractions and {b before} the nested forms, we can give a {b name} to expressions, which become {b constants}, and to anonymous functions, which become {b named functions}. Names are added to a single {b dictionary} initially empty.

{pre
'{def HI Hello World}
-> {def HI Hello World}
HI, I say '{HI}
-> HI, I say {HI}
}

_p Note that writing {b HI} just displays {b HI} and we must {i bracket} the name between curly braces to get its value. Let's remember that in a standard spreadsheet writing {b PI} displays {b PI} and we must write this function call {b =PI()} to display the value, {b {PI}}.

_p Thanks to the {b def} special form the previous {b IIFE} can be split into a definition followed by one or more calls

{pre
'{def FOO {lambda {x y} « x brave new y! »}}
-> {def FOO {lambda {x y} « x brave new y! »}}

'{FOO Hello World}
-> {FOO Hello World}
'{FOO ♥ ♣}
-> {FOO ♥ ♣}
}

_p Beyond replacing words we can compose functions to build {b data structures}?

{center --- {{note.call data_structures} data structures} ---}
}

{{note.content data_structures}
_img data/brussels/operators.jpg
_h2 2. data structures

_p Lambdas can be nested, allowing convoluted expressions, for instance

{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  of a couple of words, {b Hello World}.

{center --- {note_start TRACE Fine, but how does it work?} ---}

{note_end {@ id="TRACE"}
{blockquote
_p 1) Lambdas are first evaluated, each returning a name bound to an {i anonymous} function added to the dictionary

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

_p 2) Then simple forms are evaluated from inside out

{pre
1: '{_LAMB_3 {_LAMB_2 Hello World}}
   -> '{_LAMB_3 {{lambda {x y z} {z x y}} Hello World}} // see below 
}

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

{pre
2: '{_LAMB_3 _LAMB_4}
   -> '{{lambda {z} {z _LAMB_1}} _LAMB_4}
3: '{_LAMB_4 _LAMB_1}
   -> '{{lambda {z} {z Hello World}} _LAMB_1}
4: '{_LAMB_1 Hello World}
   -> '{{lambda {x y} x} Hello World}
5: Hello 
}
}}

_h5 pairs

_p The second special form {b '{def name expression}} helps to split the two previous composed lambda expressions returning {b Hello} and {b World} from {b Hello World} into three names

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

'{LEFT {PAIR Hello World}}
-> {LEFT {PAIR Hello World}}
'{RIGHT {PAIR Hello World}}
-> {RIGHT {PAIR Hello World}}
}

_p Giving a name to {b '{PAIR Hello World}}

{pre
'{def BAR {PAIR Hello World}}
-> {def BAR {PAIR Hello World}}

'{LEFT {BAR}}
-> {LEFT {BAR}}
'{RIGHT {BAR}}
-> {RIGHT {BAR}}
}

_p enlights a binary data structure whose elements are accessed using {b LEFT} and {b RIGHT}. We can compose pairs to build more complex data structures like {b lists}.

_h5 lists

_p A list is a recursive data structure whose first element is a {b word} and the second is a {b pair} or some ending word. For instance

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

_p At this point the ending word {b NIL} can be any word characterizing the end of a list, for instance {b \, -1, '(), améliepoulain, ...}

_p The elements of {b FRUITS} can be accessed using {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}}}}}
'{LEFT {RIGHT {RIGHT {RIGHT {RIGHT {FRUITS}}}}}}
-> {LEFT {RIGHT {RIGHT {RIGHT {RIGHT {FRUITS}}}}}}
'{LEFT {RIGHT {RIGHT {RIGHT {RIGHT {RIGHT {FRUITS}}}}}}}
-> {LEFT {RIGHT {RIGHT {RIGHT {RIGHT {RIGHT {FRUITS}}}}}}}           // ooops! what is it?
}

_p Displaying in sequence the elements of a list can quickly become boring. We need something to automatize the process, something to create a {b loop}. We need a {b control structure}.

{center --- {{note.call control_structures} control structures} ---}
}

{{note.content control_structures}
_img data/brussels/infinity_time.jpg"
{center « To Iterate is Human, to Recurse, Divine » {i attributed to  L. Peter Deutsch}}

_h2 3. control structures

_p In '{lambda talk} loops are built on {b recursion}. A recursive function calls itself inside its body until some ending condition is reached. For instance, displaying {b FRUITS} is calling some function which gets its first term, '{LEFT {FRUITS}}, then calls itself on the rest of the list, '{RIGHT {FRUITS}}, until the rest is no more a list.

_p We are going to redefine the word {b NIL} as a lambda paired with a predicate function {b NIL?} returning {b LEFT} if applied on {b NIL} else {b RIGHT}.

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

'{NIL! NIL}
-> {NIL? NIL}
'{NIL? {FRUITS}}
-> {NIL? {FRUITS}}
}

{center --- {note_start NIL Fine, but how does it work?} ---}
{note_end {@ id="NIL"}
{pre

0: '{NIL? NIL}
1: '{{lambda {n} {n {lambda {x} RIGHT} LEFT}}
    {lambda {f x} x}
   }
2: '{{lambda {f x} x} {lambda {x} RIGHT} LEFT}
3: LEFT
}

_p Showing that '{NIL? {FRUITS}} is evaluated to RIGHT is left as an exercice.
}

_p We can now build a recursive function to display {b FRUITS}

{pre
'{def LIST.DISP
 {lambda {list}
  {{{NIL? list}                  // return LEFT or RIGHT
   {PAIR
    {lambda {list} }             // if LEFT do nothing
    {lambda {list} {LEFT list}   // else get element and ...
                   {LIST.DISP {RIGHT list}}}  // ... recurse
  }} list}}}                // the lambda is applied on list
-> {def LIST.DISP
 {lambda {list}
  {{{NIL? list}
    {PAIR
     {lambda {list} }
     {lambda {list} {LEFT list}
                     {LIST.DISP {RIGHT list}}}}} list}}}

'{LIST.DISP {FRUITS}} 
-> apple banana lemon grapes orange
}

{center --- {note_start REC Fine, but how does it work?} ---}

{note_end {@ id="REC"}
{blockquote

_ul 1. first evaluate special forms, lambdas and defs

{pre  
'{def LIST.DISP
 {lambda {list}
  {{{NIL? list}
   {PAIR
    {lambda {list} }
    {lambda {list} {LEFT list}
                    {LIST.DISP {RIGHT list}}} }} list}}}
-> '{def LIST.DISP
 {lambda {list}
  {{{NIL? list} {PAIR _LAMB_0 _LAMB_1} list}} }}
-> '{def LIST.DISP _LAMB_2}
-> LIST.DISP
}

_ul 2. then evaluate simple forms

{pre

'{LIST.DISP {FRUITS}}
-> LIST.DISP, alias of _LAMB_2, replaces list by FRUITS 
    in '{{{NIL? list} {PAIR _LAMB_0 _LAMB_1} list}}
-> '{{{NIL? FRUITS} {PAIR _LAMB_0 _LAMB_1} FRUITS}} 
    then evaluates this expression

1) if FRUITS is not NIL then '{NIL? FRUITS} is RIGHT 
-> '{{RIGHT {PAIR _LAMB_0 _LAMB_1}} FRUITS}

-> '{{RIGHT _LAMB_3} FRUITS} // memorize _LAMB_0 _LAMB_1
   '{RIGHT _LAMB_3} is _LAMB_1
-> '{_LAMB_1 FRUITS}
    _LAMB_1 replaces list by FRUITS 
    in '{LEFT list} '{LIST.DISP {RIGHT list}}
-> '{LEFT FRUITS} '{LIST.DISP {RIGHT FRUITS}}

-> apple '{LIST.DISP {RIGHT FRUITS}}
-> and recurse on '{RIGHT FRUITS} until FRUITS is NIL
 
2) if FRUITS is NIL then '{NIL? FRUITS} is LEFT 
-> '{{LEFT {PAIR _LAMB_0 _LAMB_1}} FRUITS}
-> '{{LEFT _LAMB_3} FRUITS} // memorize _LAMB_0 _LAMB_1
   '{LEFT _LAMB_3} is _LAMB_0
-> '{_LAMB_0 FRUITS}
    _LAMB_0 replaces list by FRUITS in empty
-> empty 
-> stop

}}}
_p So, we could define a recursive algorithm, thanks to the data structure [{b PAIR, LEFT, RIGHT}] and a "zest" of lambdas introducing some "delay" in a "from inside out" evaluation, without any "extra" {b '{IF THEN ELSE}} boolean special form. Remember that we use nothing but words, applications, abstractions and, temporarily, definitions.

_p The replacement process becomes quickly difficult to trace but remains systematic, without any shade area, any {i magic}, enlighting the deep equivalence between data and code - {b code is data and data is code} - the duality between abstraction and application, between lazyness and eagerness, between "yin" and "yang".

_h5 numbers?

_p When we want to compute the number of elements in a list we are facing a major problem: '{lambda talk} ignores numbers, {b 123} or {b 3.141592653589793} are nothing but words. Never mind, we will write numbers in an old numeral unary notation: {b 1 = |, 2 = | |, 3 = | | |, 4 = | | | |, ...}

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

'{LIST.LENGTH {FRUITS}} 
-> | | | | |  // 5 pipes
}

_p In some other pages of the '{lambda way} [[workshop|?view=start]], for instance [[NIL]], we go further, defining functions reversing and concatening lists, and more. Following {b Alonzo Church} we define the set of {b Church numbers} and their associated operators, {b NEXT, PRED, ADD, SUBTRACT, MULT, DIVIDE, MOD, POWER, GCD, ...} with which we can do some arithmetic, compute factorials, fibonaccis, and more. It's theoretically of a great interest but practically useless and out of the scope of this short introduction. We want to stay a little more at the foundation level, nothing but [{b words, applications, abstractions}].

_h3 Y-combinator is your friend

_p We are going to show that the second special form, {b '{def name expression}}, can be avoided thanks to a strange operator beloved by so many doctors in computer sciences, the {b Y-combinator}. A small {b Y-combinator} will allow us to replace the recursive definition of {b LIST.LENGTH} by an {i almost recursive} one

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

'{def ALMOST.REC
 {lambda {g l}
  {{{NIL? l}
   {PAIR {lambda {g l} }
         {lambda {g l} | {g g {RIGHT l}}} }} g l}}}
-> {def ALMOST.REC
 {lambda {g l}
  {{{NIL? l}
   {PAIR {lambda {g l} }
         {lambda {g l} | {g g {RIGHT l}}}
   }} g l}}}

'{Y ALMOST.REC {FRUITS}} 
-> | | | | |  // 5 pipes
}

_p Note that the function {b ALMOST.REC} does not contain anymore a call to its name. It's now possible to forget the names of {b Y} and {b ALMOST.REC} and create an {b IIFE}

{pre
'{{lambda {g n} {g g n}} 
  {lambda {g l}
   {{{NIL? l}
    {PAIR {lambda {g l} }
          {lambda {g l} | {g g {RIGHT l}}} }} g l}} {FRUITS}}
-> | | | | |   // 5 pipes
}

_p Finally replacing {b NIL, PAIR, RIGHT, FRUITS} by their definitions leads to an expression in a pure {b λ-calculus} style

{pre {@ style="word-wrap: break-word; white-space:pre-wrap;"}
'{{lambda {g n} {g g n}} {lambda {g l} {{{{lambda {n} {n {lambda {x} {lambda {z} {z {lambda {x y} y}}}} {lambda {z} {z {lambda {x y} x}}}}} l} {{lambda {x y z} {z x y}} {lambda {g l}} {lambda {g l} | {g g {{lambda {z} {z {lambda {x y} y}}} l}}}}} g l}} {{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}} grapes {{lambda {x y z} {z x y}} orange {lambda {f x} x}}}}}}}
-> | | | | |   // 5 pipes 
}

_p We understand now how {b data & control structures} can be built on a minimalist set of 3 rules, [{b words|application|abstraction}].

_p But how do applications and abstractions work under the hood?

{center --- {{note.call implementation} implementation} ---}
}

{{note.content implementation}
_img data/brussels/engrenages.jpg" width="100%"
{center {i 
{quote /\{([^\s{}]*)(?:[\s]*)([^{}]*)\}/g}
{br}
Do you want to solve a problem? Use Regular Expression!
{br} And now you have two problems.
{br} (Jamie Zawinski, a world class hacker)
}}
_h2 4. implementation

_p It's time to understand how applications and abstractions evaluate the input code, how the heart of '{lambda talk} is implemented. Contrary to the majority of parsers tokenizing the code's string, building an {b A}bstract {b S}yntaxic {b T}ree and recursively evaluating it, '{lambda talk} evaluates the code using {b Regular Expressions}, a language created in the 1950s by {b Stephen Cole Kleene}, a student of {b Alonzo Church}.

_h3 4.1. applications
_p {b Applications} replace nested forms {b '{first rest}} by words through a {b window} built on a {b single} Javascript one line function, {b eval_forms()}
{pre
var eval_forms = function( str ) '{
  while (str != (str = str.replace( regexp, eval_leaf ))) ;
  return str;
};
}

_p working on a {b single regular expression}
{pre
var regexp = /\'{([^\s{}]*)(?:[\s]*)([^{}]*)\}/g;
}

_p designed to catch leaves

{pre
var eval_leaf = function() '{
  var f = arguments[1] || '',
      r = arguments[2] || '';
  if (DICT.hasOwnProperty(f))
    return DICT[f].apply(null, [r]); // apply f to r
  else
    return '('+f+' '+r+')';          // don't evaluate
};
}

_p In order to illustrate the mechanism, we will suppose for a while that the language knows numbers and three operators, [{b +, *, sqrt}] and we will trace the evaluation of the hypotenuse of a right triangle, {b [3,4]}, ie {b √(3{sup 2}+4{sup 2})}

{pre
0: '{sqrt {+ {* 3 3} {* 4 4}}}
1: '{sqrt {+ 9 16}}
2: '{sqrt 25}
3: 5
}

_p enlighting the "{b from inside out}" evaluation process.

_p This is what {b Ward Cunningham}, the creator of the first wiki in 1995, wrote about this implementation: {i « I was surprised that the technique worked so well in so many cases. I knew that regex are highly optimized and the cpus themselves optimize sequential access to memory which the regex must have at its core. [..] Yes, this has at its heart the repeated application of a text transformation. The fact that it is repeated application of the same transformation makes it exceptional. [..] Repeated application of Regular Expressions can perform Turing Complete computations. This works because the needed "state" is in the partially evaluated text itself. »} All is said!

_h3 4.2. abstractions
_p {b Abstractions} use arguments as regular expressions to successively replace their occurences found in the function's body by the given words. This makes partial application native and makes closure (close to be) useless.

{pre
0: '{{lambda {x y} « x brave new y! »} Hello World}
1: '{{lambda {y} « Hello brave new y! »} World}
2: '{{lambda {} « Hello brave new World! »}}
-> « Hello brave new World! »
}

_p Note that when the number of values is less than the number of arguments a function is returned waiting for the missing values, for instance

{pre
0: '{{lambda {x y} « x brave new y! »} Hello}
1: '{{lambda {y} « Hello brave new y! »}}
-> '{lambda {y} « Hello brave new y! »}
}

_p Note that arguments are used as regular expressions and must be carefully chosen to avoid unwanted results, as in the following expression
{pre

'{{lambda {a b} « a brave new b! »} Hello World}
-> {{lambda {a b} « a brave new b! »} Hello World}  // ooops!
}

_p To be safe you should {b tag} arguments names, ie.  "{b :a}" or better "{b :a:}", to avoid {b brave} to be replaced first by {b brHellove} then by {b WorldrHellove}. Generally some common sense is enough and, at least, local variables are pretty well enlighted.

{pre
'{{lambda {:a :b} « :a brave new :b! »} Hello World}
-> {{lambda {:a :b} « :a brave new :b! »} Hello World}
}

_p Note also that applications work on the whole (long) code string - minus {b abstracted} short strings abstractions work on. It's a kind of {b NAST}, a {b N}ot {b A}bstract {b S}yntaxic {b T}ree of strings recursively transformed into words.

_p This implementation of the '{lambda talk}'s evaluator remembers the process translated in the 1930s by an other student of {b Alonzo Church}, {b Alan Turing}, into the shape of an hypothetic "{b replacement machine}" made of a window running on an infinite stripe of cells containing [{b 0,1}].

{img {@ src="data/brussels/turing_machine.png" width="100%"}}

_p To conclude, the {b infrastructure} of '{lambda talk} can be seen as a dialect of the {b λ-calculus} implemented as a {b Turing machine}. It's still theoretically of a great interest but practically useless!

_p It's time to build superstructures!

{center --- {{note.call superstructures} superstructures} ---}
}

{{note.content superstructures}
_img data/brussels/nef.jpg
_h2 5. superstructures

_p This small infrastructure constitutes a solid and coherent foundation on which can be raised many {b superstructures} making '{lambda talk} a true programmable programming language!

_p Working in a small wiki, '{lambda tank}, a thin overlay - {b 100kb} - built upon any modern web browser and easy to install on any web provider running PHP, '{lambda talk} takes benefit of powerfull capabilities coming for free, HTML/CSS, SVG, DOM, MATHS, HTTPs, ..., and Javascript.

_h4 special forms
_p The set of special forms is extended to nine

{pre
lambda:  '{lambda {args} body}                        -> ref
def:     '{def name body}                             -> name
if:      '{if bool then one else two} -> one or two
quote:   ''{first rest}                       -> (first rest)
let:     '{let { {args vals} ... } body} 
                         -> '{{lambda {args} body} vals}
macro:   '{macro regular exp to lambdatalk expr}        -> ''
script:  '{script any JS code}                          -> ''
style:   '{style any CSS code}                          -> ''
require: (require lib_xxx lib_yyy ...)                 -> ''
}

_h4 the dictionary
_p The {b dictionary} is populated with several built-in primitives 
_h6 MATHS
{pre 
<, >, <=, >=, =, not, or, and, +, -, *, /, %, abs, acos, asin, atan, ceil, cos, exp, floor, pow, log, random, round, sin, sqrt, tan, min, max, PI, E, date, serie, map, reduce, 
}
_h6 STRINGS
{pre
equal?, empty?, chars, charAt, substring, length, first, rest, last, nth, replace,
} 
_h6 PAIRS, LISTS
{pre
cons, cons?, car, cdr, cons.disp, list.new, list, list.disp, list.null?, list.length, list.reverse, list.first, list.butfirst, list.last, list.butlast
} 
_h6 ARRAYS
{pre
array.new, array, array.disp, array.array?, array.null?, array.length, array.in?, array.get, array.item, array.first, array.last, array.rest, array.slice, array.concat, array.set!, array.addlast!, array.push!, array.sublast!, array.pop!, array.addfirst!, array.unshift!, array.subfirst!, array.shift!, array.reverse!, array.sort!, 
}
_h6 HTML/CSS
{pre
@, div, span, a, ul, ol, li, dl, dt, dd, table, br, tr, td, h1, h2, h3, h4, h5, h6, p, b, i, u, center, hr, blockquote, sup, sub, del, code, img, pre, textarea, canvas, audio, video, source, select, option, object, 
}
_h6 SVG
{pre
svg, line, rect, circle, ellipse, polygon, polyline, path, text, g, mpath, use, textPath, pattern, image, clipPath, defs, animate, set, animateMotion, animateTransform, 
}
_h6 OTHERS
{pre
debug, lib, eval, apply, input, iframe, mailto, back, hide, turtle, drag, note, note_start, note_end, show, lightbox, minibox, editable, forum, ...}

_p This set can be extended {i ad libitum}.

_h4 libraries

_p Directly written in the wiki and containing {b user defined functions}, {b scripts} and {b styles}, an extendable set of {b libraries} can be stored in wiki pages and called in any other wiki page, extending '{lambda talk} on demand.

{center --- {{note.call applications} applications} ---}
}

{{note.content applications}
_img data/brussels/bibliotheque_virtuelle.jpg
_h2 6. applications

_p We will finish this presentation with three examples illustrating recursive processes. The {b '{if bool then one else two}} special form coming "for free" with a built-in lazy behaviour will help us to write more readable and much more effective recursive functions. Beginning with the display of lists.

_h4 displaying fruits
_p Using the built-in [{b cons, car, cdr, nil, list.null?}] primitives equivalent to [{b PAIR, LEFT, RIGHT, NIL, NIL?}] and much more effective
{pre
'{def fruits 
 {cons apple 
  {cons banana
   {cons lemon
    {cons grapes
     {cons orange nil}}}}}}

'{def list.display
 {lambda {:list}
  {if {list.null? :list}
   then 
   else {car :list} {list.display {cdr :list}}}}}
-> {def list.display
 {lambda {:list}
  {if {list.null? :list}
   then 
   else {car :list} {list.display {cdr :list}}}}}

'{list.display {fruits}}
-> apple banana lemon grapes orange
}

_p or, more simply, using the built-in primitives {b list.new} and {b list.disp}

{pre
'{def fruits {list.new apple banana lemon grapes orange}}
-> fruits

'{list.disp {fruits}}
-> apple banana lemon grapes orange
}

_p Actually in '{lambda talk} lists are implemented using the Javascript {b arrays}.

_h4 factorial
_p The product of the first {b n} natural numbers, {b 1*2*3*...*(n-1)*n}, is usually defined as a recursive function, {b fac(n)}

{pre
if {b n < 1} 
then fac(n) = 1
else fac(n) = n*fac(n-1)
}

_p which is easily translated in the '{lambda talk} syntax

{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 5} -> {fac 5}
'{fac 50} -> {fac 50}
'{fac 500} -> Infinity
}

_p As you can see '{fac 50} is not exact beyond 15 digits and '{fac 500} exceeds the limits of Javascript numbers. Using a JS code written by a smart coder, {b Jonas Raoni Soares Silva}, and stored in a wiki page, the {b [[lib_BN]]} library, we can overcome JS limitations and compute big numbers with an exact precision

{pre {@ style="word-wrap: break-word; white-space:pre-wrap;"}
'{def bigfact
 {lambda {:n}
  {if {< :n 1}
   then {BN.new 1}
   else {BN.* :n {bigfact {- :n 1}}}}}}
-> {def bigfact
 {lambda {:n}
  {if {< :n 2}
   then {BN.new 1}
   else {BN.* :n {bigfact {- :n 1}}}}}}

'{bigfact 5}  ->
120

'{bigfact 50}  -> 30414093201713378043612608166064768844377641568960512000000000000

'{bigfact 500} -> 1220136825991110068701238785423046926253574342803192842192413588385845373153881997605496447502203281863013616477148203584163378722078177200480785205159329285477907571939330603772960859086270429174547882424912726344305670173270769461062802310452644218878789465754777149863494367781037644274033827365397471386477878495438489595537537990423241061271326984327745715546309977202781014561081188373709531016356324432987029563896628911658974769572087926928871281780070265174507768410719624390394322536422605234945850129918571501248706961568141625359056693423813008856249246891564126775654481886506593847951775360894005745238940335798476363944905313062323749066445048824665075946735862074637925184200459369692981022263971952597190945217823331756934581508552332820762820023402626907898342451712006207714640979456116127629145951237229913340169552363850942885592018727433795173014586357570828355780158735432768888680120399882384702151467605445407663535984174430480128938313896881639487469658817504506926365338175055478128640000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
}

_h4 turtle SVG graphics

_p Using the built-in primitive {b turtle}, we can define a Lindenmeier {b L-system} structure and call it in a SVG container

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

'{svg
 {@ width="540px" height="540px"}
 {polyline 
  {@ points="{turtle 400 590 180 {tree 5 200 {/ 2 3} 40 4}}"
     fill="transparent" stroke="red" stroke-width="1"}}

... and so on with the green, blue and grey trees
}
}
{LIFTED data/brussels/turtle_20161105.jpg" {def TURTLE A Lindenmeier tree}}

_p Other examples can be seen in the [['{lambda way}'s workshop|?view=start]].

{center --- {{note.call conclusion} conclusion} ---}
}

{{note.content conclusion}
_h2 conclusion

{img {@ src="http://epsilonwiki.free.fr/ELS_YAW/data/2CV_boule_et_bill.jpg" width="100%"}}

_p {b Here we are}, finally we have built from scratch a true programmable programming language for the web, a language which can, {i thanks to modern web browsers}, be used from everywhere, on every systems and every devices, free from any proprietary or/and obfuscated tools.

_h5 it's small
_p The '{lambda way} project is built on a 30kb PHP file and a 60kb JS file free of any external dependancies and is extendable on demand. The JS code is {b Small & Simple}, it can be read, edited and improved by any coder, it's just plain Javascript.

_h5 it's simple
_p '{lambda talk} keeps writing rich structured and dynamic web documents {b Small & Simple}. The {b current wiki page}, built on a handfull of small '{lambda talk} user functions and CSS rules, is by itself an example of a useful application. First you 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 can 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. And so your documents will always be sustainable, easy to edit, improve and publish.

_h5 it's free
_p The '{lambda way} project is a free software under the {b GNU GPL} licence, and its {b 50kb} archive is easy to [[download & install|?view=download]] on any web host provider running PHP.

_p This was the goal of the '{lambda way} project and it's exactly how the current wiki page was created
{center {b http://lambdaway.free.fr/workshop/?view=lambda_factory}}

_p Thank you.
_p {i Alain Marty 2018/05/15}

{center 
{img {@ src="data/fathers/Alonzo_Church.jpg" height ="{hh}" title="Alonzo Church"}}
{img {@ src="data/fathers/Alan_Turing2.jpg" height ="{hh}" title="Alan Turing"}}
{img {@ src="data/fathers/Stephen_Cole_Kleene.jpg" height ="{hh}" title="Stephen Cole Kleene"}}
{img {@ src="data/fathers/John-McCarthy.jpg" height ="{hh}" title="John McCarthy"}}
{img {@ src="data/fathers/Ward_Cunningham.jpg" height ="{hh}" title="Ward Cunningham"}}
with  my grateful thanks to all these pioneers
}

{hr}

_p Et voici un complément bien utile proposé par Pierre Grabolosa.

{div {@ style="transform:rotate(-2deg);
       -webkit-transform:rotate(-2deg);
               box-shadow:0 0 8px #000;
               background:#ffe;
               padding:20px;"}

_h1 oui mais pourquoi ?

_p {i Il y a y déjà des centaines de wikis et des centaines de langages. Pourquoi un wiki de plus et un langage de plus que personne ne va jamais utiliser ?}

_p On peut ajouter ceci :

_ul  1) l'implémentation se fait en JavaScript et vit au cœur de la plateforme Web – tout particulièrement le navigateur. On en retire tout le bénéfice d'une application portable et riche (WebCam, Audio, etc)

_ul  2) Cela vous permet de proposer un Wiki où le contenu est "scriptable" dans la même forme où le contenu est produit ({b data is code / code is data}). Du coup, contrairement au HTML/CSS/JavaScript, vous avez un seul langage.

_ul  2) Comme vous êtes dans un navigateur Web vous devez néanmoins traduire ces contenus en HTML et CSS, mais on peut aisément reprendre le même contenu pour une présentation différente (format "paper" ; seulement en redéfinissant certaines commandes – à l'image de '{b …}

}

_p J'ajouterai que s'attaquer à la construction d'un langage est un exercice enrichissant, éclairant l'usage qu'on peut faire d'autres langages.

_p Et de plus c'est réjouissant !

}

;; the coder's corner
 
{{hide}

{def note.call {lambda {:id} 
  span {@ style="cursor:pointer;"
          onmouseover="this.style.color='#f00'"
          onmouseout="this.style.color='#000'"
          onclick="getId(':id').style.display =    
   (getId(':id').style.display==='none')?'block':'none';"}}}

{def note.content {lambda {:id} 
  div {@ id=":id" 
         style="display:{DISPLAY};
                padding:5px; margin:10px 0;
                box-shadow:0 0 8px #000;"}}}

{def MENU
{pre
 {@ id="menu"
    style="position:fixed; top:50px; left:2px;
           color:#fff; background:transparent"}
{{note.call introduction} introduction}
{{note.call foundations} 1. foundations}
{{note.call data_structures} 2. data structures}
{{note.call control_structures} 3. control structures}
{{note.call implementation} 4. implementation}
{{note.call superstructures} 5. superstructures}
{{note.call applications} 6. applications}
{{note.call conclusion} conclusion}
}
}

{def codeview
 {lambda {:col} div
  {@ style="{if {= :col 1} 
   then color:black; background:#eee; 
        font:normal 1.2em courier;
   else color:#000; background:#fff; 
        font:normal 1.4em arial;
   }
   white-space:pre-wrap; 
   padding:10px 5px 5px 5px; 
   margin:10px 0 0 0;"}
   {div {@ style="font-size:0.6em; 
                  text-align:right;
                  margin:0px 0 -30px -8px;"}
   {if {= :col 1} then code else view}
}}}

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

{def hh 110}

{def LIFTED
 {lambda {:url :txt}
  {div
   {@ class="box lifted-corners"} 
   {img {@ src=":url" width="100%"}} 
   {:txt} 
}}}

{def SPLASH_SCREEN 
{div {@ style="font-size:4.5em; text-align:center; color:#f00; "} '{lambda factory}}

{center 
{div {@ style="font-size:1.0em; letter-spacing:0.11em"} Alain Marty Engineer Architect | Villeneuve de la Raho, France}
{div {@ style="font-size:1.0em; letter-spacing:0.24em"} Présentation à l' [[IMERIR|https://www.imerir.com/]], Perpignan, le 15 Mai 2018}
}

{def TXT Computers are made of [{b NOT,AND,OR}]* gates}

{LIFTED data/cpu_intel.jpg TXT}

{center Languages are made of [{b word|abstraction|application}]*}

;; {audio {@ controls style="width:100%; height:20px;"} {source {@ src="http://marty.alain.free.fr/musique/JohnSurmanTaleOfTheAncient.mp3"}}}

} 
} ;; end hide

{style

@import url( https://fonts.googleapis.com/css?family=Quicksand
);

body {
 background:#444; 
}
#title {
 display:block; 
}
#page_view {
 font-family: Quicksand;
}
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; 
}
#menu a { color:#fff; }

h2, h3, h4, h5, h6 { color:#800 }

b, pre { font:bold 1.0em courier new; color:#400; }

.box { position:relative; top:0; left:0;
    padding: 10px;
    border: solid 1px #555;
    background-color: #eed;
    width: 550px; margin:20px auto;
    border-radius:5px;
    text-align:center;
}
.lifted-corners {
    box-shadow: 0px 10px 8px rgba(0,0,0,0.8);
}
.lifted-corners:after {
    content: "";
    position: absolute;
    width: 100%;
    height: 20px;
    bottom: -20px;
    left: 0px;
    background-image: 
    -moz-radial-gradient(
    	center bottom, 
    	ellipse farthest-side, 
    	rgb(250, 250, 250) 80%, 
    	rgba(250, 250, 250, 0) 100%);
    background-image: 
    -webkit-radial-gradient(
    	center bottom, 
    	ellipse farthest-side, 
    	rgb(250, 250, 250) 80%, 
    	rgba(250, 250, 250, 0) 100%);
    background-image: 
    -o-radial-gradient(
    	center bottom, 
    	ellipse farthest-side, 
    	rgb(250, 250, 250) 80%, 
    	rgba(250, 250, 250, 0) 100%);
}
}