workshop

user:anonymous

{TITLE}

{require lib_mathLT}

°°°
{audio
 {@ controls preload="true" style="width:100%; height:20px;"}
 {source
  {@ src="http://b2b3.free.fr/coleman_hawkins/BodyAndSoul.m4a" type="audio/mp4" 
 }}
 {p Your browser does not support HTML5 audio.}
}
°°°

{div  {COLUMNS}

_h2 abstract

_p The '{lambda way} project is a web application built on two engines, '{lambda talk} and '{lambda tank}. '{lambda talk} is a purely functional programming language unifying authoring, styling and scripting in a single and coherent Lisp-like syntax, working in '{lambda tank}, a tiny wiki built as a thin overlay on top of any web browser.

_p In this paper we progressively introduce {b the making of} '{lambda talk}. We define a reduced set of rules [abstraction, application, definition] working on words as the foundations of '{lambda talk}. Upon this invariant set we build data structures (pairs & lists) and recursion constituting a first subset called '{lambda word}. As an application we build a second subset called '{lambda number} where natural numbers are defined as lists and their associated operators as recursive processes. Then, taking benefit of the powerful capabilities of modern browsers, we build a third set of primitives leading to '{lambda web}, a programming language for the web. Finally we quickly show some extensions making '{lambda talk} a programmable programing language on the web.

{blockquote Thanks to a comment in [[HN|https://news.ycombinator.com/item?id=16970131]] I just discover something similar about the λ-calculus by [[Ron Garret|http://www.flownet.com/ron/lambda-calculus.html]].}

_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

_h2 introduction

_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 fom simple consumers to creators of sharable informations. But these tools come generally with rather rudimentary and heterogeneous syntaxes to enter, enrich and structure texts. '{lambda tank} comes with a true programming language, '{lambda talk}, allowing not only to enter, enrich and structure text, but also to {b write code}.

_p Computer languages are generally introduced from a long enumeration of their syntaxic rules and via numerous examples. We can learn how to resolve problems 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 their fabrication. In order to avoid grey areas, magical functions, abstract concepts, we are going to introduce '{lambda talk} from the most elementary bricks. Nothing but words to assemble and compose, which could {i theoretically} be manipulated by hand, without any computer. So:

_ul 1) we begin to define the smallest and strongest infrastructure on which can be built different superstructures leading to a programmable programming language, 
_ul 2) '{lambda word} is an ultra-light superstructure gently introducing pairs, lists and recursive processes working on words,
_ul 3) '{lambda number} is an extension of '{lambda word} introducing natural numbers and their associate operators, 
_ul 4) '{lambda web} is a more efficient superstructure taking benefit of the powerful capabilities of modern browsers  and coming with an extended set of primitives (Math, HTML/CSS, SVG, ...) and libraries (big numbers, spreadsheet, graphics, ...).
  
_p Let's introduce the foundations of '{lambda talk}.

_h2 1. '{lambda talk}'s foundations

_p Imagine a {i machine} understanding 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} where this question is formulated using a slightly different syntax:

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

_p This {i rather strange} syntax is freely inspired by the '{λ calculus}{ref 3} created in the 1930s by {b Alonzo Church} and uses the {b LISP} S-expressions introduced by {b John McCarthy} in the 1950s{ref 4}and used by all its dialects, ie SCHEME{ref 5}. In '{lambda talk} a valid expression is made of a reduced set of {b nested terms}, [{b words, abstractions, applications}] and is evaluated to {b words}. More precisely:

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

{pre {WRAP}
2. an {b abstraction}, a special form written {b '{lambda {words} expression}}, is evaluated into a word bound to an anonymous function selecting words (arguments) in expression (body) to be replaced by some future given words (values),
}

{pre {WRAP}
3. an {b application}, a nested form written {b '{expression1 expression2}}, determines if expression1 is bound to a function then evaluates expression2 into words2 and applies that function to words2,
}

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

{pre {WRAP}
4. a {b definition}, a special form written '{def word expression}, first evaluates expression into words then binds word to these words. 
}

_p Anonymous functions and user defined constants and functions are stored in a single dictionary initially empty. {b Abstractions} and {b definitions} are {b special forms} caught and evaluated before {b applications}. They can be nested. {b Applications} are {b simple forms} evaluated {b from inside out}. Functions don't create closures but accept {i de facto} partial calls, memorizing the given values and returning a new function waiting for the rest.

_p Note that, at this point, there is neither any data structure nor control structure built on some '{if bool then one else two} special form. What can be done with so little?

_h2 2. '{lambda words}

_h4 2.1. basics

_p Words are not evaluated. Quoting sequences of words is useless. As in any text or spreadsheet editor.

{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 a spreadsheet writing {b PI} displays {b PI}, 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} 
}

_h4 2.2 data structures

_p Lambdas can be {b nested and partially called}, allowing to build data structures and their associated selectors, beginning with {b PAIR}s

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

'{def AP {PAIR Amélie Poulain}} -> {def AP {PAIR Amélie Poulain}}

'{LEFT {AP}}    -> {LEFT {AP}}
'{RIGHT {AP}}   -> {RIGHT {AP}}
}

_p A {b LIST} is a special combination of {b PAIR}s where the ending character can be any word, say {b NIL}.

{pre
list = '{pair a {pair b ... {pair z NIL}}}

'{def VEGETABLES
 {PAIR broccoli
  {PAIR asparagus NIL}}} 
-> {def VEGETABLES {PAIR broccoli {PAIR asparagus NIL}}}

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

'{LEFT {VEGETABLES}}         -> {LEFT {VEGETABLES}}
'{LEFT {RIGHT {VEGETABLES}}} -> {LEFT {RIGHT {VEGETABLES}}}
}

_p The next step will be to display the elements of {b LIST}s in an easier way, automatically in a {b loop}. Here comes recursion!

_h4 2.3. control structure

_p In a pure functional programming language we use {b recursion} to create loops. In a recursive process a function calls itself until some ending condition is reached. At this point neither booleans nor any '{if bool then one else two} special form are supposed to exist. We build the following control structure

{pre
'{{{ISNIL bool}         // return LEFT | RIGHT
 {PAIR 
  {lambda {args} one}  // delay one
  {lambda {args} two}  // delay two
 }} args}              // force one or two
}
 
_p where the word {b NIL} is redefined as a function, {b ISNIL} is a "predicate" function returning {b LEFT} | {b RIGHT}, {b one} and {b two} are protected from evaluation by lambdas. 
 
{pre
'{def NIL {lambda {:f :x} :x}} 
-> {def NIL {lambda {:f :x} :x}} 
'{def ISNIL {lambda {:n} {:n {lambda {:x} RIGHT} LEFT}}} 
-> {def ISNIL {lambda {:n} {:n {lambda {:x} RIGHT} LEFT}}}
}

_p If {b bool} is {b NIL} then {b '{ISNIL bool}} returns {b LEFT}

{pre
-> '{{LEFT 
 {PAIR {lambda {args} one} 
       {lambda {args} two}
 }} args}
-> '{{lambda {args} one} args}
}

_p and {b one} is evaluated. If {b bool} is not {b NIL} then '{ISNIL bool} returns {b RIGHT} and {b two} is evaluated. We can now build a recusive function to display a {b LIST}

{pre

'{def LIST.DISP
 {lambda {:l}
  {{{ISNIL :l}
   {PAIR
    {lambda {:l} } // ending char omitted
    {lambda {:l} {LEFT :l}
                 {LIST.DISP {RIGHT :l}}}
  }} :l}}}
-> {def LIST.DISP
 {lambda {:l}
  {{{ISNIL :l}
   {PAIR {lambda {:l} }
         {lambda {:l} {LEFT :l} {LIST.DISP {RIGHT :l}}}}} :l} }}

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

_p We can reverse and append {b LIST}s

{pre
'{def LIST.REVERSE
 {def LIST.REVERSE.rec
  {lambda {:a :b}
   {{{ISNIL :a}
   {PAIR {lambda {:a :b} :b}
         {lambda {:a :b}
          {LIST.REVERSE.rec
           {RIGHT :a} {PAIR {LEFT :a} :b}}}
   }} :a :b}}}
 {lambda {:a} {LIST.REVERSE.rec :a \}}}
-> {def LIST.REVERSE
 {def LIST.REVERSE.rec
  {lambda {:a :b}
   {{{ISNIL :a}
   {PAIR {lambda {:a :b} :b}
         {lambda {:a :b}
          {LIST.REVERSE.rec
           {RIGHT :a} {PAIR {LEFT :a} :b}}}
   }} :a :b}}}
 {lambda {:a} {LIST.REVERSE.rec :a \}}}

'{def LIST.APPEND
 {lambda {:a :b}
  {LIST.REVERSE.rec {LIST.REVERSE :a} :b}}}
-> {def LIST.APPEND
 {lambda {:a :b}
  {LIST.REVERSE.rec {LIST.REVERSE :a} :b}}}

'{LIST.DISP {LIST.REVERSE {FRUITS}}}
-> orange grapes lemon banana apple
'{LIST.DISP {LIST.APPEND {FRUITS} {VEGETABLES}}}
-> apple banana lemon grapes orange broccoli asparagus
}

_p Even if at this point numbers are not supposed to exist, we can compute the length of a {b LIST} provided we accept to use a primitive numeral unary notation, ie {b 1 = |, 2 = | |, 3 = | | |, 4 = | | | |}

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

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

_h4 2.4. back to foundations

_p The {b def} special form is useful but not mandatory. Let's define a small {b Y-combinator} and replace the recursive definition of {b LIST.LENGTH} by an 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}
  {{{ISNIL :l}
   {PAIR {lambda {:g :l} }
         {lambda {:g :l}
              | {:g :g {RIGHT :l}}}
   }} :g :l}}}
-> {def ALMOST.REC
 {lambda {:g :l}
  {{{ISNIL :l}
   {PAIR {lambda {:g :l} }
         {lambda {:g :l} | {:g :g {RIGHT :l}}}
   }} :g :l}}}

'{{lambda {:g :n} {:g :g :n}} ALMOST.REC {FRUITS}} 
-> | | | | |
}

_p Composing {b Y} and {b ALMOST.REC}, then replacing names by their definitions leads to the following expression

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

_p We are very close to the process translated in the 1930s by a student of {b Alonzo Church}, {b Alan Turing}{ref 18}, into the shape of an hypothetic machine made of a window and an infinite stripe.

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

_p It may be interesting to know that in '{lambda talk} replacements of simple forms '{first rest} are made through a {b window} built on a single Javascript line working on a single {b regular expression}{ref 17}

{pre
while (code != (code = code.replace(
  {quote /\{([^\s{}]*)(?:[\s]*)([^{}]*)\}/g}, 
  apply     // the replacement
 ))) ;      // do nothing
}

_p following the syntax of a language created by {b Stephen Cole Kleene}{ref 7}, another student of {b Alonzo Church}. This is what {b Ward Cunningham} 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 Touring Complete computations. This works because the needed "state" is in the partially evaluated text itself. »} All is said!

_p These regular expressions are also at the heart of lambdas which are nothing but machines to replace words by other words. Lambdas use arguments as regular expressions to successively replace occurences found in the function's body by the given values. For instance

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

}

_p It's partial application made easy, nothing magic there! Everything could be done by hand, {i at least theoretically} or, more seriously, can be coded and tested on any modern web browser, thanks to this small IDE, '{lambda tank}. Nothing but words, abstractions and applications, and an empty dictionary. With such an implementation and a reduced set of rules we have built the foundations of a {b Turing complete programming language} with which we could compute the length of a list ... but in a very primitive unary notation.

_p It's time to introduce {b true} numbers!

_h2 3. '{lambda numbers}

_p At this point we are supposed not to use numbers coming with Javascript and we have to build them from words and lambdas. 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 {b LIST}s of any words, for instance {b pipes |}

{pre N = '{PAIR | {PAIR | ... n times ... NIL}}}

_p With such a definition finding the {b SUCC}essor and the {b PRED}ecessor of any number is straightforward

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

_p The previous version of {b PRED} leads to an error when {b :n} is a word and we must replace it by a new one which will simply return {b :n} in this case.

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

_p We begin to build the set of natural numbers

{pre
'{def ZERO NIL}              -> {def ZERO NIL} 
'{def ONE {SUCC {ZERO}}}   -> {def ONE {SUCC {ZERO}}}
'{def TWO {SUCC {ONE}}}    -> {def TWO {SUCC {ONE}}}
'{def THREE {SUCC {TWO}}}  -> {def THREE {SUCC {TWO}}}
'{def FOUR {SUCC {THREE}}} -> {def FOUR {SUCC {THREE}}}
'{def FIVE {SUCC {FOUR}}}  -> {def FIVE {SUCC {FOUR}}}
'{def SIX {SUCC {FIVE}}}   -> {def SIX {SUCC {FIVE}}}  
'{def SEVEN {SUCC {SIX}}}  -> {def SEVEN {SUCC {SIX}}}

'{LIST.DISP {ZERO}}         -> {LIST.DISP {ZERO}}
'{LIST.DISP {ONE}}          -> {LIST.DISP {ONE}}
'{LIST.DISP {TWO}}          -> {LIST.DISP {TWO}}
'{LIST.DISP {PRED {FIVE}}}  -> {LIST.DISP {PRED {FIVE}}}
'{LIST.DISP {SUCC {FIVE}}}  -> {LIST.DISP {SUCC {FIVE}}}
}
 
_p For convenience we will replace the primitive unary notation given by {b LIST.DISP} by a modern decimal one

{pre
'{def DECIM
 {def DECIM.rec
  {lambda {:l :a}
   {{{ISNIL :l}
    {PAIR
     {lambda {:l :a} :a }
     {lambda {:l :a}
      {DECIM.rec {RIGHT :l} {+ :a 1}}}
   }} :l :a} }}
 {lambda {:l} {DECIM.rec :l 0} }}
-> {def DECIM
 {def DECIM.rec
  {lambda {:l :a}
   {{{ISNIL :l}
    {PAIR {lambda {:l :a} :a }
         {lambda {:l :a} {DECIM.rec {RIGHT :l} {+ :a 1}}}
    }} :l :a} }}
 {lambda {:l} {DECIM.rec :l 0} }}

'{DECIM {ZERO}}         -> {DECIM {ZERO}}
'{DECIM {PRED {TWO}}}   -> {DECIM {PRED {TWO}}}
'{DECIM {TWO}}          -> {DECIM {TWO}}
'{DECIM {SUCC {SEVEN}}} -> {DECIM {SUCC {SEVEN}}}
 
'{DECIM {PRED {ZERO}}} -> {DECIM {PRED {ZERO}}}  // fixed to 0
}

_p Note that at this point we are not theoretically allowed to build a function using Javascript numbers and operators, but we will use {b DECIM} for a better readability.

_p We define some arithmetic operators, {b ADD, SUB, MUL, POW}

{pre
'{def ADD
 {lambda {:a :b}
  {{{ISNIL :b}
   {PAIR
    {lambda {:a :b} :a}
    {lambda {:a :b}
     {ADD {SUCC :a} {PRED :b}}}
  }} :a :b}}}
-> {def ADD
 {lambda {:a :b}
  {{{ISNIL :b}
   {PAIR {lambda {:a :b} :a}
         {lambda {:a :b} {ADD {SUCC :a} {PRED :b}}}
   }} :a :b}}}
'{def SUB
 {lambda {:a :b}
  {{{ISNIL :b}
   {PAIR
    {lambda {:a :b} :a}
    {lambda {:a :b}
     {SUB {PRED :a} {PRED :b}}}
  }} :a :b}}}
-> {def SUB
 {lambda {:a :b}
  {{{ISNIL :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}
   {{{ISNIL :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}
   {{{ISNIL :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}
   {{{ISNIL :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}
   {{{ISNIL :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}
   {{{ISNIL {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}
    {{{ISNIL {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} is straightforward

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

'{DECIM {FAC {SIX}}}   -> 720
'{DECIM {FAC {SEVEN}}} -> max call stack
}

_p Note that the implementation of numbers as {b LIST}s and operators as recursive processes has a severe limit, long lists may exceed the stack capacity, as it is the case for {b 7! = {* {serie 1 7}}}.

_p As a last example we map a function on a list

{pre
'{def MAP
 {def MAP.r
  {lambda {:f :l :acc}
   {{{ISNIL :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}
   {{{ISNIL :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}
   {{{ISNIL {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}
   {{{ISNIL {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 POWER2
 {lambda {:n} {DECIM {POW {TWO} :n}}}}
-> {def POWER2 {lambda {:n} {DECIM {POW {TWO} :n}}}}
'{def TEN {MUL {TWO} {FIVE}}} -> {def TEN {MUL {TWO} {FIVE}}}

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

_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 {WRAP}
[ HI, AFFIRMATION, PAIR, LEFT, RIGHT, AP, FOOD, VEGETABLES, FRUITS, NIL, ISNIL, TREE.DISP, LIST.DISP, LIST.REVERSE, LIST.APPEND, TREE.NODES, LIST.LENGTH, Y, ALMOST.REC, SUCC, PRED, ZERO, ONE, TWO, THREE, FOUR, FIVE, SIX, SEVEN, DECIM.rec, DECIM, ADD, SUB, MUL.rec, MUL, POW.rec, POW, EUCLID.r, EUCLID, DIV, MOD, FAC, MAP.r, MAP, SERIE.r, SERIE, POWER2, TEN ]
}

_p Theoretically any computation can be done,

{pre
'{LIST.DISP {FAC 50}}
-> 30414093201713378043612608166064768844377641568960512000000000000
}

_p But if computing the factorial of {b 5} is relatively fast, computing the factorial of 50, even with a huge stack, would still be too long, probably thousands years...

_p It's time to enter the real life!

_h2 4. '{lambda web}

{center
{img {@ src="data/brussels/browsers_icons.jpg" height="45"}}
{img {@ src="data/brussels/braces.png" height="45"
        style="background:#888"}}
}

_p In fact - and fortunately - '{lambda talk} can take benefit of the powerful functions of web browsers - JAVASCRIPT, HTML/CSS, DOM, SVG, ... - allowing to avoid re-inventing the wheel and to build much more efficient code. The set of special forms is extended to {b 9}

{pre
[lambda def if let macro script style require quote|']
}
_p The dictionary contains a first set of 200 built-in primitives

{pre {WRAP}
DICTionary: (203) [ debug, browser_cache, lib, eval, apply, < ,  >, < =,  >=, =, 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, equal?, empty?, chars, charAt, substring, length, first, rest, last, nth, replace, 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, 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!, @, div, span, a, ul, ol, li, dl, dt, dd, table, 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, svg, line, rect, circle, ellipse, polygon, polyline, path, text, g, mpath, use, textPath, pattern, image, clipPath, defs, animate, set, animateMotion, animateTransform, br, input, iframe, mailto, back, hide, long_mult, turtle, drag, note, note_start, note_end, show, lightbox, minibox, editable, forum, lisp ]
}

_p Thanks to the {b '{if bool then one else two}} special form giving for free the lazy evaluation laboriously coded in the previous recursive algorithms and using numbers and their associate operators - [+, -, *, /, ..., =, <, >, ...] - proposed by Javascript, we can now write more readable and efficient code. For instance

{pre
'{def fac
 {lambda {:n}
  {if {= :n 0}
   then 1
   else {* :n {fac {- :n 1}}}}}}
-> {def fac
 {lambda {:n}
  {if {= :n 0}
   then 1
   else {* :n {fac {- :n 1}}}}}}

'{fac 5}  -> {fac 5}
'{fac 50} -> {fac 50}
}

_p {b '{fac 50}} returns a float number limited to 15 digits and not the exact value. Calling an appropriate {b library} stored in the wiki, {b lib_BN}, we can compensate the limitations of JavaScript numbers - 15 digits maximum - and build a '{lambda talk} code computing the {b 65} digits of {b 50!}

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

'{fact 50} -> 
30414093201713378043612608166064768844377641568960512000000000000
}

_p The set of special forms and built-in primitives makes '{lambda talk} an efficient programming language for the web. Thanks to the set of HTML functions we can structure texts with titles, paragraphs, lists, tables, ... and apply complex styles in a single and coherent syntax. The current wiki page uses plenty of these functions and can generate an Academic paper in ACM format, directly from the browser.

{img {@ src="data/brussels/PDF_paper.jpg" width="100%" title="Academic paper, ACM US format, generated directly from the browser." style="border:1px solid #ccc"}}

_p Thanks to the {b script} special form the set of built-in primitives can be {b extended on demand}. With the browser's SVG functions and the '{lambda talk} primitive {b turtle}, we can define a tree using the Lindenmeier, L-system{ref 11}, 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    
}}}
-> {def tree 
 {lambda {:e :s :k :a :b}
  {if {< :s :e}
   then {flower :s}
   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 }}}

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

{img {@ src="data/brussels/turtle_20161105.jpg" width="100%"}}

_p Finally, here is a quick oversight of some other applications/extensions using libraries stored in the wiki:

_ul with {b lib_MathLT} we can use a set of functions to display {b maths} without MathML{ref 16}
{center 
{div {@ style="font:italic 1.2em georgia;"}
i{del h}{QUOTIENT 20 ∂ψ ∂t} (x,t) = {PAREN 3 (}mc{sup 2}α{sub 0} - i{del h}c {SIGMA 20 j=1 3} α{sub j}{QUOTIENT 20 ∂ ∂x{sub j}} {PAREN 3 )} ψ(x,t)}}

_ul with {b lib_spreadsheet} we can embed a {b spreadsheet}{ref 10} understanding '{lambda talk} expressions
{img {@ src="data/brussels/spreadsheet_shot.jpg" width="100%" title="An integrated spreadsheet using lambda talk expressions." style="border:1px solid #ccc"}}

_ul with {b lib_3D} and {b lib_ray} we can do more intensive computations like vectorial 3D geometries and ray-tracing

{img {@ src="data/brussels/pforms_coons.jpg" width="48%" title="Coons patches built on 6 cubic spline curves with embedded regular polygons" style="border:1px solid #ccc; vertical-align:top;"}}

{img {@ src="data/brussels/d1.jpg" width="48%" title="Integrated Ray-tracing" style="border:1px solid #ccc"}}

_p All these examples can be tested in the '{lambda way}'s workshop.

_p Finally, '{lambda talk} comes with the special form {b '{macro regexp to target}}, where {b regexp} is a regular expression and {b target} is a '{lambda talk} expression. For instance if we want to use {b λ} as an alias of {b lambda} we simply write a short macro

{pre 
'{macro {λ (.*?)} to {lambda €1}} {macro {λ (.*?)} to {lambda €1}}

'{{λ {x y} x*y = {* x y}} 3 4} -> {{λ {x y} x*y = {* x y}} 3 4}
}

_p We could replace the definition of a function {b sqr} defined like this:
{pre
'{def sqr {lambda {:x} {* :x :x}}} -> {def sqr {lambda {:x} {* :x :x}}}
'{sqr 12} -> {sqr 12}
}

_p by a macro {b SQR} expanding {b '{SQR x}} to {b '{* x x}} before the evaluation loop and saving time when the function is called several times

{pre
'{macro {SQR (\d+?|{.*?})} to {* €1 €1}} {macro {_SQR (\w*?|{.*?})} to {* €1 €1}} 
'{SQR 12} -> {_SQR 12}
}

_h2 conclusion

_p Upon a minimal set of rules any user can define a subset of '{lambda talk} like we did with '{lambda word}, '{lambda number} and '{lambda web}. New user functions can be stored in wiki pages used as libraries and called via the {b require} special form. The set of primitives can be edited and extended via the {b script} special form. The {b macro} special form helps creating alternative syntaxes, the {b style} special form allows the user to tune up pages style. '{lambda talk} is fully extensible.

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

_p The '{lambda way} project adds on browsers a thin overlay, '{lambda tank}, proposing a 100kb "Interactive Development Environment" without any external dependencies and thereby  easy to download and install on any web account provider running PHP. '{lambda talk} expressions are written in an editor frame, evaluated in real time, displayed in the wiki's viewer frame, then saved and published on the web. From any web browser, on any system, complex and dynamic web pages can be created, enriched, structured and tested in real time on the web. And it's free!

_p It's exactly how the current wiki page was created.

_p {i Alain Marty | [[http://lambdaway.free.fr|http://lambdaway.free.fr/]]}

_h2 references
{center Under development...}

{pre {WRAP}

{back_ref 1} The Wiki way: [[http://dl.acm.org/citation.cfm?id=375211|http://dl.acm.org/citation.cfm?id=375211]]
{back_ref 2} Ward_Cunningham: [[http://ward.asia.wiki.org/view/testing-microtalk|http://ward.asia.wiki.org/view/testing-microtalk]] 
{back_ref 3} A Tutorial Introduction to the Lambda Calculus (Raul Rojas): [[http://www.inf.fu-berlin.de/lehre/WS03/alpi/lambda.pdf|http://www.inf.fu-berlin.de/lehre/WS03/alpi/lambda.pdf]]
{back_ref 4} Lisp: [[http://www.cs.utexas.edu/~cannata/cs345/Class%20Notes/06%20Lisp.pdf|http://www.cs.utexas.edu/~cannata/cs345/Class%20Notes/06%20Lisp.pdf]]
{back_ref 5} Arold Abelson and Gerald J. Sussman. 1996. Structure and Interpretation of Computer Programs (2nd ed.). MIT Press, Cambridge, MA, USA.
{back_ref 6} Collected Lambda Calculus Functions: [[http://jwodder.freeshell.org/lambda.html|http://jwodder.freeshell.org/lambda.html]]
{back_ref 7} 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 9} Jonas Raoni Soares Silva [[http://jsfromhell.com/classes/bignumber|http://jsfromhell.com/classes/bignumber]]
{back_ref 10} Simon_Peyton_Jones: [[https://www.microsoft.com/en-us/research/people/simonpj/#|https://www.microsoft.com/en-us/research/people/simonpj/#]]
{back_ref 16} google-subtracts-mathml-from-chrome: [[https://www.cnet.com/news/google-subtracts-mathml-from-chrome-and-anger-multiplies/|https://www.cnet.com/news/google-subtracts-mathml-from-chrome-and-anger-multiplies/]]
{back_ref 17} Regular Expressions: [[http://blog.stevenlevithan.com/archives/reverse-recursive-pattern|http://blog.stevenlevithan.com/archives/reverse-recursive-pattern]]
{back_ref 18} Turing machines implemented in JavaScript  [[http://www.turing.org.uk/book/update/tmjavar.html|http://www.turing.org.uk/book/update/tmjavar.html]]
}

} ;; end of COLUMNS

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

{def COLUMNS 
  {@ style="column-count:1;
       -moz-column-count:1;
    -webkit-column-count:1;"}}
}

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

#page_view { font-family: Quicksand;}

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