What the heck is a Ycombinator

I woke up at 4am this morning for no reason and decided to go through Ycombinator in Ruby. Given that I read Hacker News daily, it's a shame I didn't know what a Ycombinator was. I thought the article was pretty clear, at least compared to Raganwald's article. As an aside, from purely a learning experience, it was kinda fun and eye opening. At least I can see why geeks think it's neat.

I had written a reply to a comment on hacker news about it, and it turned out to be really long, so I just extracted it out here. I was suppose to start some coding, but I got wrapped up in writing up the comment. My comment ended up to be pretty long, but it was shorter than it could have been. You guys get to suffer through the long version. Haha. But I'm not going to go into details. You can read that in the linked articles. Instead, I'll paint some broad strokes.

  Y = λf·(λx·f (x x)) (λx·f (x x))

or in Ruby, copied from the aforementioned article:

y = proc { |generator|
    proc { |x|
        proc { |*args|
            generator.call(x.call(x)).call(*args)
        }
    }.call(proc { |x|
        proc { |*args|
            generator.call(x.call(x)).call(*args)
        }
    })
}

or if you prefer elegance, Tom's solution in response to Raganwald

def y(&f)
    lambda { |x| x[x] } [ 
        lambda { |yf| lambda { |*args| f[yf[yf]][*args] } } ]
end

I found lambda calculus above hard to read. However, if you go through the code in Y Combinator in Ruby, you'll find it's not too bad. I find that this lecture is also pretty good, as it takes you step by step, with a little bit of humor as well.

If I had to take a stab at it, A Ycombo is a way to implement recursion mechanism when the language doesn't provide named recursion, loops, or iterators, and all you get are first-class functions and a few substitution rules.

Functions are just mappings from one set of things to another set of things--ie. give it a number, and it'll point to another number. Ycombo relies on a property of functions that sometimes, when you put something into a function, you get the exact same thing out, i.e. something gets mapped to itself, like f(x) = x^2, where f(1) = 1 is an example of this property. They call this the fixed point of a function.

The thing about functions is that they don't just have to map numbers to numbers. They can map functions to other functions. A derivative is an example of a function that takes one function as an input, and spits another function back out. like d(x^2) = 2x. Where is the fixed-point of a derivative? One of them is when you put e^x into it. d(e^x) = e^x. I'm sure there are more.

This is important because if you can find the point in which a function can return a function unchanged, you can use that to call the function again, which is what we call recursion. And all the trickiness you see in ycombinator that you see is mainly a result of functional programming not keeping state, so you have to pass everything you need into a function. So if you have to do recursion, you have to have a mechanism pass the function itself, so you can call it again. And this mechanism kinda bends back onto itself, and that's why you see a part of the ycombinator repeated twice in the code above, and in the lambda calculus.

It seems pretty inane to use ycombo given that modern high level languages provide named recursions, and if anything, for loops and iterators with closures. But what if you don't? How do you process lists/arrays without loops or named recursion? Generally, you'd have to make your own recursion mechanism.

When would you ever have languages that don't have those things? Probably not often. But Forth comes to mind. I've never used Forth, but from what little I know about it, the language starts off with some basic primitives and that's it. No loops, no if statements. How do you get anything done? Well, you build your own control structures. People use Forth because it's possible to build your own very small compiler from the ground up written in Forth itself, and still understand the entire thing. I suspect it's used in embedded programming because of that reason.

So you'd pretty much use it when you want to have a powerful system from first principles. I'm guessing it's possible to build your own computer by implementing only functions and substitution rules in hardware, and then you can derive everything else, numbers, pairings, and even recursions in software. That way, you keep your hardware costs down, while retaining the power of a Turing machine.

Speculating here...but another thing that might be interesting is that ycombinator might be a way to compress code. Software size should be reducible if the code is compressible. And recursion can be thought of as a compressing code, and expanding it when the recursion is run. I wonder if there's other ways to reduce software bloat with the use of a ycombinator besides recursion?