Hacker News Reader

Comment by khaledh | Hacker News Reader

I admire how someone passionate about a subject can provide in-depth explanation of _how_ that thing works. But to me, I still have absolutely no idea _why_ or _when_ I would need to apply this (even after reading the original post[0]). A motivating practical example would go a long way as an introduction before getting into the nitty-gritty details.

[0] https://eli.thegreenplace.net/2016/some-notes-on-the-y-combi...

View on HN

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.

Fixed-point combinator > Y Combinator, Implementations in other languages: https://en.wikipedia.org/wiki/Fixed-point_combinator

Y-combinator in like 100 languages: https://rosettacode.org/wiki/Y_combinator #Python

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.

The thing is that you don't want to use directly the Y-combinator, ever.

It is a tool to show that untyped lambda calculus with just anonymous functions and applications is already Turing-complete, because you can write the `Y-combinator`, thus you can define recursive functions, and thus you can write `while` loops.

In a way, the Y-combinator is one of the possible ways to reach Turing-completeness by accident. It is an important example to keep in mind if you want to design a type system for a programming language that is not Turing-complete.

But as soon as you want Turing-completeness, the Y-combinator is not a nice primitive for most users. In this case, either your language is flexible enough to write a good library for recursive definitions based on the Y-combinator. Otherwise, it often works better to introduce recursive definitions as a primitive, even if theoretically this primitive is not absolutely needed.

You're right, these posts assume one knows what the Y combinator is for. Wikipedia has a decent explanation: https://en.wikipedia.org/wiki/Fixed-point_combinator

Key point:

    the Y combinator implements simple recursion. In the lambda calculus it is not possible to refer to the definition of a function in a function body. Recursion may only be achieved by passing in a function as a parameter. The Y combinator demonstrates this style of programming.

You don't really need it in modern programming languages that natively support named functions and recursion, but it's an interesting part of the underlying theory of lambda calculus.

i've read this article multiple times, and i have to say it is absolute garbage. This general layman description ( which i never noticed before) should really be at the beginning and not buried deep after pages of lambda calculus expressions..

If only there was something you could do about that…

I really don't feel legitimate to update a wikipedia article about Y-combinator, sorry. The bar is too high :)

The Y combinator lets you implement recursion without using recursion. For example, a Javascript closure can't refer to itself. But if we define the (strict) Y combinator using JS closures:

    let Y = f => (x => x(x))(x => f(z => x(x)(z)))

then we can call it, again only using closures, and define a function that sums the numbers from 1 to N by "calling itself":

    let sumToN = Y(sumToN => n => n == 0 ? 0 : n + sumToN(n-1))

    sumToN(4)
    // -> 10

In practice, no one actually implements recursion this way because it would be slow. So instead it's more of a statement about the expressiveness of languages, and how "we have recursion!" doesn't actually give you any power you didn't have before, if you had functions.

It's a plaything, it's not meant to be applied in the real world. It's like asking for a "motivating practical example" for a quine.

Knowledge of the Y-combinator helps avoid making your language divergent (sometimes desirable), disallowing explicit recursion is not enough! The typed lambda calculus uses static types to prevent the Y-combinator and give a sound logic for proofs.

Static types doesn't seem sufficient? Typed languages have no problem expressing passing functions as parameters. Where does it break when you apply static types?

I think it's because the y-combinator needs to be passed to itself as an argument, and it's hard to come up with a static type for a function where one of the parameters is the type itself.

The Y-combinator require (equi)recursive types for the intermediary step `x x` where `x` has type `('a -> 'b as 'a) -> 'b` using OCaml notation.

The same question could be posed for many other mathematical and theoretical computer science constructs. It's a mathematical building block, a node in the graph that is the world of mathematics, and it's possible it plays a part in some advance if you were working in that field.

Look at eg the Curry's Paradox part on the WP page for a taste.

Reply on news.ycombinator.com