News for hackers. Stuff that matters.
Re:The Y Combinator (no, not that one) – A Crash Course on L... by anatoly on Wednesday September 10, 2014 @05:37PM (#8299332)
Has 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.

Re:The Y Combinator (no, not that one) – A Crash Course on L... by jng on Wednesday September 10, 2014 @05:53PM (#8299402)
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 L... by fexl on Wednesday September 10, 2014 @06:14PM (#8299531)
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])
Where '@' is the Y-combinator.

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 L... by anatoly on Thursday September 11, 2014 @02:41AM (#8301186)
Why? Is it unreasonably difficult for you to implement recursion via direct self-reference in your language? Or do you just not want to because the Y combinator is there and it's cool?
Re:The Y Combinator (no, not that one) – A Crash Course on L... by fexl on Sunday September 21, 2014 @12:34PM (#8347518)
OK, I went ahead and revived the "==" syntax for recursive definitions, so you don't have to use '@' (fixpoint) explicitly.

https://github.com/chkoreff/Fexl/commit/57b841cb6c2347cad147...

Re:The Y Combinator (no, not that one) – A Crash Course on L... by fexl on Thursday September 11, 2014 @10:42AM (#8302836)
True, I could implement it in terms of direct self-reference. At one point I used the "==" syntax for just that purpose:

    \append==(\x\y x y \h\t [h; append t y])
Maybe I should resurrect that syntax option. :)

It was trivial to implement. When the parser sees the "==", it just automatically abstracts the symbol "append" from the definition and applies the fixpoint operator (Y combinator).

The only reason I eliminated "==" in the first place was that I was in the throes of using different syntaxes for lazy, eager, and self-referencing definitions. Now I've settled in on "=" always meaning eager evaluation, without exception. Then I got hyper-minimalist and said that's it, there's only one syntax for definitions, and it's "=", and if you want self-reference, use "@".

However, the decision to settle in on eager evaluation now frees up "==" once again as an option for self-reference. So I may bring that back.

Thanks for the food for thought.

Re:The Y Combinator (no, not that one) – A Crash Course on L... by fexl on Thursday September 11, 2014 @10:50AM (#8302891)
Postscript: You might well ask why not just use "=" only, and assume that all definitions are potentially self-referencing?

That's a non-starter because I find that redefinition is the more common intent:

    \x=4
    \x=(* x 5)
    \x=(+ y x)
In those cases I don't want x defined in terms of itself, but rather in terms of the previous definition of x.

That is why I would insist on a special token such as "==" to express the intention of self-reference.

Re:The Y Combinator (no, not that one) – A Crash Course on L... by anatoly on Thursday September 11, 2014 @02:40AM (#8301183)
>derives automatically and inevitably from just basic rewrite rules.

Sorry, I don't understand what that means.

Also, (lambda x: x(x))(lambda x: x(x)) already gives you an infinite loop, so why do you need a Y combinator to show non-termination? Once you have functions as first-class citizens that you can copy around, you've lost control of termination. Seems pretty intuitive. What's the specific contribution of the Y combinator?

Re:The Y Combinator (no, not that one) – A Crash Course on L... by jng on Thursday September 11, 2014 @05:20AM (#8301602)
">derives automatically and inevitably from just basic rewrite rules."

I said "full general computation, including recursion and iteration, derives automatically and inevitably from just basic rewrite rules". You can't cut a sentence wherever you want and still think you're responding to the original thought.

There is an imprecision in my original comment, but it's not there. If you can stop nitpicking long enough, you may be able to see something that's pretty powerful.

Re:The Y Combinator (no, not that one) – A Crash Course on L... by vertex-four on Thursday September 11, 2014 @07:17AM (#8301884)
Thanks for the assertion that everybody can understand you when you use terms without defining them. Not everybody here is so lucky as to have the same educational background as you.

What is a rewrite rule? To me, it's something you put in a web server configuration.

Re:The Y Combinator (no, not that one) – A Crash Course on L... by jng on Thursday September 11, 2014 @01:21PM (#8303810)
My apologies, I was only responding to the previous comment, forgot momentarily about others, sorry about that. Let me try to fix this.

A computation engine based on rewrite rules, in general, performs computations by replacing instances of certain patterns by some other patterns. Patterns can be literal or generic. The rules according to which these rewrites are done are "code" of the computation, they determine what computation the system performs. Different rules can result in a system that may do one of: computing prime numbers, computing digits of pi, factoring large number in prime divisors, finding the shortest path visiting all cities exactly once in a given map, rendering a 3D scene from a list of objects and coordinates, finding the best potential dating matches for a given user out of list containing many other users, or outputting a Schonberg-style tonal composition in waveform with synthetic piano-like sound.

The lambda calculus is one such type of computation system. The core element is a lambda expression of the form (\x.y), where "\" is just ASCII for the greek lambda letter which is hard to type for me now. The core thing a lambda-calculus system does is it takes lambda expressions and it applies a simple rewrite rule: where there is a sequence of the form (\x.y)z, where x,y,z can be anything, it will substitute the whole thing by "y", but wherever "x" appears inside "y", it will write "z". For example:

  (\x.xx)A
Will be rewritten to:

  AA
Given an initial string, the engine that computes the lambda expression will apply this rewrite rule repeatedly until no more rewrites can be done. This may or may not reach an end (this is the halting problem - in a general case, it is impossible to know whether the computation will reach an ending point or not).

The rewrite rule is called "beta reduction", by the way, but try to remember the concept, not the name, which is arbitrary and unimportant.

Using lambda notation you can craft code that will do any of the things above. The code will look like a long lambda expression, which the lambda-calculus engine can work on following the standard rules to end up producing the end result.

The Y combinator is a specific (\x.y) lambda expression that, once applied to some value by the rewriting system, it results in a computation being done on that value, plus an extra copy of the Y combinator, thus allowing a new iteration of the same computation. Thus resulting in being able to keep on computing - thus being able to compute anything requiring arbitrary recursion, such as the factorial of a number, the Ackerman function, the shortest path in an arbitrary graph, or whatever.

Although I've never seen Paul Graham explain it, my take is that the accelerator is called Y Combinator because they put some money in, this allows the startups to get to profitability, they get their money back, and they can use it again to fund new startups, thus achieving infinite effective resources from finite initial resources.

PS: the author of the original comment was handwaving and nitpicking since he didn't like being in the point of having missed something (which we all do quite often, incidentally, including myself in the previous comment). I don't like that behavior and I don't like the time and energy waste it results in, thus my dismissive response, apologies everyone for not responding constructively.

Re:The Y Combinator (no, not that one) – A Crash Course on L... by eru on Wednesday September 10, 2014 @05:57PM (#8299419)
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 L... by javajosh on Wednesday September 10, 2014 @08:21PM (#8300102)
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 L... by lambdaknight on Wednesday September 10, 2014 @06:22PM (#8299572)
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 L... by tel on Wednesday September 10, 2014 @09:37PM (#8300408)
Well, in 1936 Church invented the LC in order to serve as a foundational logic for mathematics. This was around the time that Hilbert's Program was attempting to totally mechanize reasoning through rich logical languages and Church wanted to use LC to define the notion of "efficiently computable" which was part of Hilbert's specification.

The Y-combinator was discovered originally as a flaw in the LC. It meant that you couldn't use LC as a logical language because you could form infinite loops which are not just not efficiently computable (in a sense, har har) but also correspond to vacuous logical statements like "If A proves A then A is true" which, in the context of rules like reflexivity "If A then A" (provable in LC as λ x . x) is logical nonsense.

To be more clear, here's the Y combinator

    λ f . (λ x . f (x x)) (λ x . f (x x))
and here's the Y-combinator applied to `id = λ x . x`

    (λ x . (x x)) (λ x . (x x))
which reduces into itself—a dead loop and a logical inconsistency (named "omega" as the end of LC!)

Anyway, Church worked for the next 4 years to invent the Simply Typed Lambda Calculus which imposes a Russell-like typing discipline on the LC in order to outlaw the Y-combinator. This made LC more useful for logic (and indeed STLC models Gentzen's Natural Deduction logical system) but it threw away its ability to compute any "recursively enumerable" function. That latter thing was what eventually came to be the definition of "efficiently computable" (after corroboration between Church's LC, Turing's Turing Machines invented the next year).

And now we happen to care about writing programs which, in general, may be r.e. and so we use either untyped LC or typed LC which has logically unsound recursion principles.

Re:The Y Combinator (no, not that one) – A Crash Course on L... by anatoly on Thursday September 11, 2014 @02:47AM (#8301198)
> (λ x . (x x)) (λ x . (x x))

This shows an infinite loop in lambda calculus evaluation. It can be arrived at independently (and I'd be surprised if it hadn't been) just by trying to build the simplest expression that doesn't reduce. Why do you need the Y combinator for this?

Re:The Y Combinator (no, not that one) – A Crash Course on L... by tel on Thursday September 11, 2014 @08:17AM (#8302112)
It had been. Everyone was just talking about the Y-combinator so I derived from there, but Omega was first.

Once you have any fixed-point, though, deriving the others is trivial. The explosive self-referential nature of your system has been uncovered.

Re:The Y Combinator (no, not that one) – A Crash Course on L... by eruditely on Thursday September 11, 2014 @12:00AM (#8300809)
Can you recommend me to any further reading regarding this or good literature? I've always meant to keep up with that, but aside from source papers is there a good overview of essentially what you're explaining? ie Further reading about Hilbert's Program.
Re:The Y Combinator (no, not that one) – A Crash Course on L... by tel on Thursday September 11, 2014 @09:39AM (#8302455)
The Stanford Emcyclopedia of Philsophy is usually a good source. If you're in Boston I'm going to be giving a Papers We Love talk on this stuff next week.
Re:The Y Combinator (no, not that one) – A Crash Course on L... by sklogic on Thursday September 11, 2014 @04:14AM (#8301430)
Yes, it is useful. For example, if you want to bootstrap a language implementation from the smallest possible subset, with a very trivial interpreter, then using Y-combinator as a way to implement recursion is reasonable (after all, performance does not matter for the bootstrap phase). See an example of such a use in https://github.com/combinatorylogic/mbase/blob/master/src/l/...
Re:The Y Combinator (no, not that one) – A Crash Course on L... by chriswarbo on Thursday September 11, 2014 @07:33AM (#8301943)
Named recursion requires a notion of time, which is clear from your distinction between "permanent" and "temporary" names. This can add unnecessary complexity.

Let's use an analogy: is it ever useful to call a function with another function's return value?

    p = \q. f (g q)
We can implement the same thing using named arguments with permanent or temporary names, for example:

    p = \q. let g_of_q = g q
             in f g_of_q
That forces us to write the same boilerplate every time. We can do better by encapsulating it in a function (DRY):

    compose = \a. \b. \c. let b_of_c = b c
                           in a b_of_c
    p = compose f g
The Y/Z combinators do exactly the same job as compose, except for self-application rather than chained application. They let us write down what we mean, directly, without having to break it up into artificial chunks and chain them back together. Notice that the final definition of "p" doesn't even need a lambda abstraction, since the function is being calculated automatically rather than defined manually.

For example, I've used the Z combinator when defining arrays of functions in PHP. Without it, I'd have to define the functions separately, using brand-new function abstractions to inherit the self-reference (which is horribly verbose in PHP), then combine them into an array; or I'd have to define them separately, using brand-new function abstractions to inherit the array, then combine them into the array. Either way, it would add a bunch of complexity and boilerplate.