+
1
|
skin
|
login
|
edit
workshop
::
lambdaspeech
user:anonymous
_img data/chevaux.jpg {center [[Mustangs at Las Colinas|https://en.m.wikipedia.org/wiki/Mustangs_at_Las_Colinas]]} {center _h1 (λ speech) {sup {i ze making of}}} {center {i Page under construction | 2018/06/01-08 {br}See also how lambdaspeech could be used in a minimal [[wiki|http://b2b3.free.fr/lambdaspeech/]] {br}and the parallel work/fork by [[Graham Simkins|https://github.com/phouchguk/lambda-speech/]]. }} _p {b (λ speech)} is a dialect of {b (λ calculus)}{sup (1936)} taking benefit of modern web browsers. _p At the lowest level, {b (lambda speech)} is based on nested {b expressions} made of {b words, abstractions & applications} recursively evaluated to {b words}: {pre - word is {b [^\s()]*} - application is {b (expression1 expression2)} - abstraction is {b (lambda (words) expression)} } _p More precisely _ul a {b word} is a group of any characters except spaces and braces (), and stands for itself, ie is its own value, _ul an {b application} determines if {b expression1} is bound to a {b function} then evaluates {b expression2} into {b words2}, applies that function to words2 and returns other {b words}, _ul an {b abstraction} is evaluated into a {b word} bound to an anonymous function selecting words (arguments) in expression (body) to be replaced by some future given words (values). _p The implementation of (lambda speech) insures that _ul words are not evaluated, _ul abstractions are {b special forms} evaluated to words {b before} applications, _ul applications are {b nested forms} evaluated to words from inside out, from the leaves to the root. _p The evaluation stops when the code is reduced to words without any braces. These words are sent to the browser's engine for anymore evaluations - HTML/CSS/SVG,... - and display. _p That's it! _p That's it? But what can be done with so little? _p Just one thing, we can replace selected words by others in a sentence. For instance {pre {b replace} "fruit" and "unknown" {b in} "The color of fruits is unknown." {b by} "apple" and "green" } _p rewritten using this syntax {pre ((lambda (fruit unknown) The color of fruits is unknown.) apple green) } _p displays {pre The color of apples is green. } _p The evaluation is done in a sequence of replacements {pre . ((lambda ({b fruit unknown}) The color of fruits is unknown.) {{red} apple green}) -> ((lambda ({b unknown}) The color of {{red} apples} is unknown.) {b green}) -> ((lambda () The color of {{red} apples} is {{red} green}.)) -> The color of {{red} apples} is {{red} green}. } _p {b Ok!} it's nothing but simple {b text substitution}. Let's try expressions nesting lambdas {pre ((lambda (z) (z (lambda (x y) x)) ((lambda (x y z) (z x y)) {b ♥ ♠})) -> {b ♥} ((lambda (z) (z (lambda (x y) y)) ((lambda (x y z) (z x y)) {b ♥ ♠})) -> {b ♠} } _p These expressions work on a couple of words, [{b ♥ ♠}], and respectively return the first and the second. Let's follow the successive replacements in the first expression {pre . ((lambda (z) (z (lambda (x y) x)) ((lambda ({b x} y z) (z {b x} y)) {b ♥} ♠)) |_________|-----| -> ((lambda (z) (z (lambda (x y) x)) ((lambda ({b y} z) (z {{red}♥} {b y})) {b ♠})) |_________|---| -> ((lambda (z) (z (lambda (x y) x)) ((lambda (z) (z {{red}♥} {{red}♠})))) |==================| -> ((lambda ({b z}) ({b z} (lambda (x y) x)) {{red}(}{b (lambda (z) (z {{red}♥} {{red}♠}))}{{red})}) |___|--------------------|==================| -> ((lambda ({b z}) ({b z} {{red}♥ ♠})) {b (lambda (x y) x)}) |___|-------|==============| -> ((lambda ({b x} y) {b x}) {{red}♥ ♠}) |____|--| -> {b {{red}♥}} } _p And we can also build much more complex replacements using deeply nested lambdas. For instance, writing {pre {@ style="white-space:pre-wrap"} ((lambda (:f :n) (:f :f :n)) (lambda (:f :t) ((((lambda (:n) (:n (lambda (:x) (lambda (:z) (:z (lambda (:x :y) :y)))) (lambda (:z) (:z (lambda (:x :y) :x))))) :t) ((lambda (:x :y :z) (:z :x :y)) (lambda (:f :t)) (lambda (:f :t) ((lambda (:z) (:z (lambda (:x :y) :x))) :t) (:f :f ((lambda (:z) (:z (lambda (:x :y) :y))) :t))))) :f :t)) ((lambda (:x :y :z) (:z :x :y)) apple ((lambda (:x :y :z) (:z :x :y)) banana ((lambda (:x :y :z) (:z :x :y)) lemon ((lambda (:x :y :z) (:z :x :y)) orange (lambda (:f :x) :x)))))) } _p displays {pre apple banana lemon orange } _p {b Amazing, isnt'it?}, we have displayed a list of fruits! In fact the amazing fact is that, meanwhile, we have built two data structures, {b pair & list}, and a control structure, {b recursion}, with which we can go further and code, at least theoretically, any imaginable algorithm. For instance reversing, appending and sorting lists, counting their elements, building numbers, computing the factorial of {b 6}, playing with the Towers of Hanoï, and so on. Ad libitum. _h3 1. how does it work? _p How is it possible to write the long and {i unreadable} expression given in the introductive section? We are going to build this expression from a set of smaller compositions of lambdas. To make things easier, we will add and use an {i optionnal but useful} second special form, {b (def name expression)} giving a name to chuncks of code. _p First we define 3 functions, [{b pair, left, right}] {pre (def pair (lambda (:x :y :z) (:z :x :y))) -> pair (def left (lambda (:z) (:z (lambda (:x :y) :x)))) -> left (def right (lambda (:z) (:z (lambda (:x :y) :y)))) -> right } _p We have just defined a fundamental {b data structure}. Something close to the [{b cons, car cdr}] construction beloved by good old Lispians... Thanks to this data structure we can aggregate two words with {b pair} and access each of them with {b left} and {b right} {pre (def mypair (pair Amélie Poulain)) -> mypair (left (mypair)) -> Amélie (right (mypair) -> Poulain } _p We define two associated functions, [{b nil, nil?}], where {b nil?} is a predicate function returning {b right} if applied on a pair or {b left} if applied on {b nil} {pre (def nil? (lambda (:n) (:n (lambda (:x) right) left))) -> nil? (def nil (lambda (:f :x) :x)) -> nil (nil? nil) -> left (nil? (mypair)) -> right } _p We can compose pairs to build a {b list} terminating with {b nil} {pre (def fruits (pair apple (pair banana (pair lemon (pair orange nil))))) -> fruits } _p and access each of its elements with {b left} and {b right} {pre (left (fruits)) -> apple (left (right (fruits))) -> banana (left (right (right (fruits)))) -> lemon (left (right (right (right (fruits))))) -> orange (right (right (right (right (fruits))))) -> nil } _p This sequence of expressions enlights a "pattern" leading to a {b recursive function} displaying the list {pre (def list.disp (lambda (:l) (((nil? :l) (pair (lambda (:l) ) (lambda (:l) (left :l) (list.disp (right :l)) ) )) :l))) -> list.disp (list.disp (fruits)) -> apple banana lemon orange } _p {b So it works!} We have built a {b control structure}. We will wait until the {b 4. tracing recursion} section to get some explanations about the way recursion works. At this point the problem is that a recursive function calls its name in its body and so must be named. And we have to eliminate names - we have to forget the second special form {b def} - to get a chance to find an expression exclusively made of words and lambdas. A known solution is to split the recursive function into a {b Y-combinator} and an {i almost recursive} function {i which doesn't call its name in its body} {pre (def Y (lambda (:f :n) (:f :f :n))) -> Y (def almost (lambda (:f :l) (((nil? :l) (pair (lambda (:f :l) ) (lambda (:f :l) (left :l) (:f :f (right :l)) ) )) :f :l))) -> almost (Y almost (fruits)) -> apple banana lemon orange } _p Finally, replacing in {b (Y almost (fruits))} all user defined names, {b pair, left, right, nil, nil?, Y, almost, fruits}, by their lambda definitions, we get an expression exclusively made of words and lambdas, in a pure {b λ-calculus} style {pre {@ style="white-space:pre-wrap"} ((lambda (:f :n) (:f :f :n)) (lambda (:f :t) ((((lambda (:n) (:n (lambda (:x) (lambda (:z) (:z (lambda (:x :y) :y)))) (lambda (:z) (:z (lambda (:x :y) :x))))) :t) ((lambda (:x :y :z) (:z :x :y)) (lambda (:f :t)) (lambda (:f :t) ((lambda (:z) (:z (lambda (:x :y) :x))) :t) (:f :f ((lambda (:z) (:z (lambda (:x :y) :y))) :t))))) :f :t)) ((lambda (:x :y :z) (:z :x :y)) apple ((lambda (:x :y :z) (:z :x :y)) banana ((lambda (:x :y :z) (:z :x :y)) lemon ((lambda (:x :y :z) (:z :x :y)) orange (lambda (:f :x) :x)))))) -> apple banana lemon orange } _p To sum up, with nothing but 3 rules, {b words, abstractions, applications}, we have built two data structures, (pairs & lists), and a control structure, recursion. In fact, this text substitution machine is a {b Turing machine} with which we can theoretically write any "imaginable" algorithm. {i Ad libitum}. _p As a first application, we could follow the father of {b λ calculus}, Alonzo Church, and build the set of natural numbers with their related operators, (succ, pred, add, minus, mul, div, mod, ...) to do some arithmetic, for instance to compute a factorial. You can analyze such a development in [[NIL2]] and notice that computing {b (fac 6)} is slow and {b (fac 7)} locks the computer in a stack overflow. _p So in this study we choose to use the much more effective JS numbers and math operators, coming for free in a web browser environment, adding a first set of primitives, [{b +, -, *, /, %, <, =, ...}]. As a first example, on a recent laptop, we compute {b (fac 170)} in a few milliseconds {pre (def fac (lambda (:n) (((< :n 1) (pair (lambda (:n) 1) (lambda (:n) (* :n (fac (- :n 1)))) )) :n))) {b (fac 170)} -> 7.257415615307994e+306 } _p or the first 15 digits of {b sqrt(2)} {pre (* ((lambda (f x y) (f f x y)) (lambda (f u v) (((< (abs (- u v)) 1.0e-15) (pair (lambda (f u v) u) (lambda (f u v) (f f v (* u (- 1.5 (* u u)))) ))) f u v)) 0.5 1) 2) -> {b {sqrt 2}} } _p Later will be added on demand other JS primitives, more effective {b pairs & lists} built on the powerful JS arrays, HTML/CSS/SBG syntaxes and libraries, (big numbers, spreadsheet, 2D/3D graphics, ...), leading to a usable and extendable programming language. _p We can add to the dictionary a primitive {b bigfac}, see section {b 5. code}, built on a library, {b [[lib_BN]]}, written by a smart coder, Jonas Raoni Soares Silva, and compute the {b exact value} of the factorial of big numbers: {pre {@ style="word-wrap: break-word; white-space:pre-wrap;"} {b (bigfac 500)} -> 1220136825991110068701238785423046926253574342803192842192413588385845373153881997605496447502203281863013616477148203584163378722078177200480785205159329285477907571939330603772960859086270429174547882424912726344305670173270769461062802310452644218878789465754777149863494367781037644274033827365397471386477878495438489595537537990423241061271326984327745715546309977202781014561081188373709531016356324432987029563896628911658974769572087926928871281780070265174507768410719624390394322536422605234945850129918571501248706961568141625359056693423813008856249246891564126775654481886506593847951775360894005745238940335798476363944905313062323749066445048824665075946735862074637925184200459369692981022263971952597190945217823331756934581508552332820762820023402626907898342451712006207714640979456116127629145951237229913340169552363850942885592018727433795173014586357570828355780158735432768888680120399882384702151467605445407663535984174430480128938313896881639487469658817504506926365338175055478128640000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 } _p That's for maths. With HTML/CSS we have tools for building rich documents, produce PDF files, slideshows, and so on. Being a dialect of lambda calculus doesn't prevent (lambda speech) to be usefull. Even by a 11 years old kid, see [[teaching]]. _h4 about the implementation _p (lambda speech) evaluates first {b special forms}, then {b nested forms}. _h5 special forms _ul {b (lambda (words) expression)}: this special form is the key of the evaluation, creating anonymous functions which will be eventually called during the evaluation of nested forms. As we have seen previously, this special form is the only one needed for the evaluation but new {i optionnal} ones will be defined to make things easier: _ul {b (def name expression)}: we have seen that this second special form could help to split deeply nested expressions in a set of constants and small named functions. _ul {b (quote expressions) or '(expressions)}: this special form protects {b expressions} from evaluation which stay as they are, _ul {b (let ( (arg val) ... ) body)}: is a "syntaxic sugar" leading to {b ((lambda (args) body) vals)}, allowing to define and enlight local variables, _ul {b (when bool then one else two[ with args])}: is another "syntaxic sugar" allowing to create more easily {b (((bool) (pair one two)) args)}, a structure exclusively made of lambdas, using the set of user defined functions [{b pair, left, right, nil, nil?}], see section {b 4. trace}, _ul {b (if bool then one else two)}: is {b the special form to use} to easily build effective control structures, independently of any other function. _h5 nested forms _p When constants and functions have been added to the dictionary, nested forms can be recursively evaluated. Functions are applied to values from inside out. For instance: {pre 0: (sqrt (+ (* 3 3) (* 4 4))) 1: (sqrt (+ 9 16)) 2: (sqrt 25) 3: 5 } _p The remarkable fact is that nested forms are evaluated in a single line of Javascript working on a single regular expression, as it can be seen in section {b 5. code}. Not counting of course the dictionary which can contain any number of primitives. {i Beginning with zero, thanks to lambdas}. _h5 notes _ul predicate functions, ie {b bool}, return {b left|right} which could have been named {b true|false}, {b car|cdr} or {b #t|#f}, JS booleans aren't used in (lambda speech), _ul in a similar way numbers doesn't exist {i per se} in (lambda speech), for instance {b (+ 12 34)} displays {b {+ 12 34}} and {b (+ hello world)} displays {b {+ Hello World}} (Not A Number) the reason is that {b 12} and {b 34} are two words evaluable as numbers by the {b +} operator, {b hello} and {b world} can't, _ul for obvious reasons of efficiency the functions [pair, left, right, nil, nil?] defined in the {b 2. how does it work} section will be finally {b hard-coded} as primitives in the dictionary, _ul (lambda speech) is a progressive rewriting of '{lambda talk} where curly braces {b '{}} are replaced by round braces {b ()} to avoid conflicts when used in the '{lambda tank} environment, _ul (lambda speech) can be used outside '{lambda tank}, called by a simple HTML file, see section {b 5. code}. Test it where you like! _p You can test (lambda speech) in section {b 2. test it!} using code given in section {b 3. examples}, learn about recursion exclusively made of lambdas in section {b 4. tracing recursion} and analyze the JS underlying code in section {b 5. JS code}. _h3 2. test it! _p Code can be tested in the editor frame below, for instance using code chuncks given in the section {b 3. examples}. _h5 input {textarea {@ id="code" style="width:100%; height:450px; font:normal 1.1em courier" onkeyup="refresh()" } Hello World '(+ 1 (* 2 3) 4) is equal to (+ 1 (* 2 3) 4) (def #.display (lambda (:a) (if (#.empty? :a) then else (#.first :a) (#.display (#.rest :a)) ))) (def FRUITS (#.new apple banana lemon orange)) (#.display (FRUITS)) (div (@ style="text-align:center; font:bold 5em georgia; color:#fff; text-shadow:0 0 8px #000;") Hello World) (img (@ src="data/amelie_poulain.jpg" width="100%" title="Amélie Poulain is cute.")) } {center {@ id="infos"}} _h5 output {pre {@ id="view" style="white-space:pre-wrap; box-shadow:0 0 8px #000"}} _h3 3. examples {pre {b 1. Basics} hello world (foo bar) (def hi Hello World) hi, I just say (hi) (def affirmation (lambda (fruit unknown) The color of fruits is unknown.)) (affirmation apple green) '(+ 1 (* 2 3) 4) -> (+ 1 (* 2 3) 4) (def add (lambda (:a :b) (+ :a :b))) (add 3 4) (add 3) // partial call -> function ((add 3) 4) // calls in sequence (add 3 4 5) // variadic, because + is variadic (add 3 4 5 6 7) (def triangle (lambda (:a :b :c) ((lambda (:a :b :c :s) (sqrt (* :s (- :s :a) (- :s :b) (- :s :c))) ) :a :b :c (/ (+ :a :b :c) 2)))) (triangle 3 4 5) or using let: (def triangle (lambda (:a :b :c) (let ( (:a :a) (:b :b) (:c :c) (:s (/ (+ :a :b :c) 2)) ) (sqrt (* :s (- :s :a) (- :s :b) (- :s :c))) ))) {b 2. pairs, trees & lists} /* these user defined functions are now built-in primitives (def pair (lambda (:x :y :z) (:z :x :y))) (def left (lambda (:z) (:z (lambda (:x :y) :x)))) (def right (lambda (:z) (:z (lambda (:x :y) :y)))) (def nil? (lambda (:n) (:n (lambda (:x) right) left))) (def nil (lambda (:f :x) :x)) */ (left (pair Hello World)) (right (pair Hello World)) (def HI (pair Hello World)) (left (HI)) (right (HI)) (def LIST (pair a (pair b (pair c (pair d nil))))) (def list.disp (lambda (:l) (((nil? :l) (pair (lambda (:l) ) (lambda (:l) (left :l) (list.disp (right :l)) ) )) :l))) (list.disp (LIST)) (def TREE (pair (pair a b) (pair c d))) (def tree.disp (lambda (:t) (((pair? :t) (pair (lambda (:t) [(tree.disp (left :t)) (tree.disp (right :t))]) (lambda (:t) :t) )) :t))) (tree.disp (TREE)) (def fac (lambda (:n) (((< :n 1) (pair (lambda (:n) 1) (lambda (:n) (* :n (fac (- :n 1)))) )) :n))) (fac 21) (fac 22) // double recursion (def hanoi (lambda (:n :from :to :via) (((< :n 1) (pair (lambda (:n :from :to :via) ) (lambda (:n :from :to :via) (hanoi (- :n 1) :from :via :to) (br) move disc from :from to :to (hanoi (- :n 1) :via :to :from) ))) :n :from :to :via))) (hanoi 4 1 2 3) (def partition (def partition.mid (lambda (:k) (/ (+ (left :k) (right :k)) 2))) (lambda (:k :n) (((< :n 1) (pair (lambda (:k :n) :k) (lambda (:k :n) (pair (partition (pair (left :k) (partition.mid :k)) (- :n 1)) (partition (pair (partition.mid :k) (right :k)) (- :n 1)) )))) :k :n))) (tree.disp (partition (pair 0 1) 5)) // nested "ifs" (def sign (lambda (:n) (((< :n 0) (pair (lambda (:n) :n is negative) (lambda (:n) (((< :n 1) (pair (lambda (:n) :n is null) (lambda (:n) :n is positive) )) :n)))) :n))) (sign -1) (sign 0) (sign 1) (def choice (lambda (:x) (((= :x one) (pair (lambda (:x) :x is UN) (lambda (:x) (((= :x two) (pair (lambda (:x) :x is DEUX) (lambda (:x) (((= :x three) (pair (lambda (:x) :x is TROIS) (lambda (:x) :x is out of scope) )) :x)))) :x)))) :x))) (choice one) (choice two) (choice three) (choice four) {b 3. when as a syntaxic sugar} - need pair,left,right,nil,nil? (when (< 1 2) then (+ 1 2) else (- 1 2)) (when (< 2 1) then (+ 1 2) else (- 1 2)) (def fac (lambda (:n) (when (< :n 1) then 1 else (* :n (fac (- :n 1))) with :n))) (fac 21) (fac 22) (def choice2 (lambda (:x) (when (= :x one) then :x is UN else (when (= :x two) then :x is DEUX else (if (= :x three) then :x is TROIS else :x is out of scope with :x) with :x) with :x) )) (choice2 one) (choice2 two) (choice2 three) (choice2 four) // sorting a list - need list.disp (def insert (lambda (:x :l) (when (nil? :l) then (pair :x nil) else (when (< :x (left :l)) then (pair :x :l) else (pair (left :l) (insert :x (right :l))) with :x :l) with :x :l))) (def sort (lambda (:l) (when (nil? :l) then nil else (insert (left :l) (sort (right :l))) with :l))) (def mylist (pair -3 (pair 1 (pair -10 (pair 4 (pair 2 (pair 8 nil))))))) (list.disp (sort (mylist))) {b 4. using if} (def fac (lambda (:n) (if (< :n 1) then 1 else (* :n (fac (- :n 1)))))) (fac 21) - need pair,left,right,nil,nil? (def insert (lambda (:x :l) (if (nil? :l) then (pair :x nil) else (if (< :x (left :l)) then (pair :x :l) else (pair (left :l) (insert :x (right :l))))))) (def sort (lambda (:l) (if (nil? :l) then nil else (insert (left :l) (sort (right :l)))))) (def list.display (lambda (:l) (if (nil? :l) then else (left :l) (list.display (right :l))))) (def mylist (pair 3 (pair 1 (pair -10 (pair 4 (pair 2 (pair 8 nil))))))) (list.display (sort (mylist))) {b 5. arrays} (def A (#.new 12 34 56)) (#.array? hello) (#.disp (A)) (#.empty? (A)) (#.length (A)) (#.first (A)) (#.last (A)) (#.disp (#.rest (A))) (#.get (A) 1) (def array.display (lambda (:a) (if (#.empty? :a) then . else (#.first :a) (array.display (#.rest :a)) ))) (array.display (A)) {b 6. HTML/CSS} (div (@ style="text-align:center; font:bold 5em georgia; color:#fff; text-shadow:0 0 8px #000;") Hello World) (img (@ src="data/amelie_poulain.jpg" width="100%")) // variadic functions (def redwords (lambda (:t) (span (@ style="color:red"):t))) (redwords hello my brave new world, (+ 1 2)) (def colwords (lambda (:c :t) (span (@ style="color::c"):t))) (colwords blue Hello world) ... more to come } _h3 4. tracing recursion _p Let's trace the definition and the evaluation of the factorial, without {b when} or {b if}, just lambdas and user defined functions [pair, left, right] built on lambdas {pre (def {b fac} (lambda (:n) (((< :n 1) (pair (lambda (:n) 1) (lambda (:n) (* :n ({b fac} (- :n 1)))) )) :n))) } _p We rewrite this definition using 3 inside functions, [{b bool, one, two}] in order to enlight the process of delaying and forcing evaluation: _ul first {u delaying} {b bool, one, two} with lambdas _ul then {u forcing} {b one OR two} depending on {b bool} {pre (def fac (def {b bool} (lambda (:n) (< :n 1) )) (def {b one} (lambda (:n) 1 )) (def {b two} (lambda (:n) (* :n (fac (- :n 1))) )) (lambda (:n) {b (((bool :n) (pair one two)) :n)} )) } _p So {pre (fac 6) -> (((bool 6) (pair one two)) 6) // 6 has replaced :n in the body -> (({b right} (pair one two)) 6) // (bool 6) returned right -> (two 6) // right selected two -> (* 6 {b (fac 5)}) // which was applied on 6 } _p Recursing until the end case {pre -> (* 6 (* 5 (* 4 (* 3 (* 2 (* 1 {b (fac 0)})))))) } _p The end case {pre (fac 0) -> (((bool 0) (pair one two)) 0) -> (({b left} (pair one two)) 0) -> (one 0) -> 1 } _p Finally {pre -> (* 6 (* 5 (* 4 (* 3 (* 2 (* 1 1)))))) -> (* 6 (* 5 (* 4 (* 3 (* 2 1))))) -> (* 6 (* 5 (* 4 (* 3 2)))) -> (* 6 (* 5 (* 4 6))) -> (* 6 (* 5 24)) -> (* 6 120) -> 720 } _p Note that the successive replacements from inside out are not done in the whole string (of the page's code which could contain thousands words) but in a local one built inside the function's call, allowing a long sequence of replacements, ie {b (fac 170) -> 7.257415615307994e+306}, to be computed in a few milli-seconds on recent laptops. As it is the case for '{lambda talk}, the regexp based evaluator of (lambda speech) doesn't tokenize every words in the code string to build and evaluate an AST, which has a cost. Skiping words, the evaluator runs first over the whole string to abstract special forms, then it runs again over the reduced string, eventually calling functions working recursively in their own strings/spaces to finally return words to the main one. _h3 5. JS code _p The evaluator's kernel of {b SPEECH} has 1 main special form, {b lambda}, 2 useful ones, [{b def,if}], 3 optionnal ones, [{b quote, let, when}] and is written in about {b 200} lines. The dictionary is populated with a first reduced set of primitives, [{b MATHS, PAIRS, ARRAYS, ...}], and can be extended on demand with [{b HTML/CSS, SVG, ...}]. _p The implementation of '{lambda speech} insures that _ul {b words} are not evaluated, _ul {b abstractions} are {u special forms} evaluated to words {b before} applications, _ul {b applications} are {u nested forms} evaluated to words from inside out, from the leaves to the root. _h5 lambdas _p Lambdas are the heart of (lambda speech) and have the following properties. Functions _ul {b are first class}: essentially they can be called as arguments, returned as values and created at run-time, _ul {b accept vals' number < args' number}: functions accept partial calls, memorizing the given values and returning a new function waiting for the rest, _ul {b accept vals' number > args' number}: extra values are simply gathered in the last arguments, if prefixed by {b &}, _ul {b don't define any closure}: the list of arguments determines the local working environment, there is no access to any external variables, no free variables, _ul {b no side effects}: like mathematical functions, '{lambda talk} functions are pure and free of any input/output side effects. _p The evaluation stops when the code is reduced to words without any curly braces. These words are sent to the browser's engine for any further evaluation - for instance HTML/CSS, SVG, ... and display. _h6 {i That's it!} _h5 5.1. wiki interface _p For every keyup in the {b input} field, the code is evaluated by the {b SPEECH.evaluate()} function, the result is displayed in the {b output} field. The {b infos} field displays the parentheses balance and the evaluation time, {b (10|10) [30ms]}. Unbalanced code is not evaluated. {pre °° var refresh = function() { var code = getId('code').value; var t0 = new Date().getTime(); code = SPEECH.evaluate( code ); var t1 = new Date().getTime(); getId('infos').innerHTML = '('+code.bal.left+'|'+code.bal.right+') | '+'['+(t1-t0)+'ms]'; if (code.bal.left === code.bal.right) getId('view').innerHTML = code.val; }; setTimeout( refresh, 1 ); // display on page load °°} _h5 5.2. the evaluator _p The function {b SPEECH} is defined and immediatelly invoked, returning essentially the function {b SPEECH.evaluate()}. To read the code click the button below: {input {@ type="button" value="SPEECH" onclick="LAMBDATANK.toggle_display('frame_editor')" style="font:bold 3.0em courier; text-align:center; width:100%;" }} _p and find the function SPEECH. {{hide} {def red span {@ style="color:red; font-weight:bold;"}} } {script ;; here is the JS code! var refresh = function() { var code = getId('code').value; var t0 = new Date().getTime(); code = SPEECH.evaluate( code ); var t1 = new Date().getTime(); getId('infos').innerHTML = '(' + code.bal.left + '|' + code.bal.right + ') | ' + '[' + (t1-t0) + 'ms]'; if (code.bal.left === code.bal.right) getId('view').innerHTML = code.val; }; var SPEECH = (function() { var dict = {}, LAMB_num = 0; var QUOT = {}, QUOT_num = 0; var COND = {}, COND_num = 0; var PAIR = {}, PAIR_num = 0; var ARRA = {}, ARRA_num = 0; var evaluate = function(s) { var bal = balance(s); if (bal.left === bal.right) { s = preprocessing(s); s = eval_special_forms(s); s = eval_forms(s); s = postprocessing(s); } return {val:s, bal:bal}; }; var eval_special_forms = function(s,flag) { while (s!==(s=form_replace(s,'(quote', eval_quote))) ; while (s!==(s=form_replace(s,'(let', eval_let))) ; while (s!==(s=form_replace(s,'(when', eval_when))) ; while (s!==(s=form_replace(s,'(if', eval_if))) ; while (s!==(s=form_replace(s,'(lambda', eval_lambda))) ; while (s!==(s=form_replace(s,'(def', eval_def, flag))) ; return s; }; var eval_forms = function(s) { // nested (first rest) var regexp = /\(([^\s()]*)(?:[\s]*)([^()]*)\)/g; while (s!==(s=s.replace(regexp, eval_form))) ; return s; }; var eval_form = function() { var f = arguments[1] || '', r = arguments[2] || ''; return dict.hasOwnProperty(f) ? dict[f].apply(null, [r]) : '[' + f + ' ' + r + ']'; }; var eval_quote = function(s) { // (quote expressions) // s = eval_special_forms( s ); return quote(s) }; var eval_lambda = function(s) { // (lambda (args) body) s = eval_special_forms( s ); var index = s.indexOf(')'), // gs commit 2018/06/06 //args = supertrim(s.substring(1, index)).split(' '), argStr = supertrim(s.substring(1, index)), args = argStr === "" ? [] : argStr.split(" "), // body = s.substring(index+2).trim(), name = '_LAMB_' + LAMB_num++, reg_args = []; for (var i=0; i < args.length; i++) reg_args[i] = RegExp( args[i], 'g'); dict[name] = function() { // gs commit 2018/06/06 //var vals = supertrim(arguments[0]).split(' '); var valStr = supertrim(arguments[0]); var vals = valStr === "" ? [] : valStr.split(" "); // return function(bod) { bod = eval_conds(bod, reg_args, vals); if (vals.length < args.length) { // partial call for (var i=0; i < vals.length; i++) bod = bod.replace( reg_args[i], vals[i] ); var _args_ = args.slice(vals.length).join(' '); bod = eval_lambda('(' + _args_ + ') ' + bod); } else if (vals.length === args.length) { // total call for (var i=0; i < args.length; i++) bod = bod.replace( reg_args[i], vals[i] ); } else { // extra are gathered in the last one var _vals_ = vals.slice(0,args.length); _vals_[args.length-1] = vals.slice(args.length-1,vals.length).join(' '); for (var i=0; i < args.length; i++) bod = bod.replace( reg_args[i], _vals_[i] ); } return eval_forms( bod ); }(supertrim(body)); }; return name; }; var eval_conds = function(bod,reg_args,vals) { // used in eval_lambda() var m = bod.match( /_COND_\d+/ ); if (m == null) { return bod } else { var name = m[0]; // _COND_n var cond = COND[m[0]]; // [bool, one, two] var bool = cond[0]; for (var i=0; i < vals.length; i++) bool = bool.replace( reg_args[i], vals[i] ); var boolval = (eval_forms(bool) === 'left') ? cond[1] : cond[2]; bod = bod.replace( name, boolval ); bod = eval_conds(bod, reg_args, vals); return bod } }; var eval_def = function(s, flag) { // (def name body) s = eval_special_forms(s, false); flag = (flag === undefined); var index = s.search(/\s/); var name = s.substring(0, index).trim(); var body = s.substring(index).trim(); if (body.substring(0,6) === '_LAMB_') { dict[name] = dict[body]; } else { body = eval_forms(body); dict[name] = function() { return body; }; } return flag ? name : ''; }; var eval_if = function(s) { // (if bool then one else two) -> COND_n s = eval_special_forms(s); s = supertrim(arguments[0]); var index, bool, one, two; index = s.indexOf('then'); bool = s.substring(0,index).trim(); s = s.substring(index); index = s.indexOf('else'); one = s.substring(5,index).trim(); s = s.substring(index); two = s.substring(5).trim(); var name = "_COND_" + COND_num++; COND[name] = [bool,one,two]; return name }; var eval_when = function(s) { // syntaxic sugar (when bool then one else two with args) // -> (((bool args) (pair one two)) args) // use pair,left,right,nil,nil? s = eval_special_forms(s); s = supertrim(arguments[0]); var index, bool, one, two, args; index = s.indexOf('then'); bool = s.substring(0,index).trim(); s = s.substring(index); index = s.indexOf('else'); one = s.substring(5,index).trim(); s = s.substring(index); index = s.indexOf('with'); if (index !== -1) { two = s.substring(5,index).trim(); s = s.substring(index+5); args = s; } else { two = s.substring(index + 5).trim(); args = ''; } bool = eval_lambda( "(" + args + ") " + bool ); one = eval_lambda( "(" + args + ") " + one ); two = eval_lambda( "(" + args + ") " + two ); return "(((" + bool + " " + args + ") (pair " + one + " " + two +")) " + args + ")" }; var eval_let = function (s) { // syntaxic sugar (let ( (arg val) ...) body) // -> ((lambda (args) body) vals) s = eval_special_forms( s ); s = supertrim( s ); var varvals = catch_form( '(', s ); var body = supertrim( s.replace( varvals, '' ) ); varvals = varvals.substring(1, varvals.length-1); var avv = [], i=0; while (true) { avv[i] = catch_form( '(', varvals ); if (avv[i] === 'none') break; varvals = varvals.replace( avv[i], '' ); i++; } for (var one ='', two='', i=0; i < avv.length-1; i++) { var index = avv[i].indexOf( ' ' ); one += avv[i].substring( 1, index ) + ' '; two += avv[i].substring(index+1, avv[i].length-1) + ' '; } return "((lambda ("+ one + ") " + body + ") " + two + ")"; }; //// var form_replace = function(str, sym, func, flag){ sym += ' '; var s = catch_form( sym, str ); return (s==='none')? str : str.replace(sym + s + ')', func(s,flag) ) }; var catch_form = function( symbol, str ) { var start = str.indexOf( symbol ); if (start == -1) return 'none'; var d1, d2; if (symbol === "(") { // {:x v} in let d1 = 0; d2 = 1; } else { // (symbol ...) d1 = symbol.length; d2 = 0; } var nb = 1, index = start; while(nb > 0) { index++; if ( str.charAt(index) == '(' ) nb++; else if ( str.charAt(index) == ')' ) nb--; } return str.substring( start+d1, index+d2 ) }; //// var balance = function (s) { var strt = s.match( /\(/g ), stop = s.match( /\)/g ); strt = (strt)? strt.length : 0; stop = (stop)? stop.length : 0; return {left:strt, right:stop}; }; var supertrim = function(s) { return s.trim().replace(/\s+/g, ' '); }; var quote = function(s) { // (quote x) -> _QUOT_n var name = '_QUOT_' + QUOT_num++; QUOT[name] = s; return name }; var unquote= function(s) { // _QUOT_n -> x var ss = QUOT[s]; // return (ss.charAt(0) !== "_") ? ss // from (quote x) : '(' + ss.substring(1) + ')'; // from '(x) }; var cond_display = function(s) { var bot = COND[s]; var bool = eval_forms(bot[0]); return eval_forms( (bool === 'left' )? bot[1] : bot[2] ) }; var preprocessing = function(s) { LAMB_num = 0; QUOT_num = 0; COND_num = 0; PAIR_num = 0; ARRA_num = 0; s = s.replace( /'\(/g, "(quote _" ); // '(x) -> (quote _x) // s = s.replace( /\(@/g, "(quote" ); // (@ x) -> (quote _x) s = s.replace( /\(λ/g, "(lambda" ); // λ -> lambda return s }; var postprocessing = function(s) { // gs commit 2018/06/06 // s = s.replace( /(_QUOT_\d+?)/g, unquote ); s = s.replace( /(_QUOT_\d+)/g, unquote ); s = s.replace( /(_COND_\d+?)/g, cond_display ); LAMB_num = 0; QUOT_num = 0; COND_num = 0; PAIR_num = 0; ARRA_num = 0; return s }; //// DICTIONARY dict['lib'] = function() { var str = '', index = 0; for (var key in dict) { if(dict.hasOwnProperty(key) && key.substring(0,6) !== '_LAMB_') { str += key + ', '; index++; } } return 'DICT: ['+ index + '] [' + str.substring(0,str.length-2) + ']'; }; //// MATHS dict['+'] = function () { var a = supertrim(arguments[0]).split(' '); for (var r=0, i=0; i < a.length; i++) { r += Number(a[i]) } return r; }; dict['*'] = function () { var a = supertrim(arguments[0]).split(' '); for (var r=1, i=0; i < a.length; i++) { r *= a[i] } return r; }; dict['-'] = function () { var a = supertrim(arguments[0]).split(' '); var r = a[0]; if (a.length === 1) { r = -r; } else { for (var i=1; i < a.length; i++) { r -= a[i] } } return r; }; dict['/'] = function () { var a = supertrim(arguments[0]).split(' '); var r = a[0]; if (a.length === 1) { r = 1/r; } else { for (var i=1; i < a.length; i++) { r /= a[i] } } return r; }; dict['%'] = function () { var a = supertrim(arguments[0]).split(' '); return Number(a[0]) % Number(a[1]) }; //// dict['<'] = function() { var a = supertrim(arguments[0]).split(' '); var x = Number(a[0]), y = Number(a[1]); return (x < y)? 'left' : 'right'; }; dict['='] = function() { var a = supertrim(arguments[0]).split(' '); return (a[0] === a[1])? 'left' : 'right'; }; var mathtags = ['abs', 'acos', 'asin', 'atan', 'ceil', 'cos', 'exp', 'floor', 'pow', 'log', 'random', 'round', 'sin', 'sqrt', 'tan', 'min', 'max']; for (var i=0; i< mathtags.length; i++) { dict[mathtags[i]] = function(tag) { return function() { return tag.apply( null, supertrim(arguments[0]).split(' ') ) } }(Math[mathtags[i]]); } dict['PI'] = function () { return Math.PI }; dict['E'] = function () { return Math.E }; //// PAIRS dict['pair'] = function () { // (pair 12 34) var a = supertrim(arguments[0]).split(' '); // [12,34] var name = '_PAIR_' + PAIR_num++; PAIR[name] = a; return name; }; dict['pair?'] = function () { // (pair? xx) var a = arguments[0].trim(); // xx return (a.substring(0,6) === '_PAIR_')? 'left' : 'right'; }; dict['nil?'] = function () { // (nil? xx) var a = arguments[0].trim(); // xx return (a === 'nil')? 'left' : 'right'; }; dict['left'] = function () { // (left _PAIR_n) var a = arguments[0].trim(); // _PAIR_n return (a.substring(0,6) === '_PAIR_')? PAIR[a][0] : a; }; dict['right'] = function () { // (left _PAIR_n) var a = arguments[0].trim(); // _PAIR_n return (a.substring(0,6) === '_PAIR_')? PAIR[a][1] : a; }; //// ARRAYS dict['#.new'] = function() { // (#.new 12 34 56) var a = supertrim(arguments[0]).split(' '); var name = '_ARRA_' + ARRA_num++; ARRA[name] = a; return name }; dict['#.array?'] = function() { // (#.array? a) var a = arguments[0].trim(); a = ARRA[a]; return (Array.isArray(a))? 'left' : 'right' }; dict['#.disp'] = function() { // (#.disp arr) var a = arguments[0].trim(); a = ARRA[a]; return ( Array.isArray( a ) )? JSON.stringify(a) : a }; dict['#.length'] = function() { // (#.length a) var a = arguments[0].trim(); a = ARRA[a]; return a.length }; dict['#.empty?'] = function() { // (#.empty? a) var a = arguments[0].trim(); a = ARRA[a]; return (a.length === 0)? 'left' : 'right' }; dict['#.first'] = function() { // (#.first a) var a = arguments[0].trim(); a = ARRA[a]; return (Array.isArray( a ))? a[0] : a }; dict['#.last'] = function() { // (#.last a) var a = arguments[0].trim(); a = ARRA[a]; return (Array.isArray( a ))? a[a.length-1] : a }; dict['#.rest'] = function() { // (#.rest a) var a = arguments[0].trim(); a = ARRA[a]; var name = '_ARRA_' + ARRA_num++; ARRA[name] = (Array.isArray( a ))? a.slice(1) : a return name }; dict['#.get'] = function() { // (#.get a i) var a = supertrim(arguments[0]).split(' '); var val = ARRA[a[0]][a[1]]; return (val !== undefined)? val : 'undefined' }; // HTML dict['@'] = function() { return '@@' + supertrim(arguments[0]) + '@@' }; var htmltags = [ 'div', 'span', 'a', 'ul', 'ol', 'li', 'dl', 'dt', 'dd', 'table', 'tr', 'td', 'h1', 'h2', 'h3', 'h4', 'h5', 'h6', 'p', 'b', 'i', 'u', 'center', 'br', 'hr', 'blockquote', 'sup', 'sub', 'del', 'code', 'img', 'pre', 'textarea', 'canvas', 'audio', 'video', 'source', 'select', 'option', 'object', 'svg', 'line', 'rect', 'circle', 'ellipse', 'polygon', 'polyline', 'path', 'text', 'g', 'mpath', 'use', 'textPath', 'pattern', 'image', 'clipPath', 'defs', 'animate', 'set', 'animateMotion', 'animateTransform', 'title', 'desc' ]; for (var i=0; i< htmltags.length; i++) { dict[htmltags[i]] = function(tag) { return function() { var s = arguments[0].trim(); var m = s.match(/@@(.*?)@@/); var html; if (m !== null) { var _att_ = m[0]; var att = _att_.replace(/@@/g, '') var body = s.replace( _att_, '' ); if (LAMBDATALK) // we are inside lambdatank return LAMBDATALK.eval_forms( "{" + tag + " {@ " + att +"}" + body + "}" ); else // we are outside return "<" + tag + " " + att + ">" + body + "" + tag + ">"; } else { if (LAMBDATALK) return LAMBDATALK.eval_forms( "{" + tag + " " + s + "}" ); else return "<" + tag + ">" + body + "" + tag + ">"; } }; }(htmltags[i]); } dict['bigfac'] = function() { // require lib_BN var fac = function(n) { if (n.compare(0) === 0) return 1; else return n.multiply( fac( n.subtract(1))) } var n = new BigNumber( arguments[0], BN_DEC ); return fac( n ) }; // and so on ... //// DICTIONARY end return { evaluate:evaluate, dict:dict, supertrim:supertrim } })(); // end SPEECH setTimeout( refresh, 1 ); }