lambdaspeech
::
BOOK_ONE
1
|
list
|
login
|
load
|
|
{macro _BLOCK_ to block} ;; block | inline-block {macro _DISP_ to block} ;; none | block | inline-block {macro _CARD_ to vcard} ;; vcard | hcard {{wrapper} {{card start 50%} {div {@ style="position:relative; left:0; top:0; margin-bottom:50px; color:#fff;"} {img {@ src="http://colette.cerda.free.fr/images/e2_t2.jpg" width="100%" title="Colette's paintings"}} {div {@ style="position:absolute; top:10px; left:0; width:100%; font:bold 3.0em courier; text-align:center; text-shadow:0 0 8px #000;"} e:=w|λw.e|ee } {div {@ style="position:absolute; bottom:10px; left:0; width:100%; font:italic 1.0em courier; text-align:center; color:#000;"} DELIEES VERS LE SUD {br}encre monotype sur papier 13x18 cm {br} Colette} °°° {div {@ style="position:absolute; bottom:-20px; left:0; width:100%; text-align:center; font:bold 1.0em courier; border:1px solid #000; border-radius:20px;"} [[choose vertical display|?view=BOOK_ONE_v]]} °°° } {center [[introduction|?view=BOOK_INTRODUCTION]] | fonctions | [[primitives|?view=BOOK_TWO]] | [[bibliothèques|?view=BOOK_THREE]] | [[conclusion|?view=BOOK_CONCLUSION]]} {div {@ style="font-size:5.0em; text-align:center; color:#800;"} functions} _p « {i Where is shown how an old and obfuscated theory coming from the thirties can help to build a modern and consistent language for the web.} » _p Imagine a {i machine} understanding this command {pre {i replace}: "x" and "y" {i in}: "x" brave new "y"! {i by}: "Hello" and "World" } _p and answering {b Hello brave new World!} _p '{lambda talk} is such a {i replacement machine} where the question is formulated using a slightly different syntax {pre '{{lambda {:x :y} // replace :x brave new :y!} // in Hello World} // by } _p and returning {b Hello brave new World!} ;; _p Note that arguments like {code :x} and {code :y} will {b always} be prefixed with a colon, enlighting the words to replace. More later. _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. We choose the λ calculus as the deepest theoretical foundation upon which we will progressively add data and control structures, a set of primitives and libraries to reach the level of a usable programming language. _p The notation used in λ calculus is rather terce, as can be seen for instance in introductions given by [[Paul Rojas|http://www.inf.fu-berlin.de/lehre/WS03/alpi/lambda.pdf]] or [[Don Blaheta|http://cs.brown.edu/courses/cs173/2001/Lectures/2001-10-25.pdf]]. In order to make code easier to read, we will uses the {b LISP} prefixed and parenthesized S-expressions introduced by {b John McCarthy} in the fifties. ;; 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 '{}. _p We first introduce the infrastructure of '{lambda talk}, on which we will progressively build the main data and control structures of a functional programming language. As a first example of application we will build the natural numbers and related operators. A couple of applications will end this introduction. _p The main idea is to show how a couple of simple operators - {i a kind of Yin and Yang principles acting on a sea of words} - living in an "empty space", can be used to discover the essence of programming - {i a kind of TAO of thinking} - without any shadow area. _p Let's go! {pre {goto functions functions} ├──{goto infrastructure 1. infrastructure} ├─────{goto syntax 1.1. syntax} ├─────{goto evaluation 1.2. evaluation} ├─────{goto anonymousFunctions 1.3. anonymous functions} ├─────{goto definitions 1.4. definitions} ├──{goto dataAndControlStructures 2. data and control structures} ├─────{goto booleans 2.1. booleans} ├─────{goto pairs 2.2. pairs} ├─────{goto lists 2.3. lists} ├─────{goto recursion 2.4. recursion} ├─────{goto theYcombinator 2.5. the Y combinator} ├──{goto introducingArithmetic 3. introducing arithmetic} ├─────{goto definingNumbers 3.1. defining numbers} ├─────{goto operators 3.2. operators} ├──{goto otherApplications 4. other applications} ├─────{goto serieMapReduce 4.1. serie, map, reduce} ├─────{goto theTowersOfHanoi 4.2. the Towers of Hanoï} ├─────{goto theHilbertCurve 4.3. the Hilbert curve} ├──{goto andSoWhat 5. and so what?} } {center {input {@ type="button" value="show all cards" onclick="show_hide(this)"}}} } {{card infrastructure 30%} _h1 1. infrastructure _p This section introduces the syntax of '{lambda talk} and the way expressions are evaluated. The kernel of '{lambda talk} analyzed in this chapter is made of {b lambdas} creating anonymous functions and {b definitions} creating constants. Two bricks on which we will build everything else, at least theoretically... {pre {goto syntax 1.1. syntax} {goto evaluation 1.2. evaluation} {goto anonymousFunctions 1.3. anonymous functions} {goto definitions 1.4. definitions} } } {{card syntax 40%} _h2 1.1. syntax {center {h1 e:=w|λw.e|ee}} _p The "strange" formula above comes from the {b λ calculus}, a rather esoterical language created by Alonzo Church in the thirties, ten years before the era of computers. This expression says shortly that expressions are made of {b words}, {b abstractions} and {b applications}. _p And it's just what '{lambda talk} is waiting for. _p More precisely: _p {b 1) words} are groups of any characters except spaces and curly braces '{}, _p {b 2) abstractions} "abstract" from the main string code two kind of expressions called "special forms", {code '{lambda {words} expression}} used to create {b anonymous functions} and {code '{def word expression}} used to create {b definitions}, _p {b 3) applications} are remaining nested expressions {code '{abstraction expression}} "applying" {b abstraction} to {b expression} to create a terminal sequence of words. _p This single and systematic parenthesized prefixed and nested syntax, {code '{first rest}}, will be used everywhere. If you find such a syntax "ugly", you should compare with some other languages, for instance in [[learn x in y minutes|https://learnxinyminutes.com/]]! {goto evaluation 1.2. evaluation} } {{card evaluation 40%} _h2 1.2. evaluation {center _h2 /\'{([^\s{}]*)(?:[\s]*)([^{}]*)\}/g} _p The implementation of '{lambda talk} insures that _p {b 1) words} are not evaluated and stand for themselves, _p {b 2) anonymous functions}, {code '{lambda {words} expression}}, are evaluated {i before} definitions and applications. They return a system defined word, a reference bound to a function selecting {code words}, the arguments, in {code expression}, the body, to be replaced by some future given words, the values, _p {b 3) definitions}, {code '{def word expression}}, are evaluated {i after} anonymous functions and {i before} applications. They evaluate {code expression} and return {b word} as a user defined name, _p {b 4) applications}, {code '{abstraction expression}}, are evaluated from inside out, from the leaves to the root. They evaluate {code expression} to words, apply to them the function created by the abstraction and return a sequence of words. _p The evaluation stops when the code string is reduced to a sequence of words, sent to the web browser for a final evaluation and display. _p If you are curious be aware that the strange "formula" at the top of this section is a {b regular expression} following the syntax of a language created by Stephen Cole Kleene in the fifties. This expression is the heart of applications. It is used in a single line JS function going up and down all along the string code, recursively catching terminal forms '{function words} - the leaves - and replacing them by the resulting words. It's a kind of {i Turing machine}. _p More can be seen in [[code|meca/JS.js]] where less than 200 JS lines suffice to implement anonymous functions and definitions. {goto anonymousFunctions 1.3. anonymous functions} } {{card anonymousFunctions 50%} _h2 1.3. anonymous functions {center _h2 '{lambda {:args} body}} _p Anonymous functions are at the heart of '{lambda talk} and have the following properties: _p {b 1) functions are first class}: essentially they can be nested, called as arguments, returned as values and created at run-time, _p {b 2) functions are pure}: they have no side effetcs, the list of arguments determines the local working environment, the {i local variabes} ; there are {b no free} variables: lambdas have no {i automatic} access to any external variables ; outer lambda's arguments having to be used in an inner lambda must be {i manually} redefined in its arguments' list, _p {b 3) functions accept partial calls}: they memorize the given values in their body and return a new function waiting for the missing values, _p {b 4) functions accept variable length of arguments}: extra values are gathered in the last argument, a kind of variadicity. _p Finally, 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! _p But what can be done with so little? _p First of all we can now understand that the first 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, {i kindly} called an {b IIFE}, {pre '{{lambda {args} body} values}} _p replacing 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 {b Hello brave new World!} _p Let's compare to a similar Javascript code: {pre (function (x,y) '{ return x + " brave new " + y; })("Hello","World"); } _p Difficult to say that this syntax is easy to understand. To understand that it's nothing but a replacement process {pre replace: x & y in: "x brave new y" by: "Hello" & "World" } {goto definitions 1.4. definitions} } {{card definitions 40%} _h2 1.4. definitions {center _h2 '{def name expression}} _p Definitions {b '{def name expression}} are used to create global constants added to a single {b dictionary}: _ul they are used to evaluate {code expression} - provided expression is evaluable - and give the result a used defined {code name}, _ul they are used to replace system defined references bound to anonymous functions by user defined names, _ul names are added to a single {b dictionary} initially empty. It will remain empty in the current chapter. _p Thanks to the {b def} special form we can give a name to a sequence of words: {pre '{def HI Hello World} -> {def HI Hello World} } _p and use it this way {pre HI, I say '{HI} -> HI, I say {HI} } _p Note that writing {code HI} just displays {b HI}, a word is not evaluated, and writing {code '{HI}} displays its value. Let's remember that in a standard spreadsheet writing {b 1+2} displays {b 1+2} and writing {b =1+2} displays its value, {b 3}. _p Thanks to the {b def} special form, the IIFE seen in section 1.1. syntax {pre '{{lambda {x y} x brave new y!} Hello World} } _p can be split into a definition {pre '{def FOO {lambda {:x :y} :x brave new :y!}} -> {def FOO {lambda {:x :y} :x brave new :y!}} } _p and one or more calls {pre '{FOO Hello World} -> {FOO Hello World} '{FOO ♥ ♣} -> {FOO ♥ ♣} } _p Comme exemple plus utile on peut donner un nom à l'opération qui consiste à échanger deux mots : {pre '{def swap {lambda {:x :y} :y :x}} -> {def swap {lambda {:x :y} :y :x}} '{swap Hello World} -> {swap Hello World} } _p On peut créer un modèle de lettre et l'utiliser plusieurs fois : {prewrap '{def letter {lambda {:name :loc} Dear :name
It was a pleasure to meet you in :loc
Friendly
Alain }} -> {def letter {lambda {:name :loc} Dear :name
It was a pleasure to meet you in :loc
Friendly
Alain }} '{letter Ward Munich} -> {letter Ward Munich} } _p As you can see, it's nothing but text replacements! No mystery! It is useless to ask for explanations on forums and try to understand explanations given by those who are in the secret of gods. We are going now to see that many things can be done with a {i replacement machine}. Convoluted compositions of replacements can lead to very useful structures. {goto dataAndControlStructures 2. data & control structures} } {{card dataAndControlStructures 30%} _h1 2. data & control structures _p 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. {pre {goto booleans 2.1. booleans} {goto pairs 2.2. pairs} {goto lists 2.3. lists} {goto recursion 2.4. recursion} {goto theYcombinator 2.5 the Y combinator} } } {{card booleans 35%} _h2 2.1. booleans _p Commençons avec trois petites fonctions très simples : {pre '{def | {lambda {:a :b} :a}} -> {def | {lambda {:a :b} :a}} '{def ø {lambda {:a :b} :b}} -> {def ø {lambda {:a :b} :b}} '{def ? {lambda {:a :b :c} {:a :b :c}}} -> {def ? {lambda {:a :b :c} {:a :b :c}}} } _p Les fonctions {code |} and {code ø} ne sont rien d'autre que les {b booléens} standards {code true} et {code false} et la fonction {code ?} est similaire à la structure conditionnelle connue sous la forme "{code if bool then one else two}". _p La fonction {code ?} permet de choisir entre deux mots : {pre '{? | YES NO} -> {? | YES NO} '{? ø YES NO} -> {? ø YES NO} } _p Choisir entre deux phrases - deux séries de mots - demande un peu plus d'attention. On commence par "encapsuler" chaque phrase dans une lambda sans arguments, ce qui a pour effet de la remplacer par sa référence, donc un mot. Une fois le choix réalisé il suffira d'appeler la fonction sans lui fournir de valeur. Exemple : {pre '{{? | {lambda {} a b c} {lambda {} x y z}}} -> {{? | {lambda {} a b c} {lambda {} x y z}}} '{{? ø {lambda {} a b c} {lambda {} x y z}}} -> {{? ø {lambda {} a b c} {lambda {} x y z}}} } _p On peut ainsi soumettre l'appel d'une fonction, son exécution, à une condition, par exemple : {pre '{def conditionnal_application {lambda {:f :c :a :b} {{? :c {lambda {:f :a :b} {:f :a :b}} {lambda {:f :a :b} :f is not applied on :a and :b}} :f :a :b}}} -> {def conditionnal_application {lambda {:f :c :a :b} {{? :c {lambda {:f :a :b} {:f :a :b}} {lambda {:f :a :b} :f is not applied on :a and :b}} :f :a :b}}} '{conditionnal_application swap | hello world} -> {conditionnal_application swap | hello world} '{conditionnal_application swap ø hello world} -> {conditionnal_application swap ø hello world} } _p Le point remarquable est que la fonction n'est exécutée que si elle est appelée avec la valeur {code |}, ce qui peut-être utile si son temps de calcul est important ou/et si on se trouve dans une procédure dite {i récursive}. Nous y reviendrons bientôt. _p Nous avons vu qu'une fonction pouvait appeler un nombre de valeurs supérieur au nombre de ses arguments, le dernier collectant toutes les valeurs suivantes. Appliquées à une séquence de mots la fonction {code |} retournera le premier mot et la fonction {code ø} retournera les suivants. Exemple dans la séquence suivantes affichant chaque mot et les restes successifs d'une phrase se terminant, par exemple, par {code ø} : {pre '{? | hello brave new world ø} -> {? | hello brave new world ø} '{? ø hello brave new world ø} -> {? ø hello brave new world ø} '{? | {? ø hello brave new world ø}} -> {? | {? ø hello brave new world ø}} '{? ø {? ø hello brave new world ø}} -> {? ø {? ø hello brave new world ø}} '{? | {? ø {? ø hello brave new world ø}}} -> {? | {? ø {? ø hello brave new world ø}}} '{? ø {? ø {? ø hello brave new world ø}}} -> {? ø {? ø {? ø hello brave new world ø}}} '{? | {? ø {? ø {? ø hello brave new world ø}}}} -> {? | {? ø {? ø {? ø hello brave new world ø}}}} '{? ø {? ø {? ø {? ø hello brave new world ø}}}} -> {? ø {? ø {? ø {? ø hello brave new world ø}}}} } _p Ceci ressemble fort à un schéma récursif qui devrait conduire à une fonction affichant les mots d'une phrase. A condition d'avoir un test d'arrêt sur la valeur {code ø} ... que je n'ai pas trouvé à ce jour. Quelqu'un a-t-il une idée ? A suivre ... _p Définissons enfin 3 autres fonctions booléennes utiles, {code [&& || !=]}, bien connues sous les noms {code [AND OR NOT]}: {pre '{def && {lambda {:x :y} {:x :y ø}}} -> {def && {lambda {:x :y} {:x :y ø}}} '{&& | |} -> {&& | |} '{&& | ø} -> {&& | ø} '{&& ø |} -> {&& ø |} '{&& ø ø} -> {&& ø ø} '{def || {lambda {:x :y} {:x | :y}}} -> {def || {lambda {:x :y} {:x | :y}}} '{|| | |} -> {|| | |} '{|| | ø} -> {|| | ø} '{|| ø |} -> {|| ø |} '{|| ø ø} -> {|| ø ø} '{def != {lambda {:x} {:x ø |}}} -> {def != {lambda {:x} {:x ø |}}} '{!= |} -> {!= |} '{!= ø} -> {!= ø} } {goto pairs 2.2. pairs} } {{card pairs 45%} _h2 2.2. pairs _p Définissons une importante structure de données, la {b paire}, avec son constructeur {code []}, ses deux accesseurs {code [ & ]} et une fonction retournant {code [} appliquée à une paire et {code ]} sinon : {pre '{def [] {lambda {:a :b :c} {:c :a :b}}} -> {def [] {lambda {:a :b :c} {:c :a :b}}} '{def [ {lambda {:c} {:c |}}} -> {def [ {lambda {:c} {:c |}}} '{def ] {lambda {:c} {:c ø}}} -> {def ] {lambda {:c} {:c ø}}} '{def ø? {lambda {:c} {:c {| ]} [}}} -> {def ø? {lambda {:c} {:c {| ]} [}}} } _p Les noms choisis peuvent sembler inutilement "cryptiques" mais on peut remarquer qu'ils parlent d'eux-même - la fonction [ sélectionne bien la partie gauche d'une paire construite avec la fonction []. Tout ceci va permettre l'écriture de codes compacts faciles à lire d'un seul coup d'oeil, comme une image. Au moins aussi parlants que les {code cons, car, cdr} chéris du LISP. _p Exemple {pre '{def P {[] Hello World}} -> {def P {[] Hello World}} '{[ {P}} -> {[ {P}} '{] {P}} -> {] {P}} '{ø? {P}} -> {ø? {P}} '{ø? ø} -> {ø? ø} } _p Noter que {code []} attend 3 valeurs et n'en obtient que 2. Il s'agit de ce que l'on appelle une "application partielle" et dans ce cas '{lambda talk} mémorise les valeurs données dans son corps et retourne une fonction attendant celle qui manque, {code '{lambda {:c} {:c hello world}}}. Ainsi l'application de {code [} ou de {code ]} sélectionnera {b hello} ou {b world}. _p On peut suivre les substitutions en remplaçant les noms par leurs lambda expressions {pre °° exp = '{[ {[] ♥ ♠}} = {{lambda {z} {z {lambda {x y} x}}} {{lambda {x y z} {z x y}} ♥ ♠}} = {{lambda {z} {z {lambda {x y} x}}} {lambda {z} {z ♥ ♠}}} = {{lambda {z} {z ♥ ♠}} {lambda {x y} x}} = {{lambda {x y} x} ♥ ♠} = ♥ °°} _p We can also follow the two evaluation steps, first abstractions then applications. {pre exp = '{{lambda {z} {z {lambda {x y} x}}} {{lambda {x y z} {z x y}} ♥ ♠}} 1. abstract '{lambda {x y} x} -> ref1 '{lambda {z} {z ref1}} -> ref2 '{lambda {x y z} {z x y}} -> ref3 exp = '{ref2 {ref3 ♥ ♠}} // no more lambdas 2. apply exp = '{ref2 {ref3 ♥ ♠}} = '{ref2 {{lambda {x y z} {z x y}} ♥ ♠}} // partial application on x y = '{ref2 {lambda {z} {z ♥ ♠}}} // leading to a lambda on z = '{ref2 ref4} // referenced by ref4 = '{{lambda {z} {z ref1}} ref4} = '{ref4 ref1} = '{{lambda {z} {z ♥ ♠}} ref1} = '{ref1 ♥ ♠} = '{{lambda {x y} x} ♥ ♠} = ♥ } {goto lists 2.3. lists} } {{card lists 40%} _h2 2.3. lists _p En composant des paires on va construire des listes, qu'on conviendra de terminer par le mot (la fonction) {code ø}. {pre '{def L {[] hello {[] brave {[] new {[] world ø}}}}} -> {def L {[] hello {[] brave {[] new {[] world ø}}}}} } _p La séquence suivante affiche chaque terme de la liste ainsi qu'un test sur le reste de la liste {pre '{[ {L}} '{ø? {L}} -> {[ {L}} {ø? {L}} '{[ {] {L}}} '{ø? {] {L}}} -> {[ {] {L}}} {ø? {] {L}}} '{[ {] {] {L}}}} '{ø? {] {] {L}}}} -> {[ {] {] {L}}}} {ø? {] {] {L}}}} '{[ {] {] {] {L}}}}} '{ø? {] {] {] {L}}}}} -> {[ {] {] {] {L}}}}} {ø? {] {] {] {L}}}}} '{ø? {] {] {] {] {L}}}}}} -> {ø? {] {] {] {] {L}}}}}} } _p Ceci ressemble aussi à un schéma récursif et nous avons maintenant un test d'arrêt sur la valeur {code ø}. {goto recursion 2.4. recursion} } {{card recursion 50%} _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 Here we are, it's straightforward, using nothing but lambdas and defs, we have built a very powerful control structure, the {b recursion}. _p Afin de comprendre le fonctionnement de cet algorithme récursif donnons un nom aux deux lambdas internes {pre '{def one {lambda {:l} }} '{def two {lambda {:l} {[ :l} {D {] :l}}}} '{def D {lambda {:l} {{{ø? :l} {[] one two}} :l} }} } _p et détaillons la suite des évaluations successives {pre '{D {L}} -> '{{lambda {:l} {{{ø? :l} {[] one two}} :l} } {L}} -> '{{{ø? {L}} {[] one two}} {L}} if '{ø? {L}} = ] then -> '{{] {[] one two}} {L}} -> '{two {L}} -> '{{lambda {:l} {[ :l} {D {] :l}}} {L}} -> '{[ {L}} '{D {] {L}}} -> hello '{D {] {L}}} // we got the first and now recurse on the rest ... if '{ø? {L}} = [ then -> '{{[ {[] one two}} {L}} -> '{one {L}} -> '{{lambda {:l} } {L}} // got nothing and exit recursion } _p La récursion est LA structure de contrôle centrale dans '{lambda talk}. Dans ce chapitre ce sera la seule et nous allons en étudier diverses applications. _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 Binary trees can be created using pairs: {pre '{def TD {lambda {:t} {{{ø? {] :t}} {[] {lambda {:t} {[ :t}} {lambda {:t} ({TD {[ :t}} {TD {] :t}})}}} :t}}} -> {def TD {lambda {:t} {{{ø? {] :t}} {[] {lambda {:t} {[ :t}} {lambda {:t} ({TD {[ :t}} {TD {] :t}})}}} :t}}} '{def T {[] {[] {[] {[] A ø} {[] B ø}} {[] {[] C ø} {[] D ø}} } {[] {[] {[] E ø} {[] F ø}} {[] {[] G ø} {[] H ø}} }}} -> {def T {[] {[] {[] {[] A ø} {[] B ø}} {[] {[] C ø} {[] D ø}} } {[] {[] {[] E ø} {[] F ø}} {[] {[] G ø} {[] H ø}} }}} '{TD {T}} -> {TD {T}} } _p And so on. _p To sum up, we have defined {b recursive} algorithms, built on a data structure [ {code [],[,], ø?} ] and a "zest" of lambdas introducing some "delay" in a by default "from inside out" evaluation, without any "extra" {code '{if bool then one else two}} boolean special form, which will be introduced in the next section. _p Remember that we used nothing but words, abstractions (functions and definitions) and applications. In fact we are going to see that {b definitions} are optional and could be theoretically forgotten. {goto theYcombinator 2.5. the Y combinator} } {{card theYcombinator 40%} _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 (without definitions) and applications. A recursive function calling its name inside its body, we first replace it by an "almost-recursive" one, {code AD}, which doesn't call its name {pre '{def AD {lambda {:f :l} {{{ø? :l} {[] {lambda {:f :l} } {lambda {:f :l} {[ :l} {:f :f {] :l}} } }} :f :l}}} -> {def AD {lambda {:f :l} {{{ø? :l} {[] {lambda {:f :l} } {lambda {:f :l} {[ :l} {:f :f {] :l}} } }} :f :l}}} } _p This function is called by a Y-combinator function acting as a fix point {pre '{def Y {lambda {:f :l} {:f :f :l}}} '{Y AD {L}} -> hello brave new world } _p We compose {code Y & AD} into {code YD} {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}} -> hello brave new world } _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}} -> hello brave new world } _p and, replacing all other names by their lambda expressions, we get this convoluted expression {pre '{{lambda {:k} {{lambda {:f :k} {:f :f :k}} {lambda {:f :k} {{{{lambda {:z} {:z {{lambda {:x :y} :x} {lambda {:z} {:z {lambda {:x :y} :y}}}} {lambda {:z} {:z {lambda {:x :y} :x}}}}} :k} {{lambda {:x :y :z} {:z :x :y}} {lambda {:f :k} } {lambda {:f :k} {{lambda {:z} {:z {lambda {:x :y} :x}}} :k} {:f :f {{lambda {:z} {:z {lambda {:x :y} :y}}} :k}} } }} :f :k}} :k}} {{lambda {:x :y :z} {:z :x :y}} hello {{lambda {:x :y :z} {:z :x :y}} brave {{lambda {:x :y :z} {:z :x :y}} new {{lambda {:x :y :z} {:z :x :y}} world {lambda {:x :y} :y}}}}}} -> hello brave new world } _p which is a pure λ-calculus expression. We came back to the fundamentals, {b [w | λw.e | ee]}. {i Words, Yin, Yang. Why not?} _p That said, thanks to the {i optional} {code '{def name expression}} special form, we could easily introduce the first data and control structures, and we are going to use them in the following developments, beginning with arithmetic. {goto introducingArithmetic 3. introducing arithmetic} } {{card introducingArithmetic 40%} _h1 3. introducing arithmetic _p At this point '{lambda talk} knows words, booleans, pairs and lists but has no idea of what can be numbers. Let's build them. _p We know how to display lists' items. But instead of displaying lists' items we could display dots (or anything else) {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 4 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, for convenience, we will use the {b N} display mode. {pre {goto definingNumbers 3.1. defining numbers} {goto operators 3.2. operators} } } {{card definingNumbers 50%} _h2 3.1. defining numbers _p We forget the initial definition proposed by Church 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. _p We define two fundamental operators {code «} and {code »} 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}}}}}} } _p and to start the sequence of natural numbers {pre '{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}} } _p ... and so on {goto operators 3.2. operators} } {{card operators 50%} _h2 3.2. operators _p We define basic arithmetical operators as recursive functions : {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 Tests: {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 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. Any help is welcome! _p Meanwhile, even with small numbers, we can explore some more interesting algorithms. {goto otherApplications 4. other applications} } {{card otherApplications 30%} _h1 4. other applications {pre {goto seriMapReduce 4.1. serie, map, reduce} {goto theTowersOfHanoi 4.2. the Towers of Hanoï} {goto theHilbertCurve 4.3. the Hilbert curve} } } {{card serieMapReduce 50%} _h2 4.1. serie, map, reduce _p Three "syntactic sugar" are often used in functional programming, hiding recursion behind iterative processes: _ul {code '{SERIE start end step}} returns a list of numbers from {code start} to {code end} with step {code step}, _ul {code '{MAP func list}} returns a list of values resulting from the application of {code func} to a {code list}, _ul {code '{REDUCE func list start}} returns the application of {code func} to a {code list} beginning with {code start}. {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 ø}}} '{def REDUCE {lambda {:f :l :acc} {{{ø? :l} {[] {lambda {:f :l :acc} :acc} {lambda {:f :l :acc} {REDUCE :f {] :l} {:f {[ :l} :acc}}} }} :f :l :acc}}} -> {def REDUCE {lambda {:f :l :acc} {{{ø? :l} {[] {lambda {:f :l :acc} :acc} {lambda {:f :l :acc} {REDUCE :f {] :l} {:f {[ :l} :acc}}}}} :f :l :acc}}} '{D {MAP N {SERIE {five}}}} -> 1 2 3 4 5 '{D {MAP {lambda {:n} {N {^^ {two} :n}}} {SERIE {five}}}} -> 2 4 8 16 32 '{N {REDUCE ++ {SERIE {five}} {zero}}} -> {N {REDUCE ++ {SERIE {five}} {zero}}} '{N {REDUCE ** {SERIE {five}} {one}}} -> {N {REDUCE ** {SERIE {five}} {one}}} } _p Note how {code SERIE} is used to build loops and how {code REDUCE} is used to make variadic diadic functions. And given their great interest, these three functions will obviously be integrated as primitives in the next chapter. {goto theTowersOfHanoi 4.2. the Towers of Hanoï} } {{card theTowersOfHanoi 50%} _h2 4.2. 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 words and numbers are easily concatenated in {code '{br} move disc '{N :n} from tower :from to tower :to}. And yes, the {code '{br}} expression calls the HTML breakline function which is not supposed to exist in this chapter. It is used for a better display and that doesn't invalidate the demonstration. {goto theHilbertCurve 4.3. the Hilbert Curve} } {{card theHilbertCurve 40%} _h2 4.3. 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 _img data/hilbert_1.png _img data/hilbert_2.png {goto andSoWhat 5. and so what?} } {{card andSoWhat 50%} _h1 5. and so what? _p To sum up, let's remind the main points: _ul 1) '{lambda talk} code is made of IIFE, '{{lambda {:args} expression} expression}, evaluated to words, _ul 2) IIFE can be splitted in two steps, giving a name to lambdas, '{def name {lambda {:args} expression} and applying this name to other expressions}, '{name expression}, _ul 3) evaluations are "greedy", from inside out, and can be made "lazy" using lambdas, _ul 4) the behaviour of lambdas is entirely determined by their arguments' list, their body and global constants, they don't get values from their context (no lexical closure), they have no side effects, they accept partial calls and variable number of values. _p With so little we could build useful data structures (booleans, pairs, lists, trees) and a fundamental control structure (recursion). Using these tools, as a first application, we have built a "rudimentary implementation" of natural numbers their related operators. We have sketched three {i iterative-like} control structures, (serie, map, reduce), which will become efficient useful primitives in the next chapter, when recursion is not the best answer. And with the Hilbert curve we began to understand how some "soft devices", here the turtle function, can transform words into pictures. And more. _p In this chapter the goal was to introduce in the simplest way some programming concepts often hidden behind obfuscated explanations. At least it's my experience. Recursion should be familiar to you now and you are aware that there is a life out of iteration. _p Now we leave the λ-calculus level and remember that '{lambda talk} is not lost in an empty space! _p In chapter {b [[2) primitives|?view=BOOK_TWO]]} we are going to take the plain benefit of the rich environment brought by web browsers and introduce a more powerful and more "human" programming language. {center [[introduction|?view=BOOK_INTRODUCTION]] | fonctions | [[primitives|?view=BOOK_TWO]] | [[bibliothèques|?view=BOOK_THREE]] | [[conclusion|?view=BOOK_CONCLUSION]]} } } ;; end of wrapper ;; =================================== ;; coder's corner {{hide} {def wrapper div {@ class="scrolling-wrapper"}} {def goto {lambda {:id :val} {input {@ type="button" value=":val" onclick="oc(':id')"}} }} {def card {def card.col {lambda {:r} {floor {+ 220 {* 35 :r}}} }} ;; 220 + 35 = 255 {lambda {:id :w} div {@ class="_CARD_" id=":id" style="display:_DISP_; {if {equal? _CARD_ hcard} then width::w else }; background:rgb({card.col {random}},{card.col {random}},{card.col {random}})"}}} } {style ;; @import url(https://fonts.googleapis.com/css?family=Quicksand); body { background:#eee; } ;; #page_frame { width:100%; font-family:optima; background:transparent; } ;; #page_content { background:transparent; } #page_frame { width:100%; background:#fff; } #page_content { background:transparent; color:#000; font-size:1.0em; font-family:Quicksand; } .scrolling-wrapper { overflow-x: scroll; overflow-y: hidden; white-space: nowrap; border-bottom:10px solid #888; background:transparent; padding:10px; } .hcard { display:_DISP_; box-shadow:0 0 8px #000; background:#fff; padding:10px; white-space:initial; vertical-align:top; overflow-y:scroll; margin:0 5px; height:600px; } .vcard { display:_DISP_; box-shadow:0 0 8px #000; background:#fff; padding:10px; white-space:initial; position:relative; top:0; left:50%; width:60%; margin-left:-30%; margin-top:10px; margin-bottom:10px; } pre { box-shadow:0 0 8px #000; background:#fff; padding:5px;} } {script ;; var show_hide = function(target) { var cards = document.getElementsByClassName('_CARD_'); if (target.value === 'show all cards') { for (var i=0; i < cards.length; i++) cards[i].style.display = '_BLOCK_'; target.value = 'hide all cards' } else { for (var i=1; i < cards.length; i++) cards[i].style.display = 'none'; target.value = 'show all cards' } }; var oc = function(id) { document.getElementById(id).style.display = (document.getElementById(id).style.display === 'none')? '_BLOCK_' : 'none'; document.getElementById(id).scrollIntoView(); }; var init = function(card,disp) { var cards = document.getElementsByClassName('_CARD_'); cards[0].style.display = '_BLOCK_' }; setTimeout( init, 10 ); } {br}
lambdaspeech v.20200126