From The Little Schemer - http://www.ccs.neu.edu/home/matthias/BTLS/sample.pdf
That chapter made me grok the Y Combinator.
The Y Combinator (no, not that one) – A Crash Course on Lambda Calculus
11–20 of 51 posts
Re: The Y Combinator (no, not that one) – A Crash Course on Lambda Calculus
#12Has the Y combinator been useful to anything? Has it been used in any software in a role other than pedagogic? It's a beautiful way to make a recursive call without binding the function to an identifier, but has it actually proven useful? It would seem that languages that allow that make it easy to use the Y combinator also typically make it easy to use named recursion with a permanent or a temporary name.
Hey. You're completely missing it. The Y combinator shows that full general computation, including recursion and iteration, derives automatically and inevitably from just basic rewrite rules. Obviously it is too raw to be used directly. But if you design/implement any system with rewrite rules, you have provided indefinite power for recursions, and you have opened the Pandora box of undecidable-termination. This means that decidable computation can only occur without rewriting, which is incredibly restricted.
Food for thought.
Re: The Y Combinator (no, not that one) – A Crash Course on Lambda Calculus
#13Has the Y combinator been useful to anything? Has it been used in any software in a role other than pedagogic? It's a beautiful way to make a recursive call without binding the function to an identifier, but has it actually proven useful? It would seem that languages that allow that make it easy to use the Y combinator also typically make it easy to use named recursion with a permanent or a temporary name.
Hey. You're completely missing it. The Y combinator shows that full general computation, including recursion and iteration, derives automatically and inevitably from just basic rewrite rules. Obviously it is too raw to be used directly. But if you design/implement any system with rewrite rules, you have provided indefinite power for recursions, and you have opened the Pandora box of undecidable-termination. This mean…
Exactly! Look at eg primitive recursion for an interesting subset of computation that does not suffer from undecidability.
Most programmers are familiar with regular expressions, too. There are another interesting subset.
Re: The Y Combinator (no, not that one) – A Crash Course on Lambda Calculus
#14Has the Y combinator been useful to anything? Has it been used in any software in a role other than pedagogic? It's a beautiful way to make a recursive call without binding the function to an identifier, but has it actually proven useful? It would seem that languages that allow that make it easy to use the Y combinator also typically make it easy to use named recursion with a permanent or a temporary name.
Hey. You're completely missing it. The Y combinator shows that full general computation, including recursion and iteration, derives automatically and inevitably from just basic rewrite rules. Obviously it is too raw to be used directly. But if you design/implement any system with rewrite rules, you have provided indefinite power for recursions, and you have opened the Pandora box of undecidable-termination. This mean…
I do use it directly. For example in Fexl I define the append function for lists as:
\append=(@\append\x\y x y \h\t [h; append t y])
Note that there's no direct self-reference with the symbol "append" there. I could define it equivalently as:
\append=(@\loop\x\y x y \h\t [h; loop t y])Re: The Y Combinator (no, not that one) – A Crash Course on Lambda Calculus
#15Has the Y combinator been useful to anything? Has it been used in any software in a role other than pedagogic? It's a beautiful way to make a recursive call without binding the function to an identifier, but has it actually proven useful? It would seem that languages that allow that make it easy to use the Y combinator also typically make it easy to use named recursion with a permanent or a temporary name.
It has some minor uses, but not a whole lot. If, for example, you wanted to do recursion with an anonymous function, you could use the Y combinator (well, more likely the Z combinator which is a variant of the Y combinator that works with strict evaluation). However, it'd probably just be easier (and clearer!) to give the function a name and do it that way.
However, as someone pointed out, the Y combinator's utility is not as an actual tool for programmers but as a tool for mathematicians working in computational mathematics. Alonzo Church solved the Entscheidungsproblem using a primitive variant of the Y combinator called the omega combinator. The Y combinator itself was invented by Haskell Curry (his name is familiar for a reason) in order to demonstrate what is commonly called Curry's paradox.
Re: The Y Combinator (no, not that one) – A Crash Course on Lambda Calculus
#16tl;dr
A fixed point p for a function f, is a value so that f(p)=p.
A semi-recursive function f is a like a recursive function, except that instead of invoking itself, it invokes some other function provided as an argument to f.
The y-combinator (aka fixed-point-combinator) is a function, that for a function f, finds a fixed point for f.
We can turn a semi-recursive function f into the corresponding recursive function g, by finding a fix point for f, which we can do using the y-combinator.
Re: The Y Combinator (no, not that one) – A Crash Course on Lambda Calculus
#17One of my favorite programming videos: Jim Weirich on the Y Combinator https://www.youtube.com/watch?v=FITJMJjASUs
Thanks for this. I just learned a lot!
Re: The Y Combinator (no, not that one) – A Crash Course on Lambda Calculus
#18Has the Y combinator been useful to anything? Has it been used in any software in a role other than pedagogic? It's a beautiful way to make a recursive call without binding the function to an identifier, but has it actually proven useful? It would seem that languages that allow that make it easy to use the Y combinator also typically make it easy to use named recursion with a permanent or a temporary name.
Hey. You're completely missing it. The Y combinator shows that full general computation, including recursion and iteration, derives automatically and inevitably from just basic rewrite rules. Obviously it is too raw to be used directly. But if you design/implement any system with rewrite rules, you have provided indefinite power for recursions, and you have opened the Pandora box of undecidable-termination. This mean…
What do you mean by "rewrite rules" - are you referring to beta reduction?
Re: The Y Combinator (no, not that one) – A Crash Course on Lambda Calculus
#19Has the Y combinator been useful to anything? Has it been used in any software in a role other than pedagogic? It's a beautiful way to make a recursive call without binding the function to an identifier, but has it actually proven useful? It would seem that languages that allow that make it easy to use the Y combinator also typically make it easy to use named recursion with a permanent or a temporary name.
Hey. You're completely missing it. The Y combinator shows that full general computation, including recursion and iteration, derives automatically and inevitably from just basic rewrite rules. Obviously it is too raw to be used directly. But if you design/implement any system with rewrite rules, you have provided indefinite power for recursions, and you have opened the Pandora box of undecidable-termination. This mean…
What do you mean by "rewrite rules" - are you referring to beta reduction?
Re: The Y Combinator (no, not that one) – A Crash Course on Lambda Calculus
#20If there's one thing that the prolific rise of the Y Combinator accelerator has done, it's made the combinator much harder to google for. (Though ofc Fixed-point combinator would still work).
I actually complained about this on twitter a while ago, and pg said he didn't believe me - recommending "y combinator lambda" as a search string. But more specific things like "y combinator golang" require you to block HN and a few other sites to get meaningful results.