+
1
|
skin
|
login
|
edit
workshop
::
NIL
user:anonymous
{center _h1 शून्य | النيل | אפסי | NIL} {center _h3 See also [[NIL2]]} {img {@ src="data/coca_cola.jpg" width="100%" title="You should drink water!"}} {center {h4 '{def NIL {lambda {f g} g}}}} _p This is an approach of the {b [[λ-calculus|http://jwodder.freeshell.org/lambda.html]]} using a minimal subset of the '{lambda talk} syntax and enlighting the power of {b NIL} as a terminal operator in {b recursive} processes. Following the pure λ-calculus, a valid expression is made of a reduced set of nested terms, [{b words, abstractions, applications}] and is evaluated to {b words}. More precisely: {pre {WRAP} {b 1 word}: any character(s) except spaces and curly braces, {b '{}} {b 2 abstraction}: '{lambda {words} expression} {b 3 application}: '{expressions1 expression2} } {pre {WRAP} 1. a {b word} is a group of any characters except spaces and curly braces '{}, and stands for itself, ie is its own value, } {pre {WRAP} 2. an {b abstraction}, a special form written {b '{lambda {words} expression}}, is evaluated into a word bound to an anonymous function selecting words (arguments) in expression (body) to be replaced by some future given words (values), } {pre {WRAP} 3. an {b application}, a nested form written {b '{expression1 expression2}}, determines if expression1 is bound to a function then evaluates expression2 into words2 and applies that function to words2, } _p For convenience we add a second special form, {b definition}, with which users can create constants and give a name to anonymous functions {pre {WRAP} 4. a {b definition}, a special form written '{def word expression}, first evaluates expression into words then binds word to these words. } _p Anonymous functions and user defined constants and functions are stored in a single dictionary initially empty. {b Abstractions} and {b definitions} are {b special forms} caught and evaluated before {b applications}. They can be nested. {b Applications} are {b simple forms} evaluated {b from inside out}. Functions don't create closures but accept {i de facto} partial calls, memorizing the given values and returning a new function waiting for the rest. _p Let's see what can be done with so little. _h3 1. words _p Out of braces words are not evaluated. Contrary to most of programming languages, quoting sequences of words is useless, as in HTML syntax and any text or spreadsheet editor. {pre Hello World -> Hello World } _p Sequences of words can be given a name {pre '{def HI Hello World} -> {def HI Hello World} HI, I just say '{HI} -> HI, I just say {HI} } _p Note that writing {b HI} displays {b HI}. You must write {b '{HI}} to get its value, {b {HI}}. In a spreadsheet writing {b PI} displays {b PI}, writing {b =PI()} displays {b {PI}}. _p Anonymous functions can be created and immediately called {pre '{{lambda {fruit unknown} The color of fruits is unknown.} apple green} -> {{lambda {fruit unknown} The color of fruits is unknown.} apple green} } _p This {b IIFE}, (Immediately Invoked Function Expression), can be seen as a {b shorthand} for {pre {b replace} "fruit" and "unknown" {b in} "The color of fruits is unknwon." {b by} "apple" and "green" } _p Nothing magic here! To make things easier, anonymous functions can be given a name and called by this name {pre '{def AFFIRMATION {lambda {fruit unknown} The color of fruits is unknown.}} -> {def AFFIRMATION {lambda {fruit unknown} The color of fruits is unknown.}} '{AFFIRMATION apple green} -> {AFFIRMATION apple green} '{AFFIRMATION banana yellow} -> {AFFIRMATION banana yellow} } _h3 2. data structures _p Lambdas can be {b nested and partially called}, allowing to build data structures and their associated selectors, beginning with {b pairs} {pre '{def PAIR {lambda {:x :y :z} {:z :x :y}}} -> {def PAIR {lambda {:x :y :z} {:z :x :y}}} '{def LEFT {lambda {:z} {:z {lambda {:x :y} :x}}}} -> {def LEFT {lambda {:z} {:z {lambda {:x :y} :x}}}} '{def RIGHT {lambda {:z} {:z {lambda {:x :y} :y}}}} -> {def RIGHT {lambda {:z} {:z {lambda {:x :y} :y}}}} '{LEFT {PAIR Hello World}} -> {LEFT {PAIR Hello World}} '{RIGHT {PAIR Hello World}} -> {RIGHT {PAIR Hello World}} } {center {note_start pair Fine, but how does it works?}} {note_end {@ id="pair"} {blockquote _p Let's trace the first call, {code '{LEFT {PAIR Hello World}} -> Hello} {pre '{{lambda {:c} {:c {lambda {:a :b} :a}}} {{lambda {:a :b :c} {:c :a :b}} Hello World}} -> {{lambda {:c} {:c {lambda {:a :b} :a}}} {{lambda {:a :b :c} {:c :a :b}} Hello World}} _h6 1) abstractions are evaluated first and create anonymous functions 1: '{lambda {:a :b} :a} -> {def abstract_0 {lambda {:a :b} :a}} '{{lambda {:c} {:c abstract_0}} {{lambda {:a :b :c} {:c :a :b}} Hello World}} -> {{lambda {:c} {:c abstract_0}} {{lambda {:a :b :c} {:c :a :b}} Hello World}} 2: '{lambda {:c} {:c abstract_0}} -> {def abstract_1 {lambda {:c} {:c abstract_0}}} '{abstract_1 {{lambda {:a :b :c} {:c :a :b}} Hello World}} -> {abstract_1 {{lambda {:a :b :c} {:c :a :b}} Hello World}} 3: '{lambda {:a :b :c} {:c :a :b}} -> {def abstract_2 {lambda {:a :b :c} {:c :a :b}}} '{abstract_1 {abstract_2 Hello World}} -> {abstract_1 {abstract_2 Hello World}} 4: '{lambda {:c} {:c Hello World}} -> {def abstract_3 {lambda {:c} {:c Hello World}}} '{abstract_1 abstract_3} -> {abstract_1 abstract_3} 5: '{{lambda {:c} {:c abstract_0}} abstract_3} -> {{lambda {:c} {:c abstract_0}} abstract_3} _h6 2) then applications are evaluated using the anonymous functions 6: '{abstract_3 abstract_0} -> {abstract_3 abstract_0} 7: '{{lambda {:c} {:c Hello World}} abstract_0} -> {{lambda {:c} {:c Hello World}} abstract_0} 8: '{abstract_0 Hello World} -> {abstract_0 Hello World} 9: '{{lambda {:a :b} :a} Hello World} -> {{lambda {:a :b} :a} Hello World} 10: Hello 11: no more curly braces -> stop! } }} _p Functions' arguments are used as regular expressions in the internal replacement process of lambdas. In order to avoid unwanted substitutions, we will systematically prefix arguments with a colon, {b :args}. The key point being that {i the intersection of arguments must be {b null}}, the best would be to bracket them between two colons, {b :args:}. _p Using pairs, we can build {b trees} and {b lists}, and {b manually} get their elements {pre '{def LIST {PAIR Hello {PAIR brave {PAIR new {PAIR World NIL}}}}} // more about NIL later -> {def LIST {PAIR Hello {PAIR brave {PAIR new {PAIR World NIL}}}}} '{LEFT {LIST}} -> {LEFT {LIST}} '{LEFT {RIGHT {LIST}}} -> {LEFT {RIGHT {LIST}}} '{LEFT {RIGHT {RIGHT {LIST}}}} -> {LEFT {RIGHT {RIGHT {LIST}}}} '{LEFT {RIGHT {RIGHT {RIGHT {LIST}}}}} -> {LEFT {RIGHT {RIGHT {RIGHT {LIST}}}}} } _p Two useful functions will help to go further, {b NIL} and {b ISNIL} {pre '{def NIL {lambda {:f :x} :x}} -> {def NIL {lambda {:f :x} :x}} '{def ISNIL {lambda {:n} {:n {lambda {:x} RIGHT} LEFT}}} -> {def ISNIL {lambda {:n} {:n {lambda {:x} RIGHT} LEFT}}} } _p Note that {b NIL} could be written {b NULL, ZERO, -1, '(), النيل, CocaCola}. Let's test: {pre '{NIL foo bar} -> {NIL foo bar} '{ISNIL NIL} -> {ISNIL NIL} '{ISNIL LEFT} -> {ISNIL LEFT} '{ISNIL RIGHT} -> {ISNIL RIGHT} '{ISNIL {LIST}} -> {ISNIL {LIST}} '{ISNIL {RIGHT {LIST}}} -> {ISNIL {RIGHT {LIST}}} '{ISNIL {RIGHT {RIGHT {LIST}}}} -> {ISNIL {RIGHT {RIGHT {LIST}}}} '{ISNIL {RIGHT {RIGHT {RIGHT {LIST}}}}} -> {ISNIL {RIGHT {RIGHT {RIGHT {LIST}}}}} '{ISNIL {RIGHT {RIGHT {RIGHT {RIGHT {LIST}}}}}} -> {ISNIL {RIGHT {RIGHT {RIGHT {RIGHT {LIST}}}}}} } _p Here {b LEFT} and {b RIGHT} can be seen as booleans {b TRUE} and {b FALSE}. _h3 3. recursion _p Thanks to the {b NIL} terminal operator and the predicate function {b ISNIL}, we can define a recursive process to {b automatically} display the elements of a list {pre '{def LIST.DISPLAY {lambda {:list} {{{ISNIL :list} {PAIR {lambda {:list} } {lambda {:list} {LEFT :list} {LIST.DISPLAY {RIGHT :list}}}}} :list}}} -> {def LIST.DISPLAY {lambda {:list} {{{ISNIL :list} {PAIR {lambda {:list} } {lambda {:list} {LEFT :list} {LIST.DISPLAY {RIGHT :list}}}}} :list }}} '{LIST.DISPLAY {LIST}} -> {LIST.DISPLAY {LIST}} } _p Note how lambdas introduce a "zest" of {b lazyness} in an applicative order (call by value) evaluation. Depending on list, {b ISNIL} returns {b LEFT} or {b RIGHT} and selects the first or the second term of {b PAIR}, abstracted from evaluation. Then the selected lambda is applied on list, triggering the evaluation. _p So, thanks to the data structure [PAIR, LEFT, RIGHT] and a "zest" of lambdas , we could define a {b recursive algorithm} without any {b '{IF THEN ELSE}} boolean special form, not to speak of any strange {b Y-combinator} {sup more later}. _p We can also apply a recursive process to count words in this list. But until now '{lambda talk} doesn't know anything about numbers. A workaround is to use a primitive {b unary numeral notation}, {b [ , |, ||, |||, ||||, ... ]} to display numbers as pipes {pre '{def LIST.SIZE {lambda {:list} {{{ISNIL :list} {PAIR {lambda {:list} } {lambda {:list} | {LIST.SIZE {RIGHT :list}}}}} :list}}} -> {def LIST.SIZE {lambda {:list} {{{ISNIL :list} {PAIR {lambda {:list} } {lambda {:list} |{LIST.SIZE {RIGHT :list}}}}} :list}}} '{LIST.SIZE {LIST}} -> {LIST.SIZE {LIST}} // read the number {b 4} } _p Ok, obviously we need numbers! _h3 4. numbers _p Until now datas are nothing but words. After Giuseppe Peano and Alonzo CHURCH, we can define the ordered set of natural number, {b N}, as some element, called {b ZERO}, and its successors via a function {b SUCCessor} {center {pre {b n} is '{SUCC {SUCC {SUCC ... n times ...{ZERO}}}}}} {pre '{def SUCC {lambda {:n :f :x} {:f {{:n :f} :x}}}} -> {def SUCC {lambda {:n :f :x} {:f {{:n :f} :x}}}} } _p We define natural numbers as constants {pre '{def ZERO NIL} -> {def ZERO NIL} // ZERO is equivalent to NIL '{def ONE {SUCC {ZERO}}} -> {def ONE {SUCC {ZERO}}} '{def TWO {SUCC {ONE}}} -> {def TWO {SUCC {ONE}}} '{def THREE {SUCC {TWO}}} -> {def THREE {SUCC {TWO}}} '{def FOUR {SUCC {THREE}}} -> {def FOUR {SUCC {THREE}}} '{def FIVE {SUCC {FOUR}}} -> {def FIVE {SUCC {FOUR}}} ... and so on } _p Calling {b '{FIVE}} returns {FIVE}, it's the reference of an anonymous function and it's not readable. At this point, without nothing but words, abstractions and applications, we could display numbers in the primitive {b unary numeral notation} seen before, {b [ ', '|, '||, '|||, '||||, ... ]}. But for a better readability, forgetting that JS numbers and the + operator are not supposed to exist at this point, we will also define a function {b DECIM} displaying numbers in a more modern and familiar {b decimal notation}, {b [ 0, 1, 2, 3, 4, ... ]}. {pre '{def CHURCH {lambda {:n} {{:n {lambda {:x} :x|}} '}}} -> {def CHURCH {lambda {:n} {{:n {lambda {:x} :x|}} '}}} '{def DECIM {lambda {:n} {{:n {lambda {:x} {+ :x 1}}} 0}}} -> {def DECIM {lambda {:n} {{:n {lambda {:x} {+ :x 1}}} 0}}} '{CHURCH {ZERO}} -> {CHURCH {ZERO}} or '{DECIM {ZERO}} -> {DECIM {ZERO}} '{CHURCH {ONE}} -> {CHURCH {ONE}} or '{DECIM {ONE}} -> {DECIM {ONE}} '{CHURCH {TWO}} -> {CHURCH {TWO}} or '{DECIM {TWO}} -> {DECIM {TWO}} '{CHURCH {THREE}} -> {CHURCH {THREE}} or '{DECIM {THREE}} -> {DECIM {THREE}} '{CHURCH {FOUR}} -> {CHURCH {FOUR}} or '{DECIM {FOUR}} -> {DECIM {FOUR}} '{CHURCH {FIVE}} -> {CHURCH {FIVE}} or '{DECIM {FIVE}} -> {DECIM {FIVE}} } _p Church numbers are {b iterators} and we can easily build a first set of operators, [{b ADDition, MULTiplication, POWER}] {pre '{def ADD {lambda {:n :m :f :x} {{:n :f} {{:m :f} :x}}}} -> {def ADD {lambda {:n :m :f :x} {{:n :f} {{:m :f} :x}}}} '{def MULT {lambda {:n :m :f :x} {:n {:m :f} :x}}} -> {def MULT {lambda {:n :m :f :x} {:n {:m :f} :x}}} '{def POWER {lambda {:n :m :f :x} {{:m :n :f} :x}}} -> {def POWER {lambda {:n :m :f :x} {{:m :n :f} :x}}} '{CHURCH {ADD {TWO} {THREE}}} -> {CHURCH {ADD {TWO} {THREE}}} // 5 '{CHURCH {MULT {TWO} {THREE}}} -> {CHURCH {MULT {TWO} {THREE}}} // 6 '{CHURCH {POWER {TWO} {THREE}}} -> {CHURCH {POWER {TWO} {THREE}}} // 8 } _p Building opposite operators like [{b PREDecessor, SUBTRACTion, DIVision}] is not so easy, and {b Church} himself avoided them in the primitive version of λ-calculus. The answer was given by {b Stephen Cole Kleene}, the father of {b Regular Expressions}: « {i Church numbers can be used to iterate and pairs to aggregate.} » So, following this scheme {pre 1: [0,0] -> [0,0+1] 2: [0,1] -> [1,1+1] 3: [1,2] -> [2,2+1] 4: [2,3] -> [3,3+1] {b 5}: [3,4] -> [{b 4},4+1] -> {b 4} } _p we define the {b PRED} and {b SUBTRACT} operators {pre '{def PRED {def PRED.PAIR {lambda {:p} {PAIR {RIGHT :p} {SUCC {RIGHT :p}}}}} {lambda {:n} {LEFT {{:n PRED.PAIR} {PAIR {ZERO} {ZERO}}}}}} -> {def PRED {def PRED.PAIR {lambda {:p} {PAIR {RIGHT :p} {SUCC {RIGHT :p}}}}} {lambda {:n} {LEFT {{:n PRED.PAIR} {PAIR {ZERO} {ZERO}}}}}} '{def SUBTRACT {lambda {:m :n} {{:n PRED} :m}}} -> {def SUBTRACT {lambda {:m :n} {{:n PRED} :m}}} '{CHURCH {PRED {ZERO}}} -> {CHURCH {PRED {ZERO}}} // 0 has no predecessor '{CHURCH {PRED {ONE}}} -> {CHURCH {PRED {ONE}}} // 0 '{CHURCH {PRED {THREE}}} -> {CHURCH {PRED {THREE}}} // 2 '{CHURCH {SUBTRACT {THREE} {TWO}}} -> {CHURCH {SUBTRACT {THREE} {TWO}}} // 1 } _p We can now write recursive algorithms, for example the factorial {b n!} {pre '{def FAC {lambda {:n} {{{ISNIL :n} {PAIR {lambda {:n} {ONE}} {lambda {:n} {MULT :n {FAC {PRED :n}}}}}} :n}}} -> {def FAC {lambda {:n} {{{ISNIL :n} {PAIR {lambda {:n} {ONE}} {lambda {:n} {MULT :n {FAC {PRED :n}}}}}} :n}}} } {pre '{CHURCH {FAC {ZERO}}} -> {CHURCH {FAC {ZERO}}} // 1 '{CHURCH {FAC {THREE}}} -> {CHURCH {FAC {THREE}}} // 6 '{CHURCH {FAC {MULT {TWO} {TWO}}}} -> {CHURCH {FAC {MULT {TWO} {TWO}}}} // 24 '{DECIM {FAC {ADD {TWO} {THREE}}}} -> {DECIM {FAC {ADD {TWO} {THREE}}}} } _h3 5. some other examples _p {b 5.1.} The tail-recursive version of {b FAC} should be faster, a kind of {b GOTO} with arguments {pre '{def TFAC {lambda {:a :b} {{{ISNIL :b} {PAIR {lambda {:a :b} :b} {lambda {:a :b} {TFAC {MULT :a :b} {PRED :b}}}}} :a :b}}} -> {def TFAC {lambda {:a :b} {{{ISNIL :b} {PAIR {lambda {:a :b} :a} {lambda {:a :b} {TFAC {MULT :a :b} {PRED :b}}}}} :a :b}}} '{DECIM {TFAC {ONE} {MULT {TWO} {THREE}}}} -> 720 } _p {b 5.2.} The Euclide algorithm returns a pair containing the integer part and the rest of the division of two numbers. {pre '{def EUCLID {def EUCLID.r // this code should be cleaned, later ... {lambda {:a :b :q :r} {{{ISNIL {SUBTRACT {MULT :b :q} :a}} {PAIR {lambda {:a :b :q :r} {EUCLID.r :a :b {SUCC :q} {SUBTRACT :a {MULT :b :q}}}} {lambda {:a :b :q :r} {PAIR {PRED :q} :r} } }} :a :b :q :r}}} {lambda {:a :b} {EUCLID.r :a :b {ZERO} :b}}} -> {def EUCLID {def EUCLID.r {lambda {:a :b :q :r} {{{ISNIL {SUBTRACT {MULT :b :q} :a}} {PAIR {lambda {:a :b :q :r} {EUCLID.r :a :b {SUCC :q} {SUBTRACT :a {MULT :b :q}}}} {lambda {:a :b :q :r} {PAIR {PRED :q} :r} } }} :a :b :q :r} }} {lambda {:a :b} {EUCLID.r :a :b {ZERO} :b}}} } _p It's interesting to compare {b EUCLID} with the plain '{lambda talk} version of the {b euclide algorithm} {blockquote {pre '{def euclide {def euclide.r {lambda {:b :q :r} {if {< :r :b} then [:q :r] else {euclide.r :b {+ :q 1} {- :r :b}} }}} {lambda {:a :b} {euclide.r :b 0 :a} }} '{euclide 87 7} -> [12 3] // 87=7*12+3 '{euclide 84 7} -> [12 0] // 84=7*12+0 }} _p {b 5.3.} Thanks to {b EUCLID} we can {b now} write the {b DIV} and {b MOD} operators {pre '{def DIV {lambda {:a :b} {LEFT {EUCLID :a :b}}}} -> {def DIV {lambda {:a :b} {LEFT {EUCLID :a :b}}}} '{def MOD {lambda {:a :b} {RIGHT {EUCLID :a :b}}}} -> {def MOD {lambda {:a :b} {RIGHT {EUCLID :a :b}}}} '{DECIM {DIV {FIVE} {TWO}}} -> 2 '{DECIM {MOD {FIVE} {TWO}}} -> 1 } _p {b 5.4.} The greater common divisor {pre '{def GCD {lambda {:a :b} {{{ISNIL :b} {PAIR {lambda {:a :b} :a} {lambda {:a :b} {GCD :b {MOD :a :b}} }}} :a :b}}} -> {def GCD {lambda {:a :b} {{{ISNIL :b} {PAIR {lambda {:a :b} :a} {lambda {:a :b} {GCD :b {MOD :a :b}} }}} :a :b}}} '{DECIM {GCD {THREE} {TWO}}} -> 1 '{DECIM {GCD {FOUR} {TWO}}} -> 2 } _p {b 5.5.} The length of a list {pre '{def LIST.LENGTH {lambda {:list} {{{ISNIL :list} {PAIR {lambda {:list} {ZERO}} {lambda {:list} {ADD {ONE} {LIST.LENGTH {RIGHT :list}}}}}} :list}}} -> {def LIST.LENGTH {lambda {:list} {{{ISNIL :list} {PAIR {lambda {:list} {ZERO}} {lambda {:list} {ADD {ONE} {LIST.LENGTH {RIGHT :list}}}}}} :list}}} '{DECIM {LIST.LENGTH {LIST}}} -> 4 } _p {b 5.6.} The mapping of a function on a list {pre '{def MAP {def MAP.r {lambda {:f :l :acc} {{{ISNIL :l} {PAIR {lambda {:f :l :acc} :acc} {lambda {:f :l :acc} {MAP.r :f {RIGHT :l} {PAIR {:f {LEFT :l}} :acc}}}}} :f :l :acc}}} {lambda {:f :l} {MAP.r :f :l NIL}}} -> {def MAP {def MAP.r {lambda {:f :l :acc} {{{ISNIL :l} {PAIR {lambda {:f :l :acc} :acc} {lambda {:f :l :acc} {MAP.r :f {RIGHT :l} {PAIR {:f {LEFT :l}} :acc}}}}} :f :l :acc}}} {lambda {:f :l} {MAP.r :f :l NIL}}} '{def SERIE {def SERIE.r {lambda {:a :b :l} {{{ISNIL {SUBTRACT :b :a}} {PAIR {lambda {:a :b :l} {PAIR :b :l}} {lambda {:a :b :l} {SERIE.r {SUCC :a} :b {PAIR :a :l}}}}} :a :b :l}}} {lambda {:a} {SERIE.r {ONE} :a NIL}}} -> {def SERIE {def SERIE.r {lambda {:a :b :l} {{{ISNIL {SUBTRACT :b :a}} {PAIR {lambda {:a :b :l} {PAIR :b :l}} {lambda {:a :b :l} {SERIE.r {SUCC :a} :b {PAIR :a :l}}}}} :a :b :l}}} {lambda {:a} {SERIE.r {ONE} :a NIL}}} '{def TEN {MULT {TWO} {FIVE}}} -> {def TEN {MULT {TWO} {FIVE}}} '{LIST.DISPLAY {MAP DECIM {SERIE {TEN}}}} -> 1 2 3 4 5 6 7 8 9 10 '{def POWER2 {lambda {:n} {DECIM {POWER {TWO} :n}}}} -> {def POWER2 {lambda {:n} {DECIM {POWER {TWO} :n}}}} '{LIST.DISPLAY {MAP POWER2 {SERIE {TEN}}}} -> 2 4 8 16 32 64 128 256 512 1024 } _p {b 5.7.} The {b Towers of Hanoï} illustrate a double recursive process {pre '{def MOVE {lambda {:n :from :to :via} {{{ISNIL :n} {PAIR {lambda {:n :from :to :via} } {lambda {:n :from :to :via} {MOVE {PRED :n} :from :via :to} {br}move disc from :from to :to {MOVE {PRED :n} :via :to :from} }}} :n :from :to :via}}} -> {def MOVE {lambda {:n :from :to :via} {{{ISNIL :n} {PAIR {lambda {:n :from :to :via} } {lambda {:n :from :to :via} {MOVE {PRED :n} :from :via :to} {br}move disc from :from to :to {MOVE {PRED :n} :via :to :from} }}} :n :from :to :via}}} '{MOVE {FOUR} 1 2 3} -> {MOVE {FOUR} 1 2 3} } _p To be honest the {code '{br}} operator is not supposed to exist at this point in '{lambda talk}. But note how the row {code '{br}move disc from :from to :to} demonstrates how easy it is to mix text and variables. {i In '{lambda talk} strings don't need to be protected by quotes}. _p At this point '{lambda talk} is still reduced to a couple of special forms {code [lambda, def]} working on words and the dictionary contains {pre {WRAP} [HI, AFFIRMATION, PAIR, LEFT, RIGHT, LIST, NIL, ISNIL, LIST.DISPLAY, ZERO, SUCC, CHURCH, DECIM, ONE, TWO, THREE, FOUR, FIVE, ADD, MULT, POWER, PRED.PAIR, PRED, SUBTRACT, FAC, TFAC, EUCLID.r, EUCLID, DIV, MOD, GCD, LIST.LENGTH, MAP, SERIE.r, SERIE, TEN, POWER2, MOVE] } _h3 6. the Y-combinator _p It's theoretically interesting to build recursion in a pure λ-calculus style reduced to abstractions and applications working on words. Here comes the Y-combinator! {pre '{def Y {lambda {:g :n} {:g :g :n}}} -> {def Y {lambda {:g :n} {:g :g :n}}} } _p We define now an {b almost} recursive version of {b FAC} coming with a reference to a function used as a kind of fixed-point by the Y-combinator {pre '{def ALMOST_FAC {lambda {:g :n} {{{ISNIL :n} {PAIR {lambda {:g :n} {ONE}} {lambda {:g :n} {MULT :n {:g :g {PRED :n}}} } }} :g :n}}} -> {def ALMOST_FAC {lambda {:g :n} {{{ISNIL :n} {PAIR {lambda {:g :n} {ONE}} {lambda {:g :n} {MULT :n {:g :g {PRED :n}}} } }} :g :n}}} '{DECIM {Y ALMOST_FAC {FIVE}}} -> 120 } _p We now compose {b Y and ALMOST_FAC} {pre '{def YFAC {lambda {:n} {{lambda {:g :n} {:g :g :n}} {lambda {:g :n} {{{ISNIL :n} {PAIR {lambda {:g :n} {ONE}} {lambda {:g :n} {MULT :n {:g :g {PRED :n}}} } }} :g :n }} :n}}} -> {def YFAC {lambda {:n} {{lambda {:g :n} {:g :g :n}} {lambda {:g :n} {{{ISNIL :n} {PAIR {lambda {:g :n} {ONE}} {lambda {:g :n} {MULT :n {:g :g {PRED :n}}} } }} :g :n }} :n}}} '{DECIM {YFAC {FIVE}}} -> 120 } _p We define and immediately call an anonymous function {pre '{DECIM {{lambda {:n} {{lambda {:g :n} {:g :g :n}} {lambda {:g :n} {{{ISNIL :n} {PAIR {lambda {:g :n} {ONE}} {lambda {:g :n} {MULT :n {:g :g {PRED :n}}} } }} :g :n }} :n}} {FIVE}}} -> 120 } _p and finally skip names, colons (useless here), and replace lambda by the greek {b λ} character to get a pure λ-calculus expression {pre {WRAP} '{{λ {n} {{n {λ {x} x|}} '}} {{λ {n} {{λ {g n} {g g n}} {λ {g n} {{{{λ {n} {n {λ {x} {λ {z} {z {λ {x y} y}}}} {λ {z} {z {λ {x y} x}}}}} n} {{λ {x y z} {z x y}} {λ {g n} {λ {f x} {f x}}} {λ {g n} {{λ {n m f x} {n {m f} x}} n {g g {{λ {n} {{λ {z} {z {λ {x y} x}}} {{n {λ {p} {{λ {x y z} {z x y}} {{λ {z} {z {λ {x y} y}}} p} {{λ {n f x} {f {{n f} x}}} {{λ {z} {z {λ {x y} y}}} p}}}}} {{λ {x y z} {z x y}} {λ {f x} x} {λ {f x} x}}}}} n}}}}}} g n }} n}} {λ {f x} {f {f {f {f {f x}}}}}}}} -> '|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| // ie. 120 pipes } _h3 as a conclusion _h6 Nothing but words, abstractions and applications, and an empty dictionary! _p We are very close to the process translated in the 1930s by a student of {b Alonzo Church}, {b Alan Turing}, into the shape of an hypothetic machine made of a window and an infinite stripe. {img {@ src="data/brussels/turing_machine.png" width="100%"}} _p It may be interesting to know that in '{lambda talk} replacements of expressions between curly braces are made through a {b window} built on a single Javascript line {pre while (code != (code = code.replace( regexp , apply ))) ; } _p working on a single {b regular expression} {pre {@ style="font:normal 1.0em courier; text-align:center;"} regexp = {quote /\{([^\s{}]*)(?:[\s]*)([^{}]*)\}/g }} _p following the syntax of a language created by {b Stephen Cole Kleene}, another student of {b Alonzo Church}. This is what {b Ward Cunningham}, the creator of the {b wiki} concept, wrote about that: « {i I was surprised that the technique worked so well in so many cases. I knew that regex are highly optimized and the cpus themselves optimize sequential access to memory which the regex must have at its core. [..] Yes, this has at its heart the repeated application of a text transformation. The fact that it is repeated application of the same transformation makes it exceptional. [..] Repeated application of Regular Expressions can perform Touring Complete computations. This works because the needed "state" is in the partially evaluated text itself.} » All is said! _p These regular expressions are also at the heart of lambdas which are nothing but machines to replace words by other words. Lambdas use arguments as regular expressions to successively replace occurences found in the function's body by the given values. For the call {pre '{{lambda {fruit unknown} The color of fruits is unknown.} apple green} } _p {b partially} replaces the first argument {b fruit} by the value {b apple}, generating the new call {pre '{{lambda {unknown} The color of apples is unknown.} green} } _p replacing the second argument {b unknown} by the value {b green}, resulting in {pre The color of apples is green. } _p Partial call made easy, nothing magic there! Everything could be done by hand, {i at least theoretically} or, more easily, can be coded and tested on any modern web browser, thanks to a small IDE, a wiki called '{lambda tank}, a 100kb file freely downloadable and easy to install on any web host provider. _p Your opinion is welcome, for instance in the workshop's [[forum]]. _p {i Alain Marty} {blockquote _p Actually '{lambda talk} is not lost in empty space. '{lambda talk} takes benefit of the powerful functionalities of modern web browsers (Javascript, HTML/CSS, DOM, SVG, ...) and comes with an extended set of special forms and built-in primitives. For instance, thanks to the browser's SVG functions and the lambdatalk primitive {b turtle}, we could define a tree like this {pre '{def flower {lambda {:s} T-30 M:s T120 M:s T120 M:s T150}} -> {def flower {lambda {:s} T-30 M:s T120 M:s T120 M:s T150}} '{def tree {lambda {:e :s :k :a :b} {if {< :s :e} then {flower :s} else M:s T:a {tree :e {* :k :s} :k :a :b} T-{+ :a :b} {tree :e {* :k :s} :k :a :b} T:b M-:s }}} -> {def tree {lambda {:e :s :k :a :b} {if {< :s :e} then {flower :s} else M:s T:a {tree :e {* :k :s} :k :a :b} T-{+ :a :b} {tree :e {* :k :s} :k :a :b} T:b M-:s }}} } _p and call it in a SVG container {pre '{svg {@ width="540px" height="540px"} {polyline {@ points="{turtle 400 590 180 {tree 5 200 {/ 2 3} 40 4}}" fill="transparent" stroke="red" stroke-width="1"}} } } {img {@ src="data/brussels/turtle_20161105.jpg" width="100%"}} _p Feel free to learn more about '{lambda talk} in this [[workshop|?view=start]]. } {center {i updated on 2018/02/03}} {{hide} {def WRAP {@ style="word-wrap: break-word; white-space:pre-wrap;"}} } {style body { background:#eee; } pre { font:normal 1.0em courier; } }