{λ way}

user:anonymous

{blockquote {center Feel free to write a comment in [[forum]].}}{hr}_h1 Ycombinator {sup (for ze dummies)}

_p Following [[cannata/cs345|http://www.cs.utexas.edu/~cannata/cs345/Class%20Notes/27%20Lambda%20Calculus%20and%20the%20Y%20Combinator.html]] « 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.} The Ycombinator helps {i almost recursive functions} to be recursive. This is how it can be defined in lambdatalk:

{pre
'{def Y 
 {lambda {:f :n}
  {:f :f :n}}}
-> {def Y {lambda {:f :n} {:f :f :n}}}
}

_p Let's define {i almost recursive} functions, for instance {code almost-fac} and {code almost-fibo}:

{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 And test:

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

_p We could also compose the Ycombinator and the almost recursive functions:
{pre
'{def fac {lambda {:n} {Y almost-fac :n}}}
-> {def fac {lambda {:n} {Y almost-fac :n}}}
'{def fibo {lambda {:n} {Y almost-fibo :n}}}
-> {def fibo {lambda {:n} {Y almost-fibo :n}}}
'{fac 6} 
-> {fac 6}
'{fibo 8} 
-> {fibo 8}
}

_p We could also forget the Ycombinator and names:
{pre
1) fac:
'{{lambda {:f :n} {:f :f :n}} 
 {lambda {:f :n}
  {if {= :n 1} 
   then 1 
   else {* :n {:f :f {- :n 1}}}}} 6}  
-> {{lambda {:f :n} {:f :f :n}} 
 {lambda {:f :n}
  {if {= :n 1} 
   then 1 
   else {* :n {:f :f {- :n 1}}}}} 6}

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

}

_p Funny, isnt'it? And moreover it can be useful, {b tail recursion} loves the Y combinator. Usually a tail_recursive function adds an accumulator and must be called by another one initializing it. Thanks to the Y combinator, a tail-recursion can be written without any helper function:
{pre
 '{{lambda {:n}
  {{lambda {:f :n :r} {:f :f :n :r}} 
   {lambda {:f :n :r}
    {if {= :n 1}
     then :r
     else {:f :f {- :n 1} {* :n :r}}}} :n 1}} 6}
-> {{lambda {:n}
  {{lambda {:f :n :r} {:f :f :n :r}} 
   {lambda {:f :n :r}
    {if {= :n 1}
     then :r
     else {:f :f {- :n 1} {* :n :r}}}} :n 1}} 6}

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

_p We can easily add a test on the input's validity, the number must be positive:

{pre

'{def ifac {lambda {:n}
  {{lambda {:f :n :r} {:f :f :n :r}} 
   {lambda {:f :n :r}    
    {if {< :n 0} then the number must be positive! 
     else {if {= :n 0} then :r
     else {:f :f {- :n 1} {* :n :r}}}}} :n 1}}}
-> {def ifac {lambda {:n}
  {{lambda {:f :n :r} {:f :f :n :r}} 
   {lambda {:f :n :r}    
    {if {< :n 0} then the number must be positive! 
     else {if {= :n 0} then :r
     else {:f :f {- :n 1} {* :n :r}}}}} :n 1}}}

'{ifac -1} -> {ifac -1}
'{ifac 0} -> {ifac 0}
'{ifac 5} -> {ifac 5}

}

{pre

'{def ifibo {lambda {:n}
  {{lambda {:f :n :a :b} {:f :f :n :a :b}} 
   {lambda {:f :n :a :b}
    {if {< :n 0} then the number must be positive! 
     else {if {< :n 1} then :a
     else {:f :f {- :n 1} {+ :a :b} :a}}}} :n 1 0}}}
-> {def ifibo {lambda {:n}
  {{lambda {:f :n :a :b} {:f :f :n :a :b}} 
   {lambda {:f :n :a :b}
    {if {< :n 0} then the number must be positive! 
     else {if {< :n 1} then :a
     else {:f :f {- :n 1} {+ :a :b} :a}}}} :n 1 0}}}

'{ifibo -1} -> {ifibo -1}
'{ifibo 0} -> {ifibo 0}
'{ifibo 8} -> {ifibo 8}
'{map ifibo {serie 1 20}}
-> {map ifibo {serie 1 20}}
}

_p Using the syntactic sugar {b let}:
{pre
'{{lambda {:n}
  {let {{:n :n}
        {:fac {lambda {:f :n :r}
               {if {= :n 1}
                then :r
                else {:f :f {- :n 1} {* :n :r}}}} }}
   {{lambda {:f :n :r} {:f :f :n :r}} :fac :n 1}}} 6}
-> {{lambda {:n}
  {let {{:n :n}
        {:faa {lambda {:f :n :r}
               {if {= :n 1} then :r
                else {:f :f {- :n 1} {* :n :r}}}} }}
  {{lambda {:f :n :r} {:f :f :n :r}} :faa :n 1}}} 6}
}
_p where {code :fac} is a local variable which doesn't pollute the dictionary.

{hr}
_p See also [[lambda_calculus]], a language in which Ycombinators are used as a workaround to the lack of recursive functions.
_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]]