Y combinator (the function) in Ruby

http://www.eecs.harvard.edu/~cduan/technical/ruby/ycombinator.shtml

by cduan • 19 years ago

10 3 19 years ago

eecs.harvard.edu

altano• 19 years ago

How ridiculous. He presents a very simple, easy to read recursive function as the solution, but claims "This is risky: what if someone redefines or deletes the method? Can it be done without defining any methods, to prevent this problem?"

He then provides a much larger, incredibly harder to understand YCombinator method and mixes it into the Object class. How is that not a method with the same downsides as the recursive one?

This is why I still have no idea what the ycombinator is... every explanation is as inane as this one. Does anyone have a simple explanation of it, where either (a) the ycombinator solves a problem more simply or (b) the ycombinator is the only tool to solve a problem ?

iamwil• 19 years ago

I woke up at 4am this morning for no reason and decided to go through it. I thought it was pretty clear. 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.

Anyway, the namespace clash is reduced with a ycombinator because you'd only have to declare it once. Here, it seems like there's not much of a gain because we only used it on hash. But if you wanted to use the same trick on array, or other containers, you'd essentially be not only duplicating code, but also taking up namespace with a make_array, or make_othercontainer. In addition, any time you wanted recursion, you'd be able to use it.

If I had to take a stab at it, 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.

As for (a), It seems pretty inane to use ycombo given that modern high level languages provide named recursions, loops, and iterators. But what if you don't get those things? 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.

By that notion, I'm guessing you can physically build a lisp interpreter machine based on very few principles, like functions and substitution. Everything else can be derived in software, even things we think as basic, such as numbers and counting. Because of that, we can just build the basic axioms in hardware, and everything else can be built in software on top. That lowers the cost of your hardware if you can build it in fewer parts. ycombinator, in this case, would be a way to build recursion on a piece of hardware that only supports functions and substitution rules. With recursion, you can process lists of things, which means you can get stacks, and data structures, and rest of the wonderful world you're use to.

In any case, I figured PG and co. called it ycombinator because they hope that people they fund will in turn pay it forward and start other early stage funding companies. They're the first of many recursive calls to make_startup().

d0mine• 18 years ago

Just out of curiosity I've made a bug-to-bug translation of original Ruby version of the Y Combinator function from the submitted link to Python language.

In Ruby http://is.gd/gdJ :

  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)
        }
    })
  }

In Python:

  # Y = λf·(λx·f (x x)) (λx·f (x x))
  y = lambda generator:\
    (lambda x: lambda *args: generator(x(x))(*args))\
    (lambda x: lambda *args: generator(x(x))(*args))

Example with factorial:

  factorial_generator = lambda callback: lambda n: n*callback(n-1) if n > 1 else 1
  factorial = y(factorial_generator)
  n = 5
  print "%d! = %d" % (n, factorial(5))

Y combinator (the function) in Ruby

Related Stories