6 ms·

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 wi

• jng 12y ago
  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.
  • eru 12y ago
    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.
  • fexl 12y ago
    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])
    • anatoly 12y ago
      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?
      • fexl 12y ago
        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.
        • fexl 12y ago
          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.
      • fexl 12y ago
        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/57b841cb6c2347cad1473ccf34040a1a007b9e97 https://github.com/chkoreff/Fexl/commit/57b841cb6c2347cad147...
  • javajosh 12y ago
    What do you mean by "rewrite rules" - are you referring to beta reduction?
  • javajosh 12y ago
    What do you mean by "rewrite rules" - are you referring to beta reduction?
  • anatoly 12y ago
    >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?
    • jng 12y ago
      ">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.
      • vertex-four 12y ago
        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.
        • jng 12y ago
          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.
• lambdaknight 12y ago
  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.
• tel 12y ago
  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.
  • eruditely 12y ago
    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.
    • tel 12y ago
      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.
  • 12y ago
• sklogic 12y ago
  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/boot/boot.al https://github.com/combinatorylogic/mbase/blob/master/src/l/...
• chriswarbo 12y ago
  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.