lambdaspeech :: factory_201902

lambdaspeech :: factory_201902_paper

2 | list | login |load

| |

{blockquote {center See [[last paper|?view=factory_201902_short_2]] submitted on 2019/03/01 to [[ICFP 2019|https://icfp19.sigplan.org]] and [[rejected|http://lambdaway.free.fr/lambdaspeech/?view=ICFP_2019]] on 2019/04/16
}}

_img http://lambdaway.free.fr/workshop/data/brussels/mies_pav.jpg
{div {@ style="margin-top:-70px; margin-bottom:20px; text-align:center; font:italic 3.0em georgia; color:#fff; "} {i e := v | λv.e | ee}}
{center {i The Barcelona Pavilion built in the thirties by Mies van der Rohe{br}is for architecture what the λ-calculus is for computing.}}

{TITLE}

_h1 abstract

_p Wikis are everywhere. In a typical wiki, pages are written using simplified syntaxes which are not designed for creating highly structured documents naturally intermixing text, enrichments and active code. In this paper we introduce the {b making of} '{lambda talk}, an integrated functional programming language, freely inspired by the λ-calculus, unifying the markup, styling and scripting in a Lisp-like prefixed syntax, and working in a wiki context, '{lambda tank}, installed as a slight overlay on any modern web browsers. 
°°°
_p Alternative:

_p The paper introduces the implementation of a functional programming language, '{lambda talk}, a dialect of the λ-calculus, where functions are "absolutely pure". Functions have no access to the outer environment and no side effects. Functions just get an input and return an output, always the same, independantly of the context, obviously with the exception of global constants and functions, when they are added to a single dictionary initially empty. 
_p The paper demonstrates how the lack of closure is partially compensated by two native capabilities of functions: functions can be called with a number of values {u lesser than}, equal to or {u greater than} the number of arguments. The implementation is mainly built on a regular expressions based evaluator, and not on an AST based one. The single dictionary is progressively populated with user defined functions and JS primitives, leading to a functional programming language working as a light overlay on any modern web browser.
°°°

_h1 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
 
_h1 introduction

_p Computer languages are generally introduced with a long enumeration of key words, grammar and syntaxic rules, data and control structures, built-in primitives and libraries. Numerous examples help to learn how to resolve problems, but not to understand the way languages have been conceived and there remains a great deal of mystery which can only be lifted by those who have had access to the {b making of}.

_p It's the reason why we choose to introduce '{lambda talk} by it's {b making of}, from the most elementary bricks, on a couple of rules without any grey area, any magical functionality. Nothing but words to replace, assemble and compose, words which could {i theoretically} be manipulated by hand, without any computer.

_h2 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.

_h2 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, the {b Markdown syntax} is not a language.

_h2 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.

_h2 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 programming language} unifying authoring, styling and scripting in a single and coherent prefixed notation, the '{lambda way} project proposes an answer making easier the {i 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 and editable - for authorised people - on the web. This is a session's screenshot:

{center
{img {@ src="data/session_1.jpg" width="90%"}}
{br} Using '{lambda talk} in '{lambda tank}
}

_h2 content of this paper

_p So, upon a solid {b infrastructure{sup (1)}} made of a reduced set of substitution rules, we add progressively a first set of {b data & control structures{sup (2)}}. Once the fundamental concepts have been introduced, taking benefit of the powerful functionalities of the modern web browsers, we can build efficient {b superstructures{sup (3)}} leading to useful {b applications{sup (4)}}, making '{lambda talk} a true programming language on the web. An overview of the Javascript implementation is given in the last section, {b implementation}.

_h1 1. infrastructure

{center {i « Where is shown how an old and obfuscated theory coming from the thirties
{br}can help to build a modern and consistent language for the 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} created in the thirties by {b Alonzo Church} ten years before the era of computers, and uses the {b LISP} S-expressions introduced by {b John McCarthy} in the fifties. Following the initial paper, numerous introductions have been proposed, for instance "A Tutorial Introduction to the Lambda Calculus" by Raul Rojas{ref 10} and "The Lambda Calculus" by Don Blaheta{ref 11}.
 
_p 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 Inspired by these introductions we choose the λ calculus set of rules, [word|abstarction|application] as the deepest foundation upon which we progressively add data and control structures, a set of primitives, useful special forms and libraries to reach the level of a usable 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 (where parenthesis are used for other purposes) round braces will be replaced by the less used curly braces '{}.

_h2 1.1. syntax

_p At the foundation level, '{lambda talk} expressions are made of words, applications & abstractions:

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

_p More precisely

_ul a {b word} is a group of any characters except spaces and curly braces '{},
_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),

_h2 1.2. evaluation

_p The implementation of '{lambda talk} insures that

_ul {b words} are not evaluated, stand for themselves, {b words},
_ul {b abstractions} are special forms evaluated to {b words} {i before & during} applications,
_ul {b applications} are nested forms evaluated to {b words} from inside out, from the leaves to the root,

_h2 1.3. lambdas

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

_ul {b first class}: essentially they can be nested, called as arguments, returned as values and created at run-time,
_ul {b no closure}: the list of arguments - local variables - determines the local working environment, there is no {i automatic} access to any external variables, no free variables ; outer lambda's arguments having to be used in an inner lambda must be {i manually} redefined in its arguments' list,
_ul {b no side effects}: 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 missing values, 
_ul {b accept variable length of arguments}: extra values are gathered in the last argument.

_p The evaluation stops when the code is reduced to words without any curly braces. These words are sent to the browser's engine which evaluates any HTML/CSS/SVG/DOM/JS code and display the result. '{lambda talk} is just a dwarf on the shoulders of giants!

_p That's it! But what can be done with so little? We can now understand that the given example

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

_p is an {b I}mmediately {b I}nvoked {b F}unction {b E}xpression  ({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! »}

_p But '{lambda talk} is not just a {i replacement machine}. Words, which are the '{lambda talk}'s unique primitive data, can be composed to create useful {b structures} leading to more complex data and powerful control processes.

_h1 2. data structures

{center {i Data is code and code is data.}}

_p Lambdas can be nested and composed, 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}. Leading to the concept of {i data structure} expressed in a form not very readable. For convenience we will add an {i optional} second special form

{pre {center '{def word expression}}}

_p  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 will be added to a single {b dictionary} initially empty.

_h2 2.1. constants

_p Thanks to the {b '{def word expression}} special form we can give a name to a sequence of words

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

_h2 2.2. named functions

_p Thanks to the {b '{def word expression}} special form the IIFE seen in section 1. infrastructure
{pre '{{lambda {x y} « x brave new y! »} Hello World}
} 
_p  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 ♥ ♣}
}

_h2 2.3. pairs & lists

_p The second special form {b '{def word expression}} will help to split convoluted lambda expressions into a set of small elementary blocks of code:

{pre 
'{def | {lambda {:a :b} :a}}             -> {def | {lambda {:a :b} :a}}    // true, one
'{def ø {lambda {:a :b} :b}}             -> {def ø {lambda {:a :b} :b}}    // false, zero
'{def □ {lambda {:a :b :c} {:c :a :b}}}  -> {def □ {lambda {:a :b :c} {:c :a :b}}}    // pair, cons
'{def [ {lambda {:c} {:c |}}}            -> {def [ {lambda {:c} {:c |}}}    // left, car
'{def ] {lambda {:c} {:c ø}}}            -> {def ] {lambda {:c} {:c ø}}}    // right, cdr
'{def ? {lambda {:c} {:c {| ]} [}}}      -> {def ? {lambda {:c} {:c {| ]} [}}}    // isnil?
'{def ¿ {lambda {:c} {:c {| [} ]}}}      -> {def ¿ {lambda {:c} {:c {| [} ]}}}    // isnotnil?
'{def Y {lambda {:f :l} {:f :f :l}}}     -> {def Y {lambda {:f :l} {:f :f :l}}}    // Y combinator
}

_p {b Note:} for the following we will systematically prefix arguments with a colon, for reasons explained in the {b implementation} section.

_h3 2.3.1. pairs

_p As a first application the two expressions returning Hello and World can be simply rewritten as a pair

{pre 
'{def P {□ Hello World}} -> {def P {□ Hello World}}
'{[ {P}}                 -> {[ {P}} 
'{] {P}}                 -> {] {P}}
}

_h3 2.3.2. lists

_p Pairs can be composed to create lists and trees. Let's define a list and access its terms

{pre 
'{def L {□ a {□ b {□ c {□ d {□ e {□ f {□ g ø}}}}}}}} -> {def L {□ a {□ b {□ c {□ d {□ e {□ f {□ g ø}}}}}}}}

'{[ {L}} -> {[ {L}}
'{[ {] {L}}} -> {[ {] {L}}}
...
'{[ {] {] {] {] {] {] {L}}}}}}}} -> {[ {] {] {] {] {] {] {L}}}}}}}}
'{? {] {] {] {] {] {] {] {L}}}}}}}}} -> {? {] {] {] {] {] {] {] {L}}}}}}}}}   // is nil -> true
}

_h2 2.4. recursion

_p The previous sequence displaying terms reveals a recursive process leading to the the following code

{pre

'{def D
 {lambda {:l}
  {{{? :l}
   {□ {lambda {:l} }
      {lambda {:l} {[ :l} {D {] :l}} } }} :l}}}
-> {def D
 {lambda {:l}
  {{{? :l}
   {□ {lambda {:l} }
      {lambda {:l} {[ :l} {D {] :l}} } }} :l}}}

'{D {L}}
-> {D {L}}
}

_p Let's quickly trace the evaluation's steps

{pre °°
0: {D {L}}                         // D is replaced by its lambda expression
1: {{lambda {:l}
  {{{? :l}
   {□ {lambda {:l} }                         // has been evaluated to a word
      {lambda {:l} {[ :l} {D {] :l}} }       // has been evaluated to a word 
   }} :l}} {L}}
2: {{{? {L}}                         // {L} has replaced :l and {? {L}} -> ]
   {□ {lambda {:l} }
      {lambda {:l} {[ :l} {D {] :l}} } }} {L}}
3: {{lambda {:l} {[ :l} {D {] :l}} } {L}}                     // second word
4: {[ {L}} {D {] {L}}}                                // {L} has replaced :l
5: a {D {] {L}}}                             // and so on until {? {L}} -> [
°°}

_p Lists can be reversed and appended

{pre
'{def R                             // list.reverse
 {def R.r
  {lambda {:a :b}
   {{{? :a}
    {□ {lambda {:a :b} :b}
       {lambda {:a :b} {R.r {] :a} {□ {[ :a} :b}}} }} :a :b}}}
 {lambda {:a} {R.r :a ø}}} 
-> {def R
 {def R.r {lambda {:a :b}
   {{{? :a} {□
    {lambda {:a :b} :b}
    {lambda {:a :b} {R.r {] :a} {□ {[ :a} :b}}} }} :a :b}}}
 {lambda {:a} {R.r :a ø}}} 
'{def A                             // list.append
 {def A.r
  {lambda {:a :b}
   {{{? :b}
    {□ {lambda {:a :b} :a}
       {lambda {:a :b} {A.r {□ {[ :b} :a} {] :b}}}  }} :a :b}}}
 {lambda {:a :b} {A.r :a {R :b}}}} 
-> {def A
 {def A.r
  {lambda {:a :b}
   {{{? :b} {□
    {lambda {:a :b} :a}
    {lambda {:a :b} {A.r {□ {[ :b} :a} {] :b}}}  }} :a :b}}}
 {lambda {:a :b} {A.r :a {R :b}}}}

'{D {R {L}}}         -> {D {R {L}}}
'{D {A {L} {R {L}}}} -> {D {A {L} {R {L}}}}
}

_p And so on. To sum up, we have defined {b recursive} algorithms, built on data structure [ {code □,[,]} ] and a "zest" of lambdas introducing some "delay" in a "from inside out" evaluation, without any "extra" {code '{if then else}} boolean special form. Remember that we use nothing but words, applications, abstractions and, {i temporarily}, definitions.

_h2 2.5. the Y combinator

_p To conclude this section we demonstrate that recursion can be written as a true λ calculus expression exclusively made of words, abstractions, applications and so without definitions. A recursive function calling its name inside its body, we replace it by an "almost-recursive" one called by the previously defined Y-combinator, {code '{def Y {lambda {:f :l} {:f :f :l}}}}, acting as a fix point.

{pre 
'{def DD 
 {lambda {:f :l}
  {{{? :l}
   {□ {lambda {:f :l} }
      {lambda {:f :l} {[ :l} {:f :f {] :l}} } }} :f :l}}}
-> {def DD 
 {lambda {:f :l}
  {{{? :l}
   {□ {lambda {:f :l} }
      {lambda {:f :l} {[ :l} {:f :f {] :l}} } }} :f :l}}}

'{Y DD {L}}
-> a b c d e f g
}

_p Replacing {code Y} by its lambda expression definition {code '{lambda {:f :l} {:f :f :l}} } we stick both

{pre
'{def YD
 {lambda {:l}
  {{lambda {:f :l} {:f :f :l}} 
   {lambda {:f :l}
    {{{? :l}
     {□ {lambda {:f :l} }
        {lambda {:f :l} {[ :l} {:f :f {] :l}} } }} :f :l}} :l}}}
-> {def YD
 {lambda {:l}
  {{lambda {:f :l} {:f :f :l}} 
   {lambda {:f :l}
    {{{? :l}
     {□ {lambda {:f :l} }
        {lambda {:f :l} {[ :l} {:f :f {] :l}} } }} :f :l}} :l}}}

'{YD {L}}
-> a b c d e f g
}

_p Now we can forget the name {code YD} and build an IIFE

{pre
'{{lambda {:l}
  {{lambda {:f :l} {:f :f :l}} 
   {lambda {:f :l}
    {{{? :l}
     {□ {lambda {:f :l} }
        {lambda {:f :l} {[ :l} {:f :f {] :l}} } }}
   :f :l}} :l}} {L}}
-> a b c d e f g
}

_p and, replacing all other names by their lambda expression definitions, we get this convoluted expression

{pre
'{{lambda {:l}
 {{lambda {:f :l} {:f :f :l}}
  {lambda {:f :l}
   {{{{lambda {:c} {:c 
    {{lambda {:a :b} :a}
     {lambda {:c} {:c
      {lambda {:a :b} :b}}}}
       {lambda {:c} {:c
        {lambda {:a :b} :a}}}}} :l}
         {{lambda {:a :b :c} {:c :a :b}}
          {lambda {:f :l} }
           {lambda {:f :l}
            {{lambda {:c} {:c 
             {lambda {:a :b} :a}}} :l} {:f :f 
              {{lambda {:c} {:c 
               {lambda {:a :b} :b}}} :l}} } }} :f :l}} :l}} 
                {{lambda {:a :b :c} {:c :a :b}} a 
                {{lambda {:a :b :c} {:c :a :b}} b 
                {{lambda {:a :b :c} {:c :a :b}} c 
                {{lambda {:a :b :c} {:c :a :b}} d 
                {{lambda {:a :b :c} {:c :a :b}} e 
                {{lambda {:a :b :c} {:c :a :b}} f 
                {{lambda {:a :b :c} {:c :a :b}} g 
                 {lambda {:a :b} :b}}}}}}}}}

-> a b c d e f g
}

_p which is a pure λ-calculus expression. Thanks to the {i optional} {code '{def name expression}} special form we could easily introduce the first data and control structures. As an application we are going to explore a primitive version of arithmetic.

_h2 2.6. introducing arithmetic

_p We know how to display lists' items. But instead of displaying lists' items we could display dots

{pre
'{def K                             // list.length
 {lambda {:l}
  {{{? :l}
   {□ {lambda {:l} } 
      {lambda {:l} . {K {] :l}} } }} :l}}}
-> {def K
 {lambda {:l}
  {{{? :l} {□    
    {lambda {:l} } 
    {lambda {:l} . {K {] :l}} } }} :l}}}

'{K {L}} -> {K {L}}          // read 7 items
}

_p It's a kind of primitive unary numeration which can be replaced by a more modern one, if we accept, only for display, to use the numbers of Javascript, the underlying language.

{pre

'{def N                             // number.display
 {lambda {:l}
  {{{? :l}
   {□ {lambda {:l} 0} 
      {lambda {:l} {+ 1 {N {] :l}}} } }} :l}}} 
-> {def N
 {lambda {:l}
  {{{? :l} {□    
    {lambda {:l} 0} 
    {lambda {:l} {+ 1 {N {] :l}}} } }} :l}}}

'{N {L}} -> {N {L}}
}

_p It's a matter of choice. In what follows we will use the {b N} display mode.

_h3 2.6.1. defining numbers and some operators

_p We forget the initial definition proposed by Church{ref 10} and we will simply define {b natural numbers} as lists of dots. {b zero} will be {b ø}, {b one} will be {b '{□ . ø}}, {b two} will be {b '{□ . {□ . ø}}} and so on. Two operators {b « & »} will help to build the sequence of numbers and to get a number before or after any number.

{pre
'{def » {lambda {:n} {□ . :n}}}                     // next
-> {def » {lambda {:n} {□ . :n}}}
'{def « {lambda {:n} {{{? :n} {□ ø {] :n}}}}}}      // prev
-> {def « {lambda {:n} {{{? :n} {□ ø {] :n}}}}}}

'{def zero ø}           = '{N {zero}}  -> {def zero ø}  = {N {zero}}
'{def one {» {zero}}}   = '{N {one}}   -> {def one {» {zero}}}   = {N {one}} 
'{def two {» {one}}}    = '{N {two}}   -> {def two {» {one}}}   = {N {two}}
'{def three {» {two}}}  = '{N {three}} -> {def three {» {two}}} = {N {three}}
'{def four {» {three}}} = '{N {four}}  -> {def four {» {three}}}  = {N {four}}
'{def five {» {four}}}  = '{N {five}}  -> {def five {» {four}}}  = {N {five}}
... and so on
}

_h3 2.6.2. operators

{pre
'{def ++                    // add
 {lambda {:a :b}     
  {{{? :b}
   {□ {lambda {:a :b} :a}
      {lambda {:a :b} {++ {» :a} {« :b}}} }} :a :b}}} 
-> {def ++
 {lambda {:a :b}
  {{{? :b}
   {□ {lambda {:a :b} :a}
      {lambda {:a :b} {++ {» :a} {« :b}}} }} :a :b}}}
'{def --                    // sub
 {lambda {:a :b}
  {{{? :b}
   {□ {lambda {:a :b} :a}
      {lambda {:a :b} {-- {« :a} {« :b}}} }} :a :b}}} 
-> {def -- {lambda {:a :b}
  {{{? :b}
   {□ {lambda {:a :b} :a}
      {lambda {:a :b} {-- {« :a} {« :b}}} }} :a :b}}} 
'{def **                            // times
 {def **.r
  {lambda {:a :b :c}
   {{{? :b}
    {□ {lambda {:a :b :c} :a}
       {lambda {:a :b :c} {**.r {++ :a :c} {« :b} :c}} }} :a :b :c}}}
 {lambda {:a :b} {**.r :a {« :b} :a}}}  
-> {def **
 {def **.r {lambda {:a :b :c}
   {{{? :b}
    {□ {lambda {:a :b :c} :a}
       {lambda {:a :b :c} {**.r {++ :a :c} {« :b} :c}} }} :a :b :c}}}
 {lambda {:a :b} {**.r :a {« :b} :a}}} 
'{def ^^                           // power
 {def ^^.r
  {lambda {:a :b}
   {{{? :b}
    {□ {lambda {:a :b} :a}
       {lambda {:a :b} {^^.r {++ :a :a} {« :b}}} }} :a :b}}}
 {lambda {:a :b} {^^.r :a {« :b}}}}
-> {def ^^
 {def ^^.r {lambda {:a :b}
   {{{? :b}
    {□ {lambda {:a :b} :a}
       {lambda {:a :b} {^^.r {++ :a :a} {« :b}}} }} :a :b}}}
 {lambda {:a :b} {^^.r :a {« :b}}}}
'{def //                            // divide
  {lambda {:x :y}
   {{{? {-- :y :x}}
    {□ {lambda {:x :y} {++ {one} {// {-- :x :y} :y}}}
       {lambda {:x :y} {zero}} }} :x :y}}}
-> {def //
  {lambda {:x :y}
   {{{? {-- :y :x}}
    {□ {lambda {:x :y} {++ {one} {// {-- :x :y} :y}}}
       {lambda {:x :y} {zero}} }} :x :y}}}
'{def %%                             // modulo
 {lambda {:x :y}
  {-- :x {** {// :x :y} :y}}}}
-> {def %%
 {lambda {:x :y}
  {-- :x {** {// :x :y} :y}}}}
'{def !! {lambda {:a :b}             // factorial
  {{{? :b}
   {□ {lambda {:a :b} :a}
      {lambda {:a :b} {!! {** :a :b} {« :b}}} }} :a :b}}}
-> {def !! {lambda {:a :b} 
  {{{? :b}
   {□ {lambda {:a :b} :a}
      {lambda {:a :b} {!! {** :a :b} {« :b}}} }} :a :b}}}
}

_p testing

{prewrap
'{N {« {two}}}  -> 1
'{N {« {one}}}  -> 0
'{N {« {zero}}} -> 0    // zero is the floor of natural numbers

'{N {++ {four} {three}}} -> 7
'{N {** {four} {three}}} -> 12
'{N {-- {four} {three}}} -> 1
'{N {// {four} {three}}} -> {N {// {four} {three}}}
'{N {// {four} {two}}}   -> 2
'{N {// {four} {one}}}   -> 4
'{N {%% {four} {three}}} -> 1 
'{N {%% {four} {two}}}   -> 0
'{N {^^ {two} {five}}}  -> 32 
'{N {!! {one} {** {two} {three}}}}  -> 720 
'{N {!! {one} {** {two} {four}}}}   -> too much recursion 
}

_p And so on.

_p {b Note:} It's obvious that defining numbers as lists of dots is very, very inefficient if we have to do useful arithmetic. A decimal position numeration would be a much better choice and it's a next way to explore. Meanwhile, even with small numbers, we can build some interesting new functions.

_h3 2.6.3. serie & map

_p The {code SERIE} function displays a list of numbers [ {code start,end,step} ] allowing to build iterative loops and the {code MAP} function applies a function on such a list.

{pre
'{def SERIE
 {def SERIE.r {lambda {:a :b :l}
   {{{? {-- :b :a}}
    {□ {lambda {:a :b :l} {□ :b :l}}
       {lambda {:a :b :l} {SERIE.r {» :a} :b {□ :a :l}}}
   }} :a :b :l}}}
 {lambda {:a} {SERIE.r {one} :a ø}}} 
-> {def SERIE
 {def SERIE.r {lambda {:a :b :l}
   {{{? {-- :b :a}}
    {□ {lambda {:a :b :l} {□ :b :l}}
          {lambda {:a :b :l} {SERIE.r {» :a} :b {□ :a :l}}} }} :a :b :l}}}
 {lambda {:a} {SERIE.r {one} :a ø}}}

'{def MAP
 {def MAP.r {lambda {:f :l :acc}
   {{{? :l} {□
    {lambda {:f :l :acc} :acc}
    {lambda {:f :l :acc} {MAP.r :f {] :l} {□ {:f {[ :l}} :acc}}}
   }} :f :l :acc}}}
 {lambda {:f :l} {MAP.r :f :l ø}}} 
-> {def MAP
 {def MAP.r {lambda {:f :l :acc}
   {{{? :l} {□
    {lambda {:f :l :acc} :acc}
    {lambda {:f :l :acc} {MAP.r :f {] :l} {□ {:f {[ :l}} :acc}}} }} :f :l :acc}}}
 {lambda {:f :l} {MAP.r :f :l ø}}}

'{D {MAP N {SERIE {five}}}} 
-> 1 2 3 4 5

'{D {MAP {lambda {:n} {N {^^ {two} :n}}} {SERIE {five}}}} 
-> 2 4 8 16 32 
 }

_h3 2.6.4. The Towers of Hanoï

_p The game {b Towers of Hanoï} gives an example of double recursion

{pre
'{def hanoi
 {lambda {:n :from :to :via}
  {{{? :n} {□ 
   {lambda {:n :from :to :via} }
   {lambda {:n :from :to :via}
    {hanoi {« :n} :from :via :to}
     {br} move disc {N :n} from tower :from to tower :to 
    {hanoi {« :n} :via :to :from} }}}
   :n :from :to :via}}}
-> {def hanoi
 {lambda {:n :from :to :via}
  {{{? :n}
   {□ {lambda {:n :from :to :via} }
         {lambda {:n :from :to :via}
            {hanoi {« :n} :from :via :to}
            {br} move disc {N :n} from tower :from to tower :to 
            {hanoi {« :n} :via :to :from} }}}
   :n :from :to :via}}}

'{hanoi {four} A B C} ->
}

{pre 
{hanoi {four} A B C}
}

_p Note the way tags, words and values are easily concatenated in {code '{br} move disc '{N :n} from tower :from to tower :to}.

_h3 2.6.5. The Hilbert Curve

_p The Hilbert curve is built on two twinned functions {code left & right}

{pre
'{def left
 {lambda {:d :n}
  {{{? :n} {□
   {lambda {:d :n} }
   {lambda {:d :n} T90      {right :d {« :n}}
                   M:d T-90 {left  :d {« :n}}
                   M:d      {left  :d {« :n}}
                   T-90 M:d {right :d {« :n}}
                   T90
   }}} :d :n}}}
-> {def left
 {lambda {:d :n}
 {{{? :n} {□
   {lambda {:d :n} }
   {lambda {:d :n} 
     T90      {right :d {« :n}}
     M:d T-90 {left  :d {« :n}}
     M:d      {left  :d {« :n}}
     T-90 M:d {right :d {« :n}}
     T90 }}} :d :n}}}
'{def right
 {lambda {:d :n}
  {{{? :n} {□
   {lambda {:d :n} }
   {lambda {:d :n} T-90    {left  :d {« :n}}
                   M:d T90 {right :d {« :n}}
                   M:d     {right :d {« :n}}
                   T90 M:d {left  :d {« :n}}
                   T-90
  }}} :d :n}}}
-> {def right
 {lambda {:d :n}
  {{{? :n} {□
   {lambda {:d :n} }
   {lambda {:d :n}
     T-90    {left  :d {« :n}}
     M:d T90 {right :d {« :n}}
     M:d     {right :d {« :n}}
     T90 M:d {left  :d {« :n}}
     T-90 }}} :d :n}}}
}

_p we write

{pre
'{left 10 {one}}
'{left 10 {two}}
'{left 10 {three}}
}

_p to generate these sequences of drawing commands

{prewrap
T90  M10 T-90  M10  T-90 M10  T90

T90 T-90  M10 T90  M10  T90 M10  T-90 M10 T-90 T90  M10 T-90  M10  T-90 M10  T90 M10 T90  M10 T-90  M10  T-90 M10  T90 T-90 M10 T-90  M10 T90  M10  T90 M10  T-90 T90

T90 T-90 T90  M10 T-90  M10  T-90 M10  T90 M10 T90 T-90  M10 T90  M10  T90 M10  T-90 M10 T-90  M10 T90  M10  T90 M10  T-90 T90 M10 T90  M10 T-90  M10  T-90 M10  T90 T-90 M10 T-90 T90 T-90  M10 T90  M10  T90 M10  T-90 M10 T-90 T90  M10 T-90  M10  T-90 M10  T90 M10 T90  M10 T-90  M10  T-90 M10  T90 T-90 M10 T-90  M10 T90  M10  T90 M10  T-90 T90 M10 T90 T-90  M10 T90  M10  T90 M10  T-90 M10 T-90 T90  M10 T-90  M10  T-90 M10  T90 M10 T90  M10 T-90  M10  T-90 M10  T90 T-90 M10 T-90  M10 T90  M10  T90 M10  T-90 T90 T-90 M10 T-90 T90  M10 T-90  M10  T-90 M10  T90 M10 T90 T-90  M10 T90  M10  T90 M10  T-90 M10 T-90  M10 T90  M10  T90 M10  T-90 T90 M10 T90  M10 T-90  M10  T-90 M10  T90 T-90 T90
...
}
 
_p which can be used by a [[turtle graphic|/?view=hilbert]] tool - understanding the {code T+/-90} and {code M10} commands - to display
{center {img {@ src="data/hilbert_1.png" width="49%"}} {img {@ src="data/hilbert_2.png" width="49%"}}}

_p Now we leave the λ-calculus level and remember that '{lambda talk} is not lost in an empty space!

_h1 3. superstructures

{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"}}
{br}{i As a dwarf on the shoulders of giants.}
}

_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 powerful capabilities coming for free, HTML/CSS, SVG, DOM, MATHS, HTTPs, ..., and Javascript. The small λ-calculus infrastructure constitutes a solid and coherent foundation on which can be raised many {b superstructures} making '{lambda talk} a useful programmable programming language!

_h2 3.1. special forms
_p The set of special forms is extended to nine

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

_h2 3.2. the dictionary

_p The {b dictionary} is populated with several built-in primitives

_h3 STRINGS
{pre
equal?, empty?, chars, charAt, substring, length, first, rest, last, nth, replace,
}

_h3 PAIRS, LISTS
{pre
pair|cons, pair?, nil?, left|list.first|car, right|list.rest|cdr, pair.disp, list.new, list.disp, list.null?, list.length, list.reverse, list.butfirst, list.last, list.butlast,
}

_h3 ARRAYS
{pre
#.new, #.disp, #.join, #.split, #.array?, #.null?, #.empty?, #.in?, #.length, #.get, #.first, #.last, #.rest, #.slice, #.concat, #.set!, #.addlast!, #.push!, #.sublast!, #.pop!, #.addfirst!, #.unshift!, #.subfirst!, #.shift!, #.reverse!, #.sort!, 
}

_h3 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, 
}

_h3 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, input, iframe, mailto,
}

_h3 SVG
{pre
svg, line, rect, circle, ellipse, polygon, polyline, path, text, g, mpath, use, textPath, pattern, image, clipPath, defs, animate, set, animateMotion, animateTransform, 
}

_p This set can be extended {i ad libitum} inline, directly from inside the browser. For instance {code lib, back, hide, turtle, drag, ...}.

_h2 3.3. 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.

_h1 4. applications

;; {center {i ... }}

_p These "superstructures" added to the λ calculus kernel make '{lambda talk} a usable programming language of which we will show some applications. Beginning with displaying a list.

_h2 4.1. displaying a list

_p 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 code. Using the built-in [{b cons,car,cdr,nil,list.null?}] primitives equivalent to [{b □,[,],ø,?}] and much more effective, we could display a list writing 
{pre
'{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}}}}}

'{def list {cons a {cons b {cons c {cons d {cons e {cons f {cons g nil}}}}}}}} -> list

'{list.display {list}}
-> a b c d e f g
}

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

{pre
'{def list {list.new a b c d e f g}} -> {def list {list.new a b c d e f g}} = {list}
'{list.disp {list}} -> a b c d e f g
}

_h2 4.2. computing the factorial

_p We can now use the built-in Javascript numbers and associated operators. 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 {center 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 we can see '{fac 50} is not exact beyond 15 digits and '{fac 500} exceeds the limits of Javascript numbers. Thanks to the '{script ...} special form we can add to the dictionary two primitives, {code ADD & MUL}

{pre °°
var ADD = function(a,b) {
  var ADDR = function(a, b, c, d) { 
    var al = a.length, bl = b.length;
    if (al === 0 && bl === 0 && c === 0)
      return d
    else {
      var cc = c + Math.floor( a.charAt(al-1) )
                 + Math.floor( b.charAt(bl-1) );
      return ADDR(a.substring(0,al-1),
                  b.substring(0,bl-1), 
                  ((cc > 9)? 1 : 0),
                  ((cc % 10) + d)
                 );  
    }
  };
  if (a === '0' && b === '0') return '0';
  return ADDR(a,b,0,'').replace(/^0+/, '');
};

var MUL = function(a,b) {
  var c = ''; 
  for (var i=0; i < b.length; i++ ) {
     for (var j=0, d = ''; j < b.charAt(i); j++)
       d = ADD(a,d); 
     c = ADD(c,d) + '0';       
  }
  return c.substring(0,c.length-1); 
};

LAMBDATALK.DICT['ADD'] = function() {
  var args = LAMBDATALK.supertrim(arguments[0]).split(' ');
  return ADD(args[0],args[1])
};
LAMBDATALK.DICT['MUL'] = function() {
  var args = LAMBDATALK.supertrim(arguments[0]).split(' ');
  return MUL(args[0],args[1])
};
°°}

_p with which we can build an extended version of the factorial function

{pre
'{def FAC
 {lambda {:a :b}
  {if {< :b 1}
   then :a
   else {FAC {MUL :a :b} {- :b 1}}}}}
}

_p allowing to compute in a decent time big numbers with an exact precison

{pre
'{FAC 1 500}
-> 1220136825991110068701238785423046926253574342803192842192413588385845373153881997605496447502203281863013616477148203584163378722078177200480785205159329285477907571939330603772960859086270429174547882424912726344305670173270769461062802310452644218878789465754777149863494367781037644274033827365397471386477878495438489595537537990423241061271326984327745715546309977202781014561081188373709531016356324432987029563896628911658974769572087926928871281780070265174507768410719624390394322536422605234945850129918571501248706961568141625359056693423813008856249246891564126775654481886506593847951775360894005745238940335798476363944905313062323749066445048824665075946735862074637925184200459369692981022263971952597190945217823331756934581508552332820762820023402626907898342451712006207714640979456116127629145951237229913340169552363850942885592018727433795173014586357570828355780158735432768888680120399882384702151467605445407663535984174430480128938313896881639487469658817504506926365338175055478128640000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
}

_p {b Note:} actually '{lambda talk} comes with a more complete set of functions working on real numbers of any size packaged in a library, [[lib_BN]], written by a smart coder, {i Jonas Raoni Soares Silva}, interfaced with '{lambda talk}, stored in a wiki page and included on demand via the {code require} special form.

_h2 4.3. Horner & Newton

_p We follow a W. Kahan's paper{ref 12} giving a synthesis of the Horner and Newton methods for polynomial functions. Given the coefficients {code a{sub j}} of the polynomial {code A(x) = Σ{sub 0}{sup N} a{sub j}x{sup N-j}}, and a numerical value {code z}, we can compute both {code p := A(z)} and the derivative {code q := A'(z)} by means of {b Horner}'s recurrence:
     
{pre
q := 0 ; 
p := a{sub 0} ;
for j = 1 to N do 
    q := zq + p ;
    p := zp + a{sub j} ;
}

_p We translate this pseudo-code in '{lambda talk}:

{pre
'{def horner
 {def horner.rec
  {lambda {:l :x :q :p}
   {if {equal? :l nil}
    then {cons :p {/ :p :q}}
    else {horner.rec {cdr :l}
                     :z 
                     {+ {* :z :q} :p}
                     {+ {* :z :p} {car :l}}}}}}
 {lambda {:l :z}
  {horner.rec :l :z 0 0}}} 
-> {def horner
 {def horner.rec {lambda {:l :x :q :p}
   {if {equal? :l nil}
    then {cons :p {/ :p :q}}
    else {horner.rec {cdr :l} :x 
                   {+ {* :x :q} :p}
                   {+ {* :x :p} {car :l}}}}}}
 {lambda {:l :x} {horner.rec :l :x 0 0}}}
}
_p Note that the {code horner} function returns the pair {code [f(x),f(x)/f'(x)]}. The first term will be used to evaluate {code f(x)} for a given value {code x}. For instance:

{pre
'{car {horner {list.new 9 8 7 6 5 4 3 2 1} 10}}
-> {car {horner {list.new 9 8 7 6 5 4 3 2 1} 10}}    // as you might guess!
}

_p The second will be used in the Newton's method:

{pre
'{def newton
 {def epsilon 1.0e-15}
 {lambda {:l :x}
  {let { {:l :l} {:x :x} {:h {horner :l :x}} }
  {if {< {abs {car :h}} {epsilon}}
   then :x
   else {newton :l {- :x {cdr :h}}}}}}}
-> {def newton
 {lambda {:l :x}
  {let { {:l :l} {:x :x} {:h {horner :l :x}} }
  {if {< {abs {car :h}} 1.0e-15}
   then :x
   else {newton :l {- :x {cdr :h}}}}}}}
}

_h3 Some tests

_p 1) Compute the root of {code x{sup 2}-2=0}  which is known to be  √2 = {code {sqrt 2}}:
{pre
'{newton {list.new 1 0 -2} 1} 
-> x = {newton {list.new 1 0 -2} 1}
}

_p 2) Compute the root of {code x{sup 2}-1-1=0}  which is known to be Φ = {code {/ {+ 1 {sqrt 5}} 2}}:
{pre
'{newton {list.new 1 -1 -1} 1.5} 
-> x = {newton {list.new 1 -1 -1} 1.5}
}

_p 3) Compute the root of {code cos(x)=0} which is known to be π/2. We will use the {b Mac Laurin's} development:

{pre {center cos(x) = Σ{sub k=0}{sup k=10} (-1){sup 2k}x{sup 2k}/{sub (2k)!}}}

_p So defining {code n!} simply as {code '{* {serie 1 n}}} we build the serie {code cosx} with {code 10} terms, {code k ∈ [10,1]}:

{pre
'{def cosx {list.new {map {lambda {:n}
  {/ {pow -1 :n} {* {serie 1 {* 2 :n}}}} 0} {serie 10 1 -1}} 1}}
-> {def cosx {list.new 
 {map {lambda {:n} {/ {pow -1 :n} {* {serie 1 {* 2 :n}}}} 0} {serie 10 1 -1}} 1}}
}

_p Finally we can call {code newton} on {code cosx} function with {code 1} as initial value:

{pre
'{* 2 {newton {cosx} 1}}    // which is {PI} 
-> x = {* 2 {newton {cosx} 1}}

}
_p It's simple, quick and accurate!

_h2 4.4. quicksort

_p '{lambda talk} comes with a fast '{#.sort! <|> array} primitive built on Javascript. As an illustration of array primitives, this is how a quicksort could be coded in '{lambda talk}, creating a binary tree from a random array, then walking the canopy.

_p 1) three functions for readability:         
{pre
'{def BT.data  {lambda {:t} {#.get :t 0}}} -> {def BT.data  {lambda {:t} {#.get :t 0}}}
'{def BT.left  {lambda {:t} {#.get :t 1}}} -> {def BT.left  {lambda {:t} {#.get :t 1}}}
'{def BT.right {lambda {:t} {#.get :t 2}}} -> {def BT.right {lambda {:t} {#.get :t 2}}}
}

_p 2) creating the tree from an array of numbers:
{pre
'{def BT.create           
 {def BT.create.rec
  {lambda {:t1 :t2}
   {if {#.empty? :t1}
    then :t2
    else {BT.create.rec {#.rest :t1} 
                        {BT.add {#.first :t1} :t2}} }}}
 {lambda {:t}
  {BT.create.rec :t {#.new}} }}
-> {def BT.create           
 {def BT.create.rec
  {lambda {:l :t}
   {if {#.empty? :l}
    then :t
    else {BT.create.rec {#.rest :l}
                        {BT.add {#.first :l} :t}} }}}
 {lambda {:l}
  {BT.create.rec :l {#.new}} }}
}

_p 3) adding a leaf to the tree: 
{pre
'{def BT.add {lambda {:x :t}
 {if {#.empty? :t}
  then {#.new :x {#.new} {#.new}}
  else {if   {= :x {BT.data :t}}
        then :t
        else {if {< :x {BT.data :t}}
              then {#.new {BT.data :t} 
                          {BT.add :x {BT.left :t}}
                          {BT.right :t}}
              else {#.new {BT.data :t} 
                          {BT.left :t}
                          {BT.add :x {BT.right :t}} }}}}}}
-> {def BT.add {lambda {:x :t}
 {if {#.empty? :t}
  then {#.new :x {#.new} {#.new}}
  else {if   {= :x {BT.data :t}}
        then :t
        else {if {< :x {BT.data :t}}
              then {#.new {BT.data :t} 
                          {BT.add :x {BT.left :t}}
                          {BT.right :t}}
              else {#.new {BT.data :t} 
                          {BT.left :t}
                          {BT.add :x {BT.right :t}} }}}}}}
}

_p 4) walking the canopy -> sorting in increasing order:
{pre
'{def BT.sort
 {lambda {:t}
  {if {#.empty? :t}
   then else {BT.sort {BT.left :t}}
             {BT.data :t}
             {BT.sort {BT.right :t}} }}}   
-> {def BT.sort
 {lambda {:t}
  {if {#.empty? :t}
   then else {BT.sort {BT.left :t}} {BT.data :t}{BT.sort {BT.right :t}} }}}
}

_p 5) Testing

{prewrap
'{def list_numbers {#.new {map {lambda {:n} {floor {* {random} 100000}}} {serie 1 50}}}} 
-> {def list_numbers {#.new {map {lambda {:n} {floor {* {random} 100000}}} {serie 1 50}}}} =  {#.disp {list_numbers}}

'{def tree_numbers {BT.create {list_numbers}}} -> {def tree_numbers {BT.create {list_numbers}}}

'{BT.sort {tree_numbers}} -> {BT.sort {tree_numbers}}     
}

_h2 4.5. the Discrete Fourier Transform

_p The {b Discrete Fourier Transform} (DFT){ref 13} is an algorithm that takes a sample of some curve and determines its {b frequency spectrum}. The DFT algorithm computes the vectorial product of a sequence of N values and the roots of unity. Its expression is usualy given like this

{pre {@ style="padding-left:100px;"}
X(x,k) = {SIGMA}x(n)*e{sup -i2π*kn/N}
       = {SIGMA}x(n)*cos(2π*kn/N)-i{SIGMA}x(n)*sin(2π*kn/N)
}

_p We build a {b dft(x,k)} function taking as input the sample {b x(n)} and a frequency {b k} and returning the norm of {b X(k)}, {b √(X.real{sup 2}+X.imag{sup 2})}.

{pre
'{def dft
 {def dft.r
  {lambda {:x :k :N :X :Y :n}
   {if {= :n {- :N 1}}
    then {round {sqrt {+ {* :X :X} {* :Y :Y}}}}
    else {dft.r {cdr :x} :k :N 
                {+ :X {* {car :x} {cos {/ {* 2 {PI} :k :n} :N}}}}   
                {+ :Y {* {car :x} {sin {/ {* 2 {PI} :k :n} :N}}}}
                {+ :n 1}}
 }}}
 {lambda {:x :k}
  {dft.r :x :k {list.length :x} 0 0 0} 
}}
-> {def dft
 {def dft.r {lambda {:x :k :N :X :Y :n}
   {if {= :n {- :N 1}}
    then {round {sqrt {+ {* :X :X} {* :Y :Y}}}}
    else {dft.r {cdr :x} :k :N 
                {+ :X {* {car :x} {cos {/ {* 2 {PI} :k :n} :N}}}}   
                {+ :Y {* {car :x} {sin {/ {* 2 {PI} :k :n} :N}}}}
                {+ :n 1}} }}}
 {lambda {:x :k} {dft.r :x :k {list.length :x} 0 0 0} }}
}

_p As an example we sample a square curve with 32 levels at +100 and 32 levels at -100

{prewrap
'{def sample 
 {list.new {map {lambda {_}  100} {serie 1 32}} 
           {map {lambda {_} -100} {serie 1 32}} }}
-> {def sample {list.new {map {lambda {_} 100} {serie 1 32}} {map {lambda {_} -100} {serie 1 32}} }} 
'{list.disp {sample}} -> 
{list.disp {sample}}
}

_p We compute correlations for frequencies in range [1,10], find the maximum dft's value and display frequencies and amplitudes

{pre 
'{def dfts {map {dft {sample}} {serie 1 15}}} 
-> {def dfts {map {dft {sample}} {serie 1 15}}}

'{dfts}
-> {dfts}

'{def dft.max {max {dfts}}} 
-> {def dft.max {max {dfts}}} = {dft.max}

'{map {lambda {:k} [{+ :k 1}: 1/{round {/ {dft.max} {nth :k {dfts}}}}]}
     {serie 0 9 2}}
-> {map {lambda {:k} [{+ :k 1}: 1/{round {/ {dft.max} {nth :k {dfts}}}}]}
     {serie 0 9 2}}
}

_p We have found five increasing odd frequencies, [1,3,5,7,9], and decreasing amplitudes, [1/1,1/3,1/5,1/7,1/9]. Finally writing

{pre
'{def CURVE 
 {lambda {:k :t}
  {- :t 180}
  {* 100 {+ {map 
             {{lambda {:t :k} 
              {* {/ 1 :k} {sin {* {/ {PI} 180} :k :t}}} } :t} 
             {serie 1 :k 2}}} 
}}}
-> {def CURVE
 {lambda {:k :t}
  {- :t 180}
  {* 140 {+ {map {{lambda {:t :k}
                   {* {/ 1 :k} {sin {* {/ {PI} 180} :k :t}}} }
                  :t} {serie 1 :k 2}}} }}}

'{svg {@ width="600px" height="300px" style="background:#eee"}
 {g {AXES 600 300}
  {polyline {@ points="-180 0 -180 110 0 110 0 -110 180 -110 180 0"
                                                        {stroke #888 5"}}}
  {polyline {@ points="{map {CURVE 1} {serie 0 360 2}}" {stroke #222 1}}}
  {polyline {@ points="{map {CURVE 3} {serie 0 360 2}}" {stroke #444 1}}}
  {polyline {@ points="{map {CURVE 5} {serie 0 360 2}}" {stroke #444 1}}}
  {polyline {@ points="{map {CURVE 7} {serie 0 360 2}}" {stroke #444 1}}}
  {polyline {@ points="{map {CURVE 9} {serie 0 360 2}}" {stroke #f00 3}}} 
}}
}

_p we plot the five curves and their limit, the square curve

{center {@ style="background:#eee; padding:10px;"}
{svg {@ width="700px" height="300px" style="background:#eee"}
 {g {AXES 700 300}
  {polyline {@ points="-180 0 -180 110 0 110 0 -110 180 -110 180 0" {stroke #888 5"}}}
  {polyline {@ points="{map {CURVE 2} {serie 0 360 2}}" {stroke #222 1}}}
  {polyline {@ points="{map {CURVE 3} {serie 0 360 2}}" {stroke #444 1}}} 
  {polyline {@ points="{map {CURVE 5} {serie 0 360 2}}" {stroke #444 1}}}
  {polyline {@ points="{map {CURVE 7} {serie 0 360 2}}" {stroke #444 1}}}
  {polyline {@ points="{map {CURVE 9} {serie 0 360 2}}" {stroke #f00 3}}} 
}}}

_h2 4.6. de casteljau algorithm

_p A Bézier curve {ref 14} is defined by a set of control points, {b [p0 p1  ... pn]}. The de Casteljau’s algorithm {ref 15} 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 false} {#.new} :t1 true}}}
-> {def CASTEL.stretch {lambda {:arr :t0 :t1}
  {CASTEL.split
   {CASTEL.split :arr {#.new} :t0 false} {#.new} :t1 true}}}

'{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 true} {- :n 1}}
               {CASTEL.blossom {CASTEL.split :arr {#.new} 0.5 false} {- :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}}
}}

_h2 4.7. 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 16}, 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 25 100 {/ 2 3} 45 45} -> blue 
'{tree 25 150 {/ 2 3} 45 45} -> green
'{tree 25 200 {/ 2 3} 45 45} -> red}}
 {td {pre
'{tree 5 200 {/ 2 3} 40 4}  -> red
'{tree 5 180 {/ 2 3} 40 10} -> green
'{tree 5 180 {/ 2 3} 4 20}  -> blue
'{tree 5 150 {/ 2 3} 4 50}  -> black
}}}}}

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

_h2 4.8. intensive computing

_p  For intensive computing '{lambda talk} can always be easily interfaced with the underlying language, Javascript, via the {code script} special form. For instance interactive ray-tracing, curved shapes modeling, fractal drawing:

{center
{img {@ src="http://epsilonwiki.free.fr/lambdaway_2.0/data/lambdaray_20130329/d1.jpg" height="200"}}
{img {@ src="http://epsilonwiki.free.fr/alphawiki_2/data/pforms_coons.jpg" height="200"}}
{img {@ src="http://epsilonwiki.free.fr/alphawiki_2/data/mandel_20160104.jpg" height="200"}}
}

_h1 conclusion

{center {i {b K}eep {b I}t {b S}imple and {b S}mall!}}

_p 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.

_h2 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.

_h2 it's simple
_p '{lambda talk} keeps writing easily rich structured and dynamic web documents.

{center
{img {@ src="data/session_2.jpg" width="90%"}}  
{br} Editing the wiki page generating the current PDF paper.
}

_p The current {b PDF paper} {ref 17} could be seen by itself as a {b full application} of the '{lambda way} project. This paper is a print directly generated from the web browser of a wiki page {ref 18} created, structured, enriched, tested online (code is alive!), built on a handful of '{lambda talk} user defined functions. In other words:

_ul {b First} you insert your ideas, what you think, as it comes to you, as in any text editor. The main difference is that you can't select words with the mouse and click on some button {b [B]} to boldify them, you have to write code and see the result in a viewer frame, coming back to the middle age of web design. But it's in real time, inline and you can begin to code with a reduced set of simple textual commands closely related to well known basic HTML/CSS. 
_ul {b Later} you will be able to enrich the document by yourself or helped by a cute web designer or a smart coder, in a true collaborative work. And so your documents will be sustainable, easy to edit, improve and publish.

_h2 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{ref 19} 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.

_p {i Alain Marty 2019/02}

_h1 annexe: implementation

_p '{lambda talk} is not implemented on a standard AST approach, tokenizing the code and building a tree recursively evaluated, {b eval(build_tree(tokenize(code)))}, but on an original approach based on {b Regular Expressions}. 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
  }
})();
}

_h2 the main function

_p Each key entry in the wiki - or in a simple HTML interface - calls the function {b 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 simple forms.

_h2 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 20}.

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

_h2 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 The main part of the evaluation is done in the {b eval_lambda()} function whose code is self-explanatory:

{pre 
  var {b eval_lambda} = function(s) °°{°° 
    {b s = eval_special_forms(s);}                            // nested lambdas
    var index = s.indexOf("°°)°°"),                            
      argStr = supertrim(s.substring(1, index)),
      {b args} = argStr === "" ? [] : argStr.split(" "),     // arguments
      {b body} = s.substring(index + 2).trim(),              // body
      {b name} = "_LAMB_" + LAMB_num++,                      // reference
      {b reg_args} = [];
    for (var i = 0; i < args.length; i++)           // arguments become
      reg_args[i] = RegExp(args[i], "g");           // regular expressions
    {b body = eval_special_forms( body );}
    {b DICT[name]} = function() °°{°°                     // function added to DICT
      var valStr = supertrim(arguments[0]);
      var {b vals} = valStr === "" ? [] : valStr.split(" "); // given values 
      return (function(bod) °°{°°
        {span {@ style="color:#888;"} bod = eval_conds(bod, reg_args, vals);          // if special forms}
        {b if (vals.length < args.length)} °°{°°            // nb values < arguments
          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);  // return a function 
        °°}°° {b else if ( vals.length === args.length)} °°{°°   // nb values = arguments
          for (var i=0; i < args.length; i++)
          bod = bod.replace( reg_args[i], vals[i] );       // return a value
        °°}°° {b else} °°{°°                          // nb values > arguments
          var _vals_ = vals.slice(0,args.length);  // extra vals are gathered
          _vals_[args.length-1] =                  // in the last argument
          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);}  // evaluate and return the result
      °°}°°)(supertrim(body));
    °°}°°;
    return name;  // return the reference
  °°}°°; 
}

_p Note that arguments are used as regular expressions and must be carefully chosen to prevent 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}
}

_h2 a replacement machine

_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 {PATH}/brussels/turing_machine.png

_p To conclude, at its lowest level, the {b infrastructure} of '{lambda talk} could be seen as a dialect of the {b λ-calculus} implemented as a {b Turing machine}. The whole evaluator is a simple text replacement process. It's understandable and quite unexpected as a strong infrastructure on which can be built several superstructures extendable on demand to make a usable functional programming language.

_h1 references

{prewrap 
{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} The Lambda Calculus (Don Blaheta): [[http://cs.brown.edu/courses/cs173/2001/Lectures/2001-10-25.pdf|http://cs.brown.edu/courses/cs173/2001/Lectures/2001-10-25.pdf]]

{back_ref 12} Horner and Newton methods for polynomial functions (W.Kahan): [[http://www.cs.berkeley.edu/~wkahan/Math128/Poly.pdf|http://www.cs.berkeley.edu/~wkahan/Math128/Poly.pdf]]
{back_ref 13} Discrete Fourier Transform: [[http://practicalcryptography.com/miscellaneous/machine-learning/intuitive-guide-discrete-fourier-transform/|http://practicalcryptography.com/miscellaneous/machine-learning/intuitive-guide-discrete-fourier-transform/]]
{back_ref 14} 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 15} de Casteljau: [[https://en.wikipedia.org/wiki/De_Casteljau%27s_algorithm|https://en.wikipedia.org/wiki/De_Casteljau%27s_algorithm]]
{back_ref 16} Lindenmeier L-system: [[https://en.wikipedia.org/wiki/L-system|https://en.wikipedia.org/wiki/L-system]]

{back_ref 17} [[paper's PDF (8Mb)|http://lambdaway.free.fr/lambdaspeech/data/lambda_factory_201902.pdf]]
{back_ref 18} [[paper's wiki page|http://lambdaway.free.fr/lambdaspeech/?view=factory_201902_paper]]
{back_ref 19} [[download & install|http://lambdaway.free.fr/lambdaspeech/?view=machine2]]

{back_ref 20} Remove Nested Patterns with One Line of JavaScript: [[http://blog.stevenlevithan.com/archives/reverse-recursive-pattern|http://blog.stevenlevithan.com/archives/reverse-recursive-pattern]]

}

_img http://lambdaway.free.fr/workshop/data/brussels/nef.jpg
{center {i The Sagrada Familia built in Barcelona by Antonio Gaudi (& alii){br}is an amazing composition built on a very reduced set of rules.}}

;; the coder's corner
 
{{hide}
 {def PATH http://lambdaway.free.fr/workshop/data}

{def TITLE 
{center 
 {@ style="border-bottom:0px solid #ccc;
           margin:15px 0; padding:15px 0"}      
 {div {@ style="font:italic 5.0em times new roman"} '{lambda factory}}    ;; 18pt
 {div {@ style="font:normal 12pt arial"} 
 Alain Marty Engineer Architect{br}Villeneuve de la Raho, France{br}
 marty•alain © free•fr{br}
 [[http://lambdaway.free.fr/|http://lambdaway.free.fr/lambdaspeech/]]
}}}

{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 SIGMA
 {table {@ style="display:inline-block; vertical-align:middle; font-family:georgia;"}
  {tr {td N-1}}
  {tr {td {@ style="font-size:2.0em; line-height:0.5em;"}Σ}}
  {tr {td n=0}}
}}

{def AXES 
 {lambda {:w :h}
  {@ transform="translate({/ :w 2},{/ :h 2}) scale(1,-1)"} 
  {line {@ x1="-{/ :w 2}:w" y1="0" 
           x2="{/ :w 2}" y2="0"
           stroke="red" fill="transparent"}}
  {line {@ x1="0" y1="-{/ :h 2}" 
           x2="0" y2="{/ :h 2}"
           stroke="green" fill="transparent"}} 
}}
 
{def stroke
 {lambda {:col :w}
 stroke=":col" fill="transparent" stroke-width=":w" }}
}

{style ;;
body { background:#fff; }
#page_frame { width:750px; padding:0px; border:0;}  ;; 750px | 100%
#page_content { font-family: Times new Roman; background:#fff; padding:0px; box-shadow:0 0 0px #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; 
}
#menu a { color:#fff; }
h1, h2, h3, h4, h5, h6 { font:times new Roman; color:#800 }
b, pre, code { font:bold 1.0em courier new; color:#400; }
}