szeiger.de

Y Combinator in Java With Generics

August 12th, 2007 | In Java

After reading Y Combinator for Dysfunctional Non-Schemers I wondered how far you could go with implementing a Y Combinator in Java with generic types. And I had a strong feeling that it would be rather ugly!

I started with the call-by-value version of the Y Combinator as given by the following expression, straight from the Wikipedia page:

Z = λf. (λx. f (λy. x x y)) (λx. f (λy. x x y))

This one innocent line translates directly to the following mess in untyped Java:

static interface F { Object call(Object arg1); }
 
static F z(final F f)
{
  return (F)
  (
    new F()
    {
      public Object call(final Object x)
      {
        return f.call
        (
          new F()
          {
            public Object call(final Object y)
            {
              return ((F)((F)x).call(x)).call(y);
            }
          }
        );
      }
    }
  )
  .call
  (
    new F()
    {
      public Object call(final Object x)
      {
        return f.call
        (
          new F()
          {
            public Object call(final Object y)
            {
              return ((F)((F)x).call(x)).call(y);
            }
          }
        );
      }
    }
  );
}

It could be simplified further (it’s not necessary to create an F object at the beginning because it is called immediately) but the simplified version turned out to be even harder to annotate with generic types.

The next step was to gradually add type annotations where possible and remove the type casts. I finally arrived at this point where I could not add any more consistent annotations:

static interface F<R,P> { R call(P arg1); }
 
static <R,P> F<R,P> z(final F<F<R,P>,F<R,P>> f)
{
  return
  (
    new F<F<R,P>,F>()
    {
      public F<R,P> call(final F x)
      {
        return f.call
        (
          new F<R,P>()
          {
            public R call(final P y)
            {
              return (R) ((F) x.call(x) ) .call(y);
            }
          }
        );
      }
    }
  )
  .call
  (
    new F<F<R,P>,F<F<R,P>,F<?,?>>>()
    {
      public F<R,P> call(final F<F<R,P>,F<?,?>> x)
      {
        return f.call
        (
          new F<R,P>()
          {
            public R call(final P y)
            {
              return x.call(x).call(y);
            }
          }
        );
      }
    }
  );
}

This version still contains two casts and several type warnings due to the use of raw types. I am not sure if it would be possible to get closer to the ambiguously typed part and I didn’t want to spend any more time trying to. It was already clear that this can only serve as a proof of concept and that you would be ill advised to ever use something like this in production code.

Finally, here’s some code to show how the z function is used and that it really works:

final F<F<Integer,Integer>,F<Integer,Integer>> fac = new F<F<Integer,Integer>,F<Integer,Integer>>()
{
  public F<Integer,Integer> call(final F<Integer,Integer> rec)
  {
    return new F<Integer,Integer>()
    {
      public Integer call(final Integer i)
      {
        if(i <= 1) return 1;
        else return i * rec.call(i-1);
      }
    };
  }
};
 
System.out.println("5! = " + z(fac).call(5));

Share This | Comments RSS | Trackback

2 Responses to “Y Combinator in Java With Generics”

Daniel Martin says:
February 28th, 2008 at 1:14 pm
You can go further with the annotations – it’s possible to do it entirely with annotations and no casting (I note that you need to do a cast to R and a cast to F in your version). What you need to do to do this is to define a recursive type.

I show how here: http://dtm.livejournal.com/36832.html

I use the interface com.google.common.base.Function, which is like F except that the single method is called “apply” and the order of the type parameters are switched. (So that Function is a function that takes a String as a parameter, and returns an Integer)
Daniel Martin says:
February 28th, 2008 at 1:17 pm
Ugh. That was supposed to be:
So that Function<String,Integer> is a function that takes a String as a parameter, and returns an Integer.

Unfortunately, I had no way of knowing whether this blog accepted html in the comments and no way of previewing my comment before I made it.

Y Combinator in Java With Generics

2 Responses to “Y Combinator in Java With Generics”

Leave a Reply