lambdaspeech
::
tao
1
|
list
|
login
|
load
|
|
{style ;; #page_frame { width:98%; } #page_content { font:normal 2.0em papyrus; background:#ffe; } pre { box-shadow:0 0 8px #000; padding:5px; background:#fff; } } {center {i It must be understood that this is not a paper on Taoism! {br} A minimum sense of humour is required. {br} If not see [[tao2]] or [[nutshell]] }} {center {div {@ style="font:italic 6.0em times; margin:20px;"} '{λ 道}} {i « In the beginning was the Word. »} } _p But what are Words in an empty World? Something is needed to give life to words. According to [[wikipedia|https://en.wikipedia.org/wiki/Yin_and_yang]]: {div {@ style="font:italic 0.8em times; border-left:1px solid #000; margin:0 20px; padding:0px 40px;"} _p The {b Tao} philosophy is more commonly expressed in the relationship between {b wu} (void or emptiness, in the sense of wuji) and {b yinyang} (the natural dynamic balance between opposites), leading to its central principle of wu wei (inaction, or inexertion). °°° _ul Yin 陰 or 阴 Noun ① [philosophy] negative/passive/female principle in nature ② Surname Bound morpheme ① the moon ② shaded orientation ③ covert; concealed; hidden ④ ⑦ negative ⑧ north side of a hill ⑨ south bank of a river ⑩ reverse side of a stele ⑪in intaglio Stative verb ① overcast _ul Yang 陽 or 阳 Bound morpheme ① [Chinese philosophy] positive/active/male principle in nature ②the sun ④ in relief ⑤ open; overt ⑥ belonging to this world ⑦ [linguistics] masculine ⑧ south side of a hill ⑨ north bank of a river °°° } _p So what can be done with Words, Yin & Yang? _h2 1) let's talk _p In human language we can swap words using such a command: {pre {b replace} x & y {b in} ... y x ... // swap x & y {b by} hello & world -> ... world hello ... } _p We can also compose several commands: {pre {b replace} h & w // capitalize h & w {b in} {b replace} x & y {b in} ... y x ... // swap x & y {b by} hello & world {b by} H & W -> ... World Hello ... } _p {i Ad libitum.} _p These commands are quite understandable but, in order to enlight the difference between words used as verbs and words used as objects, we are going to {i carefully} insert well balanced curly braces: {pre '{{replace {x & y} in ... y x ...} by hello & world} } _p The "{code &}", "{code in}" and "{code by}" separators are now useless and we forget them {pre '{{replace {x y} ... y x ...} hello world} } _p If finally we replace {code replace} by {code lambda} and write in a single line {pre '{{lambda {x y} ... y x ...} hello world} } _p we have got an {b IIFE}, a valid expression written in '{lambda talk}, a dialect of a language created by {i Alonzo Church} in the thirties, the {i λ-calculus}, and using a Lisp-like syntax. Such a language allows to, {i theoretically}, compute any algorithm one can think of. And more efficiently to ask a computer to do the job! _h2 2) IIFE _p An {b IIFE} is an {b I}mmediatly {b I}nvoked {b F}onction {b E}xpression {center {pre '{{lambda {words1} words2} words3}}} _p where we can distinguish two parts, an {i abstraction} and an {i application} {prewrap 1) {b abstraction}: '{lambda {words1} words2} replaced by a word, {b ref}, referencing an anonymous function added to some dictionary {b DICT}, with {code words1} as arguments and {code words2} as the body, 2) {b application}: '{ref words3} replaced by other words resulting from the application to words3 of the function referenced by {b ref}. } _p Notes: _ul 1) {code words2} and {code words3} can be either {b words or inner expressions}, the evaluation being done from inside out: it's a {i recursive replacement}, _ul 2) abstractions are replaced before applications, _ul 3) the dictionary {b DICT} is initially empty, there are no primitives, we are in an empty space with nothing but words, abstractions and applications. _p So, in the general case, an expression is defined like this: {pre expression : word | '{lambda {words} expression} | '{expression expression} } _p An expression is an instable construction whose future is to be reduced to words. _p Ok, and what about Yin and Yang? _p Well, Yin is abstraction, the {i female principle} who delays, keeping "unfinished" datas in her belly until completion, and Yang is application, the {i male principle} who get finished but instable expressions and forces them to be reduced to words. Why not? _p More seriously, in the current '{lambda talk} implementation, see [[start]], {i lambdas} have the following properties: _ul 1) called with a number of values equal to the number of arguments a lambda returns a value {pre '{{lambda {x y} ... y x ...} hello world} -> {{lambda {x y} ... y x ...} hello world} } _ul 2) called with a number of values lesser than the number of arguments a lambda returns a new lambda waiting for the missing ones {pre 1: '{{lambda {x y} ... y x ...} hello} -> _LAMB_32 // some unique ref given by the system 2: '{_LAMB_32 world} -> {{{lambda {x y} ... x y ...} hello} world} } _ul 3) called with a number of values greater than the number of arguments, the extra ones are taken by the last argument and the lambda returns a value {pre '{{lambda {x y ♥} y x ♥} // ♥ gets any sequence of words one two, any sequence of words} -> {{lambda {x y ♥} y x ♥} one two, any sequence of words} } _ul 4) lambdas can be nested {pre '{{lambda {h w} {{lambda {x y} ... y x ...} hello world}} H W} -> {{lambda {h w} {{lambda {x y} ... y x ...} hello world}} H W} '{{lambda {z} {z {lambda {x y} x}}} {{lambda {x y z} {z x y}} Hello World}} -> {{lambda {z} {z {lambda {x y} x}}} {{lambda {x y z} {z x y}} Hello World}} '{{lambda {z} {z {lambda {x y} y}}} {{lambda {x y z} {z x y}} Hello World}} -> {{lambda {z} {z {lambda {x y} y}}} {{lambda {x y z} {z x y}} Hello World}} } _p The two last expressions remind a pair structure. It's time to introduce names! _h2 3) names _p In order to make expressions easier to write and read, we introduces a second {i optional and useful} abstraction, {code '{def name expression}}, allowing to give a name to functions and to constants. {pre '{def HI Hello World} -> {def HI Hello World} HI means '{HI} -> HI means {HI} '{def swap {lambda {x y} y x}} -> {def swap {lambda {x y} y x}} '{swap hello world} -> {swap hello world} } _p Let's define 7 useful functions {pre '{def | {lambda {x y} x}} -> {def | {lambda {x y} x}} '{def ø {lambda {x y} y}} -> {def ø {lambda {x y} y}} '{def [] {lambda {x y z} {z x y}}} -> {def [] {lambda {x y z} {z x y}}} '{def [ {lambda {z} {z |}}} -> {def [ {lambda {z} {z |}}} '{def ] {lambda {z} {z ø}}} -> {def ] {lambda {z} {z ø}}} '{def ? {lambda {z} {z {| ]} [}}} -> {def ? {lambda {z} {z {| ]} [}}} } _p Now we can easily write pairs {pre '{def P {[] hello world}} -> {def P {[] hello world}} '{[ {P}} -> {[ {P}} '{] {P}} -> {] {P}} } _p Note the partial application {code '{[] hello world}} in which {code []} waits for 3 values, gets only two, memorizes them and returns a function waiting for the missing one. At this point we have defined a first important data structure, we can agregate two words and select each of them. _h2 4) lists and recursion _p We can nest pairs to build a {i list} and select its elements {pre '{def L {[] hello {[] brave {[] new {[] world ø}}}}} -> {def L {[] hello {[] brave {[] new {[] world ø}}}}} '{[ {L}} -> {[ {L}} '{[ {] {L}}} -> {[ {] {L}}} '{[ {] {] {L}}}} -> {[ {] {] {L}}}} '{[ {] {] {] {L}}}}} -> {[ {] {] {] {L}}}}} '{? {] {] {] {] {L}}}}}} -> {? {] {] {] {] {L}}}}}} // '{? ø} } _p This sequence of selections leads us to build a {i recursive} algorithm displaying the list {pre '{def D {lambda {list} {{{? list} {[] {lambda {list} } {lambda {list} {[ list} {D {] list}} } }} list}}} -> {def D {lambda {list} {{{? list} {[] {lambda {list} } {lambda {list} {[ list} {D {] list}} } }} list}}} '{D {L}} -> {D {L}} } _p At this point, in a few lines without any shadow areas, we have got 3 fundamental data and control structures, {i pairs, lists and recursion}. Remember that all of this is nothing but {i replacements in sequences of words}. We began this page with a command replacing "x" and "y" by "hello" and "world", we introduced curly braces, we replaced {i replace} by {i lambda} and this is how the last expression {code '{D {L}}} can be rewritten {i without names} and coming back to primitives {pre '{{lambda {k} {{lambda {f k} {f f k}} {lambda {f k} {{{{lambda {z} {z {{lambda {x y} x} {lambda {z} {z {lambda {x y} y}}}} {lambda {z} {z {lambda {x y} x}}}}} k} {{lambda {x y z} {z x y}} {lambda {f k} } {lambda {f k} {{lambda {z} {z {lambda {x y} x}}} k} {f f {{lambda {z} {z {lambda {x y} y}}} k}} } }} f k}} k}} {{lambda {x y z} {z x y}} hello {{lambda {x y z} {z x y}} brave {{lambda {x y z} {z x y}} new {{lambda {x y z} {z x y}} world {lambda {x y} y}}}}}} -> {{lambda {k} {{lambda {f k} {f f k}} {lambda {f k} {{{{lambda {z} {z {{lambda {x y} x} {lambda {z} {z {lambda {x y} y}}}} {lambda {z} {z {lambda {x y} x}}}}} k} {{lambda {x y z} {z x y}} {lambda {f k} } {lambda {f k} {{lambda {z} {z {lambda {x y} x}}} k} {f f {{lambda {z} {z {lambda {x y} y}}} k}} } }} f k}} k}} {{lambda {x y z} {z x y}} hello {{lambda {x y z} {z x y}} brave {{lambda {x y z} {z x y}} new {{lambda {x y z} {z x y}} world {lambda {x y} y}}}}}} } _p {b Note:} _ul some of you will discover in this long convoluted expression a {i strange Y-combinator}, {code '{lambda {f k} {f f k}}}, allowing to build recursion without names. It's out of the scope of this short introduction, see more explanations in [[kiss]]. _ul this wiki page is written using '{lambda talk}, you can freely open the wiki page in edition and uncomment this convoluted expression to see that it's actually evaluated - in this wiki page - to "hello brave new world". _p So, just words and replacements. Words, Abstractions and Applications. Words, Yin & Yang. _p And so what? _h2 5) let's compute _p The last function {code D} can be slightly modified to return dots {pre '{def N {lambda {list} {{{? list} {[] {lambda {list} } {lambda {list} .{N {] list}} } }} list}}} -> {def N {lambda {list} {{{? list} {[] {lambda {list} } {lambda {list} .{N {] list}} } }} list}}} '{N {L}} -> {N {L}} // read 4 in a primitive unary numeration } _p We have everything to build arithmetic from scratch, the set of natural numbers, [0 1 2 3 ...], the operators [» « + * - / % ...], useful functions [serie map reduce sort ...] and more on demand. For instance playing with the Towers of Hanoï: {pre '{def hanoi {lambda {:n :from :to :via} {{{? :n} {[] {lambda {:n :from :to :via} } {lambda {:n :from :to :via} {hanoi {« :n} :from :via :to} {br} move disc {N :n} from tower :from to tower :to {hanoi {« :n} :via :to :from} }}} :n :from :to :via}}} -> hanoi '{hanoi {four} A B C} -> move disc 1 from tower A to tower C move disc 2 from tower A to tower B move disc 1 from tower C to tower B move disc 3 from tower A to tower C move disc 1 from tower B to tower A move disc 2 from tower B to tower C move disc 1 from tower A to tower C move disc 4 from tower A to tower B move disc 1 from tower C to tower B move disc 2 from tower C to tower A move disc 1 from tower B to tower A move disc 3 from tower C to tower B move disc 1 from tower A to tower C move disc 2 from tower A to tower B move disc 1 from tower C to tower B } _p And my question is: {i Was Alonzo Church Taoist?} _p {i I'm joking of course.} _p More to see in these pages: _ul [[tao2]] _ul [[kiss]] _ul [[factory_201902_paper]] _ul [[start]] _p Your opinion is welcome, for instance in [[HN|https://news.ycombinator.com/item?id=20144399]], in [[agora]] or by mail to {i marty•alain_at_free•fr}. Please, don't be evil. _p {i Alain Marty 2019/06/10}
lambdaspeech v.20200126