lambdaway :: Y

5 | list | login |load

| |

{require lib_uncover}
{uncover http://www.marktarver.com/tree.png  100 600 As simple as that!}

_h1 From [[Y]] to [[Ω|?view=omega]] | [[florilege|?view=Y_en2]]

_p I read {b [["The Why of Y"|https://www.dreamsongs.com/Files/WhyOfY.pdf]]}, a 4 pages paper where, using the Scheme language, Richard P.Gabriel - a respectable teacher for whom I have great respect. - tries to explain to me the beauties of the Y-combinator.

_p {b And, sorry, I don't understand it.}

_p When I read such a paper [[implementing recursion with the y-combinator in 7 languages |https://levelup.gitconnected.com/implementing-recursion-with-the-y-combinator-in-any-language-9e83fa369ca]], or this one [[Y & Ω|https://medium.com/@dkeout/why-you-must-actually-understand-the-%CF%89-and-y-combinators-c9204241da7a]], or even this one [[everything|https://www.everything2.com/title/fixed+point+combinator]], I feel better but I am still unsatisfied. I personally need to code algorithms to have a chance to understand them. To do this I generally use my homemade language, [[lambdatalk|?view=start]], a dialect of λ-calculus, a small cousin of Scheme, which has the advantage to work in a wiki, the simplest IDE I'm aware of.

_h2 1) recursion

_p Recursion is usually introduced on the example of the factorial function defined as follows

{pre 
fac(0) = 1 
fac(n) = n*fac(n-1)
}

_p The lambdatalk code is easily derived from this

{pre
'{def fac                           // define fac as the
 {lambda {:n}                      // function of n
  {if {= :n 0}                     // if n=0
   then 1                          // then return 1
   else {* :n {fac {- :n 1}}}      // else return n*fac(n-1)
  }                                // end of if
 }                                 // end of function
}                                  // end of define
-> {def fac {lambda {:n} {if {= :n 0} then 1 else {* :n {fac {- :n 1}}}}}}
}

_p and applying this function on a number displays the result

{pre
'{fac 10}
-> {fac 10}
}

_p This works very well but for various reasons discussed below I would like to discard the function's global name from the body. Here comes the {b Y-combinator}

_h2 2) Y-combinator

_p In λ-calculus the {b Y-combinator} is defined like this:

{center {pre 
Y = λf.(λx. f(x x)) (λx. f(x x))
}}

_p Translated into the lambdatalk syntax I get:

{pre
'{def Y
 {lambda {:f}
  {{lambda {:x} {:f {:x :x}}}
   {lambda {:x} {:f {:x :x}}}
}}}
}

_p But lambdatalk doesn't know closures and I must add {b :f} in the list of arguments of inside lambdas, and redefine it using an {i Immediately Invoked Function Expression}, IIFE:

{pre

'{def Y
 {lambda {:f}
  {{{lambda {:f :x} {:f {:x :x}}} :f}
   {{lambda {:f :x} {:f {:x :x}}} :f}
}}}
}

_p Lambdatalk uses a "call by value" evaluation (no call by name) and I must postpone the evaluation of inside expressions embedded in a lambda, and again I must use an IIFE

{pre
'{def Y
 {lambda {:f}
  {{{lambda {:f :x} {:f {{lambda {:x :y} {{:x :x} :y}} :x}}} :f}
   {{lambda {:f :x} {:f {{lambda {:x :y} {{:x :x} :y}} :x}}} :f}
}}}
}

_p which could be rewritten this way

{pre
'{def Y {lambda {:f} {{ω :f} {ω :f}}}}
-> {def Y {lambda {:f} {{ω :f} {ω :f}}}}
}
_p using

{pre
'{def ω
 {lambda {:f :x}
  {:f {{lambda {:x :y} {{:x :x} :y}} :x}}}}
-> {def ω
 {lambda {:f :x}
  {:f {{lambda {:x :y} {{:x :x} :y}} :x}}}} 
}

_p It's time to redefine the {b fac} recursive function as an {i almost recursive} function, adding a new argument, {b :f}, acting as local variable where is stored the function's name.

{pre
'{def yfac
 {lambda {:f :n}
  {if {= :n 0} then 1 else {* :n {:f {- :n 1}}}}}}
-> {def yfac
 {lambda {:f :n}
  {if {= :n 0} then 1 else {* :n {:f {- :n 1}}}}}}

'{{Y yfac} 10} 
-> {{Y yfac} 10} 
}

_p It works fine ... but stays somewhat "twisted". And so I will explore another way using a very simple combinator.

_h2 3) Ω-combinator

_p I redefine the {b yfac} almost recursive function in a slightly different way, just doubling the {b :f} argument

{pre
'{def afac                
 {lambda {:f :n}
  {if {= :n 0} 
   then 1 
   else {* :n {:f :f {- :n 1}}}}}}  // note the double :f :f
-> {def afac
 {lambda {:f :n}
  {if {< :n 1} then 1 else {* :n {:f :f {- :n 1}}}}}}
}

_p and I rewrite the call {b doubling the name}, like this

{pre
'{afac afac 10}
-> {afac afac 10}
}

_p As simple as that! And even more I can use a nice {b Ω-combinator} simply doubling the name for me.

{pre
'{def Ω {lambda {:f} {:f :f}}}             
-> {def Ω {lambda {:f} {:f :f}}}

'{{Ω afac} 10}                               
-> {{Ω afac} 10}
}

_h2 4) going further

_p But until now I have two global names, which is not better. So I first compose {b Ω} & {b afac} into a single function {b Ωfac}

{pre
'{def Ωfac
 {lambda {:n}
  {{{lambda {:f} {:f :f}}
   {lambda {:f :n}
    {if {= :n 0} then 1 else {* :n {:f :f {- :n 1}}}}}} :n}}} 
-> {def Ωfac
 {lambda {:n}
  {{{lambda {:f} {:f :f}}
   {lambda {:f :n}
    {if {< :n 1} then 1 else {* :n {:f :f {- :n 1}}}}}} :n}}}

'{Ωfac 10}  
-> {Ωfac 10}
}

_p and I forget the name using an IIFE

{pre
'{{lambda {:n}       
 {{{lambda {:f} {:f :f}}                  // the Ω combinator
  {lambda {:f :n}                         // the afac function
   {if {< :n 1}
    then 1
    else {* :n {:f :f {- :n 1}}}}}} :n}}
 10}                                       // the call
-> {{lambda {:n}
  {{{lambda {:f} {:f :f}}
   {lambda {:f :n}
    {if {< :n 1} then 1 else {* :n {:f :f {- :n 1}}}}}} :n}} 10}
}

_p I remember that an {b IIFE} can be replaced by a friendly {i lexical sugar}, the {b let} special form:

{pre
'{let { {:ω {lambda {:f} {:f :f}}}          // the Ω-combinator
       {:f {lambda {:f :n}                 // the afac function
             {if {= :n 0} 
              then 1 
              else {* :n {:f :f {- :n 1}}}}}} 
       
     } {{:ω :f} 10}                        // the call
}
-> {let { {:f {lambda {:f :n}
           {if {< :n 2} then 1 else {* :n {:f :f {- :n 1}}}}}}
          {:ω {lambda {:f} {:f :f}}}
        } {{:ω :f} 10} 
}
}

_p And so I can recurse in a local context. And I understand the whole trip.

_p {b That's it!}

_h2 let's summarize

_ul 1) in the {b global version} I understand that the initial factorial function, {b fac}, has just been supplemented in the {i almost-recursive} version, {b afac}, with a new argument {b :f}, acting as a {b local variable} that will be called by a {b Ω} function acting as a {b doubler}. 
_ul 2) in the {b local version} the {b afac & ω} global functions became {b :f & :ω} local functions.

_p All codes work in the wiki page, it can be tested, edited and I don't need anything more to understand what the Y-combinator does.

_p Regarding the lambdatalk language I just need to remember that:

_ul 1) the special form {b '{lambda {var ...} expression}} does not accept free variables. Lambdas are combinators, they are really pure functions without edge effect, in input as well as in output.

_ul 2) the special form {b '{let { {var val} ...} expression}} is a syntactic sugar for the {b IIFE} expression {b '{{lambda {var ...} expression} val ...}}, which is nothing else than the text replacement process "{b replaces var ... in expression by val ...}" {i to which all language is reduced}.

_h2 conclusion

_p See [[lambda]] for detailed explanations about lambdas. Everything stays in a basic text substitution process all the time. The operation of a function can be understood by reading the list of arguments. No need to look outside. Contextual independence is total.

_p On the contrary, in his four-page paper Richard P. Gabriel introduces the {b letrec} special form to use instead of the {b let} special form when dealing with recursion. And of course he assumes that I know that in Scheme lambdas are {b closures} and accept free variables taking their values automatically from the lexical context. For me {b letrec} and {b closures} are useful {b but magical} processes functioning behind the curtain, preventing me from understanding the substance of the operation.

_p Richard P. Gabriel wants to explain the {b Y-combinator} to me, but I don't understand.

_p {b Did I miss something?}

_p Alain Marty | 2022/03/04

_p [[HN|https://news.ycombinator.com/item?id=31051015]]

{style 
body { background:#fff; }
#page_frame { border:0; }
#page_content { background:transparent; color:#000; border:0;}
.page_menu { background:transparent; color:#000;}
a {color:red}
pre { font-size:1.2em; }
}