Understanding the Y Combinator using Java

I've been interested in clojure lately, and therefore functional programming. This lead me to reading about the Y Combinator, which is essentially the theory explaining how recursion can be implemented without naming, and therefore without being able to make the recursive call to the function name itself. It's also a fun puzzle, and I suspect that's why it is so popular among functional programming geeks.

Here is the Y Combinator in clojure:

(defn Y [r]
  ((fn [f] (f f))
   (fn [f]
     (r (fn [x] ((f f) x))))))

This article does a pretty good job explaining how to apply it, but didn't really explain how the Y Combinator works. What I wanted was the Y Combinator in a familiar form where I could step through the code and see what was going on. Since java is the environment that is easiest for me to step through code, I looked around until I came across this article that does a good job explaining the Y Combinator, and provides source code in both lisp and java.

When you perform a direct translation of functional code into java, you get a mess of anonymous inner classes that isn't particularly easy to reason about. So after pasting into into my IDE, I tried to remove all unnecessary anonymous inner classes while still preserving the essence of what the Y Combinator solves: how to implement recursion without making a direct recursive call. I ended up with a lot more code of course, but java's verbosity shines when trying to understand this dense concept.

/**
 * Demonstrates the principles of the Y-Combinator in java.
 */
public class YComboDemo {

    /**
     * Let's start with a simple function implemented 
     * recursively: factorial
     */
    static int factorial(int n) {
        return n == 0 ? 1 : n * factorial(n - 1);
    }

    /**
     * conceptually, factorial implements an interface 
     * that takes an integer and returns an integer
     */
    interface IntFunc {int apply(int n);}

    /**
     * Here it is again in terms of a class implementing 
     * this interface:
     */
    static class SimpleFactorial implements IntFunc {

        public int apply(int n) {
            return n == 0 ? 1 : n * apply(n - 1);
        }
    }

    /**
     * Suppose java didn't support recursive calls.  
     * How can we accomplish the same thing? Let's 
     * start by abstracting away the recursive call by
     * delegating to some other function.
     *
     * This won't work unless we find a way to get 
     * that function to call back into us...
     */
    static class DelegatingFactorial implements IntFunc {
        private final IntFunc f;
        public DelegatingFactorial(IntFunc f) {
            this.f = f;
        }

        public int apply(int n) {
            // we can't call apply directly, so delegate
            return n == 0 ? 1 : n * f.apply(n - 1);
        }
    }

    /**
     * Let's start by defining something that can generate
     * a function in terms of some other.
     */
    interface IntFuncToIntFunc {IntFunc apply(IntFunc f);}

    /**
     * And then implement it for factorial.  This will generate
     * a function that delegates to the passed in argument.
     *
     * But we still need to pass in the right argument to make
     * the "recursion" work...
     */
    static class FactGen implements IntFuncToIntFunc {
        public IntFunc apply(IntFunc f) {
            return new DelegatingFactorial(f);
        }
    }

    /**
     * That's where the Y-combinator comes in.  It finds the
     * fixed point of any {@link IntFuncToIntFunc}.  That is,
     * it finds the function for which calling 
     * {@link IntFuncToIntFunc} one more time will yield the
     * same function.
     *
     * This is all just a fancy way of saying that it contains 
     * the plumbing to make sure the original function that 
     * needs to get calls back into itself will get them.
     *
     * This implements recursion for any 
     * {@link IntFuncToIntFunc} that generates
     * a function that calls back to the passed in function.
     */
    static class YCombinator implements IntFunc {
        private final IntFuncToIntFunc mIntFuncToIntFunc;

        public YCombinator(IntFuncToIntFunc intFuncToIntFunc) {
            mIntFuncToIntFunc = intFuncToIntFunc;
        }

        /**
         * The fixed point works by kicking of the first call to 
         * generate the int function.  We pass in ourselves as 
         * the argument so it will call back to our
         * {@link #apply(int)} as necessary.
         */
        public IntFunc fixedPoint() {
            return mIntFuncToIntFunc.apply(this);
        }

        /**
         * If the function calls back into us, we generate 
         * another function that calls back into us again.  
         * This will keep happening until it knows the 
         * answer itself (its base case).
         */
        public int apply(int n) {
            // setup another function with ourselves as 
            // the callback again
            final IntFunc func = mIntFuncToIntFunc.apply(this);

            // then just apply it
            return func.apply(n);
        }
    }

    public static void main(String args[]) {     
        final IntFuncToIntFunc factGen = new FactGen();

        // if we apply the ycombinator to factgen, we have 
        // a working implementation of factorial
        final IntFunc factorial = new YCombinator(factGen).fixedPoint();

        System.out.println(factorial.apply(3));
  }
}

So the Y Combinator works by serving as a trampoline for a generated function to bounce off back into itself after another function has been generated.