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.