SyntaxHighlighter

16 Sep 2013

The Y Combinator

The Y combinator is one of the most beautiful ideas in programming theory. It allows one to define recursive functions from non-recursive, anonymous functions. The "anonymous" is what makes this particularly amazing: We are going to have recursion without having a way for a function to refer to itself by name. The usual example is the factorial function.

The theoretical background is beautifully and thoroughly explained by Mike Vanier in his article The Y Combinator (Slight Return), which I am not going to repeat here. (For a very short, readable intro to the topic, you might also refer to Deron Meranda's blog post on fixpoints.)

Many people seem to enjoy implementing the Y combinator, even in Java. Most implementations seem in some way to go back to this one by Ken Shirriff, which is in Java 7 and almost unreadable due to the use of inner classes. And here is a Java 8 implementation by Arul Dhesiaseelan. Note that the code on that last-mentioned post uses a method name Y, and that the comments on it propose a simplification which uses the this reference. Both are strictly not allowed, one might say that this is cheating. So here is my own, very similar but non-cheating implementation:

 
import java.util.function.Function;

public class YCombinator {

    // First a few abbreviations

    /** Function on T returning T. */
    interface Func<T> extends Function<T,T> {
    }

    /**
     * Higher-order function returning a T function.
     * <br>F: F -> (T -> T)
     * <br>This is the type of the Y combinator subexpressions.
     */
    interface FuncToTFunc<T> extends Function<FuncToTFunc<T>, Func<T>> {
    }

    /**
     * Function from a function on T functions to a T function.
     * <br>((T -> T) -> (T -> T)) -> (T -> T)
     * <br>This is the type of the fixed point operator.
     */
    interface Fix<T> extends Function<Func<Func<T>>, Func<T>>  {
    }

    // And now the real thing

    /**
     * Computes the factorial with the applicative-order Y combinator.
     * <br>Y = λr.(λf.(f f)) λf.(r λx.((f f) x))
     */
    public static int factorial(int n) {
        return  // Y combinator
                ((Fix<Integer>) r ->
                    ((FuncToTFunc<Integer>) (f -> f.apply(f)))
                            .apply(f -> r.apply(x -> f.apply(f).apply(x)))
                )
                .apply(
                        // Recursive function generator
                        f -> x -> (x == 0) ? 1 : x * f.apply(x - 1)
                )
                .apply(
                        // Argument
                        n);
    }
}

This code really computes the factorial function. And it does this using only anonymous functions: no function names or variables anywhere except lamba parameters. (You can plug-in any other recursive function you might want to compute, e. g. Fibonacci, or Ackermann, etc.).

The regrettable thing is having to have those casts. It would be nice to be able to get rid of them.

-- Sebastian