7 ms·
The Y Combinator
- selimthegrim 5y agoVanier was my instructor for CS 1 at Caltech, a couple years before it abandoned SICP and Scheme. A more dedicated lecturer is impossible to find.
- tromp 5y agoCuriously, the graphical lambda calculus notation for the Y combinator slightly resembles a Y, especially when bent a little as shown at the top of https://tromp.github.io/cl/diagrams.html https://tromp.github.io/cl/diagrams.html
- eru 5y agoI always assumed that's where it got the same from?
- tromp 5y agoThe name Y combinator is many decades old, while this graphical notation is not even one decade old. But you do raise an interesting question: How did the fixed point combinator come to be known as the Y combinator?
- amelius 5y agoProbably just drawing letters from the alphabet. It's like the question: why do we use "x" to denote the unknown value in mathematics, most of the time?
- bidirectional 5y agoThe drawing random letters is true for the lambda in lambda-calculus, but not true for (at least some) combinators. e.g. the K combinator derives from Konstanzfunktion, and I from Identitätsfunktion[1]. So I do think it is an interesting question why Y, and we can't just assume it's arbitrary. [1] https://www.johndcook.com/blog/2014/02/06/schonfinkel-combinators/ https://www.johndcook.com/blog/2014/02/06/schonfinkel-combin...
- amelius 5y agoThen perhaps this reply comes closest to the truth: > Y because the letter Y has one stem which splits in two, just like what the function does. That’s probably the reason, or at least that’s how I look at it.
- amw-zero 5y agoWhy was lambda chosen as the abstraction character in the lambda calculus? Mathematicians just pick random letters and symbols for things.
- yesenadam 5y agoOn the origin of the lambda symbol: https://en.wikipedia.org/wiki/Lambda_calculus#Origin_of_the_lambda_symbol https://en.wikipedia.org/wiki/Lambda_calculus#Origin_of_the_...
- amelius 5y agoThey should draw these diagrams upside-down. Then they resemble a λ.
- kragen 5y agoThis is gorgeous!
- teddyh 5y agoIf you prefer video, here is an explanation of the Y combinator from Gerald Sussman himself: https://www.youtube.com/watch?v=0m6hoOelZH8#t=1h12m30s https://www.youtube.com/watch?v=0m6hoOelZH8#t=1h12m30s
- selimthegrim 5y agoThe kabbalah joke at 4:48 is priceless
- Joker_vD 5y agoI still think it's a device of rather dubious value, the most actual use of it I've seen is from being able to do it at the type-level (in one of Kiselyov's articles), because honestly, if you are allowed to name things at all, getting the function to refer to itself is pretty straightforward: factorial' self n = if n == 0 then 1 else n * self self (n - 1) factorial n = factorial' factorial' n That's it. Unless your evaluation strategy is literally implemented as term substitution/rewriting, it's about as efficient as having actual letrec primitive. This technique is straightforwardly extended to the case of mutual recursion: even' even odd n = if n == 0 then True else odd even odd (n - 1) odd' even odd n = if n == 0 then False else even even odd (n - 1) even n = even' even' odd' n odd n = odd' even' odd' n
- Koshkin 5y agoAs the article points out, the value of the Y combinator is largely theoretical/aesthetical, in both of which aspects your examples suffer greatly: they are ad hoc, lack abstraction/code reuse (which is why, perhaps, you needed more examples), and they look ugly (at least to my untrained eye). The point of the Y combinator is that it is a beautiful, mathematically precise, abstract, purely-functional way of expressing recursion.
- Joker_vD 5y ago"Ad hoc, lack abstraction/code reuse"? How does this fix f = f f almost_factorial f n = if n == 0 then 1 else n * f f (n - 1) factorial = fix almost_factorial lack code reuse compared to fix f = (\x. x x) (\x. f (\y. x x y)) almost_factorial f n = if n == 0 then 1 else n * f (n - 1) factorial = fix almost_factorial ? As for ugliness, well, it is indeed in the eye of the beholder: I personally think the fixpoint combinators that enable mutual recursion are pretty ugly, even more so than "(\x. x x) (\x. f (\y. x x y))". The only real problem is that in my approach the recursive calls look like "f closed_over_functions... new_args..." instead of "f new_args..." but that's what the compilers are for: this transformation is called "closure conversion" and is pretty straightforward. Sure, if you have to encode those things manually, then perhaps using Y is clearer and may even be the only option if you can't mess with the original definitions.
- ProfHewitt 5y agoY Combinator does not work for strongly-typed programs because the definition is not strongly typed. Instead recursion must be added as an additional primitive to the lambda calculus. See https://papers.ssrn.com/abstract=3418003 https://papers.ssrn.com/abstract=3418003
- Joker_vD 5y agoIt's perfectly well typed in System F as "forall a. (a -> a) -> a".
- ProfHewitt 5y agoCould you write this in Java?
- bidirectional 5y agoI think it is approximately `public <T> T y(Function <T, T> f)`.
- ProfHewitt 5y agoThanks! Could you use your Java code to define Factorial?
- Joker_vD 5y agoNot my code, but: https://gist.github.com/aruld/3965968 https://gist.github.com/aruld/3965968
- ProfHewitt 5y agoDoes the github Java code make use of recursion?
- Joker_vD 5y agoAs you can clearly see, it does not. It also doesn't use any forced typecasts to circumvent type checking.