Heterogeneous Lists and the Limits of the Java Type System

Today, we’re going on a journey. It is a sojourn to the outer limits of the expressiveness of the Java type system, and to the edge of what can be considered sane programming. This is definitely one for the power users. You will need a firm grasp of the Java language, and an iron constitution for type annotations. But the reward will be something far greater than any treasure: understanding, entertainment, and perhaps even enlightenment. Remember that we choose to do these things in Java, not because they are easy, but because they are hard. Now then, to the ships.

A Most Versatile Vessel

In Java, we can create a list that contains values of type A, by constructing a value of type List<A>. The type system will enforce that each element in the list is in fact of type A. But sometimes we want lists of values that aren’t necessarily of the same type. Normally, for such a purpose, we would use a heterogeneous list, which in Java is just the raw list type List<?> or List<Object>. Since every class in Java is a subclass of Object (and now that we have autoboxing), such a list can contain any Java value. There are many kinds of situation where this would be necessary. For example, a row of database results will comprise values that are not all of the same type.

However, there’s a problem with the raw list approach. In using the List<?> type, we are dispensing with the type system. When you get a value from the list, how do you know what it is? How do you know which operations it supports? Well, you will have to defer that discovery until runtime, and use explicit type casting. Most will shrug at this and say: “So what?” After all, this is what we did anyway, before generics. Ah, but what if we don’t have to? Can we create generic heterogeneous collections that are type-safe? Yes, we can. Sort of.

Products of Types

What we would like to see is if it’s possible to declare some constraints on the types of a heterogeneous collection, to achieve essential type-safety while maintaining the extensibility of a list. Of course, it’s easy to create types that are the product of two or more types:

public abstract class P2<A, B> {
  public abstract A _1();
  public abstract B _2();
}

But the length of this kind of product is as fixed as the length of a string in Pascal. It isn’t extensible, so it’s more like a type-safe heterogeneous array than a list. If you want products of different lengths, you will need to declare separate classes for P3<A, B, C>, P4<A, B, C, D>, etc. What we’re trying to achieve is a product of arbitrary length, whose length might even vary at runtime. There’s no reason we couldn’t create products of products in a chain, like P2<A, P2<B, P2<C, D>>>, and this is more or less the approach that we will take.

Introducing HList

To achieve our goal, we’re going to implement linked lists in the type system. Let’s remind ourselves what a linked list looks like. A List<T> is essentially either the empty list or a value of type T paired with a List<T>. In Java, using the List<A> type from Functional Java, an unsafe heterogeneous list might be constructed in a manner like the following:

List<?> x = cons("One", cons(2, cons(false, nil()));

The cons method constructs a list, and the nil method returns the empty list. With just these two methods, we can create any homogeneous list. A list has two methods to access its members, head() which returns the first element, and tail() which returns the rest of the list. Getting the head or tail of the empty list is an error at runtime.

Let’s now take a step up into the type system, and say that a list of types is either the empty list or a type paired with a list of types. This gives rise to our heterogeneous list type:

public abstract class HList<A extends HList<A>> {
 private HList() {}

 private static final HNil nil = new HNil();

 public static HNil nil() {
   return nil;
 }

 public static <E, L extends HList<L>> HCons<E, L> cons(final E e, final L l) {
   return new HCons<E, L>(e, l);
 }

 public static final class HNil extends HList<HNil> {
   private HNil() {}
 }

 public static final class HCons<E, L extends HList<L>> extends HList<HCons<E, L>> {
   private E e;
   private L l;

   private HCons(final E e, final L l) {
     this.e = e;
     this.l = l;
   }

   public E head() {
     return e;
   }

   public L tail() {
     return l;
   }
 }
}

That’s not a lot of code, and it’s all relatively straightforward Java. The HList class is parameterised with a parameterised subclass of itself. There are only two concrete subclasses of HList that can possibly occupy that slot: the type HNil and the type constructor HCons. These represent the empty list and the list constructor, respectively. HCons takes two type parameters, the first representing the first element of the list, and the second being another HList, allowing us to form a chain of them. HNil does not take type parameters, so it terminates the chain.

As with regular old lists, you can access the head() and tail() of the list. Note, however, that the fact that you cannot get the head or tail of the empty list is now enforced by the type system. There’s a nil method to get the empty list, and a cons method to construct a nonempty list, just like with regular lists.

Here’s an example of how we would construct a heterogeneous list using this new type:

HCons<String, HCons<Integer, HCons<Boolean, HNil>>> x = cons("One", cons(2, cons(false, nil()));

This is more verbose than the unsafe version before, but not by much. Obviously, the HList example assumes a static import of HList.cons and the List<?> example assumes a static import of List.cons. Using the type-safe version is, however, much nicer. Compare these two contrived examples:

if (x.tail().tail().head()) {
  return x.head().length() == x.tail().head();
}

if ((boolean) x.index(3)) {
  return ((String) x.head()).length() == (int) x.index(2);
}

The latter, of course, offers no static guarantees and may throw ClassCastExceptions, or we might inadvertently get the head or tail of the empty list at runtime. The former will always work as long as it compiles, guaranteed.

Concatenating HLists

Now let’s do something more interesting with these lists. Notice that the cons methods for both type-safe and unsafe lists prepend an element to a list rather than appending. Sometimes we want to append a list to the end of another. This is unsurprisingly uncomplicated for unsafe lists:

List<?> c = a.append(b);

Behind the scenes, we can think of append as reversing the first list and consing each element to the second list in reverse order. Doing that for HList is a little more involved. We have to construct a chain of types in exactly the right way, at compile-time.

Appending an HList to another is a function that takes two HList-valued arguments and returns an HList. Using first-class functions from Functional Java, the append operation for HLists of specific types L and R, would be a function of the following type:

F2<L extends HList<R>, L extends HList<L>, LR extends HList<LR>>

Where LR is the type of the concatenated HList. Now, since we necessarily have the two arguments, we know the specific types of L and R. Since Java doesn’t have type inference, it cannot automatically figure out the specific type of LR. We will have to supply it as type annotation. Not to worry. Even though Java doesn’t infer types, it can be coerced into doing some type arithmetic. All we have to do is a little inductive reasoning.

Types as Formulae

According to the Curry-Howard isomorphism, a program is a proof, and the hypothesis that it proves is a type for the program. In this sense, Java’s type system is a kind of crude theorem prover. Put another way, a type is a predicate, and values of that type represent the terms for which the predicate holds. The function type above therefore asserts that for any two HLists, L and R, there exists some program to derive the HList LR. The function type by itself does not put any constraints on LR, however. It can be derived by any function, not just the concatenation function. We will remedy that presently. We need a formula that states that the two types L and R imply a third type LR which is the HList concatenation of L and R, given some concatenation function. Here is the type that represents that formula:

public static final class HAppend<L, R, LR> {
    private final F2<L, R, LR> append;

    private HAppend(final F2<L, R, LR> f) {
      append = f;
    }

    public LR append(final L l, final R r) {
      return append.f(l, r);
    }
}

At this point, HAppend is still just a hypothesis without evidence. Remember that a value of a type is proof of the formula that it represents. So we will need to supply two proofs in the form of constructors for values of this type; one for the base case of appending to the empty list HNil, and another for the case of appending to an HCons. The base case is easy. Appending anything to the empty list should result in that same thing. So the HAppend constructor for appending to the empty list looks like this:

    public static <L extends HList<L>> HAppend<HNil, L, L> append() {
      return new HAppend<HNil, L, L>(new F2<HNil, L, L>() {
        public L f(final HNil hNil, final L l) {
          return l;
        }
      });
    }

The case for the nonempty list is not quite as easy. Consider its type:

    public static <X, A extends HList<A>, B, C extends HList<C>, H extends HAppend<A, B, C>>
                         HAppend<HCons<X, A>, B, HCons<X, C>> append(final H h)

Read the return type first. This returns an HAppend that appends some B to an HCons<X, A>. The type of the head of the first list (X) becomes the type of the head of the concatenated list. The tail of the concatenated list is C. The type constraints state that C must be an HList, and that there must exist some way to append B (the second list) to A (the tail of the first list) so that they make C. We must supply proof that this last constraint holds, and you’ll see that such a proof is in fact supplied as an argument (in the form of the value h).
What this is saying is that, given the premise that A and B can be concatenated, the concatenation of HCons<X, A> and B can be inferred. A value of type HAppend<A, B, C> is precisely proof of the hypothesis that A and B can be concatenated, since there are only these two cases and we’ve supplied a proof for both. In other words, if we can append to the empty list, then that’s proof enough that we can append to a list of one element, which proves that we can append to a list of two elements, and so on. Given this, we can construct a chain of proofs. This concatenated proof, then, is a function that concatenates lists of the corresponding types.

OK, so how do we use this? Well, here’s an example program that appends one list to another:

public class HList_append {
  public static void main(final String[] args) {
    // The two lists
    final HCons<String, HCons<Integer, HCons<Boolean, HNil>>> a =
      cons("Foo", cons(3, cons(true, nil())));
    final HCons<Double, HCons<String, HCons<Integer[], HNil>>> b =
      cons(4.0, cons("Bar", cons(new Integer[]{1, 2}, nil())));

    // A lot of type annotation
    final HAppend<HNil, HCons<Double, HCons<String, HCons<Integer[], HNil>>>,
      HCons<Double, HCons<String, HCons<Integer[], HNil>>>> zero = append();
    final HAppend<HCons<Boolean, HNil>, HCons<Double, HCons<String, HCons<Integer[], HNil>>>,
      HCons<Boolean, HCons<Double, HCons<String, HCons<Integer[], HNil>>>>> one = append(zero);
    final HAppend<HCons<Integer, HCons<Boolean, HNil>>, HCons<Double, HCons<String, HCons<Integer[], HNil>>>,
      HCons<Integer, HCons<Boolean, HCons<Double, HCons<String, HCons<Integer[], HNil>>>>>> two = append(one);
    final HAppend<HCons<String, HCons<Integer, HCons<Boolean, HNil>>>,
      HCons<Double, HCons<String, HCons<Integer[], HNil>>>,
      HCons<String, HCons<Integer, HCons<Boolean, HCons<Double, HCons<String, HCons<Integer[], HNil>>>>>>>
      three = append(two);

    // And all of that lets us append one list to the other.
    final HCons<String, HCons<Integer, HCons<Boolean, HCons<Double, HCons<String, HCons<Integer[], HNil>>>>>>
      x = three.append(a, b);

    // And we can access the components of the concatenated list in a type-safe manner
    if (x.tail().tail().head())
      System.out.println(x.tail().tail().tail().tail().tail()[1] * 2); // 4
  }
}

Holy pointy brackets, Batman! Do we really need all of that? Well, look at what it’s doing. It’s constructing a concatenation function of the appropriate type, by supplying the premise at each step. If this seems mechanical, then that’s because it is. There is only one possible implementation for the HAppend we need, but Java does not have any mechanism for figuring this out, nor does it provide a facility for the programmer to tell it how.
Contrast that to Scala. The above is a clear example of where Scala’s implicit arguments come in handy. If we import this to Scala, we can make both of the append functions implicit, and we can further make the H argument to the append function for nonempty lists implicit as well. There can be only one possible implementation of each function, so it can be declared once and used implicitly wherever proofs of the corresponding types are required. Jesper Nordenberg has implemented an HList library for Scala that demonstrates this well. With implicits and Scala, the whole middle section of our program is condensed from 12 lines of type annotations to just:

 val x = a.append(b)

Now, if you’re really into this Java stuff, you’re probably thinking: “implicits are just dependency injection”. Well, in a sense, you would be right. Both dependency injection and inheritance are degenerate forms of implicits. However, there is currently no dependency injection framework for Java that can abstract over type constructors such that it provides injection of parameterised types with injection of type parameters also. If you can prove me wrong, by all means send me evidence in the form of working code.

Conclusion

Clearly, Java is not very useful for this kind of type-safe programming. I was actually quite surprised that you can do this in Java at all, but we’ve definitely hit the outer boundary of what can be considered reasonably expressible.

The code you’ve seen in this article uses the new HList package that was released with Functional Java 2.16. And is based on the Haskell HS library by Oleg Kiselyov.

Higher-Order Java Parallelism, Part 4: A Better Future

This is the fourth installment in a series of posts about making highly concurrent software easier to write in Java. Previous entries are available here: part 1, part 2, part 3. However, I aim to make it possible to follow along even if you haven’t read the previous posts.

I Have Seen the Future…

If you have used the Java 5 concurrency API at all, you will have come across the Future class. For example, when you submit a Callable<Integer> to an ExecutorService, what you get back is a Future<Integer> which represents a computation, running concurrently, that will (hopefully) result in an integer at some time in the future. Once you have the Future<Integer> fi, you can later get the integer out of it by calling fi.get().

That’s all fine and dandy, but let’s say you want do do something like add two future integers. You could do something like this:

int sum = x.get() + y.get();

This will block the current thread until both of those integers are available, then add them together. But why wait for that? If you have an ExecutorService, you can create a new Future that computes the sum:


Future<Integer> sum = executorService.submit(new Callable<Integer>() {
  public Integer call() {
    return x.get() + y.get();
  }
});

Now the current thread can continue, but we’ve started a new thread that does nothing until the values of x and y have both been calculated by yet another thread.

We’re beginning to see a problem here. We want to be able to compose Futures together to form new Futures, but find that the number of threads required to compose n Future values is on the order of O(n). If we have a fixed-size thread pool, we’ll run into starvation. If we have an unbounded thread pool, then we might start more threads than the operating system can handle, most of which will be doing nothing at all but wait for other threads.

This should all sound very familiar. Threads are a space resource. What kind of processes are O(n) in their space requirement? If you said “linearly recursive processes”, go to the head of the class. Intuitively, for the same reason that we can find iterative versions of any recursive algorithm, it seems that we should be able to find an algorithm to accomplish the same thing with O(1) threads.

…and it is a Monad

In the above example, it’s like we’re giving seperate instructions, waiting for the results of each in between. Imagine if we were working in an office with Bob and Alice, and we needed work on something from both of them. We might go to Bob and say: “Bob, process this and give me the result”. Then we’d take the result to Alice and say: “Alice, here’s a result from Bob.” It would be much better, if we could just go to Bob and say: “Bob, process this and give the result to Alice.” This is the essential difference between recursive and iterative processes.

But wait! We say that kind of thing all the time, in Java:


public Work bob(Work w) { ... }
public Work alice(Work w) { ... }

public Work bobThenAlice(Work w) {
  Work b = bob(w);
  return alice(b);
}

Here, we’re instructing a single thread to do some work, then use the result of that work to do more work. What’s really sneaky here is the meaning of the semicolon. In this context, what the former semicolon means is “take the stored value b from the previous statement and bind it to the free variable b in the next statement”. You can think of the second semicolon as binding a blank statement over the result of the preceding statement.

Using first-class functions from Functional Java, and using the Callables monad from the first part of this series, you could implement that same behaviour using something like this:

F<Work, Callable<Work>> bob = new F<Work, Callable<Work>>() {
  public Callable<Work> f(final Work w) {
    return new Callable<Work>() {
      public Work call() { ... }
    };
  }
};
F<Work, Callable<Work>> alice = new F<Work, Callable<Work>>() { ... };

public Callable<Work> bobThenAlice(Work w) {
  return Callables.bind(bob.f(w), alice);
}

That’s pretty neat. Now we have a single Callable that we can run concurrently in a new thread, turning it into a Future. But wouldn’t it be cool if we could bind Futures? That would let us take already running computations and combine them in exactly this way. We want a Future monad.

The problem with combining Futures is in the nature of the future. This is a deliberate pun on “future”. Think about time for a second. What does it mean to get a value that’s in the future? By the very fact that causality is sequential, it’s a violation of the nature of reality to have something that doesn’t yet exist. It’s the future; you’re not supposed to get stuff out. But, we can put stuff in, can’t we? Yes we can. You know those corny time-capsule things where people put their mountain bikes and Nintendo games for future generations to enjoy later? We can do that with data values. And not just values, but computations.

Here’s One I Made Earlier

The Future class in the standard Java libraries doesn’t come with any methods for projecting computations into the future. But Functional Java comes with a class called Promise<A> which does have that feature. It makes use of light-weight concurrent processes (actors), and parallel strategies, as described in the previous post, to implement the ability to combine concurrent computations into larger (concurrently executing) structures.

Since it is implemented as a monad, the methods it provides are all the usual suspects: unit, bind, fmap, join, etc. Here’s a quick overview of what they do and why they’re useful. Grasping them doesn’t just help you understand the Promise class, but any monad you may come across in the (ahem) future.

The unit function, the constructor of Promises, is just called promise. It has a few overloaded forms, but here is the simplest one.

public static <A> Promise<A> promise(Strategy<A> s, P1<A> p);

The P1 class is just a simple closure with no arguments, provided by the Functional Java library. P1<A> consists of one abstract method: A _1(). Strategy represents a method of evaluating P1s concurrently. I also talk about Strategies in the previous post, but the long and the short of it is that it has methods to evaluate the P1 value according to some parallelisation strategy, like with a thread pool for instance.

Calling the promise method starts a concurrent computation, in a manner according to the given strategy, that evaluates p. The resulting Promise value is a handle on the running computation, and can be used to retrieve the value later. Promise.claim() will block the current thread until the value is available, exactly like Future.get(), but this is generally not what you want to do. Instead, you want to bind.

The essence of the monad pattern is the binding function. If you don’t think you already know what a monad is, but understand this method, then you know more than you think:

public Promise<B> bind(F<A, Promise<B>> f);

This method means that if you have a Promise of an A, and a function from an A to a Promise of a B, you can get a Promise of a B. I.e. if somebody promises you an A, and I can promise you a B for every A, it’s the same thing as being promised a B in the first place.

The mapping function:

public Promise<B> fmap(F<A, B> f);

This method means that if you have an Promise of an A, and a function from A to B, you can get a Promise of a B. In other words, you can map any function over a Promise, and fmap will return you a Promise of the result. Behind the scenes, fmap is implemented by calling the bind and promise methods. The difference between this method and the bind method is subtle but important. Calling p.bind(f) is exactly equivalent to calling Promise.join(p.fmap(f)).

The join function:

public static <A> Promise<A> join(Promise<Promise<A>> a);

Join is a lot more useful than it looks. If you have a promised Promise, it’s the same as just having a Promise. In practise, that means that if you can start a concurrent task that starts a concurrent task, you can combine those into one concurrent task. You can think of it as the semantic equivalent of Thread.join(), except that our method returns the joined Promise immediately.

Coming back to Bob and Alice for a second, we can implement bob and alice from the Callables example above, using Promise instead of Callable . Both bob and alice will construct Promises using the promise method, putting whatever work they do inside a P1. That way, when you call bob, he’s already doing his work by the time you mention Alice’s name:

final Strategy<Work> s = Strategy.simpleThreadStrategy();
F<Work, Promise<Work>> bob = new F<Work, Promise<Work>>() {
  public Promise<Work> f(final Work w) {
    return promise(s, new P1() {
      public Work _1() { ... }
    });
  }
};
F<Work, Promise<Work>> alice = new F<Work, Promise<Work>>() { ... };

public Promise<Work> bobThenAlice(Work w) {
  return bob.f(w).bind(alice);
}

So now that we can build arbitrarily complex concurrent processes from already-running processes, how do we get the final promised value out? Again, you could call Promise.claim(), but that blocks the current thread as we know. Instead, Promise comes equipped with a method to(Actor<A>) which promises to send the value to the given Actor as soon as it’s ready. Control is returned to the current thread immediately, and the whole computation continues in the background, including the action to take on the final result. Actors were discussed in the previous post.

A Fully Functional Example

I think an example is in order. The following program calculates Fibonacci numbers using a naive recursive algorithm. This is an algorithm that benefits particularly well from parallelisation (barring any other kind of optimisation). If we were just using plain old Future instead of Promise, the number of Threads required to calculate the nth Fibonacci number is O(fib(n)). But since we’re using Promise, we can use a fixed number of actual Java threads.


package concurrent;

import static fj.Bottom.error;
import fj.Effect;
import fj.F;
import fj.F2;
import fj.Function;
import fj.P;
import fj.P1;
import fj.P2;
import fj.Unit;
import fj.data.List;
import fj.control.parallel.Actor;
import fj.control.parallel.Promise;
import fj.control.parallel.Strategy;
import static fj.data.List.range;
import static fj.function.Integers.add;
import static fj.control.parallel.Promise.join;
import static fj.control.parallel.Promise.promise;
import static fj.control.parallel.Actor.actor;

import java.text.MessageFormat;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class Fibs {

  private static final int CUTOFF = 35;

  public static void main(final String[] args) throws Exception {
    if (args.length < 1)
      throw error("This program takes an argument: number_of_threads");

    final int threads = Integer.parseInt(args[0]);
    final ExecutorService pool = Executors.newFixedThreadPool(threads);
    final Strategy<Unit> su = Strategy.executorStrategy(pool);
    final Strategy<Promise<Integer>> spi = Strategy.executorStrategy(pool);

    // This actor performs output and detects the termination condition.
    final Actor<List<Integer>> out = actor(su, new Effect<List<Integer>>() {
      public void e(final List<Integer> fs) {
        for (P2<Integer, Integer> p : fs.zipIndex()) {
          System.out.println(MessageFormat.format("n={0} => {1}", p._2(), p._1()));
        }
        pool.shutdown();
      }
    });

    // A parallel recursive Fibonacci function
    final F<Integer, Promise<Integer>> fib = new F<Integer, Promise<Integer>>() {
      public Promise<Integer> f(final Integer n) {
        return n < CUTOFF ?
                promise(su, P.p(seqFib(n))) :
                f(n - 1).bind(f(n - 2), add);
      }
    };

    System.out.println("Calculating Fibonacci sequence in parallel...");

    join(su, spi.parMap(fib, range(0, 46)).map(Promise.<Integer>sequence(su))).to(out);
  }

  // The sequential version of the recursive Fibonacci function
  public static int seqFib(final int n) {
    return n < 2 ? n : seqFib(n - 1) + seqFib(n - 2);
  }

}

For all you Scala fans out there, the Functional Java library comes with convenient bindings for Scala as well. Here’s the same thing written in Scala. Note that this does not use the Actor library from the standard Scala libraries, but the same lighter weight Java implementation that the Java example above uses.


package concurrent

import fj.control.parallel.{Actor, Promise}
import fj.Function.curry
import fj.control.parallel.Strategy.executorStrategy
import fjs.control.parallel.Strategy.parMap
import fjs.control.parallel.Promise._
import fjs.control.parallel.Actor._
import Integer.parseInt
import List.range
import java.util.concurrent.Executors.newFixedThreadPool
import fjs.F._
import fjs.F2._
import fjs.P1._
import fjs.P2._
import fjs.data.List._
import fjs.control.parallel.Strategy.ListPar

object Fibs {
  val CUTOFF = 35;

  def main(args: Array[String]) = {
    if (args.length < 1)
      error("This program takes an argument: number_of_threads")

    val threads = parseInt(args(0))
    val pool = newFixedThreadPool(threads)
    implicit def s[A] = executorStrategy[A](pool)

    // This actor performs output and detects the termination condition.
    val out: Actor[List[Int]] = actor{
      ns =>
        for ((n, i) <- ns.zipWithIndex) printf("n=%d => %d\n", i, n)
        pool.shutdown()
    }

    // A parallel recursive Fibonacci function
    def fib(n: Int): Promise[Int] = {
      if (n < CUTOFF) promise(() => seqFib(n))
      else fib(n - 1).bind(fib(n - 2), curry((_: Int) + (_: Int)))
    }

    println("Calculating Fibonacci sequence in parallel...")
    out ! sequence(parMap[Int, Promise[Int], List](fib, range(0, 46)));
  }

  // The sequential version of the recursive Fibonacci function
  def seqFib(n: Int): Int = if (n < 2) n else seqFib(n - 1) + seqFib(n - 2);
}

Here’s an example run of this program using a pool of 10 threads. It runs about 7 times faster that way than with just 1 thread on my 8-way machine. The Scala version is also very slightly faster for some reason.

$ scala -classpath .:../../../build/classes/src concurrent.Fibs 10
Calculating Fibonacci sequence in parallel...
n=0 => 0
n=1 => 1
n=2 => 1
n=3 => 2
n=4 => 3
n=5 => 5
n=6 => 8
n=7 => 13
n=8 => 21
n=9 => 34
n=10 => 55
n=11 => 89
n=12 => 144
n=13 => 233
n=14 => 377
n=15 => 610
n=16 => 987
n=17 => 1597
n=18 => 2584
n=19 => 4181
n=20 => 6765
n=21 => 10946
n=22 => 17711
n=23 => 28657
n=24 => 46368
n=25 => 75025
n=26 => 121393
n=27 => 196418
n=28 => 317811
n=29 => 514229
n=30 => 832040
n=31 => 1346269
n=32 => 2178309
n=33 => 3524578
n=34 => 5702887
n=35 => 9227465
n=36 => 14930352
n=37 => 24157817
n=38 => 39088169
n=39 => 63245986
n=40 => 102334155
n=41 => 165580141
n=42 => 267914296
n=43 => 433494437
n=44 => 701408733
n=45 => 1134903170

Massive win! If we had been using Future instead of Promise, we would have needed at least 55 threads (since we’re using a cutoff at 35 and 45 – 35 = 10 and fib(10) = 55). Heck, we could even remove the threshold value altogether and calculate all 45 parallel fibs, in parallel. That would require 1,134,903,170 threads in the absence of non-blocking concurrency abstractions like Promise and Actor. We can run that in just one thread if we’d like.

Higher-Order Java Parallelism, Part 2: Parallel List Transformations

With a Callable monad and Parallel Strategies in hand, we’re ready to construct some general-purpose parallel functions of a higher order.

Something we’ll want to do quite often in parallel programming is run a function over a whole list of values, in parallel. So often, in fact, that it would be very tedious and repetitive to write a loop every time we want to do this, sparking off threads for each function call, and collecting the results. Instead, what we’re going to develop next is a kind of parallel list functor. That is, a higher-order function that will turn any function into a function that operates on every element of a list simultaneously.

First, let’s get some terminology out of the way, since I’ve been accused of not defining my terms.

A higher-order function is simply a function that takes a function as an argument.

A functor is any type T for which there exists a higher-order function, call it fmap, that transforms a function of type F<A,B> into a function F<T<A>,T<B>>. This fmap function must also obey the laws of identity and composition such that the following expressions return true for all x, p, and q:

  fmap(identity()).f(x) == x
  fmap(compose(p, q)).f(x) == fmap(p).f(fmap(q).f(x))

Here, identity is a first-class function of type F<A,A> that just returns its argument, and compose is function composition. Composition is defined to mean that compose(p, q).f(x) is the same as p.f(q.f(x)).

For example, Functional Java’s List class is a functor, because it comes equipped with a method List<B> map(F<A,B> f) which obeys the laws above. The implementation of List’s map method is trivial: It iterates over the list, calling the given function for each element, and returns the list of the results.

There’s a lot of information about functors and monads on the Internet, and I’ve written about them before, with examples in Java. Tony Morris also wrote a great post where he explains functors as “function application in an environment”. That’s a good way of looking at things.

I also want to make it clear, if you’re just now tuning in, that I’m using classes from Functional Java in the code examples, in addition to classes from the J2SE concurrency library. Basically only Callable and Future are from the J2SE library. Strategy, List, and the Callables utility class are from Functional Java. The code used here is from the latest trunk head revision of that library and may differ from the current official release.

Now, let’s get to the money.

Mapping Over a List in Parallel

We’re going to make a very similar kind of thing to a list functor, except it’s going to map a function over a list in parallel. Our parallel list transformation will take the form of a static method called parMap. It will take any existing function and turn it into a parallel function on lists. That is, if we already have written a function that takes an Integer and returns a String, we can pass that function to parMap, and it will return us a function that takes a list of Integers and returns a list of Strings. This means that nothing has to be rewritten or refactored to support the mapping of a function over a list in parallel. The parMap function will convert our existing code to parallel code, at runtime.

Here’s parMap:

  public <B> F<List<B>, Callable<List<A>>> parMap(final F<B, A> f) {
    return new F<List<B>, Callable<List<A>>>() {
      public Callable<List<A>> f(final List<B> as) {
        return sequence(as.map(compose(par(), callable(f))));
      }
    };
  }

That’s a lot of power for so little code. Let’s read through what it does. It takes a function f and returns a new function that takes a list called as. This new function transforms f with Callables.callable to wrap its return type in a callable (or: callable(f) applies the Kleisli arrow for Callables to f), and composes that with a function called par(). It then maps the resulting composition over the list as, which will result in a list of Callables, which we turn into a Callable of a List with the sequence function. The only new thing here is par(), which is a very simple instance method on Strategy:

  public F<Callable<A>, Callable<A>> par() {
    return compose(Strategy.<A>obtain(), f());
  }

So par() is just the Strategy’s function composed with the obtain() method that we created in Part 1. This turns the Future back into a Callable so that we can manipulate it in a lazy manner. This little guy is the meat of parMap. That is, parMap is basically just mapping par() over a list.

The result of parMap(myFun).f(myList), then, is a Callable of a list that, when called, will give us the results of calling myFun on every element of myList in parallel. What’s more, it will work for any kind of parallelisation Strategy, and it will return immediately (remember, Callable is lazy), ready for us to make further calculations on the results even while those results are being calculated.

I think that’s pretty cool.

Nested Parallelism

Sometimes the problem at hand is not quite so flat that it can be solved with just a map over a list. You might have a need for nested traversal of lists, where for every element in a list you traverse another list. We can model that behaviour with a higher-order function very similar to parMap, except that it takes a function that generates a list. This higher-order function is parFlatMap:

  public static <A, B> Callable<List<B>> parFlatMap(final Strategy<List<B>> s,
                                                    final F<A, List<B>> f,
                                                    final List<A> as) {
    return fmap(List.<B>join_()).f(s.parMap(f).f(as));
  }

In this definition, fmap is from the Callable monad, as described in Part 1. Notice that parFlatMap provides an example use of parMap, using it to turn the given function into a parallel function. The call to parMap with that function will actually yield a Callable<List<List<B>>> (can you see why?), so we use a final join lifted into the Callable environment with fmap, to turn the List of Lists into just a List.

The parFlatMap function is analogous to a parallel list monad, and it works very much like a parallel version of nested loops. For example, given a list of Points pts, a distance function dist that takes two Points and returns the distance between them, and a Strategy<Double> s, we can use parFlatMap to calculate the distance between every Point and every other, in parallel:

  Callable<List<Double>> distances = parFlatMap(s, new F<Point, List<Double>>() {
    public List<Double> f(final Point p) {
      return pts.map(dist.f(p));
    }
  }, pts);

The inner “loop” is represented by List.map, so we’re traversing the list serially, multiplying every element in parallel with each element in sequence. I.e. the outer loop is parallel and the inner loop is serial. It’s quite possible to replace map with parMap, and I’ll leave that as an exercise for the reader (hint: you will need both fmap and join). Note that the call to parFlatMap will return immediately, and the computation will be carried out in the background.

Position-Wise Parallelism and Concurrent Folding

Another function I want to talk about is the parZipWith function. By contrast to parFlatMap, it is like a parallel version of a single loop over two lists. Values from each list are taken at matching positions and the pairs are fed through the argument function all at the same time:

  public static <A, B, C> F2<List<A>, List<B>, Callable<List<C>>> parZipWith(final Strategy<C> s,
                                                                             final F2<A, B, C> f) {
    return new F2<List<A>, List<B>, Callable<List<C>>>() {
      public Callable<List<C>> f(final List<A> as, final List<B> bs) {
        return sequence(as.zipWith(bs, compose(Callables.<B, C>arrow(), curry(f))).map(s.par()));
      }
    };
  }

You will note that parZipWith simply uses zipWith from Functional Java’s List class. There’s some manouvering required to turn the argument function into the right form. The curry method turns the F2<A,B,C> into the equivalent F<A,F<B,C>> (sometimes called a Curried function). The arrow function is the first-class Kleisli arrow for Callables. That just means that composing it with f yields a version of f which returns a Callable.

Let’s take an example of using parZipWith to do useful work. If we had a list of Points representing a path, and we wanted to get the total length of the path, we could zip the list and its tail (every element except the first) with the dist function and take the sum of the results:

  Double length = parZipWith(s, dist).f(pts, pts.tail()).call().foldLeft(curry(sum), 0);

For brevity’s sake, I’m pretending that there’s already a function called sum, which is just an F2<Double, Double, Double> that returns the sum of its two arguments. If foldLeft is something new to you, then have a look at one implementation of it. It’s a more general abstraction of a for-loop than map() is. Folding a list {1,2,3} with the sum function (and 0) can be thought of as replacing all the commas with plusses to yield [0+1+2+3]. We could have just as well iterated over the list, adding each value to a total, instead of using a foldLeft function. But we didn’t, for a reason that will become apparent presently.

There’s something about the above example that’s dissatisfying. We’re getting the distances in parallel, but then call() sticks out like a sore thumb. The computation will block until the list of distances is ready, then it will fold the list with the sum function. What’s worse, call() might throw an Exception. There’s a way we can avoid all that by traversing the list of distances while they’re being calculated. What we need to do is somehow lift the foldLeft function into the Callable environment. The call to foldLeft above turns a List<Double> into a Double. What we want is to avoid the call to call(), and turn our Callable<List<Double>> into a Callable<Double> directly.

This is really easy to do, and it’s a good thing we’re using a folding function rather than a for-loop. Here’s what we do:

  Callable<List<Double>> edges = parZipWith(s, dist).f(pts, pts.tail());
  Callable<Double> length = par(fmap(List.<B, B>foldLeft().f(curry(sum)).f(0)).f(edges));

There. No exceptions, and no waiting for results. This code will return immediately and perform the whole computation in the background. The part that calculates the edge lengths is the same as before, and we’re keeping that in a variable edges for clarity. The other line may require some explanation. We’re getting a first-class foldLeft function from the List class, partially applying it to yield a function that folds a List<Double> into a Double. Then we’re promoting it with fmap into the Callable monad. The promoted function then gets applied to edges, and finally the whole fold is evaluated concurrently by passing it to par.

Hopefully you can see what an immensely powerful tool for parallel programming functional style and higher-order functions are, even in Java. We were able to develop a couple of one-liners above that are terser, clearer, more maintainable, more re-usable (and more type-safe) than anything we could write in imperative object-oriented style using producer/consumer, factories, inversion of control, etc. There’s no secret sauce, no special syntax, no functional fairy dust. It’s just plain old Java with a handful of very useful interfaces.

In the third installment of this series, we will develop a tiny light-weight library for threadless Actors that can juggle millions of simultaneous computations in only a few threads. Stay close.

Note: The code herein is adapted from a Haskell library by Phil Trinder, Hans-Wolfgang Loidl, Kevin Hammond et al.

Higher-Order Java Parallelism, Part 1: Parallel Strategies and the Callable Monad

Now that even budget desktop and laptop computers are shipping with multi-core processors, it’s more important than ever to design programs so that they can take advantage of parallel processing. If you’re already writing software in Erlang or Parallel Haskell, then lucky you. But if you’re writing in Java (and are unable or unwilling to take up Scala), you will need to get organized.

Since Java 5, the JDK comes with a concurrency library that makes concurrent programming a lot easier than it used to be, and the library has been improved further in Java 6. This provides some basic abstractions that take care of the nitty-gritty of thread management for us. In this short series of articles, I’m going to show how we can build on top of that library to achieve concurrent programming of a higher order. We will employ some design patterns and simple abstract building blocks from functional programming. This style of writing concurrent programs will afford us the ability to:

  • Compose ordinary functions into concurrent programs.
  • Decouple parallel behavior from the algorithm itself.
  • Turn existing code into parallel code, without refactoring, at runtime.
  • Work with hypothetical results of concurrent computations, before they finish.

We will not use any locking or explicit synchronization. Basic familiarity with the java.util.concurrent package is assumed but not required. Familiarity with generics is highly recommended, and I recommend reading parts 1 and 2 of my Lazy Error Handling series as it explains some preliminaries. Most of the source code herein is already part of the Functional Java library, and I’ll use a fair bit of interfaces and classes from it, which I’ll introduce as we go along.

When we’re through, I will have demonstrated that a functional style of programming promotes code-reuse and modularity of parallel programs, above and beyond what can be achieved with the canonical object-orientated style.

The Callable Monad

The Callable interface is new in Java 5. It’s similar to the old Runnable interface that we all know and love, except that its call() method returns a result, and it may throw an Exception. If you followed my Lazy Error Handling articles, you will immediately notice that Callable is nearly identical to the Thrower interface described in that series, and you’ll know that it is indeed a potential monad. Treating Callable as a monad will allow us to work with it at a higher level of abstraction, letting us compose Callables, chain them, and project computations into them.

As you may already know, we need three ingredients (and only these three) to have a monad:

  1. Type construction. This comes free with the Callable interface, since it takes a type parameter (i.e. it’s generic).
  2. A unit function. This allows us to turn any value into a Callable that returns that value again.
  3. A binding function. This allows us to chain together Callables with functions, without actually calling them.

Here is the unit function for Callable (we will refer to it as unit in the text to avoid ambiguity):

  public static <A> Callable<A> callable(final A a) {
    return new Callable<A>() {
      public A call() {
        return a;
      }
    };
  }

And here is its binding function:

  public static <A, B> Callable<B> bind(final Callable<A> a, final F<A, Callable<B>> f) {
    return new Callable<B>() {
      public B call() throws Exception {
        return f.f(a.call()).call();
      }
    };
  }

Note: The F interface is from Functional Java. It represents a first-class function (a function that can be treated like any other value). F<A, B> has one method that takes an argument of type A and returns a value of type B.

Given the above two methods, Callable is now a monad. All monads are also functors, so we can define a Callable functor. What I mean by “functor” is that we can define a method to turn any existing function into a function on Callables, or, in other words, to apply any function to a value wrapped in a Callable, without actually calling it (i.e. lazily). This method is called fmap, and we can define it in terms of bind:

  public static <A, B> F<Callable<A>, Callable<B>> fmap(final F<A, B> f) {
    return new F<Callable<A>, Callable<B>>() {
      public Callable<B> f(final Callable<A> a) {
        return bind(a, new F<A, Callable<B>>() {
          public Callable<B> f(final A ab) {
            return new Callable<B>() {
              public B call() {
                return f.f(ab);
              }
            };
          }
        });
      }
    };
  }

Useful operations on Callables, that the methods above allow us to implement, include sequence—which is a method of turning a list of Callables into a single Callable that returns a list—and join, which peels one layer of Callables from a Callable<Callable<A>> so that it becomes just Callable<A>. You will find the source code for those as part of Functional Java.

Parallel Strategies

When working with the java.util.concurrent library, you normally don’t work with Threads directly. You might instead implement Callable<A> and submit instances of your implementation to an ExecutorService, which yields values of type Future<A> which represents a running computation that yields an A. Future has a method called get() that returns the result as soon as it’s ready. This is a great improvement over managing threads and Runnables ourselves, but it still ties our hands somewhat to the ExecutorService, and encourages tight coupling of our code to the parallelisation library.

Inspired by Haskell’s “Parallel Strategies”, let’s instead work with parallelisation in the abstract. For what is ExecutorService, really? It’s a method of turning Callables into Futures. That means it’s a kind of function, so we can abstract from it, using a function type: F<Callable<A>, Future<A>>. Such a function can then be backed by an ExecutorService, or by something else entirely, such as a load-balancing facility that serializes Callables to be executed on remote servers.

We will use a new class, Strategy<A>, that allows us to effectively separate parallelism from the algorithm itself:

  public final class Strategy<A> {

    private F<Callable<A>, Future<A>> f;

    private Strategy(final F<Callable<A>, Future<A>> f) {
      this.f = f;
    }

    public F<Callable<A>, Future<A>> f() {
      return f;
    }

    public static <A> Strategy<A> strategy(final F<Callable<A>, Future<A>> f) {
      return new Strategy<A>(f);
    }

  }

We’ll add a couple of static functions to create simple strategies:

  public static <A> Strategy<A> simpleThreadStrategy() {
    return strategy(new F<Callable<A>, Future<A>>() {
      public Future<A> f(final Callable<A> p) {
        final FutureTask<A> t = new FutureTask<A>(p);
        new Thread(t).start();
        return t;
      }
    });
  }

  public static <A> Strategy<A> executorStrategy(final ExecutorService s) {
    return strategy(new F<Callable<A>, Future<A>>() {
      public Future<A> f(final Callable<A> p) {
        return s.submit(p);
      }
    });
  }

One of the neat things that working with Strategies as functions allows us to do is use the Callable monad to compose them with existing functions. Any function can be lifted into the Callable monad using fmap, and then composed with a Strategy to yield a concurrent function. Moreover, we can use Strategies to convert existing functions to concurrent functions. The following method on Strategy will take any function and return the equivalent function that executes concurrently. Calling such a function will give you a Future value from which you can get the computed result whenever it’s ready.

  public <B> F<B, Future<A>> lift(final F<B, A> f) {
    final Strategy<A> self = this;
    return new F<B, Future<A>>() {
      public Future<A> f(final B b) {
        return self.f().f(new Callable<A>() {
          public A call() {
            return f.f(b);
          }
        });
      }
    };
  }

Alert readers will note that lift represents the Kleisli arrow for the Future monad. As for most monads, this arrow is a very useful kind of thing (see Lazy Error Handling, Part 2). In the Future monad, the Kleisli arrow provides parallel function application. If you already have a function f, then calling lift(f).f(x) will apply that function to x while simultaneously continuing with the next statement in the current program.

Lazy Futures

For functions involving Futures, we generally always want to have the Future type in the codomain (on the right-hand side, in the return type). If you think about it, you’ll see that functions that take Futures in their arguments won’t be able to do much without blocking on Future.get(). However, that doesn’t mean we can’t compose Future-valued functions together. It just means that we can only compose two of them together in such a way that we either wait for the first Future to obtain a value before firing off the second one, or we have to spark a new thread that does nothing but wait on the first Future. We’re much better off composing Callables and then turning those into Futures as needed. In fact, we might want to wrap values of type Future<A> inside of a Callable<A> again so that we can manipulate their return values while they are running:

  public static <A> Callable<A> obtain(final Future<A> x) {
    return new Callable<A>() {
      public A call() throws Exception {
        return x.get();
      }
    };
  }

And this takes us full circle back into the Callable monad, where we can compose computations, bind them to functions and map functions over them, all lazily. Which means: without actually asking what their values are until we absolutely need to know.

So we have accomplished what we set out to do in this first part of the series. We’ve written a Callable monad that lets us compose existing code into concurrent programs. We’ve implemented parallel strategies to run those programs in parallel, without regard to the actual parallelisation implementation. We have a Kleisli arrow that lets us run ordinary functions concurrently with each other, and finally we have a way of taking concurrently running computations back into the Callable monad. Not bad for a day’s work.

In the next part of this series, we will employ what we’ve built here to develop some higher-order parallel functions, including a parallel list functor. I hope you join me.

Lazy Error Handling in Java, Part 3: Throwing Away Throws

In parts 1 and 2, I covered how we could create first-class functions in Java that declare, in their types, the exceptions they might throw. I talked about exploiting a functor to lift any existing function so that it carries exception information with it, and how to compose functions of that kind by using a monad. In this third and last installment, we’re going to fully abandon checked exceptions and embrace the functional style of handling errors.

First, let’s examine what exceptions really are. During the evaluation of some expression (some function), unexpected conditions or data are encountered, with which it is undefined how to proceed. That is to say, for some inputs, the result of the computation is undefined. For example, when a parseInt function encounters a character that isn’t a digit (or a minus sign), what do we do? Well, we don’t know exactly, so we need some way to indicate failure. It would be invalid to return an integer. One could return null, but that isn’t exactly reliable, nor correct, and well, it would be lying since the type signature promises an integer.

So far, I’ve shown how we can use a Thrower monad to indicate that a computation can error. But the Thrower monad doesn’t do anything except wrap Java’s existing exception handling with a datastructure. And what do you think Java’s existing error handling is? It’s a monad. No, really, it is. In fact, Java is one big monad with bells on.

Note that throws changes the type of a method so that it may throw exceptions. Sound familiar? That’s what Thrower does (see part 1). Java’s throws keyword is the Kleisli arrow (see part 2) for Java’s exceptions functor. Binding is done with a combination of try and a Java keyword called “;” which I’m sure you use all the time without even batting an eye. You can then think of catch as a function that takes a monadic value and “extracts” from it, performing case analysis on the result.

Why did we need Thrower then? The difference is that throws needs to be hard-coded at method definition time, while our Kleisli arrow, which we called Partial, transforms function values “at runtime”.

Returning Errors

We now find that we can take this idea further. We don’t actually need the throws monad at all, and hence, we don’t need Thrower either. Don’t get me wrong. I like the Trower monad. I use the Thrower monad in production. But let’s explore what we can do to approach a more functional style of error handling, just for grins.

Instead of throwing Exceptions, we can just collapse error types into the return type. We’ll use a monad called Either, which looks very similar to Thrower except that errors are returned, not thrown. The Functional Java library luckily has Either already defined:


  public abstract class Either<A, B>

Either is the disjoint union of two types. A value of type Either<A, B> simply wraps a value of either type A or type B. The Either class comes with two static data constructors:


  public static <A, B> Either<A, B> left(final A a)

  public static <A, B> Either<A, B> right(final B b)

We’ll use the standard convention that left values represent failure, and that right values represent success.

Let’s see how we might use this data type for error handling. It’s really quite straightforward. The following declares the return type of parseInt to be either an Exception or an Integer (the left value can actually be any type, but… baby steps).


  public Either<Exception, Integer> parseInt(String s);

Oh, but wait. We’ve lost the laziness. Functional Java’s Either, by itself, is not lazy like Thrower is. If we do want laziness, we have to wrap the computation in a closure. For example, we can use fj.P1, which is just a generic interface with one method _1() which takes no arguments.


  public P1<Either<Exception, Integer>> parseInt(String s);

That’s better. Raising errors is done by returning a left value:


  return new P1<Either<Exception, Integer>>() {
    public Either<Exception, Integer> _1() {
      return Either.left(new Exception("You broke it!"));
    }
  };  

Sometimes you’re able to call functions that might fail, recovering with a default value:


  P1<Either<Exception, Integer>> a = parseInt(s);
  int addFive = (a._1().isLeft() ? 0 : a._1().right().value()) + 5;

Other times, you will be catching exceptions thrown by other people’s code and converting them to Either:


  public static P1<Either<Exception, Double>> divide(double x, double y) {
    return new P1<Either<Exception, Double>>() {
      public Either<Exception, Double> _1()
        try {
          return Either.right(x / y);
        } catch (Exception e) {
          return Either.left(e);
        }
      }
    };
  }

An error is sent to the caller simply by returning it. In the example below, the parse errors are explicitly caught and re-raised, while any errors raised by the divide method are implicitly returned.


  public static P1<Either<Exception, Double>> parseAndDivide(String sx, String sy) {
    final P1<Either<Exception, Integer>> x, y;
    x = parseInt(sx); y = parseInt(sy);
    return new P1<Either<Exception, Double>>() {
      public Either<Exception, Double> _1() {
        if (x.isLeft() || y.isLeft()) {
          return Either.left(x.isLeft() ? x.left().value() : y.left().value());
        }
        return divide(x.right().value(), y.right().value());
      }
    };
  }

Either is a monad, so we can lift existing functions into it, compose Eithers, sequence them, just like we did with Throwers. Here I’m taking an existing sine function and reusing it for values of type Either<Exception, Double>:


  F<Double, Double> sin = new F<Double, Double>() {
    public Double f(final Double a) {
      return Math.sin(a);
    };}

  P1<Either<Exception, Double>> z =
    divide(x, y).map(Either.rightMap_().f(sin));

If you need to work with more than one kind of error at a time, you can. Simply nest them on the right, like so: Either<E1, Either<E2, A>>. This is something we could not do with Thrower.

Nothing to Declare

Now, we’ve been returning Exceptions, but what does an Exception give you, really? You get some information about the failure, like an Exception type name, an error message, a stack trace, and possibly a nested Exception. If you know how to recover from an error, are you going to need the stack trace and the error message? No. You don’t actually have to return Exceptions to indicate errors if you don’t want to. You could just as well return String, Integer, fj.Unit, or your favourite data structure. Or you could return… Nothing.

There’s a simpler monad than Either which is often used in functional programming. It’s called Option (sometimes known as Maybe). An example is Functional Java’s fj.data.Option class, which I’ll demonstrate briefly here. Option<A> is a lot like a List<A> that can either be empty, or contain a single value of type A. For example:


  public static Option<Double> divide(double x, double y) {
    if (y == 0) {
      return Option.none();
    }
    return Option.some(x / y);
  }

This is similar to returning null on failure, except that callers won’t be surprised if the method fails to return a value. It’s declared in the method signature, after all. Option.none() has the correct type and will respond to methods declared on the Option class. If you want a lazy Option, simply wrap it in a P1 like we did with Either.

Not surprisingly, Option comes equipped with monadic methods like fmap (or simply “map”) to lift an F<A,B> to an F<Option<A>, Option<B>>, “bind” to chain Option-valued functions together, and “join” to collapse an Option<Option<A>> into an Option<A>. Option’s unit function is the static method Option.some. The instance method some() returns the value in the Option, if any. This last one is the Option equivalent to Thrower.extract().

So, now that we’re using Option and Either to indicate recoverable errors, what about unrecoverable errors? Those are the kinds of errors that we’re not going to catch, nor expect any reasonable application to catch. They should result in immediate and visible failure. For example, we might decide that it’s not reasonable to recover from a critical function if it returns nothing:


  Option<MyAppConfig> config = getAppConfig();
  if (config.isNone()) {
    throw new Error("No configuration!");
  } else {
    // Do stuff with config here.
  }

At this point, we have completely obviated Java’s checked exceptions mechanism. Recoverable errors are simply returned, and unrecoverable errors are thrown all the way out. We can now construct computations, and even if they might fail we can pass them around, compose them together, extract values from them, etc. All without a throws keyword in sight. The circle is complete.

That’s the end of Lazy Error Handling in Java. We’ve gone everywhere from throwing exceptions lazily, to higher-order chaining and manipulation of exception-throwing computations, to doing away with checked exceptions altogether. I hope you have found this short series educational and as fun to read as it was to write.

END

Lazy Error Handling in Java, Part 2: Thrower is a Monad

In Part 1, we talked about the Thrower interface, and how we could use it to separate error handling from the code that produces those errors. We also saw how we could exploit generics to create a functor that can promote an existing function to a function that can handle and throw errors.

In this post, we’ll see that the greatest benefit of Thrower is the ability to compose and sequence computations; even computations that may fail, all the while staying type-safe. We’ll introduce some new functions which allow us to perform a kind of Thrower arithmetic that in turn will let us manipulate values tucked away in Throwers, without ever having to extract from them, and without any exceptions being thrown or caught.

The ingredients we need are exactly the ingredients needed for a monad. That is: A type construction, a unit function, and a binding operation. The first ingredient, type construction, we already have. The Thrower interface is generic, so it lets us create a type Thrower<A, E> for any type A, given some Throwable type E.

The unit function is simple enough. It just creates a new Thrower that completely preserves the value that we put in it:

  
  public static <A, E extends Throwable> Thrower<A, E> unit(final A a) {
    return new Thrower<A, E>() {
      public A extract() {
        return a;
      }
    };
  }

The final ingredient for our Thrower monad is the bind function. It takes a Thrower and feeds its result to a function that returns another Thrower:

  
  public static <A, B, E extends Throwable> Thrower<B, E>
  bind(final Thrower<A, E> a, final F<A, Thrower<B, E>> f) {
    return new Thrower<B, E>() {
      public B extract() throws E {
        return f.f(a.extract()).extract();
      }
    };
  }

Check what this actually does. It creates a new Thrower, whose extract() method calls the extract() method on the first Thrower and applies the function f to the result. Nothing actually happens when we call bind, except that a new future call to the provided function is created. So we’re applying f to the contents of the Thrower a, but not suffering any consequences until later, whenever we decide to call extract() on the result of bind.

Note that we can only compose, in this manner, Throwers that throw the same Throwable type. To combine Throwers of different kinds of exceptions, you would need to return a Thrower<Thrower<A,E1>,E2>>, or something like a Thrower2<B,E1,E2> which can throw either E1 or E2. You cannot create a new generic Throwable like MyException<E1, E2> as the disjoint union of two Throwables, since subclasses of Throwable are not allowed to be generic due to Java’s runtime type erasure. Normally, I don’t care about the types of exceptions to that level of detail anyway, so if I need to work with different species of them, I just use the Exception type. That’s exactly what we’ll do in the example further down.

Now, notice the second argument to bind:

          
  final F<A, Thrower<B, E>> f

This is a pretty useful kind of thing. It’s a function that takes an A and either returns a B or throws an E. So it’s kind of like a Thrower that takes an argument. It’s actually a Kleisli Arrow for the Thrower monad. This is something we’ll need often, so let’s make them easy for ourselves to create:

  
  public abstract class Partial<A, B, E extends Throwable> implements F<A, Thrower<B, E>> {

  protected abstract B run(final A a) throws E;

    public final Thrower<B, E> f(final A a) {
      final Partial<A, B, E> self = this;
      return new Thrower<B, E>() {
        public B extract() throws E {
          return self.run(a);
        }
      };
    }
  }
   

It’s called Partial because it models a partial function, a function whose result is undefined for some values (i.e. it might throw an exception instead of returning a value). We’ve abstracted away all the Thrower stuff (it’s always going to work the same anyway), so concrete subclasses will only have to override the run method and do what a partial function would: turn an A into a B or throw an E.

It might seem that this has taken us full circle, that this was all an exercise in futility if we’re back to just writing methods that throw exceptions. But no, what we have so far actually gives us a lot of power under the hood.

For the token contrived example, let’s say that you have an abstract class which models an action to get some object from the network given a URLConnection, possibly throwing a network error:

    
  public abstract class NetTalker<A> extends Partial<URLConnection, A, Exception> {}

Even though this class has no body, its intent is very clear. Users of our API will just have to to override run to do something useful with a connection. But NetTalkers just use connections; the construction of URLConnections will be implementation-specific. We’ll use another class:

  
  public abstract class URLConnector extends Partial<URL, URLConnection, Exception> {}

Where concrete subclasses create different concrete URLConnections. To get an A from a URL, given some URLConnector c (that knows how to make HttpURLConnections) and some NetTalker n, we can do the following:

          
  Thrower<A, Exception> t = bind(c.f("http://foo.bar"), n);

Again, this doesn’t give you the object of type A, it merely gives you a Thrower which either returns the A or throws an exception. It’s lazy. You can take t and bind it to a Partial that takes an A and, say, writes it to a file, again returning a lazy Thrower. Then, when something calls extract() on it, the whole enchilada of operations will be executed in one go.

Or, if you have a whole list of Throwers, you could turn them into a Thrower that returns a list:

  

  public static <A, E extends Throwable> Thrower<List<A>, E> sequence(final List<Thrower<A, E>> ts)
  {
    return ts.foldRight(Throwers.<List<A>, E> unit(List.<A>nil()),
      Throwers.<A, List<A>, List<A>, E> liftM2(List.<A> cons()));
  }

The above collapses an entire list of throwers into a single thrower that returns all their results in one list. Here, List is a fj.data.List from Functional Java, not java.util.List, although this can be made to work quite easily with the Java Collections Framework by defining nil(), cons(), and foldRight(). liftM2 is almost exactly like fmap from Part 1, except that it lifts functions of arity-2.

We’ve only had a slight taste of what we can do with monads, even in Java, and there are relationships between fmap, bind, and unit that are worth understanding in detail. As you can see, it’s a powerful abstraction that can be applied to a wide variety of problems. It doesn’t stop with Throwers. Notice that NetTalker is also a generic type, with a single type parameter. Yes, it too is a functor. It too can be a monad, and can be composed as we did with Throwers. In fact, here’s fmap for NetTalker:

 
  public static <A,B> F<NetTalker<A>, NetTalker<B>>
    fmap(final F<A,B> f) {
      return new F<NetTalker<A>, NetTalker<B>>() {
        public NetTalker<B> f(final NetTalker<A> a) {
          return new NetTalker<B>() {
            public B run(URLConnection u) throws Exception {
              return f.f(a.f(u));
            }
          };
        }
      };
    }

I wonder what other types are monadic.

Unfortunately, you’ll find that you can’t write a generic Monad class in Java. Poor Java’s type system is not sophisticated enough to understand higher-kinded types, nor would that be sane without type inference in the compiler, which Java also lacks. You will have to write bind and unit for every kind of monad that you need, as well as all operations based on them (fmap, sequence, etc.), or dispense with the type system (in which case you may as well be writing Ruby), or switch to Scala.

I hope you enjoyed this little journey through monads and exceptions in Java. In Part 3 of this series, we will look at how we can remove try, catch, and throws entirely from our code, in favor of unit, bind, fmap, and join.

Lazy Error Handling in Java, Part 1: The Thrower Functor

How many try/catch blocks have you written in your day? Hundreds? Thousands? How many of the catch blocks look exactly the same? Is try/catch synonymous with copy/paste? Well, you may have written your last catch block. Follow me.

Let’s say that you’re coding in Java, and you want to call some code that might throw Exceptions, but you don’t want to be bothered with catching or throwing those exceptions in your code. Or you may want to call some existing code that doesn’t handle exceptions, passing it something that has methods which may throw exceptions. This can get ugly really fast, and you may end up with “throws Exception” declarations in places where you don’t want them, or try/catch blocks where you’re not sure whether to log the error or throw an unchecked exception, or what.

But, despair not. From very simple ingredients, we can conjure up powerful functional-style error handling to save the day. The first ingredient is a generic interface that declares, in its type expression, the exception thrown by its method:


  public interface Thrower<A, E extends Throwable>
   {public A extract() throws E;}
 

What we’re saying here is that there’s some operation preformed by extract() that returns an A and might throw an E. But the operation won’t take place (and won’t throw anything) until extract() is actually called.

What is such a thing useful for? Well, you could implement this interface, take parameters in a constructor, and perform some calculation in extract(). For example, reading a file and possibly throwing an IOException. But that’s a naive view of what generic interfaces are for. Thrower has higher aspirations than that. It’s not just an interface. It’s a functor. Observe:

  
  public static <A,B,E extends Throwable> F<Thrower<A,E>, Thrower<B,E>> fmap
    (final F<A,B> f)
    {return new F<Thrower<A,E>, Thrower<B,E>>()
      {public Thrower<B, E> f(final Thrower<A, E> a)
        {return new Thrower<B,E>()
          {public B extract() throws E
            {return f.f(a.extract());}};}};}
 

OK, so this is a static method on which class? It doesn’t matter, let’s say we put it in a utility class called Throwers (remembering to make it final and its constructor private). Just look at the type signature for now. The interface F<A,B> is from Functional Java, and it’s just an interface with one method B f(A a). So what fmap does is take a function from A to B, and return a function from Thrower<A,E> to Thrower<B,E>. In other words: fmap promotes the function f so that it works with computation that may throw checked errors, without f having been written to handle errors.

The implementation should be self-explanatory, albeit verbose (this is Java, after all). We construct an anonymous function to return, implementing its only method, which returns a new thrower which in turn yields the result of applying the function f to the contents extracted from the original thrower. It sounds a lot more complicated than it looks, so just read the code. All we’re doing is taking the A from a Thrower, turning it into a B, and wrapping that in another Thrower. If taking the A from the Thrower fails with an exception, we’ll carry that exception into the new Thrower.

The important thing to note here is that nothing actually happens until you call extract() on the resulting Thrower. Values of types F and Thrower are data structures that represent a computation to be carried out in the future. Anybody can pass Throwers around, but only a try/catch block, or a method that throws a Throwable of the right type may actually call extract() on it to run its computation and get its value. Java’s type system ensures that you can’t go wrong (although, as for unchecked exceptions, you’re on your own).

A simple example is in order. Just to illustrate the point, not to do anything very useful. This program reuses a function designed to operate on strings, so that it operates on operations that result in strings but might throw exceptions. The exception handling is done somewhere else, in ErrorHandler, outside of the main program, in an error handling library function called extractFrom, which we assume knows the right thing to do. Note that the main program has no try/catch block at all.

  
  public class Foo
   {public static void main (String[] args)
     {Thrower<String,IOException> readLn = new Thrower<String,IOException>()
       {public String extract() throws IOException
         {return new BufferedReader(new InputStreamReader(System.in)).readLine();}};
      System.out.println(ErrorHandler.extractFrom(Throwers.fmap(length).f(readLn)));}

    // A first-class function to get a String's length.
    public static F<String,Integer> length = new F<String,Integer>()
     {public Integer f(final String s)
       {return s.length();}};}
 

That’s right. You don’t have to handle exceptions at all in your code, even though you’re performing actions that throw exceptions. You just pass the buck to somebody who knows how to handle exceptions. It’s like outsourcing without the funny accents. OK, so you’re not really performing any IO actions, at least not syntactically speaking. ErrorHandler is doing that for you as well, since it’s the one calling extract() on the Thrower. This doesn’t make a difference to the compiled program except that the execution stack (and hence the stack trace, should things go terribly wrong) will look a bit different. If this makes you uncomfortable, here’s your hat and there’s the door. If you’ve ever used “Inversion of Control”, then this should be nothing new. In fact, in real life, you may want to inject something like ErrorHandler as a dependency, using Guice, or Spring, or something similar.

So there you go. That’s lazy error handling in Java, in a nutshell. But there’s more to come, as Thrower has higher aspirations still. It’s not just a functor. It’s a monad. We’ll talk about that in the next post.