Wednesday, February 19, 2014

When OO and FP meet: returning the same type

In the left corner, we have Functional Programming. FP says, "Classes shall be immutable!"

In the right corner, we have Object-Oriented programming. It says, "Classes shall be extendable!"

The battlefield: define a method on the abstract class such that, when you call it, you get the same concrete class back. In Scala.

Here comes the sample problem --

We have some insurance policies, auto policies and home policies. On any policy, you can adjust by a discount and receive a policy of the same type. Here is the test:

case class Discount(name: String)

  def test() {
    def adjust[P <: Policy](d: Discount, p: P): P = p.adjustBy(d)
    val p = new AutoPolicy
    val d = Discount("good driver")
    val adjustedP: AutoPolicy = adjust(d, p)
    println("if that compiles, we're good")

OO says, no problem!

abstract class Policy {
   protected def changeCost(d: Discount)

   def adjustBy(d: Discount) : this.type = {
       return this

class AutoPolicy extends Policy {
  protected def changeCost(d: Discount) { /* MUTATE */ }

FP punches OO in the head and says, "Mutation is not allowed! We must return a new version of the policy and leave the old one be!"[1] The easiest way is to move the adjust method into an ordinary function, with a type parameter:

object Policy {
   def adjust[<: Policy](p: P, d: Discount): P = {
     case ap: AutoPolicy => new AutoPolicy
     ... all the other cases for all other policies ...

But no no no, we'd have to change this code (and every method like it) every time we add a Policy subclass. This puts us on the wrong side of the Expression Problem.[2]

If we step back from this fight, we can find a better way. Where we declare adjustBy, we have access to two types: the superclass (Policy) and this.type, which is the special-snowflake type of that particular instance. The type we're trying to return is somewhere in between:

How can we specify this intermediate type? It seems obvious to us as humans. "It's the class that extends Policy!" but an instance of AutoPolicy has any number of types -- it could include lots of traits. Somewhere we need to specify "This is the type it makes sense to return," and then in Policy say "adjustBy returns the type that makes sense." Abstract types do this cleanly:

abstract class Policy {
  type Self <: Policy
   protected def changeCost(d: Discount): Self

   def adjustBy(d: Discount) : Self = {

class AutoPolicy extends Policy {
  type Self = AutoPolicy
  protected def changeCost(d: Discount) = 
    { /* copy self */ new AutoPolicy }

I like this because it expresses cleanly "There will be a type, a subclass of this one, that methods can return."
There's one problem:

error: type mismatch;
 found   : p.Self
 required: P
           def adjust[P <: Policy](d: Discount, p:P):P = p.adjustBy(d)

The adjust method doesn't return P; it returns the inner type P#Self. You and I know that's the same as P, but the compiler doesn't. OO punches FP in the head!

Wheeeet! The Scala compiler steps in as the referee. Scala offers us a way to say to the compiler, "P#Self is the same as P." Check this version out:

def adjust[P <: Policy](d: Discount, p: P)
               (implicit ev: P#Self =:= P): P = p.adjustBy(d)

This says, "Look Scala, these two things are the same, see?" And Scala says, "Oh you're right, they are." The compiler comes up with the implicit value by itself.
The cool part is, if we define a new Policy poorly, we get a compile error:
class BadPolicy extends Policy {
  type Self = AutoPolicy
  protected def changeCost(d: Discount) = { new AutoPolicy }
adjust(d, new BadPolicy)
error: Cannot prove that FunctionalVersion.BadPolicy#Self =:= FunctionalVersion.BadPolicy.
           adjust(d, new BadPolicy)

Yeah, bad Policy, bad.

This method isn't quite ideal, but it's close. The positive is: the abstract type is expressive of the intent. The negative is: any function that wants to work polymorphically with Policy subtypes must require the implicit evidence. If you don't like this, there's an alternative using type parameters, called F-bounded polymorphism. It's not quite as ugly as that sounds.

Scala is a language of many options. Something as tricky as combining OO and FP certainly demands it. See the footnotes for further discussion on this particular game.

The referee declares that FP can have its immutability, OO can have its extension. A few function declarations suffer, but only a little.

[1] FP prefers to simply return a Policy from adjustBy; all instances of an ADT have the same interface, so why not return the supertype? But we're not playing the Algebraic Data Type game. OO insists that AutoPolicy has additional methods (like penalizeForTicket) that we might call after adjustBy. The game is to combine immutability with extendible superclasses, and Scala is playing this game.
[2] The solution to the expression problem here -- if we want to be able to add both functions and new subclasses -- is typeclasses. I was totally gonna go there, until I found this solution. For the case where we don't plan to add functions, only subclasses, abstract types are easier.

More references:
F-bounded type polymorphism ("Give Up Now")
MyType problem
Abstract self types

Wednesday, February 5, 2014

Property-based testing of higher-order functions

Property-based testing and functional programming are friends, because they're both motivated by Reasoning About Code. Functional programming is about keeping your functions data-in, data-out so that you can reason about them. Property-based testing is about expressing the conclusions of that reasoning as properties, then showing that they're (probably) true by testing them with hundreds of different input values.

Person: "By my powers of reasoning, I can tell that this code will always produce an output collection longer than the input collection."

Test: "For any generated collection listypoo, this function will return a collection of size > listypoo.size."

Testing Framework: "I will generate 100 different collections, throw them at that test, and try to make it fail."

Property-based testing gets tricky when I try to combine it with another aspect of functional programming: higher-order functions. If the function under test accepts a function as a parameter, how do I generate that? If it returns a function, how do I validate it's the right one?

In the trivial case, we pass in the identity function or a constant function, and base our expectations on that. But that violates the spirit of generative testing.

Test operate on values. Values go in, values go out and we can check those. Functions are tested by operating on values. So to test functions that operate on functions, we need to generate functions that operate on values, and generate values to test the functions that came out of the function under test. Then we'll need to state properties in terms of values going in and out of functions going in and out... ack! It's Higher-Order-Property-Based Testing.
<self: insert drawing>

My sources on twitter tell me that QuickCheck for Erlang and Haskell have generators for functions. Looking at this sample of the Haskell one, I think this is what it does:

Each generated function from A => B includes a random factor that's constant to the function, and a generator for B that can create Bs based on a seed. When an A is passed in, it's combined with the function's random factor to prod the generator into creating a deterministically-random B.

So, we can create random functions A=>B if we have a generator of B, a random-factor-generator, and some mapping from (A, random-factor) to the seed for the generator of B. That doesn't sound so bad.
<self: this could use a drawing too>

There are two other functionalities in good generators. When a test fails, we need enough information to figure out why and fix the bug. One tool for this is shrinking: make the generated input simpler and simpler until the test doesn't fail anymore, and then report the simplest failing case. I haven't even started thinking about that in function-generation. (Does Haskell or Erlang do it?)
The second tool for fixing failed tests is simpler: print out the input that revealed the bug. That's also hard with generated functions. Since the generated functions described above are random mappings from input to output, printing the actual input-output mapping used in the failing property evaluation should be sufficient. This is implemented in Haskell, with no state, so it must be possible in Scala and Erlang. And it's in F#.

Like everything in property-based testing, generic input generation is the easy part (even when it isn't easy). Describing properties expected of output functions based on input functions - now that sounds hard. When I write a test that does it, that'll be worth another post.

Thanks to @reiddraper, @ericnormand, @silentbicycle, @natpryce, @deech, @kot_2010 and everyone who chimed in. Please continue.

Monday, February 3, 2014

Abstractions over Threads in Java and Scala

TL;DR In Java, get a library that makes Futures work like Scala's, and then never use ExecutorService directly.

In the beginning, there were Threads. And Java threads were nice and simple. That is, Java threads are simple like some assembly languages are simple: there's only a few things you can do.

Since then, Java and then Scala have created higher-level abstractions. These are what you want to use. This post explains the differences between them, and what happens when exceptions are thrown.

Java's Executor, introduced in Java 5, implements thread pooling for you. The only method on an Executor is execute(Runnable). That's simple too! Give it something to do, and it eventually does it. If an exception trickles up, it goes to the thread's UncaughtExceptionHandler, which typically prints the stack trace to System.err.

All the implementations provided in Executors also implement ExecutorService, a more extensive interface. Pass the submit() method a Callable or a Runnable, and get back a java.util.concurrent.Future. Please note that Java's Future is limited. You can't ask it to do anything on completion or failure. You can pretty much only call get(), which blocks until your task is complete, then returns its result or throws its exception.[1]

If you submitted a task for its side effects, and you never call get() on the Java Future, then no one will ever know about any Exception it throws. It never makes it to the Thread's UncaughtExceptionHandler, and it never gets output. To get an ExecutorService that never hides exceptions, extend ThreadPoolExecutor, override afterExecute and guarantee that get() is called. What a pain!

Now I'll switch over to Scala-land, because it has something to tell us about Java Futures.

Scala's ExecutionContext interface (trait) extends Executor, providing that execute() method. You'll probably never use this directly, but you'll need one to work with Scala Futures. There are two good ways to get it. First, use the default; it's good. Second, if you want your own thread pool, the factory ExecutionContext.fromExecutorService creates a thin wrapper that delegates to your carefully chosen ExecutorService.

To start an asynchronous task in Scala, call

val doStuff = Future { /* do stuff */ } (executionContext)

This will execute the stuff on that executionContext[2], and give you a reference that's useful.

When you make a Java Future by submitting on an ExecutorService, you have to pass in the whole sequence of code that you want executed. All the error handling has to be there. When you want to do something after that asynchronous code completes, there's nothing to do but block until it completes.

Scala Futures remove that restriction. You can start something going, then add error handling by calling onFailure.[3] You can extend the asynchronous work with onSuccess. You can even say, "after these three Futures complete, then do this other thing with all three results." This lets you separate deciding what needs to happen in what order from defining each thing that needs to happen. Yay separation of concerns! I like how this style of programming lets me code the interesting bits first and then fill in the rest.

All these Future-extending and Future-combining services create asynchronous computations of their own, and want an ExecutionContext. This does not have to be the same one the Future is running on. Once a Future is constructed, it does not remember the ExecutionContext.

A task tacked on to another Future will automatically run when it can. Failures will be handled, successes will proceed. This means you aren't required to ask a Scala Future for its result. It's possible to do so (and I often do in test code), but discouraged. If you want to do something with the value, use onSuccess. You never have to block a thread!

We can work this way in Java too. In Java 8 there's native support. Earlier, we can use alternative futures provided in libraries such as Guava. Use this to define asynchronous tasks in smaller, more flexible bits.

This culminates a series of posts on choosing the right ExecutorService. See also Pool-Induced DeadlockForkJoinPool, and Scala's global ExecutionContext.

For Scala developers:
[3] I said that Scala futures let you handle errors with onFailure. This isn't true for what Scala considers Fatal errors; these remain uncaught. They propagate to the UncaughtExceptionHandler, which prints to stdout, and that's it. The thread dies. Your onComplete, onFailure, onSuccess methods, they're never called. Silent death. If you Await its result, the Await will timeout. Very bad! In the Scala source as of this writing, this happens only for very serious errors: VirtualMachineError, ThreadDeath, InterruptedException, LinkageError, ControlThrowable. However, in Scala 2.10.x, NotImplementedError is "fatal". When I left a method as ???, the thread disappeared and my program hung. That took forever to debug.

One alternative is to use scalaz.

The scalaz library provides its own Future. The scalaz.concurrent.Future wants an ExecutorService. (This means you can't use the global ExecutionContext.) Some important differences:
* scalaz defaults the implicit ExecutorService parameter to one with a FixedThreadPool. Because you aren't required to supply one at all, you don't always realize you're using that default.
* Because scalaz calls submit() on the ExecutorService, uncaught exceptions do not hit the UncaughtExceptionHandler and are never printed. Do not use scalaz's Future directly: use Task instead, which wraps everything in a try {} catch {}.
* In the standard constructor of Task {...} (and Future { ... }), the work is not submitted immediately. It is submitted on a call to run or attemptRun.
* Also if you use this standard constructor, then every time you run a Task, the work will be repeated. This is not true of Scala's future; those will run exactly once.

Hopefully, once you choose a good abstraction, you won't have to think about this stuff ever again.

[1] You can also cancel a Java Future, if you care about that.
[2] If it's the global, it'll sneakily fork a ForkJoinTask.
[3] is in the "For Scala developers" bit above
[4] The behavior of the UncaughtExceptionHandler can be configured on Threads created in a ThreadFactory that you supply to an ExecutorService of your own construction that you then wrap in an ExecutionContext. And good luck figuring out anything more useful than printing them.

ForkJoinPool: the Other ExecutorService

In Java, an ExecutorService manages a pool of threads that can run tasks. Most ExecutorServices treat all tasks the same. Somebody hands it something to do, the ExecutorService parcels it out to a thread, the thread runs it. Next!

A ForkJoinPool is an ExecutorService that recognizes explicit dependencies between tasks. It is designed for the kind of computation that wants to run in parallel, and then maybe more parallel, and then some of those can run in parallel too. Results of the parallel computations are then combined, so it's like the threads want to split off and then regroup.

Maybe it's a computation like, "What's the shortest path of followers from me to @richhickey?" or "What is the total size of all files in all directories?" or "What's the most relevant ad to display to this customer?" where we don't know what all we're going to have to execute until we're in the middle of executing it.

On an ordinary ExecutorService, when we split a computation up, each task goes its separate way. Each one is allocated to a thread individually. This becomes a problem when the tasks are small, and the overhead of allocating them to threads takes longer than running them. It becomes a bigger problem when threads split off tasks and wait for all the results to come back to combine them: pretty soon so many threads are waiting that there are no more threads to do the work. This can reach deadlock.

ForkJoinPool embraces many small computations that spawn off and then come back together. It says, "When my thread wants to split its work into many small computations, it shall create them, and then start working on them. If another thread wants to come along and help, great."
A computation in a ForkJoinPool is like a mother who told all her children to clean the house. While she's waiting for them to finish their level on the video game she starts picking up. Eventually some kids get up and start helping. When Evelyn starts sweeping and isn't done by the time Linda has finished the bathroom, then Linda picks up a broom and helps. Eventually the mother takes stock and says, "Hurray! The house is clean."

That's a completely unrealistic scenario in my household, but ForkJoinPools are more disciplined than my children. They support unpredictable parallel computation, preventing pool-induced deadlock, and minimize the work of switching back and forth between threads on the CPU.

What's not to love? Well, a ForkJoinPool is harder to use than a regular old ExecutorService. It's more complicated than calling "submit." External threads submit jobs to a ForkJoinPool in an ordinary way, but within the pool, tasks are created differently. ForkJoinTask subclasses get constructed, forked off for execution, and then joined. It's custom handling, and that requires planning ahead, and that means you have to guess that ForkJoinPool is the solution before you start coding. Or retrofit it later.

Scala does something clever to hide the difference between ForkJoinPools and regular ExecutorServices, so that its Futures work this way by default. Akka uses ForkJoinPools behind the scenes for its actor messaging. Clojure uses ForkJoinPools in its collection processing with Reducers. In Scala and Clojure, you can get these optimizations without extra headache. The abstractions, they keep getting deeper!

Doug Lea wrote ForkJoin for Java and Scala.

Sunday, February 2, 2014

Scala: the global ExecutionContext makes your life easier

TL;DR - when in doubt, stick with

When you want to run some asynchronous code, choosing a thread pool isn't any fun. Scala has your back, with its global ExecutionContext.

When I try to put some code in a Future without specifying where to run it, Scala tells me what to do:

scala> Future(println("Do something slow"))
<console>:14: error: Cannot find an implicit ExecutionContext, either require one yourself or import
There are some good reasons to use that recommended ExecutionContext. It tries to do things right in several ways. See below for how you can help it along.

The global ExecutionContext has an objective of keeping your CPU busy while limiting time spent context switching between threads. To do this, it starts up a ForkJoinPool[3] whose desired degree of parallelism is the number of CPUs.[1]

ForkJoinPool is particularly smart, able to run small computations with less overhead. It's more work for its users, who must implement each computation inside a ForkJoinTask. Scala's global ExecutionContext takes this burden from you: any task submitted to the global context from within the global context is quietly wrapped in a ForkJoinTask.

But wait, there's more! We also get special handling for blocking tasks. Scala's Futures resist supplying their values unless you pass them to Await.result(). That's because Future knows that its result may not be available yet, so this is a blocking call. The Await object wraps the access in scala.concurrent.blocking { ... }, which passes the code on to BlockingContext.

The BlockingContext object says, "Hey, current Thread, do you have anything special to do before I start this slow thing?" and the special thread created inside the global ExecutionContext says, "Why yes! I'm going to tell the ForkJoinPool about this."

The thread's block context defers to the managedBlock method in ForkJoinPool, which activates the ForkJoinPool's powers of compensation. ForkJoinPool is trying to keep the CPU busy by keeping degree-of-parallelism threads computing all the time. When informed that one of those threads is about to block, it compensates by starting an additional thread. This way, while your thread is sitting around, a CPU doesn't have to. As a bonus, this prevents pool-induced deadlock.

In this way, Scala's Futures and its global ExecutionContext work together to keep your computer humming without going Thread-wild. You can invoke the same magic yourself by wrapping any Thread-hanging code in blocking { ... }.[2]

All this makes an excellent general-purpose ExecutionContext.

When should you not use it? When you're writing an asynchronous library, or when you know you're going to do a lot of blocking, declare your own thread pool. Leave the global one for everyone else.

Also, on mobile: Daniel Solano-G√≥mez reports: On startup, the global execution context "has to read its configuration.  In many apps, that’s probably fine, but in an Android app it becomes a problem.  I was trying to use Futures to avoid doing I/O on the main thread, so it was a little bit of a surprise that doing that caused I/O on the main thread.... In the end, I just created my own based on an executor service."

[1] You can alter this: set scala.concurrent.context.numThreads to a hard number or to a multiple, such as "x2" for double your CPUs. The documentation is the source code.
[2] Here's some code that illustrates using blocking { ... } to get the global ExecutionContext to start extra threads.
[3] Scala has its own ForkJoinPool implementation, because Java doesn't get it until 7, and Scala runs on Java 6 or higher.