lambdaway :: Ycombinator

3 | list | login |load

| |

{require lib_BN}

_h1 Ycombinator | [[Ycombinator2]] | [[Y]]

_p The factorial and fibonacci functions use to be defined this way:

_ul [[HN|https://news.ycombinator.com/item?id=8843550]]

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

'{def fibo
 {lambda {:n}
  {if {< :n 2}
   then 1
   else {+ {fibo {- :n 1}} {fibo {- :n 2}}}}}}
-> {def fibo
 {lambda {:n}
  {if {< :n 2}
   then 1
   else {+ {fibo {- :n 1}} {fibo {- :n 2}}}}}}

'{fac 6}
-> {fac 6}

'{fibo 10}
-> {fibo 10}
}

_h2 1) the Y combinator

_p Following [[cannata/cs345|http://www.cs.utexas.edu/~cannata/cs345/Class%20Notes/27%20Lambda%20Calculus%20and%20the%20Y%20Combinator.html]] « {i A combinator is a function that does not make use of any free variables, which is why it cannot even use basic operations like + or car. So it is basically limited to binding constructs, function applications, and its (bound) variables. }» {b  A combinator is just a lambda expression with no free variables.} This is how it is usually introduced in papers on λ-calculus:

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

_p {i Welcome in Wonderland!} 
_p This is how it can be defined in lambdatalk:

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

_p It's difficult to be more simple! And now we can work. It happens that the Ycombinator can help {i almost recursive functions} to be recursive.  Let's first redefine {code fac} and {code fibo} as {i almost recursive} functions, just adding a local variable {code :f} storing the name. The Y combinator will be the "bridge"

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

'{def almost-fibo
 {lambda {:f :n}
  {if {<  :n 2}
   then 1
   else {+ {:f :f {- :n 1}} {:f :f {- :n 2}}}}}}
-> {def almost-fibo {lambda {:f :n}
  {if {<  :n 2} then 1
   else {+ {:f :f {- :n 1}} {:f :f {- :n 2}}}}}}
}

_p We can now apply the Y-combinator to these functions and given values

{pre
'{{Y almost-fac} 6}
-> {{Y almost-fac} 6}
'{{Y almost-fibo} 10}
-> {{Y almost-fibo} 10}
}

_p Note that {code '{almost-fac almost-fac 6} and '{almost-fibo almost-fibo 10}} do work too, as we could expect. We finally compose the Ycombinator and the almost recursive functions:

{pre
'{def Yfac {lambda {:n} {{Y almost-fac} :n}}}
-> {def Yfac {lambda {:n} {{Y almost-fac} :n}}}
'{def Yfibo {lambda {:n} {{Y almost-fibo} :n}}}
-> {def Yfibo {lambda {:n} {{Y almost-fibo} :n}}}

'{Yfac 6} 
-> {Yfac 6}
'{Yfibo 10} 
-> {Yfibo 10}
}

_p And optionnaly we can forget names and write {b IIFE}s ( {i Immediately Invoked Functions Expressions} )

{pre
1) fac:
'{{{lambda {:f} {:f :f}} 
 {lambda {:f :n}
  {if {= :n 1} 
   then 1 
   else {* :n {:f :f {- :n 1}}}}}} 6}
-> {{{lambda {:f} {:f :f}} 
 {lambda {:f :n}
  {if {= :n 1} 
   then 1 
   else {* :n {:f :f {- :n 1}}}}}} 6}

2) fibo:
'{{{lambda {:f} {:f :f}} 
 {lambda {:f :n}
  {if {<  :n 2} then 1
   else {+ {:f :f {- :n 1}} {:f :f {- :n 2}}}}}} 10}  
-> {{{lambda {:f} {:f :f}} 
 {lambda {:f :n}
  {if {<  :n 2} then 1
   else {+ {:f :f {- :n 1}} {:f :f {- :n 2}}}}}} 10}

}

_h2 2) tail recursion

_p It's well known that the fibonacci naïve function is very slow and quickly locks the computer when applied on increasing values. Tail-recursion is the answer. Usually a tail_recursive function adds an accumulator and must be called by another one initializing it. 
{pre
'{def tfac

{def tfac.r         // recursive part
  {lambda {:n :a}
   {if {= :n 1}
    then :a
    else {tfac.r {- :n 1} {* :n :a}}}}}

{lambda {:n}
  {tfac.r :n 1}}}    // initialize and recurse
-> {def tfac
 {def tfac.r
  {lambda {:n :a}
   {if {= :n 1}
    then :a
    else {tfac.r {- :n 1} {* :n :a}}}}}
 {lambda {:n}
  {tfac.r :n 1}}}

'{def tfibo

{def tfibo.r
  {lambda {:n :a :b}
   {if {< :n 1}
    then :a
    else {tfibo.r {- :n 1} {+ :a :b} :a}}}}

{lambda {:n}
  {tfibo.r :n 1 0}}}
-> {def tfibo
 {def tfibo.r
  {lambda {:n :a :b}
   {if {< :n 1}
    then :a
    else {tfibo.r {- :n 1} {+ :a :b} :a}}}}
 {lambda {:n}
  {tfibo.r :n 1 0}}}

'{tfac 100}
-> {tfac 100}
'{tfibo 300}
-> {tfibo 300}

}

_p Thanks to the Y combinator, a tail-recursive function can be written without any helper function, avoiding the dictionary's pollution:

{prewrap
'{def ytfac
 {lambda {:n}
  {{{lambda {:f} {:f :f}} 
   {lambda {:f :n :a}
    {if {= :n 1}
     then :a
     else {:f :f {- :n 1} {* :n :a}}}}} :n 1}}} 
-> {def ytfac
 {lambda {:n}
  {{{lambda {:f} {:f :f}} 
   {lambda {:f :n :a}
    {if {= :n 1}
     then :a
     else {:f :f {- :n 1} {* :n :a}}}}} :n 1}}}

'{ytfac 100}
-> {ytfac 100}

'{def ytfibo
 {lambda {:n}
  {{{lambda {:f} {:f :f}} 
   {lambda {:f :n :a :b}
    {if {< :n 1}
     then :a
     else {:f :f {- :n 1} {+ :a :b} :a}}}} :n 1 0}}} 
-> {def ytfibo
 {lambda {:n}
  {{{lambda {:f} {:f :f}} 
   {lambda {:f :n :a :b}
    {if {< :n 1}
     then :a
     else {:f :f {- :n 1} {+ :a :b} :a}}}} :n 1 0}}}

'{ytfibo 300}
-> {ytfibo 300}

'{S.map ytfibo {S.serie 1 100}}
-> {S.map ytfibo {S.serie 1 100}} 
}

_h2 3) big numbers

_p Finally, using a library {code lib_BN} stored elsewhere in the wiki and called using the {code require} form, we can compute exact values. Just replace {code '{* a b}} by {code '{BN.* a b}} and initialization of {code 0 & 1} by {code '{BN.new 0} & '{BN.new 1}}.

{prewrap

'{def BN.fac
 {lambda {:n}
  {{lambda {:f :n :a} {:f :f :n :a}} 
   {lambda {:f :n :a}
    {if {= :n 1}
     then :a
     else {:f :f {- :n 1} {BN.* :n :a}}}}
    :n {BN.new 1}}}}
-> {def BN.fac
 {lambda {:n}
  {{{lambda {:f} {:f :f}} 
   {lambda {:f :n :a}
    {if {= :n 1}
     then :a
     else {:f :f {- :n 1} {BN.* :n :a}}}}}
    :n {BN.new 1}}}}

'{BN.fac 100}
-> {BN.fac 100}

'{def BN.fibo
 {lambda {:n}
  {{{lambda {:f} {:f :f}} 
   {lambda {:f :n :a :b}
    {if {< :n 1}
     then :a
     else {:f :f {- :n 1} {BN.+ :a :b} :a}}}} :n {BN.new 1} {BN.new 0}}}}
-> {def BN.fibo
 {lambda {:n}
  {{{lambda {:f} {:f :f}} 
   {lambda {:f :n :a :b}
    {if {< :n 1}
     then :a
     else {:f :f {- :n 1} {BN.+ :a :b} :a}}}} :n {BN.new 1} {BN.new 0}}}}

'{BN.fibo 300}
-> {BN.fibo 300}
}

_p Notes

_ul this page is computed in about 100ms on my iPad Pro. 
_ul the Y-combinator can be useful out of the domain of pure theory.
_ul it's shown in [[meta5]] and [[fromroots2canopy]] that the {code '{if bool then one else two}} special form could be forgotten, using nothing but lambdas, leading to a code very close to the λ-calculus level, ie. to a very basic text-substitution tool. Funny isnt'it ?

_p {i Alain Marty 2020/09/04 improved on 2021/10/24}

_h2 refs
_ul [[Y combinator real life application: recursive memoization in clojure|http://blog.klipse.tech/lambda/2016/08/10/y-combinator-app.html]]
_ul [[https://news.ycombinator.com/item?id=13045032|https://news.ycombinator.com/item?id=13045032]]
_ul [[comments|https://news.ycombinator.com/threads?id=martyalain]]
_ul [[The lambdaway project, a small and coherent language dedicated to the web|https://news.ycombinator.com/item?id=12304312]]
_ul [[https://rosettacode.org/wiki/Y_combinator#Lambdatalk|https://rosettacode.org/wiki/Y_combinator#Lambdatalk]]
_ul [[http://www.cs.utexas.edu/~cannata/Lambda Calculus and the Y Combinator|http://www.cs.utexas.edu/~cannata/cs345/Class%20Notes/27%20Lambda%20Calculus%20and%20the%20Y%20Combinator.html]]
_ul [[https://www.cs.bgu.ac.il/~comp171/wiki.files/ps6.pdf|https://www.cs.bgu.ac.il/~comp171/wiki.files/ps6.pdf]]
_ul [[codereview.stackexchange.com/do-i-understand-the-y-combinator|http://codereview.stackexchange.com/questions/152621/do-i-understand-the-y-combinator]]
_ul [[https://www.cs.bgu.ac.il/~comp171/wiki.files/ps6.pdf|https://www.cs.bgu.ac.il/~comp171/wiki.files/ps6.pdf]]
_ul [[http://mvanier.livejournal.com/2897.html|http://mvanier.livejournal.com/2897.html]]
_ul [[https://levelup.gitconnected.com/implementing-recursion-with-the-y-combinator-in-any-language-9e83fa369ca|https://levelup.gitconnected.com/implementing-recursion-with-the-y-combinator-in-any-language-9e83fa369ca]]
{style 
#page_frame, #page_content { box-shadow:0 0 0 #fff; border:0 solid #fff; }
}