lambdaspeech
::
kiss
1
|
list
|
login
|
load
|
|
_img http://lambdaway.free.fr/workshop/data/brussels/turing_machine.png _h1 keep it simple & small | [[kiss2]] _p Two data structures, (pairs & lists), one control structure, (recursion), and natural numbers are introduced in a few lines, using nothing but words and two conjugated operators. Something like TAO's Yin & Yang! _h2 1. syntax _p Following the λ-calcul which can be expressed in one "magical" formula {pre {center {b e := w | λw.e | ee}}} _p '{lambda talk}'s expressions are made of words, abstractions and applications {center {pre {b expression := [ word | abstraction | application ]* }}} _p where {pre - word := [^\s'{}]* // any char except spaces and curly braces - abstraction := '{lambda {word*} expression} | '{def word expression} - application := '{expression expression} } _h2 2. evaluation _p As a kind of Turing machine, the evaluation uses a regular expression based window runnning back and forth on the code string, catching and evaluating expressions until they are all replaced by words. Following these rules: _ul 1) {b words} are not evaluated _ul 2) {b abstractions} are evaluated before {b applications} _ul30 2.1) {b lambdas} are evaluated to a {b word}, a system defined reference to an anonymous function added to a single dictionary - initially empty - with {b word*} as arguments and {b expression} as body, _ul30 2.2) {b defs} are evaluated to a {b word}, a user defined reference to a function added to the dictionary evaluating and returning {b expression}, _ul 3) {b applications} are recursively - from inside out - evaluated to words, the first expression is evaluated to a function, the second to words on which is applied the function. _ul 4) a {b lambda replaces} occurences of arguments in the body by the given values, then evaluates and returns it, _ul30 4.1) if the number of given values is lesser than the number of arguments, values are memorized in the body and a function is returned waiting for missing ones, a kind of automatic currying, _ul30 4.2) if the number of given values is greater than number of arguments, extra values are gathered in the last one, a kind of variadicity, _ul 5) {b lambdas} and {b defs} can be nested. _h2 3. a useful set _p We first build a first set of 8 small user defined functions: {pre '{def | {lambda {:a :b} :a}} -> {def | {lambda {:a :b} :a}} // true, one '{def ø {lambda {:a :b} :b}} -> {def ø {lambda {:a :b} :b}} // false, zero '{def □ {lambda {:a :b :c} {:c :a :b}}} -> {def □ {lambda {:a :b :c} {:c :a :b}}} // pair, cons '{def [ {lambda {:c} {:c |}}} -> {def [ {lambda {:c} {:c |}}} // left, car '{def ] {lambda {:c} {:c ø}}} -> {def ] {lambda {:c} {:c ø}}} // right, cdr '{def ? {lambda {:c} {:c {| ]} [}}} -> {def ? {lambda {:c} {:c {| ]} [}}} // isnil? '{def ¿ {lambda {:c} {:c {| [} ]}}} -> {def ¿ {lambda {:c} {:c {| [} ]}}} // isnotnil? '{def Y {lambda {:f :l} {:f :f :l}}} -> {def Y {lambda {:f :l} {:f :f :l}}} // Y combinator } _h2 4. application _p Using these "bricks", we can build several structures. _h3 4.1. booleans _p The {code |} and {code ø} functions are in fact the booleans {code true} and {code false}. Let's define 3 other boolean functions, {code AND, OR, NOT} {pre '{def AND {lambda {:x :y} {:x :y ø}}} -> {def AND {lambda {x y} {x y ø}}} '{AND | |} -> {AND | |} '{AND | ø} -> {AND | ø} '{AND ø |} -> {AND ø |} '{AND ø ø} -> {AND ø ø} '{def OR {lambda {:x :y} {:x | :y}}} -> {def OR {lambda {x y} {x | y}}} '{OR | |} -> {OR | |} '{OR | ø} -> {OR | ø} '{OR ø |} -> {OR ø |} '{OR ø ø} -> {OR ø ø} '{def NOT {lambda {:x} {:x ø |}}} -> {def NOT {lambda {x} {x ø |}}} '{NOT |} -> {NOT |} '{NOT ø} -> {NOT ø} } _h3 4.2. a pair {pre '{def P {□ hello world}} -> {def P {□ hello world}} '{[ {P}} -> {[ {P}} '{] {P}} -> {] {P}} } _h3 4.3. a list {pre '{def L {□ a {□ b {□ c {□ d ø}}}}} -> {def L {□ a {□ b {□ c {□ d ø}}}}} } _h3 4.4. a recursive algorithm {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}} } _h3 4.5. a pure λ calculus expression _p We simply replace all names in '{D {L}} by their lambda expressions {pre '{{lambda {:l} {{lambda {:f :l} {:f :f :l}} {lambda {:f :l} {{{{lambda {:c} {:c {{lambda {:a :b} :a} {lambda {:c} {:c {lambda {:a :b} :b}}}} {lambda {:c} {:c {lambda {:a :b} :a}}}}} :l} {{lambda {:a :b :c} {:c :a :b}} {lambda {:f :l} } {lambda {:f :l} {{lambda {:c} {:c {lambda {:a :b} :a}}} :l} {:f :f {{lambda {:c} {:c {lambda {:a :b} :b}}} :l}} } }} :f :l}} :l}} {{lambda {:a :b :c} {:c :a :b}} a {{lambda {:a :b :c} {:c :a :b}} b {{lambda {:a :b :c} {:c :a :b}} c {{lambda {:a :b :c} {:c :a :b}} d {lambda {:a :b} :b}}}}}} -> {{lambda {:l} {{lambda {:f :l} {:f :f :l}} {lambda {:f :l} {{{{lambda {:c} {:c {{lambda {:a :b} :a} {lambda {:c} {:c {lambda {:a :b} :b}}}} {lambda {:c} {:c {lambda {:a :b} :a}}}}} :l} {{lambda {:a :b :c} {:c :a :b}} {lambda {:f :l} } {lambda {:f :l} {{lambda {:c} {:c {lambda {:a :b} :a}}} :l} {:f :f {{lambda {:c} {:c {lambda {:a :b} :b}}} :l}} } }} :f :l}} :l}} {{lambda {:a :b :c} {:c :a :b}} a {{lambda {:a :b :c} {:c :a :b}} b {{lambda {:a :b :c} {:c :a :b}} c {{lambda {:a :b :c} {:c :a :b}} d {lambda {:a :b} :b}}}}}} } _h3 4.6. natural numbers _p Note that the {code D} function displays list's items. Replacing list's items by simple dots, we can compute its {b length} in a very primitive unary notation {pre '{def N {lambda {:l} {{{? :l} {□ {lambda {:l} } {lambda {:l} . {N {] :l}}}}} :l}}} -> {def N {lambda {:l} {{{? :l} {□ {lambda {:l} } {lambda {:l} . {N {] :l}}}}} :l}}} '{N {L}} -> {N {L}} // read 4 dots } _p So, without any "grey area", using nothing than {b lambdas & defs}, we have defined two data structures, (pair and list), a control structure, (recursion) and figured a way to define natural numbers, [zero, one, two, three, ...]. With Peano and Church we can build arithmetical operators like next (»), previous («), addition (++), multiplication (**), ... and even the factorial function (!!): {prewrap '{def » {lambda {:n} {□ . :n}}} -> {def » {lambda {:n} {□ . :n}}}. // next '{def « {lambda {:n} {{{? :n} {□ ø {] :n}}}}}} -> {def « {lambda {:n} {{{? :n} {□ ø {] :n}}}}}}. // prev '{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 ** // 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 !! {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 We define one and five and compute the factorial of five: {prewrap '{def one {» ø}} -> {def one {» ø}} '{def five {» {» {» {» {» ø}}}}}} -> {def five {» {» {» {» {» ø}}}}}} '{N {!! {one} {five}}} -> {N {!! {one} {five}}}. // read 120 dots } _p {b Note:} Don't try to compute the factorial of six which locks my computer. This approach is not efficient at all, for a better efficiency see [[kiss2]] using JS numbers or use plain '{lambda talk} and a big numbers library. _p That's all! _h2 and so what? _p You are at the end of this page and need some clarification? _p You can read more in this [[paper|?view=factory_201902_paper]], where is shown how, on such a simple/terce {b infrastructure} and thanks to the powerful capabilities of web browsers, can be built very easily numerous {b superstructures}, leading to a true functional programming language, '{lambda talk}, working in a tiny wiki, '{lambda tank}, and usable in daily life by average people. _p For instance to create this wiki page intermixing text, style and active code. {center {img {@ src="http://lambdaway.free.fr/workshop/data/brussels/browsers_icons.jpg" height="80px"}} {span {@ style="font-size:4.5em; vertical-align:top;"}+} {img {@ src="http://lambdaway.free.fr/workshop/data/brussels/braces.png" height="80px"}} {br}{i « As a dwarf on the shoulders of giants. »} } _p This is what [[Paul McJones|https://www.mcjones.org/paul/]] said about the '{lambda way} project (2019/02/16): « {i I have admired the power and elegance of the λ-calculus since I first learned of it around 1970. And I have admired the elegance of the Wiki idea since I first ran across Ward Cunningham’s Wiki some years back. You’ve combined these ideas in a very interesting way, and you figured out a way to harness the power of web technologies (JavaScript, HTML, CSS, etc.) to implement them.} » _p All is said, better than I could do. Welcome in the [['{lambda way} project|http://lambdaway.free.fr/lambdaspeech/]]. Your opinion is welcome, for instance in [[HN|https://news.ycombinator.com/item?id=19927229]], [[reddit/λ-calculus|https://www.reddit.com/r/lambdacalculus/comments/bpi0rn/as_simple_as_that_maybe/]], [[reddit/programming|https://www.reddit.com/r/programming/comments/bpcnc6/the_y_combinator_or_how_to_implement_recursion_in/]] or by mail to {i marty•alain_at_free•fr}. _p {i Alain Marty 2019/05/16} {style ;; body { background:#888; } #page_content { background:#ffe; font-family:optima; } }
lambdaspeech v.20200126