workshop

user:anonymous

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

{english_french}

{div {@ id="french" style="display:none; background:#ffd;"}

_h1  '{λ talk} en bref

_p Dans sa version minimale la syntaxe de '{lambda talk} est librement inspirée du {b lambda calcul} inventé en 1936, dix ans avant les premiers ordinateurs, et se résume en quelques règles simples.

_h3 1. structure

_p Un code '{lambda talk} est une composition d' {b expressions} définies ainsi :

{div {@ style="font:bold 1.3em courier; text-align:center;"}  expression = mot | abstraction | application}

_p où :

_ul 1. un {code mot} est un assemblage de tout caractère autre que l'espace et les accolades {code '{}},

_ul 2. une {b application} a la forme générale {code '{expression expression}},

_ul 3. une {b abstraction} a la forme spéciale {code  '{lambda {mots} expression}}.

_p Cette définition d'une expression faite d'assemblages {b emboîtés} de mots et d'accolades {b équilibrées} donne au code '{lambda talk} une structure récursive dont l'évaluation peut suivre un ensemble restreint de règles simples.

_h3 2. évaluation

_p La présence d'accolades dans une expression provoque une cascade de remplacements qui se termine quand il ne reste plus que des mots. Les remplacements, appelés {b évaluations}, se font ainsi :

_ul 1. les {b abstractions} sont évaluées en premier, et ensuite les {b applications}, de l'intérieur vers l'extérieur,

_ul 2. une {b abstraction} {code '{lambda {mots} expression}} crée un processus, appelé {b fonction anonyme}, sélectionnant une série de mots, appelés {b arguments}, dans une expression, appelée {b corps} ; l'abstraction est remplacée par un mot, {code _LAMB_xxx}, référençant cette fonction dans un {b dictionnaire} initialement vide,

_ul 3. quand commence l'évaluation de l' {b application} {code '{expression_1 expression_2}}, {code expression_1} a déjà été remplacée par la référence à une fonction anonyme et {code expression_2} par une séquence de mots, appelés {b valeurs} ; la fonction anonyme est alors appelée pour remplacer dans son corps les ocurrences des arguments par les valeurs fournies et retourne une séquence de mots.

_p Que peut-on faire avec si peu ?

_h3 3. exemples

_p Voici quelques exemples d'expressions '{lambda talk} et leurs évaluations.

_p Simplement des mots :

{pre
Bonjour le Monde !
-> {b Bonjour le Monde !}
}

_p Définir et appeler une abstraction :

{pre
'{{lambda {fruit inconnue}
          Les fruits sont de couleur inconnue.} cerise rouge}
-> {b Les cerises sont de couleur rouge.}   
}

_p Accéder aux éléments d'une paire {b Amélie Poulain} :
{pre
'{{lambda {z}
 {z {lambda {x y} x}}}
  {{lambda {x y z}
   {z x y}} Amélie Poulain}} 
-> {b Amélie}
'{{lambda {z}
 {z {lambda {x y} y}}}
  {{lambda {x y z}
   {z x y}} Amélie Poulain}} 
-> {b Poulain}
}

_p Calculer une factorielle :

{pre {@ style="word-wrap: break-word; white-space:pre-wrap;"}
'{{lambda {n} {{lambda {g n} {g g n}} {lambda {g n} {{{{lambda {n} {n {lambda {x} {lambda {z} {z {lambda {x y} y}}}} {lambda {z} {z {lambda {x y} x}}}}} n} {{lambda {x y z} {z x y}} {lambda {g n} {lambda {f x} {f x}}} {lambda {g n} {{lambda {n m f x} {n {m f} x}} n {g g {{lambda {n} {{lambda {z} {z {lambda {x y} x}}} {{n {lambda {p} {{lambda {x y z} {z x y}} {{lambda {z} {z {lambda {x y} y}}} p} {{lambda {n f x} {f {{n f} x}}} {{lambda {z} {z {lambda {x y} y}}} p}}}}} {{lambda {x y z} {z x y}} {lambda {f x} x} {lambda {f x} x}}}}} n}}}}}} g n }} n}} {lambda {f x} {f {f {f {f {f x}}}}}}} 
-> {b _LAMB_100}     // référençant le nombre 120 = 1*2*3*4*5
}

_p Evidemment ce code calculant la factorielle de {b 5} est absolument illisible mais rappelons-nous qu'à ce stade '{lambdatalk} ne sait rien faire d'autre que deux opérations sur les {b mots}, 1) {b abstraire} des sélections et 2) {b appliquer} des substitutions.

_h3 4. '{lambda talk}{sup (on ze web)}

_p Il est montré par ailleurs, cf [[lambdacalc]], [[oxford_slides]], [[fabrique]], que cette syntaxe est suffisante pour faire de '{lambda talk} un langage complet avec lequel on peut construire des structures de données et de contrôle : booléens, nombres, paires, listes, arbres, tests, boucles, itérations, récursions.

_p Et donc, en ajoutant simplement une seconde forme spéciale permettant de nommer une expression, {code '{def nom expression}}, il devient possible de ré-écrire sous une forme plus "humaine" le code de la factorielle de {b 5} :

{pre
'{def FAC
 {lambda {:n}
  {{{ISZERO :n}
    {PAIRE {lambda {:n} ONE}
           {lambda {:n} {MUL :n {FAC {PRED :n}}}}}} :n}}}
-> FAC

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

_p C'est nettement plus lisible mais on peut faire mieux.

_p '{lambda talk} n'est pas tout seul, perdu au milieu de nulle part ! En fait, embarqué dans un minuscule outil d'édition appelé '{lambda tank} et juché sur les "épaules" des {b navigateurs}, ces géants modernes du web, '{lambda talk} peut  profiter de l'éco-système existant - HTML, CSS, DOM, SVG, Javascript, regexps, ... - et s'enrichir facilement d'une demi-douzaine de {b formes spéciales} supplémentaires et de plus de {b 150 fonctions primitives}. C'est ainsi que le code de la factorielle peut se ré-écrire en suivant une formulation plus proche de sa définition mathématique :

{pre
'{def fact                          // on définit fact comme nom
 {lambda {:n}                      // d'une fonction de n
  {if {= :n 0}                     // qui, si n est égal à zéro
   then 1                          // alors vaut 1
   else {* :n {fact {- :n 1}}}     // sinon vaut n*fact(n-1)
}}}
-> {def fact
 {lambda {:n}
  {if {= :n 0}
   then 1
   else {* :n {fact {- :n 1}}}}}}

'{fact 5}
-> {b {fact 5}}         // = 1*2*3*4*5 = factorielle de 5
}

_p et que '{lambda talk} devient un véritable langage de programmation utilisable en ligne, n'importe où directement sur le web et sur n'importe quel système to build, with a single and consistent syntax, sophisticated and dynamic {b web pages} full of enriched texts, math computations and pictures.

_p Le langage est présenté en détail dans le workshop '{lambda way} où vous êtes les bienvenus.

} ;; end french version

{div {@ id="english" style="display:block; background:#dff;"}

_h1 '{λ talk} in short

_p In its minimal version the '{lambda talk} syntax is freely inspired by the {b lambda calculus} invented in 1936, ten years before the computers' era, and can be sum up in a handful of simple rules.

_h3 1. structure

_p A '{lambda talk} code is a composition of {b expressions} defined like this :

{div {@ style="font:bold 1.3em courier; text-align:center;"}  expression = word | abstraction | application}

_p where :

_ul 1. a {code word} is a group of any character except spaces and curly braces {code '{}},

_ul 2. an {code application} has the general form {code '{expression expression}},

_ul 3. an {code abstraction} has the special form {code '{lambda {words} expression}}.

_p This definition of an expression made of {b nested} groups of words and {b balanced} curly braces gives the '{lambda talk} code a recursive structure whose evaluation follows a small set of simple rules.

_h3 2. evaluation

_p Inserting curly braces in an expression leads to a cascade of replacements which stops when there is nothing but words. The replacements, called {b evaluations}, are done this way :

_ul 1. {b abstractions} are evaluated first then {b applications}, from inside out,

_ul 2. an {b abstraction} {code '{lambda {words} expression}} creates a process, called an {b anonymous function}, selecting a sequence of words, called {b arguments}, in an expression, called {b body} ; the abstraction is replaced by a word, {code _LAMB_xxx}, referencing this function in a {b dictionnary} initially empty,

_ul 3. when begins the evaluation of the {b application} {code '{expression_1 expression_2}}, {code expression_1} has been soon replaced by the reference of an anonymous function and {code expression_2} has been replaced by words, called {b values} ; the anonymous function is called to replace in its body the arguments' ocurrences by the given values and returns a sequence of words.

_p What can be done with so little?

_h3 3. examples

_p Here are examples of '{lambda talk} expressions and of their evaluations.

_p Just words:
{pre
Hello World!
-> {b Hello World!}
}

_p An abstraction defined and immediately called:

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

_p Accessing elements of a pair, {b Alan Turing}:

{pre
'{{lambda {z}
 {z {lambda {x y} x}}}
  {{lambda {x y z}
   {z x y}} Alan Turing}} 
-> {b Alan}
'{{lambda {z}
 {z {lambda {x y} y}}}
  {{lambda {x y z}
   {z x y}} Alan Turing}} 
-> {b Turing}
}

_p Computing a factorial:

_p Obviously this code computing the factorial of {b 5} is totally unreadable but let's remember that at this point '{lambda talk} doesn't know anything but two operations on {b words}, 1) {b abstracting} selections and 2) {b applying} substitutions.

_h3 4. '{lambda talk}{sup (on the web)}

_p It's shown elsewhere, cf [[lambdacalc]], [[oxford_slides]], [[fabrique]], that this syntax is sufficient to make '{lambda talk} a complete language with which can be built data and control structures: booleans, numbers, pairs, lists, trees, tests, loops, iterations, recursions.

_p And so, simply adding a new special form allowing to give expressions a name, {code '{def name expression}}, it becomes possible to re-write in a more "human" shape the code of {b factorial(5)}:

{pre
'{def FAC
 {lambda {:n}
  {{{ISZERO :n}
    {PAIRE {lambda {:n} ONE}
           {lambda {:n} {MUL :n {FAC {PRED :n}}}}}} :n}}}
-> FAC

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

_p It's soon more readable but but we can do better.

_p '{lambda talk} is not alone, lost in empty space. In fact, embedded in a tiny {b wiki} called '{lambda tank}, staying as a light overlay on the shoulders of browsers, the modern giants on the web, '{lambda talk} can take benefit of the existing eco-system - HTML, CSS, DOM, SVG, Javascript, regexps, ... - and be easily enriched with half a dozen of new {b special forms} and more than {b 150 primitive functions}. Therefore the factorial's code can be rewritten closer to its mathematical definition:

{pre
'{def fact                           // we define fact as the name
 {lambda {:n}                       // of a function of the number n
  {if {= :n 0}                      // which, if n is equal to zero
   then 1                           // then returns 1
   else {* :n {fact {- :n 1}}}      // else returns n*fact(n-1)
}}}
-> {def fact
 {lambda {:n}
  {if {= :n 0}
   then 1
   else {* :n {fact {- :n 1}}}}}}

'{fact 5}
-> {b {fact 5}}                              // = 1*2*3*4*5 = factorial of 5
}

_p And so '{lambda talk} becomes a true programming language which can be used on line, everywhere and on any system to build, with a single and consistent syntax, sophisticated and dynamic {b web pages} full of enriched texts, math computations and pictures.

_p More informations can be seen in the '{lambda way} workshop where you are welcome.
 
} ;; end of the english version

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

_p Alain Marty 2017/11/01-03

{{hide}
{def english_french
{center {input {@ type="button" value="english | french" onclick="
  getId('french').style.display = 
 (getId('french').style.display==='block')?'none':'block';
  getId('english').style.display = 
 (getId('english').style.display==='none')?'block':'none';
"}}}
}
}

{style 
body { background:#666; font-size:0.9em; } 
h1,h3 { color:red; }
code { font:bold 1.1em courier; }
}