Credit Mark Tarver & Amélie PoulainThis page is
neither an introduction to the lambdatalk language
nor a presentation of lambda-calculus,
but the quasi poetic walk along a few key points
that lead from nothing to a programming language.
Less is more.
You could also compare this page to
and analyze the different way basic concepts are introduced, booleans, pairs, recursion, numbers. See also meta3, meta4, ifac_rfac, ... What follows is simple but not simplistic. It is about concepts very often hidden under accumulations of notations, definitions and implicit behaviors. The parenthesed and prefixed notation has been chosen here for its uniqueness, minimalism and the absence of any implicit behaviour. This is what is required to address in so few lines so many concepts that provide the foundation of a language.
Anyway your opinion is welcome via lambdaway©free•fr.
plan
introduction
The {lambda way} project is a light framework built on a wiki, {lambda tank}, and a functional programming language, {lambda talk}.
In this page, using {lambda talk} reduced to two special forms, lambda & def, and an empty dictionary, ie. no primitives, we will define a few data and control structures and explore some interesting things, syntax & evaluation, anonymous functions, pure functions, partial application, curryfication, no closure, composition, then pairs, lists, recursion, Y-combinator, some applications on arithmetic and graphics, and also map, reduce, ..., in other words some of the foundations of a functional programming language.
As a foreword let's consider the following command
replace x and y
in ... y x ... // where ... is any sequence of words
by hello and world
-> ... world hello ...
It's obviously very easy to understand that this command is nothing but a simple text replacement process: two words must be swapped..
And we can understand that the following strange expression
{{lambda {:x :y} ... :y :x ... } hello world}
is just a compact way to rewrite the command: the conjunction words and, in, by have been replaced by a set of well balanced curly braces and the verb replace has been replaced by a strange one, lambda, choosen for historical reasons (don't worry). And we can guess that such a syntax will be very useful to build deeply nested combinations. It's what we are going to explore a little bit.
But first let me congratulate you: you've just written your first computer program!
1) syntax & evaluation
Following the λ calculus created in the 30s by Alonzo Church a {lambda talk} expression is defined as follows
expression := words | abstractions | definitions | applications
where
. syntax evaluated to word := any chars except spaces and {} itself abstraction := {lambda {:words} expression} a function's reference definition := {def word expression} word as alias to expression application := {abstraction expression} a sequence of words
Note that the character "s" ending words, abstractions, definitions & applications means a sequence of. And note that words inside the lambda expression, {:words}, should be prefixed with a colon, ":", enlighting them as local variables and protecting against unwanted replacements in the lambda's body. Moreover these words must be chosen so that their intersection is null, for instance {:a1 :a2 :a3} is ok because :a1^:a2 === 0 but {:a :a1 :a2} is not because :a^:a1 === :a. The rule is "choose variables'names thinking in terms of replacements".
The implementation of {lambda talk} insures that evaluations are done in this order: 1) first abstractions, 2) then definitions, 3) and finally applications. The result is a sequence of words sent to the web browser which evaluates any possibly HTML/CSS/JS code and outputs the result to the browser's window.
2) lambda & def
This section can be skipped in a first reading. The prefixed parenthesized expression
{{lambda {:a0 :a1 ... :an-1} expression containing some occurences of :ai} v0 v1 ... vp-1}so called IIFE (Immediately Invoked Function Expression), defines an anonymous function containing a sequence of n arguments
:ai, immediately invoked on a sequence of p valuesvi, and returning the expression in its body as so modified:• if p < n :• the occurrences of the p first arguments are replaced in the function's body by the corresponding p given values,• a function waiting for missing n-p values is created,• and its reference is returned.• example:{{lambda {:x :y} ... :y ... :x ...} hello} -> {lambda {:y} ... :y ... hello ...} // replaces :x by hello
-> LAMB_123 // the new functions's reference• finally called with the value world this function will return ... world ... hello ...• if p = n :• the occurences of the n arguments are replaced in the function's body by the corresponding p given values,• the body is evaluated and the result is returned.• example{{lambda {:x :y} ... :y ... :x ...} hello world} -> {{lambda {:y} ... :y ... hello ...} world} // replaces :x by hello
-> {{lambda {} ... world ... hello ...} } // replaces :y by world
-> ... world ... hello ... // the value• if p > n :• the occurrences of the n-1 first arguments are replaced in the function's body by the corresponding n-1 given values,• the occurrences of the last argument are replaced in the body by the sequence of p-n supernumerary values,• the body is evaluated and the result is returned.• example:{{lambda {:x :y} ... :y ... :x ...} hello world good morning} -> {{lambda {:y} ... :y ... hello ...} world good morning} -> {{lambda {} ... world good morning ... hello ...}} -> ... world good morning ... hello ... // the value
2.1) lambdas
Lambdas can be used as arguments, as return values, to create local blocks of code and can be applyed on any number of values. Geeks give names for such a behaviour: first class, partial application, currying, variadicity, ....
A lambda has access to user defined constants|functions and eventual built-in primitives, but is a pure black box, totally independent of the context and without any side effect. At the time of invocation, the occurrences of the lambda's arguments and they alone are replaced in the lambda's body by the given values. Outer lambda's variables are inaccessible. If they are required they must be manually redefined in the inner lambda's list of arguments and their values assigned (more later...).
In short lambdatalk doesn't know what geeks call closures, but thanks to the lambdas' behaviour there is a life without closures.
More to see in the page lambda.
2.2) defs
Lambdas can be deeply nested and expressions could become completely obfuscated. For convenience we therefore introduce a second special form {def name expression} which will greatly simplify writing and reading code. This second special form def simply evaluates expression, stores the result in a dictionary (initially empty) and returns name as a reference, a constant. Constants thus defined are global and immutable. Using defs we can split the IIFE seen in the introduction
{{lambda {:x :y} :y :x} hello world}
into an abstraction and an application:
{def SWAP {lambda {:x :y} :y :x}} -> SWAP {SWAP hello world} -> world hello
We can also define global constants:
{def HI hello world} -> HI HI // remember that words are not evaluated
-> HI // stay unchanged
{HI} // we must bracket the name ...
-> hello world // ... to get the value
Things are similar in a spreadsheet, (Excel, OpenOffice.calc, ...). Remember that in a spreadsheet's cell writing 1+2 displays "1+2" and you must write =1+2 to get the value, "3". Writing PI displays PI and you must write =PI() to get the value, 3.141592653589793.
What can be done with so little?
3) data and control structures
3.1) booleans
{def TRUE {lambda {:a :b} :a}} -> TRUE {def FALSE {lambda {:a :b} :b}} -> FALSE {def IF {lambda {:c :a :b} {:c :a :b}}} -> IF {IF TRUE white black} -> white {IF FALSE white black} -> black {def CHOOSE {lambda {:bool :then :else} {IF :bool :then :else}}} -> CHOOSE {CHOOSE TRUE white black} -> white {CHOOSE FALSE white black} -> black
Considering {IF TRUE white black} it's easy to understand that when the IF function is given the three values awaited, its body becomes {TRUE white black}, and the TRUE function returns the first value, white. It's not magic, it's just text substitution.
The IF function can choose between two words, not two sentences. Lambdas without argument can help, replacing their body by a word.
{{CHOOSE TRUE {lambda {} I say white} {lambda {} {I say black}}}} -> I say white
In fact the CHOOSE function returns a word, the choosen function's reference, not its value. It's the reason why we must embed the whole expression between two curly braces to get the value.
Other boolean functions can be built, for instance AND, OR, NOT, XOR,...
{def AND {lambda {:a :b} {IF :a :b FALSE}}} -> AND {def OR {lambda {:a :b} {IF :a TRUE :b}}} -> OR {def NOT {lambda {:a} {IF :a FALSE TRUE}}} -> NOT {def XOR {lambda {:a :b} {OR {AND :a {NOT :b}} {AND :b {NOT :a}}}}} -> XOR {AND TRUE FALSE} -> FALSE {AND TRUE TRUE} -> TRUE {OR TRUE FALSE} -> TRUE {OR FALSE FALSE} -> FALSE {NOT TRUE} -> FALSE {NOT FALSE} -> TRUE ...
3.2) pairs
Words are the fundamental data lambdas work on. Pairs will be aggregations of two words.
{def CONS {lambda {:a :b :c} {:c :a :b}}} -> CONS {def HEAD {lambda {:p} {:p TRUE}}} -> HEAD {def TAIL {lambda {:p} {:p FALSE}}} -> TAIL {def P {CONS hello world}} -> P {HEAD {P}} -> hello {TAIL {P}} -> world
Note that CONS waits for three values. So {def P {CONS hello world}} getting only two values is replaced by a partial application returning a function {lambda {:c} {:c hello world}} waiting for the missing values. When {HEAD {P}} is invoked, the expression becomes
{{lambda {:p} {:p {lambda {:a :b} :a}}} // HEAD
{lambda {:c} {:c hello world}}} // P
-> {{lambda {:c} {:c hello world}} {lambda {:a :b} :a}} -> {{lambda {:a :b} :a} hello world} -> hello
It must be understood that for instance in the FOURTH line {lambda {:a :b} :a} has been evaluated to a word, the function's reference ref, and it's this word which is replaced in {:c hello world}, leading to {ref hello world} then to {{lambda {:a :b} :a} hello world} and finally to hello. One more time it's not magic it's just text substitution.
Pairs can be nested very deeply. As an example we show, without explanations, how with booleans and pairs we have everything required to build a binary numbers based arithmetic, beginning with a 4 bits adder:
{def halfAdder {lambda {:a :b} {CONS {AND :a :b} {XOR :a :b}}}} -> halfAdder {def fullAdder {lambda {:a :b :c} {{lambda {:b :ha1} {{lambda {:ha1 :ha2} {CONS {OR {HEAD :ha1} {HEAD :ha2}} {TAIL :ha2}} } :ha1 {halfAdder {TAIL :ha1} :b}} } :b {halfAdder :c :a}} }} -> fullAdder {def 4bitsAdder {lambda {:a4 :a3 :a2 :a1 :b4 :b3 :b2 :b1} {{lambda {:a4 :a3 :a2 :b4 :b3 :b2 :fa1} {{lambda {:a4 :a3 :b4 :b3 :fa1 :fa2} {{lambda {:a4 :b4 :fa1 :fa2 :fa3} {{lambda {:fa1 :fa2 :fa3 :fa4} {HEAD :fa4} {TAIL :fa4} {TAIL :fa3} {TAIL :fa2} {TAIL :fa1} } :fa1 :fa2 :fa3 {fullAdder :a4 :b4 {HEAD :fa3}}} } :a4 :b4 :fa1 :fa2 {fullAdder :a3 :b3 {HEAD :fa2}}} } :a4 :a3 :b4 :b3 :fa1 {fullAdder :a2 :b2 {HEAD :fa1}}} } :a4 :a3 :a2 :b4 :b3 :b2 {halfAdder :a1 :b1} }}} -> 4bitsAdder {4bitsAdder FALSE TRUE TRUE TRUE // 0111
FALSE FALSE FALSE TRUE} // + 0001
-> FALSE TRUE FALSE FALSE FALSE // = 1000
Don't be frightened by the apparent complexity of this code. Detail doesn't matter here. Note that everything is reduced to four nested IIFEs. And note that the addition is built without any loop structure, which helps to understand the "static behaviour" of logical gates inside a CPU. In these pages 4bit_adder and 8bit_adder is shown how numbers can be added in the range [0..256].
3.3) lists and recursion
Let's add two useful tweened functions
{def NIL {lambda {:a} TRUE}} -> NIL {def NILP {lambda {:p} {:p {lambda {:a :b} FALSE}}}} -> NILP {NILP NIL} -> TRUE {NILP {P}} -> FALSE
It's easy to understand that NILP is a predicate function returning TRUE if given the word NIL and FALSE if given a pair.
Let's compose pairs to build lists ending with NIL.
{def L {CONS hello {CONS brave {CONS new {CONS world NIL}}}}} -> L
Note that a list is just a pair whose second term is a list. It's a first example of recursive data structure. Using the HEAD & TAIL accessors let's get each term and test the rest successively:
. get the first & test the rest
{NILP {L}}
-> FALSE
{HEAD {L}} & {NILP {HEAD {L}}}
-> hello -> FALSE
{HEAD {TAIL {L}}} & {NILP {HEAD {L}}}
-> brave -> FALSE
{HEAD {TAIL {TAIL {L}}}} & {NILP {HEAD {TAIL {L}}}}
-> new -> FALSE
{HEAD {TAIL {TAIL {TAIL {L}}}}} & {NILP {HEAD {TAIL {TAIL {L}}}}}
-> world -> FALSE
{NILP {TAIL {TAIL {TAIL {TAIL {L}}}}}}
-> TRUE
Sounds a recursive process!
We now have everything we need to build a function, DISP, recursively diplaying the content of the list L.
{def DISP {lambda {:l} {{IF {NILP :l} {lambda {:l} } {lambda {:l} {HEAD :l} {DISP {TAIL :l}}}} :l}}} -> DISP {DISP {L}} -> hello brave new world
It's funny, it does work, but how does it work?
This section can be skipped in a first reading. Giving a name to the two inner lambdas in
DISP{def YES {lambda {:l} }} -> YES {def NO {lambda {:l} {HEAD :l} {DISP {TAIL :l}}}} -> NOwe can write a shorter and more readable function so called
SDISP{def SDISP {lambda {:l} {{IF {NILP :l} YES NO} :l}}} -> SDISP {SDISP {L}} -> hello brave new worldNote the double curly braces before
IF. We met it in 3.1) booleans where the chosen lambda YES or NO must be called, here applied to:l. TheSDISPfunction is easy to tracehello brave new world -> {{lambda {:l} {{IF {NILP :l} YES NO} :l}} {L}} -> {{IF {NILP {L}} YES NO} {L}} // {NILP {L}} -> FALSE
-> {{IF FALSE YES NO} {L}} // FALSE -> NO
-> {NO {L}} -> {{lambda {:l} {HEAD :l} {DISP {TAIL :l}}} {L}} -> {HEAD {L}} {DISP {TAIL {L}}} // {HEAD {L}} -> hello
-> hello {DISP {TAIL {L}}} // recurse on {TAIL {L}}and repeated until L: is NIL
-> hello brave new world {{lambda {:l} {{IF {NILP :l} YES NO} :l}} NIL} -> hello brave new world {{IF {NILP NIL} YES NO} NIL} // {NILP NIL} -> TRUE
-> hello brave new world {{IF TRUE YES NO} NIL} // HEAD -> YES
-> hello brave new world {YES NIL} -> hello brave new world {{lambda {:l} } NIL} // -> empty
-> hello brave new world // stop
In short a recursive function is built on such a following pattern
{def RECUR // begin function
{lambda {args} // begin lambda
{ // begin future apply
{IF // begin if
{NILP args} // boolean
{lambda {args} ...} // then base case
{lambda {args} {RECUR ...}} // else recurse
} // end if
args // apply on args
} // end apply
} // end lambda
} // end function
In short the two inner lambdas are first evaluated to two function's reference. As long as {NILP args} returns FALSE the IF functionn leads to the second function's ref, the function is applied to args and the {RECUR ...} recursive block is returned. When {NILP args} returns FALSE the first function's ref is chosen, applied to args and the ... base case is returned. Using inside lambdas prevents evaluations until the good term is chosen.
Now, following the same pattern, we build some more functions working on lists
{def REVERSE {def REVERSE.r // recursive part
{lambda {:a :b} {{IF {NILP :a} {lambda {:a :b} :b} {lambda {:a :b} {REVERSE.r {TAIL :a} {CONS {HEAD :a} :b}}}} :a :b}}} {lambda {:a} {REVERSE.r :a NIL}}} // init and recurse
-> REVERSE {DISP {REVERSE {L}}} -> world new brave hello {def APPEND {def APPEND.r {lambda {:a :b} {{IF {NILP :b} {lambda {:a :b} :a} {lambda {:a :b} {APPEND.r {CONS {HEAD :b} :a} {TAIL :b}}} } :a :b}}} {lambda {:a :b} {APPEND.r {REVERSE :a} :b}}} -> APPEND {DISP {APPEND {L} {REVERSE {L}}}} -> hello brave new world world new brave hello {def LENGTH {lambda {:l} {{IF {NILP :l} {lambda {:l} } {lambda {:l} . {LENGTH {TAIL :l}}}} :l}}} -> LENGTH {LENGTH {L}} -> . . . . // a primitive notation for the number 4
The last function, LENGTH, could lead to a list based arithmetic, beginning with the addition - just APPENDing two lists - and so on. See such an approach in the page meta4. In this page we will choose another approach sketched in the 4.4) arithmetic section.
3.4) the Y-combinator
It may be interesting to know that all these recursive algorithms can be written without using the second special form, def, as true λ calculus expressions exclusively made of words, abstractions and applications. The trouble is that the body of a recursive function contains its name and we need the def second special form to give a name.
Here comes the strange Y-combinator!
Let's focus on the DISP function. We add a new argument, :f, acting as a fix point and build a new almost recursive function, ADISP, which will be called by some magic Y combinator acting as a bridge.
1) adding a new argument, the fix-point: {def ADISP {lambda {:f :l} {{IF {NILP :l} {lambda {:f :l} } {lambda {:f :l} {HEAD :l} {:f :f {TAIL :l}}}} :f :l}}} -> ADISP 2) defining the bridge: {def Y {lambda {:f} {:f :f}}} // :f is applied to itself
-> Y p 3) composing boths: {{Y ADISP} {L}} // ADISP is given as the fix point
-> hello brave new world
Got it? We have replaced a global definition, DISP, by a local one, :f, and have defined a very small function acting as a bridge, the Y-combinator. Exit the global name. Now we can go further and glue Y and ADISP into a single one YDISP:
{def YDISP {lambda {:l} {{{lambda {:f} {:f :f}} {lambda {:f :l} {{IF {NILP :l} {lambda {:f :l} } {lambda {:f :l} {HEAD :l} {:f :f {TAIL :l}}}} :f :l}}} :l}}} -> YDISP {YDISP {L}} -> hello brave new world
We can even forget the name YDISP, building an IIFE:
{{lambda {:l} {{{lambda {:f} {:f :f}} {lambda {:f :l} {{IF {NILP :l} {lambda {:f :l} } {lambda {:f :l} {HEAD :l} {:f :f {TAIL :l}}}} :f :l}}} :l}} {L}} -> hello brave new world
and finally, replacing every names by their lambda expressions recalled below
{def TRUE {lambda {:a :b} :a}} {def FALSE {lambda {:a :b} :b}} {def IF {lambda {:c :a :b} {:c :a :b}}} {def CONS {lambda {:a :b :c} {:c :a :b}}} {def HEAD {lambda {:p} {:p TRUE}}} {def TAIL {lambda {:p} {:p FALSE}}} {def NIL {lambda {:a} TRUE}} {def NILP {lambda {:p} {:p {lambda {:a :b} FALSE}}}} {def L {{lambda {:a :b :c} {:c :a :b}} hello {{lambda {:a :b :c} {:c :a :b}} brave {{lambda {:a :b :c} {:c :a :b}} new {{lambda {:a :b :c} {:c :a :b}} world {lambda {:a} {lambda {:a :b} :a}}}}}}}
we get this deeply nested expression
{{lambda {:l} {{{lambda {:f} {:f :f}} {lambda {:f :l} {{{lambda {:c :a :b} {:c :a :b}} {{lambda {:p} {:p {lambda {:a :b} {lambda {:a :b} :b}}}} :l} {lambda {:f :l} } {lambda {:f :l} {{lambda {:p} {:p {lambda {:a :b} :a}}} :l} {:f :f {{lambda {:p} {:p {lambda {:a :b} :b}}} :l}}}} :f :l}}} :l}} {{lambda {:a :b :c} {:c :a :b}} hello {{lambda {:a :b :c} {:c :a :b}} brave {{lambda {:a :b :c} {:c :a :b}} new {{lambda {:a :b :c} {:c :a :b}} world {lambda {:a} {lambda {:a :b} :a}}}}}}} -> hello brave new world
Nothing but a deeply nested composition of abstractions and applications working on words, in a pure λ-calculus style. And it's not magic, it's just text substitution.
Note: According to Wikipedia "A Turing machine is a mathematical model of computation that defines an abstract machine which manipulates symbols on a strip of tape according to a table of rules."
I guess that storing the two processes abstraction and application in a Turing's machine table of rules and writing the previous expression on its stripe should display: hello brave new world.
You could see how the Universal Turing Machine can be written using plain lambdatalk in this page tm.
4) applications
Until now, bear in mind that we used nothing but lambdas & defs. We defined pairs, lists and a loop mechanism, recursion, to play with.
Let's go a little further, reducing explanations to a bare minimum in order to keep this page short and not be buried in details. The goal is to understand how apparently unreachable algorithms - at least at this level - can be defined as a direct application of the powerful pattern we have just defined, the recursion.
4.1) towers of hanoï
A set of n disks of decreasing size are stacked on a rod. The game consists in deplacing each disk to a second rod via a third one in respect of the following rule, "never put a disk on a smaller one ". The code is built on a doubly recursive function. Because numbers are not defined at this level (see arithmetic later) the set of disks will be represented by the list of 5 items L defined in section 3).
{def HANOI {lambda {:n :from :to :via} {{IF {NILP :n} {lambda {:n :from :to :via} } {lambda {:n :from :to :via} {HANOI {TAIL :n} :from :via :to} {br} move {LENGTH :n} from tower :from to tower :to {HANOI {TAIL :n} :via :to :from} }} :n :from :to :via}}} -> HANOI {HANOI {L} A B C} -> // four disks and three rods
move . from tower A to tower C
move . . from tower A to tower B
move . from tower C to tower B
move . . . from tower A to tower C
move . from tower B to tower A
move . . from tower B to tower C
move . from tower A to tower C
move . . . . from tower A to tower B
move . from tower C to tower B
move . . from tower C to tower A
move . from tower B to tower A
move . . . from tower C to tower B
move . from tower A to tower C
move . . from tower A to tower B
move . from tower C to tower B
Note that the line "{br} move {l.length :n} from tower :from to tower :to" contains a constant, {br}, which is supposed not to be known at this level. It's an HTMLelement used to break lines and produce a readable display. We could forget it.
4.2) the hilbert's curve
This is an example of two mutually recursive functions, LEFT and RIGHT, used to produce a sequence of moves and turns sent to a graphical function turtle, an external device.
{def LEFT {lambda {:d :n} {{IF {NILP :n} {lambda {:d :n} } {lambda {:d :n} T90 {RIGHT :d {TAIL :n}} M:d T-90 {LEFT :d {TAIL :n}} M:d {LEFT :d {TAIL :n}} T-90 M:d {RIGHT :d {TAIL :n}} T90 }} :d :n}}} -> LEFT {def RIGHT {lambda {:d :n} {{IF {NILP :n} {lambda {:d :n} } {lambda {:d :n} T-90 {LEFT :d {TAIL :n}} M:d T90 {RIGHT :d {TAIL :n}} M:d {RIGHT :d {TAIL :n}} T90 M:d {LEFT :d {TAIL :n}} T-90 }} :d :n}}} -> RIGHT
We build a Hilbert curve until the 5th depth using a list containing 5 dots
{def H5 {CONS . {CONS . {CONS . {CONS . {CONS . NIL}}}}}} -> H5
Calling {LEFT 10 {H5}} produces a sequence of 2387 words starting with T90 T-90 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 ...
These words are sent to a SVG graphical "device" which understands M & T as drawing procedures called on numbers 10, 90, -90:
{{SVG} {curve #000 5 5 0 {LEFT 10 {H5}}} } with: {def SVG svg {@ width="320" // standard HTML syntax
height="320" style="box-shadow:0 0 8px #000;"}} -> SVG {def curve {lambda {:c :s} {path {@ d="M {turtle :s}" // standard SVG syntax
stroke=":c" stroke-width="1" fill="transparent"}} }} -> curve
which displays
4.3) fractal trees
{def TREE {lambda {:e :s :k :a :b} {{IF {NILP :k} {lambda {:e :s :k :a :b} T-30 M:e T120 M:e T120 M:e T150} {lambda {:e :s :k :a :b} M:s T:a {TREE :e :s {TAIL :k} :a :b} T-:a T-:b {TREE :e :s {TAIL :k} :a :b} T:b M-:s}} :e :s :k :a :b}}} -> TREE
Calling {tree 10 50 {H5} 45 45} produces 410 words starting with M50 T45 M50 T45 M50 T45 M50 T45 M50 T45 T-30 M10 T120 M10 T120 M10 .... These words are sent to the SVG graphical "device" which understands M & T as drawing procedures called on numbers 50, 45, -30, 10, ....
And writing
{{SVG} {curve #f00 150 250 180 {TREE 10 50 {H5} 45 45}} {curve #0f0 160 290 180 {TREE 10 60 {H5} 30 50}} {curve #00f 140 310 180 {TREE 10 60 {H5} 20 50}} }
we get
See also fern.
4.4) arithmetic
Note that, until now, except in the outer devices used to display graphics, we never used numbers which don't exist at the λ-calculus level. Let's build them from scratch.
This is how Giuseppe Peano defines the infinite set of natural numbers:
N = {0, succ(0), succ(succ(0)), ...}
How can we implement that? See meta5 for natural numbers implemented as lists. This is how Alonzo Church encodes 0 and the successor function:
{def ZERO FALSE} -> ZERO {def SUCC {lambda {:n :f :x} {:f {:n :f :x}}}} -> SUCC
Let's define the first natural numbers
{def ONE {SUCC {ZERO}}} -> ONE {def TWO {SUCC {ONE}}} -> TWO {def THREE {SUCC {TWO}}} -> THREE {def FOUR {SUCC {THREE}}} -> FOUR {def FIVE {SUCC {FOUR}}} -> FIVE {def SIX {SUCC {FIVE}}} -> SIX ...
Displaying numbers as functions looks like _LAMB_xxx and it's not sexy, so we need a helper function to display Church numbers as decimal integers
{def CHURCH {lambda {:n} {:n {lambda {:x} {+ :x 1}} 0}}} -> CHURCH {CHURCH {ZERO}} -> 0 {CHURCH {ONE}} -> 1 ... {CHURCH {SIX}} -> 6
Note that replacing {lambda {:n} {:n {lambda {:x} {+ :x 1}} 0}} by {lambda {:n} {:n {lambda {:x} . :x} _}}, a function which doesn't use javascript maths, (+ 0 1), supposed not to be available at this level, numbers would be displayed as lists of dots with an ending "_". For instance SIX would be displayed as ". . . . . . _", it's a matter of choice.
After the SUCC function we need a function to get the PREDecessor of a number
{def PRED {lambda {:n} {HEAD {{:n {lambda {:p} {CONS {TAIL :p} {SUCC {TAIL :p}}}}} {CONS {ZERO} {ZERO}}}}}} -> PRED {CHURCH {PRED {TWO}}} -> 1 {CHURCH {PRED {ONE}}} -> 0 {CHURCH {PRED {ONE}}} -> 0 // nothing exists before ZERO
And a predicate function testing if a number is ZERO
{def ZEROP {lambda {:n} {:n {lambda {:x} FALSE} TRUE}}} -> ZEROP {ZEROP {ZERO}} -> TRUE {ZEROP {ONE}} -> FALSE
We can now build a first set of basic operators
{def ADD {lambda {:n :m :f :x} {{:n :f} {:m :f :x}}}} -> ADD {CHURCH {ADD {TWO} {FIVE}}} -> 7 {def SUB {lambda {:m :n} {{:n PRED} :m}}} -> SUB {CHURCH {SUB {FIVE} {TWO}}} -> 3 {def MUL {lambda {:n :m :f :x} {:n {:m :f} :x}}} -> MUL {CHURCH {MUL {TWO} {FIVE}}} -> 10 {def POW {lambda {:n :m :f :x} {{:m :n :f} :x}}} -> POW {CHURCH {POW {TWO} {FIVE}}} -> 32 {def IFAC {lambda {:n} {TAIL {{:n {lambda {:p} {CONS {SUCC {HEAD :p}} {MUL {HEAD :p} {TAIL :p}}}}} {CONS {ONE} {ONE}}}}}} -> IFAC {CHURCH {IFAC {SIX}}} // 6!
-> 720 {CHURCH {IFAC {MUL {TWO} {FOUR}}}} // 8!
-> 40320
Note that pairs are used in the definition of the PRED and IFAC functions, a "trick" due to a student of Alonzo Church, Stephen Cole Kleene. All previous functions are built on iterative processes, Church numbers are iterators per se.
We are going to use recursion to define an alternative version of the factorial, RFAC, the euclidean division DIV, the modulo function MOD and the greater common divisor GCD.
{def RFAC {lambda {:n} {{IF {ZEROP :n} {lambda {:n} {ONE}} {lambda {:n} {MUL :n {RFAC {PRED :n}}}}} :n}}} -> RFAC {CHURCH {RFAC {SIX}}} // 6!
-> 720 {CHURCH {RFAC {MUL {TWO} {FOUR}}}} // 8!
-> 40320 {def DIV {lambda {:a :b} {{IF {ZEROP {SUB :b :a}} {lambda {:a :b} {ADD {ONE} {DIV {SUB :a :b} :b}}} {lambda {:a :b} {ZERO}}} :a :b}}} -> DIV {CHURCH {DIV {FOUR} {TWO}}} -> 2 {CHURCH {DIV {FOUR} {THREE}}} -> 1 {def MOD {lambda {:a :b} {SUB :a {MUL {DIV :a :b} :b}}}} -> MOD {CHURCH {MOD {FOUR} {TWO}}} -> 0 {CHURCH {MOD {FOUR} {THREE}}} -> 1 {def GCD {lambda {:a :b} {{IF {ZEROP :b} {lambda {:a :b} :a} {lambda {:a :b} {GCD :b {MOD :a :b}}}} :a :b}}} -> GCD {CHURCH {GCD {IFAC {FIVE}} {THREE}}} -> 3 // 1*2*3*4*5 = 120 -> gcd(120,3) = 3
{CHURCH {GCD {IFAC {FOUR}} {FIVE}}} -> 1 // 1*2*3*4 = 24 -> gcd(24,5) = 1
4.5) range, map, reduce
A functional progamming language without map & reduce misses something.
{def RANGE {lambda {:a :b} {{IF {ZEROP {SUB :b :a}} {lambda {:a :b} {CONS :b NIL}} {lambda {:a :b} {CONS :a {RANGE {SUCC :a} :b}} }} :a :b}}} -> RANGE {def MAP {lambda {:f :l} {{IF {NILP :l} {lambda {:f :l} NIL} {lambda {:f :l} {CONS {:f {HEAD :l}} {MAP :f {TAIL :l}}}}} :f :l}}} -> MAP {def TEN {MUL {TWO} {FIVE}}} = TEN {DISP {MAP CHURCH {RANGE {ONE} {TEN}}}} -> 1 2 3 4 5 6 7 8 9 10 {DISP {MAP {lambda {:n} {CHURCH {POW {TWO} :n}}} {RANGE {ONE} {SIX}}}} -> 2 4 8 16 32 64 {DISP {MAP {lambda {:n} {CHURCH {IFAC :n}}} {RANGE {ONE} {SIX}}}} -> 1 2 6 24 120 720 {def REDUCE {def REDUCE.r {lambda {:f :a :b} {{IF {NILP :a} {lambda {:f :a :b} :b} {lambda {:f :a :b} {:f {HEAD :a} {REDUCE.r :f {TAIL :a} :b}}}} :f :a :b}}} {lambda {:f :a} {REDUCE.r :f :a {ZERO}}}} -> REDUCE {CHURCH {REDUCE ADD {ZERO} {RANGE {ONE} {TEN}}}} -> 55 // {+ 1 2 3 4 5 6 7 8 9 10}
{CHURCH {REDUCE MUL {ONE} {RANGE {ONE} {SIX}}}} -> 720 // {* 1 2 3 4 5 6}
4.6) the left factorial
As an application of RANGE, MAP & REDUCE we compute the left factorial !n defined as the sum of the factorials
!n = Σi=0i=n-1(i!) = 0! + 1! + 2! + 3! ... + (n-1)
{def LFAC {lambda {:n} {{IF {ZEROP :n} {lambda {:n} {ZERO}} {lambda {:n} {REDUCE ADD {ONE} {MAP {lambda {:n} {REDUCE MUL {ONE} {RANGE {ONE} :n}}} {RANGE {ONE} {PRED :n}}}}}} :n}}} -> LFAC {CHURCH {LFAC {TEN}}} -> 409114 // 5770ms
{DISP {MAP CHURCH {MAP LFAC {RANGE {ZERO} {TEN}}}}} -> 0 1 2 4 10 34 154 874 5914 46234 409114
conclusion
The read & replace process implemented in lambdatalk makes its evaluator working close to the raw code, a string. It follows two steps:
{def hypo {lambda {:x :y} {sqrt {+ {* :x :x} {* :y :y}}}}} -> {def hypo LAMB_123} -> hypo
{hypo 3 4} -> {{lambda {:x :y} {sqrt {+ {* :x :x} {* :y :y}}}} 3 4} -> {sqrt {+ {* 3 3} {* 4 4}}} -> {sqrt {+ 9 16}} -> {sqrt 25} -> 5
Note that lambdas are also created and evaluated in the application step, in the case of partial applications.
During the first step, the raw code (the initial string) is immediately reduced to a smaller sequence of words, some of which are pointers to functions that contain substrings that contain pointers to functions ... and so on, recursively.
During the second step, it is in this tree of strings and substrings that the evaluations of normal (nested) forms are carried out independently. It's the reason why the computation of a slow computing extensive function inserted in the middle of a page of one million words is not affected by its length. And since functions are really independent of any context - no lexical context, no closure - one could even think of a parallel evaluation, for instance defining lambdas (at least some of them) as web-workers given for free by web browsers.
It's all reminiscent of a Turing machine, with its infinite stripe on which a window comes and goes...
And so what?
What do we care about a language reduced to a dialect of this brave old λ-calculus nobody on earth would use in real life?
In real life {lambda talk} is not lost in an empty space.
He is living in a tiny wiki, {lambda tank}, a dwarf installed on top of shoulders of giants, the modern web browsers, and takes benefit from the powerful web technologies they bring for free and from the huge eco-system at their fingertips.
Lambdatalk comes with a dictionary full of Javascript primitives which can help to break the glass ceiling of the λ-calculus, sentences, arrays, math, html/css, .... For instance, using pure and basic HTML/CSS, it's straightforward to define a function positionning a colored rectangle in the browser's window
{def rgb {lambda {:y :x :w :h :c} {div {@ style="position:absolute; // standard CSS rules
top::ypx; left::xpx; width::wpx; height::hpx; background::c; border:5px solid #444;"}}}} -> rgb
and call it in a global container
{div {@ style="position:relative; top:0; left:0; width:310px; height:310px; margin:auto; background:#444;"} {rgb 10 50 200 200 #f00} {rgb 90 10 200 200 #0f0} {rgb 50 90 200 200 #00f} {rgb 50 90 160 160 #f0f} {rgb 90 50 35 120 #ff0} {rgb 215 90 120 35 #0ff} {rgb 90 90 120 120 #fff} }
to display directly in the browser's window the following graphic
Lambdatalk is not limited to two special forms, [lambda & def], the full set contains nine special forms
[ lambda def let if quote macro script style require ]
The {let { {var val} ... } expression} special form is a syntactic sugar for this one {{lambda {var ...} expression} val ...}, which is our well known IIFE, introducing blocks with local variables.
For instance instead of writing this long IIFE
{{lambda {:sqr :x :y} // applying a lambda
{sqrt {+ {:sqr :x} {:sqr :y}}}} {lambda {:x} {* :x :x}} // to an anonymous function
3 4} // and two values
-> 5
you should better write
{let { // 1) define local functions and vars
{:sqr {lambda {:x} {* :x :x}}} // sqr = function(x) { return x*x }
{:x 3} // x = 3
{:y 4} // y = 4
} {sqrt {+ {:sqr :x} {:sqr :y}}} // 2) and compute
} -> 5
enlighting two local variables, x & y, and a local function, sqr.
The {if bool then one else two} special form helps to write algorithms more easily and much more efficient, for instance the factorial of a big number:
{def fac {lambda {:n} {if {< :n 1} then 1 else {long_mult :n {fac {- :n 1}}}}}} -> fac {fac 500} -> 1220136825991110068701238785423046926253574342803192842192413588385845373153881997605496447502203281863013616477148203584163378722078177200480785205159329285477907571939330603772960859086270429174547882424912726344305670173270769461062802310452644218878789465754777149863494367781037644274033827365397471386477878495438489595537537990423241061271326984327745715546309977202781014561081188373709531016356324432987029563896628911658974769572087926928871281780070265174507768410719624390394322536422605234945850129918571501248706961568141625359056693423813008856249246891564126775654481886506593847951775360894005745238940335798476363944905313062323749066445048824665075946735862074637925184200459369692981022263971952597190945217823331756934581508552332820762820023402626907898342451712006207714640979456116127629145951237229913340169552363850942885592018727433795173014586357570828355780158735432768888680120399882384702151467605445407663535984174430480128938313896881639487469658817504506926365338175055478128640000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Arrays are powerful data structures added to the lambdatalk's dictionary. The following set of functions uses the de casteljau algorithm
{def CASTEL.interpol {lambda {:p0 :p1 :t} {A.new {+ {* {A.get 0 :p0} {- 1 :t}} {* {A.get 0 :p1} :t}} {+ {* {A.get 1 :p0} {- 1 :t}} {* {A.get 1 :p1} :t}} } }} {def CASTEL.sub {lambda {:arr :acc :t} {if {< {A.length :arr} 2} then :acc else {CASTEL.sub {A.rest :arr} {A.addlast! {CASTEL.interpol {A.get 0 :arr} {A.get 1 :arr} :t} :acc} :t} }}} {def CASTEL.split {lambda {:arr :acc :t :lr} {if {< {A.length :arr} 1} then :acc else {CASTEL.split {CASTEL.sub :arr {A.new} :t} {if :lr then {A.addlast! {A.first :arr} :acc} else {A.addfirst! {A.last :arr} :acc} } :t :lr} }}} {def CASTEL.stretch {lambda {:arr :t0 :t1} {CASTEL.split {CASTEL.split :arr {A.new} :t0 false} {A.new} :t1 true}}} {def CASTEL.blossom {lambda {:arr :n} {if {< :n 1} then :arr else {A.new {CASTEL.blossom {CASTEL.split :arr {A.new} 0.5 true} {- :n 1}} {CASTEL.blossom {CASTEL.split :arr {A.new} 0.5 false} {- :n 1}} }}}} {def p0 {A.new 50 60}} -> {p0} {def p1 {A.new 100 200}} -> {p1} {def p2 {A.new 300 200}} -> {p2} {def p3 {A.new 200 280}} -> {p3}
to display these Bézier curves
See also in this page bezier how can be plotted a Bézier curve out of any canvas or svg frame.
Finally useful libraries can be created inline (or borrowed from external sources) to do much more:
You can compare lambdatalk and some other languages, analyzing about 190 tasks in the rosettacode.org web site.
You could also compare this paper to
and analyze the way are introduced basic concepts, booleans, pairs, recursion, numbers. Your opinion is welcome.
Not forgetting that everything was written and evaluated in real time in any modern web browser, via a small engine without any external dependancy, coming as a single 50kb zipped folder easy to install in any web host provider.
But it's another story which can be discovered in the {lambda way} project's workshop.
Alain Marty (2020/03/29 last update 2020/09/06)