Fun with Generics and CGLib: Functional Programming in Java with less hassle


Come on, admit it. You've got functional envy. You've seen Quicksort in 3 lines or less of code. You've salivated over map/reduce and function curry looks as good as it tastes.

Up until now, you've had two choices. One, switch to a language which allows functional expressions with economical syntax, such as Scheme, Haskell, Ruby, or Groovy. Or, use laborious Anonymous Inner/Local classes to fake it like commons-collections.

We'll, I'm gonna show you how to do it without much syntactic overhead, and preserve enough type information to even allow your IDE to do some refactoring, and popup fields and methods on return values of "functions"

Preliminaries

Before we get started, you should review Alex Winston's Strongly Typed Java Delegates and my previous blog entry on Refactorable Type-Safe Configuration without XML or Annotations. If you don't know what functional programming is, or why it matters, read Why Functional Programming Matters.


Goal

Our goal is to try and make writing functions as easy as possible, and allow them to be curried, composed, and passed as arguments to other functions. Functions, as used in this article, are not just any old Java method. They are Java instance methods which are pure-functional, that is, without side-effects, and do not reference any object fields or non-static variables. Essentially, they are non-mutating static functions declared without a static qualifier.

This,

public MathFuncs
{
public int add(int x, int y) { return x+y; }
public int mul(int x, int y) { return x*y; }
}

is an example of functions. They are an instance methods and do not mutate state.

Example functional usage

Lambda mul = lambda(nop(MathFuncs.class).mul(0,0));
Lambda triple = mul.curry(3);
Lambda quadruple = mul.curry(4);
Lambda timesTwelve = compose(triple, quadruple);

System.out.println("10 timesTwelve = "+timesTwelve.call(10));

or how about



Lambda sum = reducel(add, 0);
// the numbers 1-10 times twelve, and then summed together
int x=sum.call(map(timesTwelve, list(1,2,3,4,5,6,7,8,9,10)));

Ok, my interest is peaked. What is that funky lambda and nop function?

All Java functions must first be converted to Lambda functions, which is a Java interface with the following signature:

public interface Lambda<T> {
public T call(Object... args);
public Lambda<T> curry(Object arg);
public Method method();
}

Extremely simple as you can see, you can either invoke a function, curry it, or get access to the underlying Java reflection Method, which is used internally. Ordinarily, to make Java functions into Lambda functions, you've have to write classes like this

public class Add implements Lambda<Integer>
{
public T call(Object... arg) { return MathFuncs.instance().add(arg[0], arg[1]); }
...
}

and indeed, you'd have to write a separate implementation for each and every interface you use.

Ahhh...Don't tell me. Delegates!
Yes, if you recall the Strongly Typed Delegates trick, this will be yet another variation. What we'll do is use the nop() function to create an CGLib interceptor for a given class, return an instance of this proxied class, and invoke a method on this instance. This will then tell the proxy which method we want to create a Lambda for.

Here's a snippet of how nop() works, the complete listing will follow later

public static <T> T nop(Class<T> clz)
{
   T x = (T) Enhancer.create(clz, new Class[]{Lambda.class},
             new LambdaInterceptor(clz));
   return x;
}

Now, you'll note that this function does not return a Lambda object! It returns an instance of the type of the class it was invoked on! nop(Foo.class) returns Foo! That's where lambda() comes in. It turns instances of Objects into Lambda interfaces! When you invoke a method like add() on Foo.class, the interceptor takes the return value of the add() function and associates itself with it. Then lambda converts these back into Lambda interfaces.

public static <T> Lambda<T> lambda(T pm) {
     Lambda<T> l = (Lambda<T>) interceptors.get(pm);
     interceptors.remove(pm);
     return l;
 }

How does it do it? Well, when you write nop(Foo.class), a CGLib proxy is created for an instance of class Foo, and placed into a global interceptors Map with object instance as key, and the Lambda interceptor as value. Next, when you call something like nop(Foo.class).add(1,2), the add() function gets intercepted, and a java.lang.Method reference is placed in this map as well. Finally, when you call lambda() on an instance that has be proxied by a LambdaInterceptor, it pulls the interceptor out of the map, and casts it into a Lambda.

Other Tricks
If you feel like typing extra generics parameters, you could have call() methods which are type-safe. For example, you could create a Lambda1 and Lambda2 interface which both extend Lambda, but which have non-varargs call() methods taking 1 and 2 parameters each.

Then you could write code like

  lambda2(nop(MathFuncs.class).add(1,2)).call("Foo", "Bar")

And your IDE would flag call("Foo", "Bar") as an error! I leave the generic type signatures of Lambda1 and Lambda2, and the definition of the lambda1 and lambda2 helper functions as an exercise for the reader.

As a final note, yet, there is a way to optimize away some of the unneccessary object creation, which will I do in a later release.

Have fun(ctional)!
-Ray



Here's the complete listing for Func.java, which includes the LambdaInterceptor
Func.java

package functional;

import net.sf.cglib.proxy.Enhancer;
import net.sf.cglib.proxy.MethodInterceptor;
import net.sf.cglib.proxy.MethodProxy;

import java.lang.reflect.InvocationTargetException;
import java.lang.reflect.Method;
import java.util.HashMap;

/**
 * Created by IntelliJ IDEA.
 * User: ray
 * Date: Jun 29, 2006
 * Time: 12:21:31 PM
 *
 */
public class Func {

    protected static HashMap<Object, LambdaInterceptor> interceptors = new HashMap<Object, LambdaInterceptor>();

    public static <T> Lambda<T> lambda(T pm) {
        Lambda<T> l = (Lambda<T>) interceptors.get(pm);
        interceptors.remove(pm);
        return l;
    }

    public static <T> T nop(Class<T> clz) {
        T x = (T) Enhancer.create(clz, new Class[]{Lambda.class}, new LambdaInterceptor(clz));
        return x;
    }


    public static <F,G> Lambda<F> compose(Lambda<F> f, Lambda<G> g) {
        return new CompositionLambda<F>(f, g);
    }

    protected static class LambdaInterceptor<T,S> implements MethodInterceptor, Lambda<S> {
        private T proxy;
        private Class<T> clazz;
        private Method binding = null;

        public LambdaInterceptor(Class<T> target) {
            try {
                this.proxy = target.newInstance();
            } catch (InstantiationException e) {
                e.printStackTrace();  //To change body of catch statement use File | Settings | File Templates.
            } catch (IllegalAccessException e) {
                e.printStackTrace();  //To change body of catch statement use File | Settings | File Templates.
            }
            this.clazz = target;
        }

        public Object intercept(final Object o, final Method m,
                                final Object[] args, MethodProxy mp) throws Throwable {


            if (m.getName().equals("toString")) {
                return "Invoked by Debugger variable display!";
            } else if (m.getName().equals("method")) {
                return method();
            } else if (m.getName().equals("call")) {
                return call(args);
            } else if (m.getName().equals("curry")) {
                return curry(args[0]);
            } else {
                Method[] meths = proxy.getClass().getMethods();
                for(Method mi : meths)
                  if(mi.equals(m)) { binding=mi; break; }
                
                if(binding==null) throw new NoSuchMethodException(m.toString());
                binding.setAccessible(true);
                Object ob = null;

                ob = binding.invoke(proxy, args);
                interceptors.put(ob, this);
                return ob;

            }
        }


        private static Class[] classes(Object[] objects) {
            Class[] classes = new Class[objects.length];
            for (int i = 0; i < objects.length; i++)
                classes[i] = objects[i].getClass();
            return classes;
        }

        public S call(Object... args) {
            try {
                return (S) binding.invoke(proxy, args);
            } catch (IllegalAccessException e) {
                e.printStackTrace();
                throw new RuntimeException(e);
            } catch (InvocationTargetException e) {
                e.printStackTrace();
                throw new RuntimeException(e);
            }
        }

        public Lambda<S> curry(Object arg) {
            return new CurriedLambda(this, arg);
        }

        public Method method() {
            return binding;
        }
    }

}

Util.java

package functional;

import static functional.Func.lambda;
import static functional.Func.nop;

import static java.util.Collections.EMPTY_LIST;
import java.util.*;

/**
 * Created by IntelliJ IDEA.
 * User: ray
 * Date: Jun 30, 2006
 * Time: 5:33:25 PM
 */
public class Util {
    public static <F, I> F reduce(Lambda<F> f, I init, List<I> list) {
        if (list == null || list.isEmpty()) return f.call(init, init);
        if (list.size() == 1) return f.call(init, list.get(0));
        return f.call(list.get(0), reduce(f, init, list.subList(1, list.size())));
    }

    public <F,I> F _reduce(Lambda<F> f, I init, List<I> list)
    {
        return reduce(f, init, list);
    }

    public static <F, I> Lambda<F> reducel(Lambda<F> f, I init) {
        return lambda(nop(Util.class)._reduce(f, init, (List<I>) EMPTY_LIST)).curry(f).curry(init);
    }


    public <T> List<T> _map(Lambda<T> lambda, List<?> list)
    {
        return map(lambda, list);
    }

    public static <T> Lambda<List<T>> mapl(Lambda<T> lambda)
    {
       return lambda(nop(Util.class)._map(lambda, (List<?>) EMPTY_LIST));
    }

    public static <T> List<T> map(Lambda<T> lambda, List<?> list)
    {

            List<T> nl = newList(list);
            for(Object o : list)
            {
               nl.add(lambda.call(o));
            }
        return nl;
    }

    private static <T> List<T> newList(List<?> list) {
        return list instanceof LinkedList ? new LinkedList<T>() : new ArrayList<T>();
    }

    public static List<Integer> list(int... ints)
    {
      ArrayList al=new ArrayList();
      for(int x : ints) al.add(x);
      return al;
    }


    public static <T> List<T> cons(T a, List<T> l)
    {
        List<T> nl = newList(l);
        nl.add(a);
        nl.addAll(l);
        return nl;
    }

    public <T> List<T> _cons(T a, List<T> l)
    {
        return cons(a, l);
    }

    public static <T> Lambda<List<T>> consl(T a)
    {
        return lambda( nop(Util.class)._cons(a, (List<T>)EMPTY_LIST));
    }
}

CurriedLambda.java

package functional;

import java.lang.reflect.Method;

/**
 * Created by IntelliJ IDEA.
 * User: ray
 * Date: Jun 30, 2006
 * Time: 5:31:43 PM
 */
public class CurriedLambda<T> implements Lambda<T> {
    private final Lambda<T> lambda;
    private final Object arg;

    public CurriedLambda(Lambda<T> lambda, Object arg) {

        this.lambda = lambda;
        this.arg = arg;
    }

    public T call(Object... args) {
        return lambda.call((Object[]) args(arg, args));
    }

    public Lambda<T> curry(Object arg) {
        return new CurriedLambda(this, arg);
    }

    public Method method() {
        return lambda.method();
    }

    private Object args(Object arg, Object[] args) {
        Object[] nargs = new Object[args.length + 1];
        nargs[0] = arg;
        System.arraycopy(args, 0, nargs, 1, args.length);
        return nargs;
    }
}

CompositionLambda.java

package functional;

import java.lang.reflect.Method;

/**
 * Created by IntelliJ IDEA.
 * User: ray
 * Date: Jun 30, 2006
 * Time: 5:31:35 PM
 */
public class CompositionLambda<T> implements Lambda<T> {
    private final Lambda<T> f;
    private final Lambda g;

    public CompositionLambda(Lambda<T> f, Lambda g) {

        this.f = f;
        this.g = g;
    }

    public T call(Object... args) {
        return f.call(g.call((Object[]) args));
    }

    public Lambda<T> curry(Object arg) {
        return new CurriedLambda<T>(this, arg);
    }

    public Method method() {
        return f.method();
    }
}

FuncTest.java test code

package functional;


import static functional.Func.compose;
import static functional.Func.nop;
import static functional.Func.lambda;
import static functional.Util.list;

import java.util.Collection;

/**
 * Created by IntelliJ IDEA.
 * User: ray
 * Date: Jun 30, 2006
 * Time: 1:16:23 PM
 */
class FuncTest {
    public int add(int x, int y) {
        return x + y;
    }

    public int mul(int x, int y) {
        return x * y;
    }

    public int square(int x) { return x*x; }
    public Boolean greater(Comparable x, Comparable y)
    {
        return x.compareTo(y) > 0;
    }

    public Boolean or(Boolean a, Boolean b) { return a.booleanValue() || b.booleanValue(); }
    public Boolean and(Boolean a, Boolean b) { return a.booleanValue() && b.booleanValue(); }

    public Boolean truth(Object o)
    {
        if(o == null) return Boolean.FALSE;
        if(o instanceof Number) return ((Number)o).longValue() != 0;
        if(o instanceof String) return ((String)o).length() != 0;
        if(o instanceof Collection) return ((Collection)o).size() != 0;

        return false;
    }

    public static void main(String[] args) {
        try {
            // Func.curry(Test.class, Func.nop(Test.class).add(1,2)).curry(1).call(2);
            Lambda<Integer> mul = lambda(nop(FuncTest.class).mul(1, 2));

            Lambda<Integer> plus = lambda(nop(FuncTest.class).add(1, 2));
            Lambda<Integer> triple = mul.curry(3);
            Lambda<Integer> quadruple = mul.curry(4);
            Lambda<Integer> timesTwelve = compose(triple, quadruple);
            Lambda<Integer> sum = Util.reducel(plus, 0);
            Lambda<Integer> square = lambda(nop(FuncTest.class).square(0));

            quadruple.call(12);

            System.out.println(
                    timesTwelve.call(
                            sum.call(list(1,2,3,4,5,6,7,8,9,10))));

            System.out.println(
                        sum.call(Util.map(square, list(1,2,3,4,5,6,7,8,9,10))));


            Lambda<Boolean> or = lambda(nop(FuncTest.class).or(true, true));
            Lambda<Boolean> and = lambda(nop(FuncTest.class).and(true, true));
            Lambda<Boolean> truth = lambda(nop(FuncTest.class).truth(true));

            Lambda<Boolean> anyTrue = Util.reducel(or, false);
            Lambda<Boolean> allTrue = Util.reducel(and, true);

            Lambda<Boolean> greater =  lambda(nop(FuncTest.class).greater(1,2));

            System.out.println("There is a number greater than less than 0 "+anyTrue.call(Util.map(greater.curry(2), list(1,2,3,4,5,6,7,8,9,10))));

        } catch (Exception e) {
            e.printStackTrace();  //To change body of catch statement use File | Settings | File Templates.
        }
    }
}