The key realization for me was that in lambda calculus, "A function can’t call itself by name, so we will have to find an alternative way."
The rest is smart acrobatics.
Understanding the Y Combinator
11–20 of 73 posts
Re: Understanding the Y Combinator
#12The key realization for me was that in lambda calculus, "A function can’t call itself by name, so we will have to find an alternative way." The rest is smart acrobatics.
A 'function' can't call itself (by name or by any other method), but since 'functions' can call each other, and can make each other to call each other, recursion is mostly trivial. You try it, then you'll get a working recursion one way or another. (Lambda calculus don't operate on functions, but on expressions/lambda terms.)
Re: Understanding the Y Combinator
#13My big brain expected startup stuff
I mean, posting about the other Y Combinator on... Y Combinator
Re: Understanding the Y Combinator
#14Note that with the standard representation of natural numbers in lambda calculus, the Church numerals [1], you don't even need the Y combinator to implement factorial: fac = λn.λf.n(λf.λn.n(f(λf.λx.n f(f x))))(λx.f)(λx.x) For example, applied to Church numeral 3 this gives (with F=(λf.λn.n(f(λf.λx.n f(f x))))): fac 3 = \f. F (F (F (\x.f))) 1 = \f. 1 (F (F (\x.f)) 2) = \f. 1 (2 (F (\x.f) 3)) = \f. 1 (2 (3 ((\x.f) 4)))…
Hey tromp, do you have any recommendations for grokking Lambda calculus properly? I've read a few tutorials and introductions, and I understand the notions of alpha- and beta-reductions, abstractions vs application, but I still have issues with practical examples like the above. Am I missing something here or should I just go back to the basics?
> I still have issues with practical examples like the above.
What issues would those be? Do you see that λf.λx.n f(f x)) is the Church numeral n+1 ? I think there's few better ways to grok lambda calculus than working through examples like these step-by-step.
Re: Understanding the Y Combinator
#15The key realization for me was that in lambda calculus, "A function can’t call itself by name, so we will have to find an alternative way." The rest is smart acrobatics.
let odd'(n, odd, even) = if n == 0 then False else even(n-1, odd, even)
let even'(n, odd, even) = if n == 0 then True else odd(n-1, odd, even)
let odd(n) = odd'(n, odd', even')
let even(n) = even'(n, odd', even')
Re: Understanding the Y Combinator
#16Well, I have to confess I was misled by the title! I was under the impression that the article was about YC, but it turned out to be about mathematics. Ironically, the below quote is still relevant to YC, I believe: > 8. Applications of the Y combinator > You might be wondering what makes the Y combinator so special.
The name Y Combinator is a metaphor: startup growth is "recursive" in a sense and Y Combinator builds such "recursive" companies out of a non-recursive input (the founders themselves)
Also Paul Graham is a Lisp nerd
(Note, I tried to find an authoritative source on how the name was chosen - the only thing I found was https://paulgraham.com/ycstart.html that lists when, but not how the name came to be; but I think this metaphor is somewhat obvious)
Re: Understanding the Y Combinator
#17Cool article, BUT! it leaves so many terms unexplained:
- What's the distinction between a "parameter`, a "variable", and an "argument"?
- What is "body" as in "Body M"?
- What's a "bound" variable?
- What exactly is a "function call"?
- In "... a value that is mapped to itself by the function.", what do "mapped to itself", and, more specifically, "mapped" mean?
Would appreciate the answers!
Re: Understanding the Y Combinator
#18I'd really like to understand why my brain screams NO when I try to grok lisp and especially the Y combinator. It's like it's anti-interesting to me or something. I know it's cool, and useful to know, but I just can't get there. Maybe it's a stack overflow in my head? Is it just me? [Edit] Re:082349872349872 - I grew up in a world of assembler programming, BASIC and Pascal. It wasn't unusual to have all sorts of self…
No, you're probably not alone. I myself enjoy functional programming quite a lot but Y combinator always stood out to me as a particularly uninteresting trick. Sure, it's nice to have it around when you try to prove some theoretical stuff but for practical work letrec is just better.
I mostly feel the same about the Church encoding of e.g. lists: yeah, it's a nice theoretical trick that you can equate a list xs with a function that gives your its fold but... that's just so inconvenient to actually use! Why not equate it with either a nil or a tuple of head and tail instead?
def empty_list(onEmpty, onNonEmpty):
return onEmpty()
def make_a_non_empty_list(head, tail):
def non_empty_list(onEmpty, onNonEmpty):
return onNonEmpty(head, tail)
return non_empty_listRe: Understanding the Y Combinator
#19The key realization for me was that in lambda calculus, "A function can’t call itself by name, so we will have to find an alternative way." The rest is smart acrobatics.
let odd'(n, odd, even) = if n == 0 then False else even(n-1, odd, even) let even'(n, odd, even) = if n == 0 then True else odd(n-1, odd, even) let odd(n) = odd'(n, odd', even') let even(n) = even'(n, odd', even') Look ma, no hands! Well, actually, it is explicit closure-conversion done by hand so... anyhow, there are more straightforward and performant ways to get recursion in practice.
In lambda calculus, you could use a variadic fixed point combinator to solve such recurrence relations elegantly
Re: Understanding the Y Combinator
#20I thought this post was about dissing Paul G, Garry Tan and the like. I was wrong.