lambdaspeech

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}