The problem is marrying two ideas: lambda calculus (where all computation is done implicitly via anonymous functions), and recursion (where some set of functions call each other by name in a cycle).
This is a bit more interesting than it looks because ostensibly you're using the name of a function in its definition before that name ever has a meaning -- you're not really saying that you should literally call that symbol, but that the compiler should produce a function according to some set of rules that fills in the self references.
That doesn't work in lambda calculus though, where definitions are concrete and you don't have compiler magic to resolve the undefined symbol in your definition. A solution is to pass some function to itself as an argument, and you have a code pattern that goes along with it (the Y combinator).
This retains some "usefulness" in the sense that lambda calculus is still being explored for various purposes as a foundation for other things, and also in that languages based on that line of thought might benefit from using that structure explicitly. If you have some sort of syntactic sugar for recursion in your language of choice though and don't care about foundations then it's probably not very applicable.
Thanks, that helps a bit. So I get the what: a way to make an anonymous function recursive. As for the why, it seems to me it's because "lambda calculus doesn't have named functions." So this tells me this is a programming language design concern, as opposed to a pattern that can be used in everyday programming. Based on this, providing examples of how to implement a Y combinator in Clojure, Python, and Go is of questionable value IMO. And that's OK, since a lot of things we do don't need to have practical value (e.g. learning, understanding, etc).
It has practical value, let say you have something that caches the result of a lambda
record Cache<T, U>(Function<T, U> function) {
U get(T value) { ... }
}
you can use it that way
var cache = new Cache<Integer, Integer>(v -> v + 1);
var result = cache.get(3);
with that settings, how do you specify a lambda which is recursive ? and how can you cache the intermediary steps if you can change the signature of get() ?
In languages with closures it would be easy to set a variable to the lambda while that same variable is also captured by the lambda. In fact, this seems to happen once in a while in Go, since closures are always lambdas.
Even if it doesn't have value for everyday programming, translating it into Clojure/Python/Go/whatever can make it easier to understand. Most explanations I've seen of the Y combinator just work in lambda calculus, which I at least find somewhat difficult to read; translating it into a more familiar language can make it easier to understand.
i've read about y-combinator a few times, but i must say your fours paragraphs are the most enlightening i've ever read. You should add them to the wikipedia introduction's in the ycombinator page.
This is a bit more interesting than it looks because ostensibly you're using the name of a function in its definition before that name ever has a meaning -- you're not really saying that you should literally call that symbol, but that the compiler should produce a function according to some set of rules that fills in the self references.
That doesn't work in lambda calculus though, where definitions are concrete and you don't have compiler magic to resolve the undefined symbol in your definition. A solution is to pass some function to itself as an argument, and you have a code pattern that goes along with it (the Y combinator).
This retains some "usefulness" in the sense that lambda calculus is still being explored for various purposes as a foundation for other things, and also in that languages based on that line of thought might benefit from using that structure explicitly. If you have some sort of syntactic sugar for recursion in your language of choice though and don't care about foundations then it's probably not very applicable.