F%$*ing Lambdas, How Do They Work?

Update: A friend was reading over this and noted that I should have linked to my two previous posts on Project Lambda, to provide more context:

• First impressions of Project Lambda
• Adding methods (and lazy transformation/traversal) to collections with Project Lambda

On my Twitter feed, I recently got a link to this document by Brian Goetz explaining how JDK8 translates lambdas into bytecode. I was surprised, since I had assumed that lambdas were simply syntactic sugar for anonymous inner classes that implement one of the functional interfaces, much as anonymous functions in Scala currently work. That is, I thought that Project Lambda was basically doing the same thing as I've been doing with my functional types, but eliminating the annoying boilerplate that goes along with an anonymous class and using better type inference.

It turns out that it's considerably more interesting than that, and makes use of the InvokeDynamic bytecode instruction added in JDK7. It inspired me to dig a little deeper with javap and try writing up an explanation in simpler terms (and only covering the simple case), since that article is pretty heavy (though I have to admit that I spent a solid hour on a Saturday night going through it with glee — I'll claim that my standards for a fun Saturday night have lowered considerably with a small child at home, rather than admitting that I'm a huge nerd).

How don't lambdas work?

I think it's clearer to understand how lambdas work by first considering how they don't work. That is, they're not just a more succinct way of writing anonymous inner classes.

Throughout the rest of this post, I'll use the following example:

While only a few lines in total, this example could desugar to something a fair bit messier. It's useful to note that our simple lambda is capturing the variable i from its scope.

Suppose lambdas were simply a nicer way to write anonymous classes. The above example would be equivalent to:

If you've ever looked at the output directory from compiling code with anonymous functions, you would notice that the above code would compile to AnonymousFunction.class and AnonymousFunction$1.class. If we run javap AnonymousFunction\$1.class (escaping the $ so the shell doesn't think I'm referencing a variable), we get the following output:

So, we have a class that holds the variable i as a field (passed to the constructor), and two versions of the apply method, with and without type erasure. (The Object version just casts its input to an Integer and invokes the Integer version.)

More explicitly, anonymous functions are also a kind of syntactic sugar. In effect, AnonymousFunction.java compiles down to something like the following:

The output of running javap AnonymousFunction\$1.class looks nearly identical (save the One vs. 1 difference) to javap InnerClassFunction\$One.class.

So, how do lambdas actually work?

It's worth noting that the contents of my compiled output directory (with file sizes) are as follows:

Interesting... no secondary classes are produced by compiling the original SimpleLambda code. So, how does it work?

The code of the lambda is moved to a private static method called (in my case) lambda$6, that takes n and i as parameters and does the addition. That's the easy part. What does main actually compile to? Let's ask javap (using the -v flag):

I think of this bytecode as divided into three parts:

1. Bytecode lines (distinct from GitHub gist lines) 0 through 6 take care of assigning local variable i and putting it on the stack.
2. Lines 7, 8, and 13 load i from the stack, do an invokedynamic to actually create the Function, then push it onto the stack.
3. Lines 14 through 27 take care of retrieving the constant System.out, loading the Function from the stack, boxing 5 into an Integer, calling our Function.apply method, and calling println.

We're most interested in line 8, which triggers the creation of the Function. Let's see what #3 points to (near the top of the javap output):

#3 = InvokeDynamic #0:#40 // #0:lambda$:(Ljava/lang/Integer;)Ljava/util/function/Function;

So, it's pointing to #0 with the expectation of a CallSite that takes an Integer and returns a Function (effectively a Function factory). Let's look at #0:

This is basically binding the last three arguments for a call to LambdaMetaFactory.metaFactory (samMethod, implMethod, and instantiatedMethodType) to our desired "single abstract method" (#37 Function.apply), the implementation method (#38, the previously-mentioned private static lambda$6), and the type arguments for the Function.apply method (#39 — it takes an Integer (within parentheses) and returns an Integer (outside the parentheses)). The first three arguments are supplied by the invokedynamic call itself. (I believe arguments 2 and 3 are lambda$ and (Ljava/lang/Integer;)Ljava/util/function/Function are bound by #3, above).

Right now, if I look at the code for LambdaMetaFactory.metaFactory, it's basically constructing a new InnerClassLambdaMetafactory and asking it to generate a CallSite. So, at runtime, we're generating an inner class that implements Function<Integer, Integer>, takes an Integer as a constructor parameter, and implements apply by calling lambda$6 with its field and the argument to apply.

Let's confirm this by creating a class that outputs this stuff at runtime:

And here is the output from running that:

In this case, our static method got called lambda$0, but you can see that it's called from the apply method of an inner class that holds an Integer field, which it probably received through its constructor (since it's a final field). Effectively, at runtime, we're getting the behaviour from InnerClassFunction.java from above (except that the actual code makes one more method call to the static method), which in turn is the same as AnonymousFunction.java, which is not what lambdas become. The one "major" difference is that the generate class doesn't implement the Integer version of apply, sticking purely to the erased version (which makes sense, since the checked cast is already required before calling lambda$0).

Wait... what?

In a very roundabout way, I hope that I've shown you that lambdas are not equivalent to anonymous classes (which are equivalent to inner classes that capture local variables via constructor arguments), but they are actually equivalent at runtime... for now. The truth is that this somewhat convoluted invokedynamic approach leaves things open for improvements in the future.

The current implementation of Project Lambda (at the time of writing) does, in fact, generate inner classes at runtime. However, by using the invokedynamic call to LambdaMetadataFactory, future runtimes will be able to provide a different implementation that may have better performance, and still work with code compiled now (or at least after JDK8 eventually ships). As a secondary bonus, by not performing this expansion at compile time, compile time should be shorter and the generated bytecode will be smaller. (Even with this trivial example, SimpleLambda compiled to 20% less bytecode than InnerClassFunction. I believe the difference would be more significant with more lambdas.)

Conclusions

I hope that this post has made you think more about how lambdas will work, along with how anonymous classes and inner classes already work.

It's worth noting that Scala currently compiles functions to inner classes, though there has been some discussion about using the invokedynamic approach there as well.

More fun with Project Lambda

What's new in Project Lambda this week?

It seems that the Project Lambda developers have conspired to ensure that my blog will always be out of date. I recently wrote about my first impressions from using Project Lambda, based on build b74. Now that I'm writing this, b75 is out and they've renamed the Block, IntBlock, DoubleBlock, and various BiBlock interfaces to replace the word Block with Consumer. I suppose that's more consistent with Supplier, since a Consumer consumes a value and returns nothing, while a Supplier takes no input and produces something. It also ties in well with the pipeline metaphor they're using for Streams (which will still need to wait for a later post, since I got playing with default methods in interfaces this week).

Additionally, they've added several more interfaces to java.util.function to accommodate Functions and BiFunctions that return primitive values (still to avoid the overhead of boxing, presumably). It's interesting to compare these specialized (and specially-named) interfaces to Scala's use of the @specialized annotation (discussed, here, for example) to avoid the same problem.

Pimping Collections

I'm horribly abusing a term that has grown popular in the Scala community for the case where you appear to add functionality to an existing type by providing an implicit view that converts objects of the existing type to objects of the enhanced type. This is referred to as the pimp my library pattern (going back several years, including by Prof. Odersky here). What I'm doing here isn't implicit, but it does show a way that we can use interfaces with default methods to layer functionality onto library types with relatively little ceremony.

In some of my previous posts, (like this one and especially this one), I talked about some nice higher-order functions on collections that most functional programming language environments provide as part of their standard library. The fact is that most of these higher-order functions can be implemented in terms of iterating through elements. Since Java 1.5, the standard collections (except Map and its implementations) all implement the Iterable interface. Wouldn't it be great if we could add these higher-order functions as methods on existing collection types? We can't really do that (without compiling our own version of the standard library), but we can inject the iterator method from the builtin types as a lambda to construct a type that does have this functionality.

Yo dawg, I herd you like iterators

Let's extend the Iterable interface with an AugmentedIterable interface that defines additional functionality based on the iterator method:

As you can see, many of the methods return a new AugmentedIterable whose iterator method (defined by a lambda) delegates to the iterator method of the original AugmentedIterable. I put an iterator in your iterator, so you can iterate while you iterate.

Note that this implementation with delegated iterators has the side-effect of making most of these methods lazy (except toList and foldLeft, which don't produce new AugmentedIterables).

Let's add a quick utility method to construct an AugmentedIterable from an existing Iterable, and test our methods:

Conclusions

This still isn't quite as nice as the "pimp my library" pattern, as we still need either the explicit call to augment to convert our Collection into an AugmentedIterable. Furthermore, I didn't really need an interface with default methods to do this, as I believe I could have made AugmentedIterable an abstract class. Where things get interesting is that we could add more functionality derived from Iterable in another interface and then mix them together in a new interface that inherits from both. Alternatively, I could create new collection types that extend the built-in types but also add the AugmentedIterable behaviour:

Project Lambda - First Impressions

Before launching into the actual post, I would like to make a quick plug for Martin Odersky's "Functional Programming Principles in Scala" course on Coursera. It will begin March 25th and run for 7 weeks. I took the course during its previous run (September-November last year), and really enjoyed it. No prior knowledge of Scala is required. The material is well-presented and quite interesting. Sign up now!

Moving on to today's topic

I created an impromptu poll on Google+ to see what I should write about next, not really expecting any suggestions (especially since most of my Google+ friends only seem to check in roughly once per month or so). As it happens, I got a vote for Project Lambda, the upcoming support for functional programming features planned for JDK8. So, with that unanimous support, I downloaded a prerelease (b74) and started porting the functional programming framework I've been developing in earlier posts.

Mapping concepts

Taking a look at that new java.util.function package, you find a fair number of interfaces (I count 38 in b74), but they're mostly specializations of the following few core interfaces:

• Supplier: Declares a get() method that returns a value. Effectively interface-equivalent to Function0 from my previous posts. There are specialized versions (BooleanSupplier, DoubleSupplier, IntSupplier, LongSupplier, but no love for floats) to return unboxed primitive values.
• Function: Has an apply method that takes an input of type T and returns an output of type R. Analogous to Function1 from my previous posts. Has subinterface UnaryOperator (for functions where the return type is the same as the input type), and many primitive type specializations (to avoid boxing), including Predicate (for functions that return boolean), IntFunction, LongFunction, DoubleFunction, plus many combinations of single-input functions for different input/output types (where at least one is primitive).
• BiFunction: Analogous to the Function2 type I described in earlier posts, these take two arguments and return a value (where, in the most general case, each input and output type may be different). Has a subinterface BinaryOperator for the special case when all three types are the same, plus specialized versions of BinaryOperator for each of the primitive types.
• Block and BiBlock: Like Function and BiFunction, but covering the case where nothing is returned (so the code must produce a side-effect). I handled these cases in my previous post by using functions that return the empty tuple (Tuple0). Again, there are several specialized interfaces to handle primitive inputs to the block.

Lambda syntax

By far, the biggest change you'll find in JDK8 from Project Lambda is the new syntax added to make working with the above interfaces much less verbose. (My previous posts serve as an example of how ugly it can be to create anonymous classes to wrap up a little bit of logic in a function object.) Here is a "before and after" example, using an anonymous class versus the lambda syntax:

I think we can all agree that the second conveys just as much useful information without the noise of the anonymous class boilerplate. IntelliJ even gives me a warning, telling me that the first version can be replaced with a lambda. This syntax can be applied to any anonymous implementation of an interface where there's a single method to implement (which includes a number of AWT or Swing EventListeners, as well as Runnable and Callable). I would argue that the lambda syntax will be pretty useful even if you're not interested in functional programming.

Since many existing codebases probably have static utility methods that behave as functions, there is also syntax to use these methods as function objects:

Similarly, an instance method without arguments can implicitly be treated as a function where the instance is the input and the result of invoking the method on the instance is the output (note that IntFunction<String> takes a String as input and returns an int):

Default methods

If you paid close attention to my previous posts (or looked at the code in GitHub), you may have noticed that most of my function types were classes. This was because I wanted to be able to implement certain helper methods that would work if you provided the actual logic of a function. For example, Function1 has a compose method that would allow you to define composition of functions. Similarly, the function classes have the logic for partial application and currying.

This is kind of annoying, as you can only inherit from a single class, whereas you can implement multiple interfaces. It would be much nicer to be able to define some logic that comes "for free" once the method(s) of an interface are defined. In particular, this is how Scala's traits work (and was one of the features that made my Why I like Scala list). As it happens, this is another feature coming to Java with Project Lambda.

There is a new keyword, default, that can be added before an interface method that allows you to define a body for the method. From what I can tell, while this introduces some multiple inheritance of behaviour to Java, it still isn't quite as flexible as Scala's multiple inheritance of traits (which avoids the diamond problem by defining a linearization of inheritance). For example, the following doesn't compile for me:

The compiler error is

java: class DefaultTest.HelloWorld inherits unrelated defaults for print() from types DefaultTest.Hello and DefaultTest.World

That said, default methods still allow some rich inheritance of interfaces, and could be used to significantly improve the collections API (much as the use of traits has given Scala a much better collections API). Based on this FAQ answer, which refers to new interfaces java.util.Sized and java.util.Traversable, it looks like this cleanup was planned at some point, but those interfaces don't exist in the b74 build of Project Lambda. I don't know if they backtracked on improving collections, or if those changes are excluded from current builds.

New collection types

In a previous post, I covered the Option type (taking the name from Scala). As it happens, Project Lambda includes the java.util.Optional type, which covers pretty much the same niche.

They've also added a hefty java.util.stream package that handles lazily-evaluated sequences, complete with evaluation pipelines (designed to accommodate concurrent evaluation). I won't go into details on streams, for the following reasons:

• I want to discuss streams (as a type) in a later post, since they're pretty easy to implement.
• This post is already going to be too long, and streams would roughly double the length.
• I haven't had time to fully investigate pipelines, so anything I write wouldn't be doing them justice.

What's missing?

So far, Project Lambda doesn't seem to include helpers for partial application of functions, or lazy evaluation. Luckily, those are both pretty easy to implement, and the syntax is much nicer with the new syntax.

Lazy Evaluation

To implement lazy evaluation, let's revisit the Function0 idea, but this time, we'll make it an interface. Of course, interfaces still can't hold data, so we'll "remember" earlier evaluations using a static WeakHashMap (relying on identity equality) and take advantage of the hot new computeIfAbsent default method added to Map.

Next, let's create a Function1 that extends Function and adds the ability to take a Supplier (which may or may not be a Function0) as input to apply. This will allow us to eagerly evaluate a previous lazy result. Whereas previously, I made the return value always lazy (where you could then force evaluation with get()), the built-in Function interface we're extending performs eager evaluation. So, we'll expose lazy evaluation via the applyLazy methods. I'll use the T,R ordering of type arguments, since my earlier R,T ordering was silly and inconsistent with what everyone else does.

Partial Application

In my previous implementation, I had an abstract base class called Curryable which implemented partial application in terms of currying. Then, it was the responsibility of each FunctionN class to implement curry to produce a Function1 that binds the first argument and returns a FunctionN-1. Unfortunately, while writing this post, I discovered a fatal flaw in that implementation that actually invalidates one of my examples in my previous post. Specifically, that implementation of partial evaluation always evaluated the partial arguments eagerly, so one of the page downloads started in the middle of constructing the lazy result of the Function2. (In retrospect, I should have been suspicious when I found that my asynchronous implementation was consistently faster than my earlier concurrent implementation. Of course it was, it had already downloaded a page before the timer started.) We'll do partial application more directly this time, so that laziness works.

Anyway, let's define Function2 in terms of BiFunction, with the additional partial application methods. Function3 and up are analogous, but need to be defined from scratch, since there are no built-in interfaces for functions of more than two arguments.

Let's confirm that this works, and play some more with lambda syntax by implementing foldLeft as a static method, binding it to a function object (a Function3, specifically), and then using partial application to produce a Function1 that concatenates strings:

That's considerably easier than the hoops I jumped through to implement a higher-order version of foldLeft previously.

Conclusions

So far, Project Lambda looks like it could actually make functional programming much more viable on Java. While my examples here haven't done anything that I haven't been able to do with my existing toy framework, the syntax alone is a massive improvement. As an example of the impact of good syntax, I immediately spotted my mistake with my earlier Curryable implementation when I started to write it with lambdas. Previously, I had missed the mistake amidst all of the anonymous function boilerplate.

I'm still not convinced that it's on par with Scala, though, since it largely seems to be catching up to where Scala was a few years ago, and you're still stuck with the old "everything is mutable" collections framework. Various features of the Scala compiler (e.g. type inference, special handling of apply) allow you to write even less boilerplate than what you get with Project Lambda. Still, if Java developers get used to this stuff (and like it), it might make it easier to convince more of them to drop the uglier legacy parts of Java and move to Scala (which still keeps the good old JVM and JIT compiler).

That said, since I imagine that I'll be stuck mostly working in Java for the foreseeable future, I can only hope that JDK8 comes out soon, so I can use these goodies in my professional life.

Finally, remember that what I've covered here is only scratching the surface. This is what I've been able to pick up playing with Project Lambda in about a week, between when my daughter falls asleep and heading to bed myself. For more details, check out the Project Lambda homepage, and the resources linked from there.

Asynchronous Evaluation

As promised at the end of my previous post, I've added (what I think is) a fairly simple asynchronous execution structure.

It's worth noting that this post actually has nothing to do with functional programming (especially since I will be producing side-effects). It just happens that what I've written works because of lazy evaluation, which itself is not a functional programming concept, so much as something that just happens to come up in some functional programming environments (most notably Haskell). The beauty of programming without side-effects is that your logic remains the same, regardless of the actual evaluation semantics. In turn, this makes it easier to "make it work, make it right, make it fast". This post largely deals with the last part.

Adding callbacks to a concurrent evaluation

Originally, when I wrote this, I had planned to write an AsyncFunction0 class, which would decorate a Function0 with asynchronous callback evaluation, and still support Function0 semantics. Upon further thought, I figured it would be easier to keep the asynchronous evaluation behaviour totally separate. Instead, I opted to create an AsyncEvaluator class which would:

• be based on a Function0 and an Executor, and could be explicitly invoked to trigger evaluation of the result lazily defined by the Function0 on the Executor.
• be able to accept callbacks, which will be called (on the same thread as evaluation) once the Function0 has been evaluated.
• support convenient chaining of Function0 evaluations, so evaluation of one result could trigger evaluation of later results.

For callbacks, rather than defining a new type, we'll use a function that takes the result of evaluation as input, but it doesn't really make sense to return something -- to whom will we be returning it? Instead, the callback should "do" something. That is, it should have a side-effect. So, the callback should return void, or something to that effect. Since we already have tuples, we can depict the lack of a value by the empty tuple, or Tuple0. This is a singleton:

With that, we can move on to the core code of AsyncEvaluator:

This is simple enough, and still useful. You could write an asynchronous event handler that would respond to a UI event (like a button click) by creating a Function0 that returns a result, wrapping it in an AsyncEvaluator, and then adding a callback that writes the result to the UI. Before your event handler returns, it would call invoke to trigger the background processing.

Chaining function evaluations

Suppose you've written a nice, working program that runs well on a single thread, but you see various pieces that could run concurrently. Assuming you have lazy values representing certain "checkpoints" in the process, it would be nice to be able to say, "When result A has been calculated, start evaluating B and C (which depend on A), then when B finishes, kick off D. When C and D are both done, invoke E." We can do that, without changing any actual logic. Effectively, we just need to trigger evaluation of the Function0s based on the completed evaluation of earlier values.

First, we'll look at creating simple or branching chains. That is, from a single Function0 that has been wrapped in an AsyncEvaluator, we can trigger one or more later Function0 evaluations:

We may not want all evaluations to occur on the same Executor, so we allow an alternative Executor to be specified for the chained evaluation. If no Executor is specified, we'll use the same one used to evaluate the current result.

Here is a silly unit test that counts to ten asynchronously:

What if we have a value that is constructed based on multiple earlier asynchronously computed values? In that case, we want the new value to be computed as soon as the last of the previous values is available:

With that, we can write an asynchronous version of our example from the previous post, where we fetch two webpages and sum their byte counts:

As mentioned in the code comments, neither of these tests really reflects what you would actually want to do with an asynchronous execution path. In the real world, your final callback would push the result as a network response or output it to the user, such that you would never actually need to block while waiting for an answer.

Conclusion

Asynchronous processing is a pretty powerful tool, made quite popular (and certainly more familiar) thanks to AJAX calls from the browser. Now that many of us are comfortable with this approach, it's not a bad idea to add more asynchronous processing to our server-side or desktop software. In particular, while a blocked thread uses fewer resources than a busy-waiting thread (or a thread that periodically polls for a result), it's better to only use a thread when there's stuff to be done. In the second unit test example above, we still have two threads blocking on the HttpURLConnection responses. A better (more scalable) program would use Java NIO to fire off the requests and react to the responses asynchronously. Unfortunately, that's outside the scope of the current post.

Adding concurrency to our functional framework

In previous posts, I hinted that someday I would discuss concurrent evaluation of functions. That time has finally come. Also, I've made the switch to Java 1.7 at home, so don't be shocked by some of the syntax here (like multi-catch or try-with-resources).

First, let's acknowledge that Function0 is effectively a Callable with result caching. Let's make this explicit, by making Function0 implement Callable:

Using that, it's quite easy to dispatch evaluation of a Function0 to an ExecutorService using a helper class:

This is a pretty powerful (but simple) pattern, since a Function0 can be built up at runtime based on successive lazy applications of functions. (Effectively, the Function0 type is a form of thunk.) Once you have several work units of decent size, you can dispatch them to background threads for evaluation, and then pass the resulting Function0s (which are probably still running) to other lazy functions. Once you need a result (e.g. for output), you invoke get() and (if necessary), your thread will block until the required background tasks have finished.

Let's see this in action:

These test cases download the two previous posts on this blog, counts their bytes (using a foldLeft), and output the sum of the byte counts, along with the time taken to compute the result. The only difference is that testConcurrentPageDownload kicks off evaluation of the two calls to getPageBytes on an ExecutorService. On my computer, the serial test typically takes about 1100ms, while the concurrent test takes about 600ms, suggesting that it takes about 500ms to download each page (they're pretty similar in size) and 100ms to count the bytes (since we're not using a particularly efficient data structure).

That's probably enough for now. I've got some code written that extends Function0 to include asynchronous evaluation of callbacks when the result is ready. Unfortunately, I still haven't developed a good example that makes it look useful yet. Once that's ready, though, I'll write it up. Stay tuned.

What is Functional?

It occurred to me that in all of my writing about functional programming so far, I haven't really talked about the basic idea of what a function really is, at a fundamental level, and how this informs functional programming.

What is a function?

The idea of a function really comes from mathematics. It's just been implemented (in various ways) in computer languages since then. Essentially, a function is a transformation -- given an input value drawn from some set, it produces an output in some set (which could be the same as the input set, but in many useful cases, it's not).

In math, we usually write something like "Let f be a function ℝ ⟶ ℝ, given by f(x) = x." In this case, we're declaring the domain and codomain of the function as the set of real numbers, and then defining the "implementation" of the function.

To define a similar function in C, we could write:

double f(double x) { return x; }

Of course, this isn't exactly the same as the mathematical definition, since doubles can't represent all of the real numbers, but it is usually "close enough". That said, we've declared a domain (double) and a codomain (double), and defined the means by which values are transformed. Generalizing, we can say that types effectively describe sets. (On any actual computer (without infinite memory), types describe finite sets.)

At some point, math students become comfortable with functions over multidimensional sets. For example, the function to determine the magnitude of a 2d vector over the real numbers is f:ℝ × ℝ ⟶ ℝ given by f(x,y) = sqrt(x^2 + y^2), where the domain ℝ × ℝ denotes the Cartesian product between the real numbers and themselves. (Since the magnitude function only returns non-negative values, we could declare the codomain to be ℝ+ or some such notation. Usually, we'll just leave the more general codomain, despite the fact that the function only hits a subset of it. This is the difference between the codomain and image of the function.)

Similarly, in software, we have functions of multiple parameters. That magnitude function can be (approximately) defined in C as:

double magnitude(double x, double y) { return sqrt(x*x + y*y); }

Equivalently, we can consider the function as taking a single tuple (double, double).

One area where mathematics and imperative languages have diverged is in the ease of defining Cartesian product codomains. For example, we can define a function that reflects through the line y=x, as f: ℝ × ℝ ⟶ ℝ × ℝ, where f(x,y) = (y,x). To denote the two return values, we generally need to define a new type that has two fields (with each field representing an operand of the Cartesian product). Typically, this would be a struct in C, a record in Pascal, or a class in an object-oriented language. We can make this somewhat generic by defining a set of tuple typeclasses.

Composition

In math, functions can be composed. That is, given a function f: A ⟶ B and a function g: B ⟶ C, we can produce the composed function g ◦ f : A ⟶ C. In traditional imperative programming, we tend to do the equivalent by defining a new function that invokes f then passes the result as input to g, returning the result. Functional languages or libraries often have more convenient syntax for composing functions. (While I haven't included an example in my "Functional programming with examples in Java" series, it is not hard to add a "compose" method to Function1.)

Partial functions

Many functions that we encounter in programming aren't "true" functions, but rather partial functions. That is, they don't actually produce values over the full range of possible input. Instead, they may throw an exception, crash, or otherwise reject a value that is "acceptable" given the input type.

In mathematics, we usually deal with this by restricting the input domain to valid values. For example, the function f(x) = 1/x would have domain ℝ∖{0} -- that is, the real numbers, excluding zero. Unfortunately, in a statically-typed programming language, we don't have a type that represents the non-zero real numbers (at least in any language with which I'm familiar).

Another approach you sometimes see in math is to define a function piecewise, where you define a "total" function over a domain by specifying the existing partial function over the values for which it's valid, and then "something else" for the other values. In particular, we could augment the codomain to include a special "undefined" value, which could propagate through other functions that "accept" an undefined value. So, the function above becomes f: ℝ ⟶ ℝ ∪ {undefined} where f(x) = 1/x, if x ≠ 0, and undefined otherwise. Then, any function that composes with f needs to do something with the undefined value. We can accomplish roughly the same thing in programming by returning null (for non-primitive types), but we risk losing track of it. A better alternative is to use an option typeclass, since it provides a compile-time guarantee that composed functions expect an Option.

Functions in disguise

A number of data structures can also be thought of as functions. An array int[10] is effectively a function from the natural numbers between 0 and 9 to the set of integers. (Similarly, a List<T> is a partial function from the integers to T.) A Set<T> in Java can be thought of as function T ⟶ boolean, via the contains method. A Map<K,V> is a function K ⟶ V, where Java makes it a total function by returning null for missing keys, while Scala treats Maps as functions K ⟶ Option[V].

Independent evaluation and substitution

Mathematical functions can be evaluated in any order and can substitute their results arbitrarily. That is, if we know f(x) = 5, we can write 5 anywhere that we see f(x) and vice-versa. This is because mathematical functions are defined in terms of equivalences, independent of side-effects. Evaluating a mathematical function doesn't log output to a console, update some state, or strangle a kitten.

Unfortunately, the same cannot generally be said for functions in a programming context (especially if you're using the Apache Commons Kittenstrangler library). In particular, for a program to be useful, it must perform some I/O, which is inherently a side-effect. (Even the most mathematical program eventually needs to update state -- mutating a user who doesn't know the answer into one who does.)

Fortunately, we can isolate our "impure" side-effecting code from our "pure" functional code. In fact, this is generally how programs in Haskell are structured. They are spawned within the impure IO monad, and dive into the pure functional logic, only coming back up to the impure world to interact with the user.

That said, even the IO monad has a functional feel, if you twist your mind just right. The way I think of it is that your program takes "the world" as input. Your pure functional code is mapped over the IO monad and can be used to produce a "new world" as output. Thus, a "Hello, world" program in Haskell takes as input the universe and outputs a new, slightly different universe: one where "Hello, world" is written one more time on your screen.

Generally, you want to keep the impure part as small as possible. In traditionally imperative languages, we can theoretically structure our programs in a similar way -- writing side-effect-free functions wherever possible, and keeping side-effects within a specific layer. Unfortunately, most imperative languages also have standard libraries that encourage updating of mutable state.

What do we get as programmers for following a purely functional approach? Like mathematical functions, it is safe to evaluate pure functions in an arbitrary order, or even all at once. Effectively, we can have near-arbitrary concurrency of our functional code, which is quite useful in today's multi-core world.

Obviously, even with pure functional code, we need to be careful about how/when we parallelize, since the overhead of context-switching could quickly dominate the gains obtained by parallel evaluation. That is, we as developers still need to find appropriately-sized work units. That said, pure functional code can be parallelized without worrying about locking shared state. When you have mutable state, you need to worry about finding appropriately-sized work units as well as locking shared state. Picking the wrong work units leads to degraded performance. Making mistakes with locking can lead to degraded performance, deadlocks, or race conditions. Worst of all, deadlocks and race conditions often only show up under heavy load (which tend to involve production scenarios).

Conclusions

In this post, I've tried to make a more mathematical argument in favour of functional programming. Computer science is a comparatively young field of study. Unfortunately, it's also very useful. This has resulted in a lot of unproven (and unprovable) solutions running our world. As a step toward maturity and stability, I believe we would benefit from adhering to the boring, predictable logic of mathematics where possible, isolating those pieces that cannot be represented by pure functions.

While Haskell (more-or-less) enforces this separation between pure functions and side effects, we can move toward purity in traditionally imperative languages like C/C++, Java, Pascal, Objective C, and the .NET languages. It's largely just a matter of changing your coding style a bit. If you find that you're bumping against limits of the language to write elegant pure code (as in my previous blog posts, where there's a lot of boilerplate involved with making Java act functional, and I dropped purity in a few cases -- e.g. memoization and lazy evaluation), you could also try a hybrid OO/functional language like Scala, or a functional language that still gives you easy mutability and side-effects when needed, like F# or most Lisps. Additionally, Python and Ruby have some convenient functional constructs in their standard libraries/syntax. Finally, while the language itself can be pretty ugly, remember that Javascript is basically Lisp disguised as a C-family language.

Why I like Scala

In my past few blog posts (actually, almost all of my blog posts), I've been trying to present ways of implementing stuff built into Scala, using old-school Java syntax. I should probably explain some reasons why I think it makes more sense to just make the jump to Scala.

Type inference

Whenever you declare an object variable in Java, you tend to need to specify the type twice: once when declaring the compile-time type for the variable (the thing that goes to the left of the variable name) and once when specifying the object constructor (the thing that goes after new). Java has added some inference of generic type parameters in 1.7, so you can now write Map<String, Integer> myMap = new HashMap<>, but it's still a fair bit of code noise compared to Scala's var myMap = new HashMap[String, Int](). You still need to specify types on method/constructor parameters, of course, and you can explicitly specify types for variables when you want (e.g. when you're making a mistake and the type inferencer is being too helpful).

Some people unfamiliar with Scala see the type inference and assume that Scala is a dynamically typed language, since the conciseness of variable declarations looks more like Ruby, Python, or Javascript. Scala is statically typed, though. The compiler just looks at the type of the expression on the right side of the =, and maps the type to the left side (and will generate a compiler error right there if you've explicitly specified a type on the left side that is not satisfied by the type of the expression on the right). In my opinion, having the short, unobtrusive code typically associated with dynamic languages, but still keeping the compile-time type-safety (and IDE autocompletion) of a static language, is awesome.

Each line in this toy example that involves a variable declaration is shorter in Scala than in Java (even ignoring the semicolon inference). Plus, as described in the next section, to make it more fair, the first and fourth line in the Java example should have final prepended.

Immutability

While I've shown in a few posts that it's possible to implement immutable data structures in Java (and you can use the Functional Java library), it's not the same as having core library support. The Java Collections API has mutability built in from the ground up. Sure, you can use Collections.unmodifiable{Set,List,Map,Collection} to produce immutable collections, but then you're left with runtime exceptions if you do try modifying their contents, and no way to create a new collection based on a previous one (besides an O(n) copy to create a new collection, versus the O(1) prepend/tail of an immutable list or the O(log n) insert/delete of an immutable trie map/set). In my humble opinion, to push the unmodifiability constraint to compile time, it would have been ideal to split the collections interfaces, adding e.g. ReadableCollection, ReadableList, ReadableIterator, etc. making the existing interfaces extend the new "read-only" interfaces, adding the modification methods. That's not how they did it, though.

Furthermore, while in Java, it's a good idea to minimize mutability (it's even Item 15 in Effective Java), I personally spend a decent amount of time and screen real estate writing final everywhere. (It's largely become habit for me, so I'm not wasting brain cycles when typing final, but it's confusing for my colleagues who aren't familiar with seeing the final keyword.)

In Scala, immutability is the default for collections, and it takes the same number of characters to create an immutable variable as it does a mutable one: it's var for mutable and val for immutable. That's it.

Uniform access principle

Most Java (or C++) developers are taught early on to hide data in private fields, and provide public accessors and mutators. This has the advantage that you can someday add validation on the mutators, log use of the accessors, delegate to some proxy object, etc. Unfortunately, 90+% of the time, you're just providing get/set access to a field. Yes, for that 10%, the flexibility is crucial, but it leads to a ridiculous amount of code noise (made less painful for the initial developer by the fact that the "fix" has been to add "Generate getter/setter methods" functionality to IDEs -- unfortunately, that code noise is still present for anyone maintaining the codebase).

Languages like Ruby allow you to first write public fields, and later drop in custom accessors or mutators, without changing the calling code. The earliest language that I know of to provide this functionality was Delphi, with its notion of properties (which were later included in the initial version of C#, since Anders Hejlsberg designed both). In general, this ends up being a form of the uniform access principle.

Scala provides support for the uniform access principle with a simple, built-in compiler trick. Effectively, whenever you create a field that is visible outside the current object, the Scala compiler outputs bytecode for the field and accessor/mutator methods (excluding the mutator method if the field is a val).

Consider the following Scala code:

Compiling that and running it through javap -c -private UAPExample1, we get the following output:

public class UAP.UAPExample1 extends java.lang.Object implements scala.ScalaObject{
private java.lang.String name;

public java.lang.String name();
  Code:
   0: aload_0
   1: getfield #11; //Field name:Ljava/lang/String;
   4: areturn

public void name_$eq(java.lang.String);
  Code:
   0: aload_0
   1: aload_1
   2: putfield #11; //Field name:Ljava/lang/String;
   5: return

public UAP.UAPExample1();
  Code:
   0: aload_0
   1: invokespecial #19; //Method java/lang/Object."":()V
   4: aload_0
   5: ldc #21; //String Michael
   7: putfield #11; //Field name:Ljava/lang/String;
   10: return

}

Our public, mutable name field was pushed into a private field called name, and methods name() and name_$eq were created to provide an accessor and mutator. We can produce (more or less) the same bytecode, following the traditional Java bean pattern, as follows:

The only difference from the previous javap output is that the private field is called _name instead of name. Of course, this code is also doing the exact same thing as UAPExample1. Let's consider a more interesting case, where the accessor/mutator are doing something more complicated, like providing access to a value stored on disk:

This example is functionally equivalent to the first two, but keeps the values on disk. In particular, the following code exercises all three. The output from the first two examples is always "Michael" followed by "Blah". The third example will output "Michael" followed by "Blah" on the first run, but will output "Blah" followed by "Blah" on subsequent runs in the same working directory (since the previously set "Blah" value is still accessible):

Traits

Traits sit somewhere between Java's interfaces and abstract classes. In particular, traits can define methods, like abstract classes, but cannot take constructor parameters. Like interfaces, a class can implement multiple traits. Since you can define behaviour in traits, this gives you a form of mixin inheritance.

Since the JVM itself does not support multiple inheritance, this mixin behaviour is accomplished by linearizing the class hierarchy. That is, you can imagine that a linear class hierarchy has been created where each class has one parent (with one fewer trait mixed in). The implementation at the bytecode level doesn't exactly work that way, from what I can in the output from javap -- rather one class is created with delegates to static methods for the implemented trait methods (passing this to the static method).

Let's consider an example using traits. I'm going to create a base CSSStyle trait, which will have subtraits for various CSS attributes. Then, we'll have two classes -- one representing an HTML element with inline style, and the other representing a CSS style rule (as you would find in a stylesheet file or within a style element). We'll add CSS attributes to each of these classes by mixing them in to new anonymous classes.

The output from running RunCSSStyle.main is:

<span style="font-weight: bold; font-style: italic; font-family: Helvetica, Arial, sans-serif"></span>
.important {
    font-weight: bold;
    font-style: italic;
    font-family: Helvetica, Arial, sans-serif
}

More refined scoping

In my example on the uniform access principle, I made use of private[this], and also stuck some imports within a method declaration. Both of these are examples of Scala's tighter compile-time scoping.

Using private[this] specifies that the method or field can only be accessed by the current object -- other instances of the same class cannot access it. (If I had simply specified private, the compiler would have generated an accessor/mutator pair for use by other instances of the object, to be consistent with the UAP.)

Scoping imports within a method (or even a nested scope), allows you to clearly specify where you're using something. Compare that to the typical Java source file, where the IDE collapses your mountain of imports, so you're not overwhelmed.

Similarly, there are times in Java where you want to invoke the same chunk of code multiple times within a method (but not in a loop), or you just want to break a method apart into logical chunks that solve independent problems, specific to the current method. So, you create a private method scoped to the class, even though the new method is only used in that one statement. Scala, on the other hand, supports nested methods. Once it's compiled, the nested method is pushed up to the class scope (since the JVM doesn't support nested methods), but your code is organized in a cleaner way, and the compiler will prevent you from using the method outside of its scope.

Incidentally, Scala also supports import aliasing, for when you're going to be using conflicting imports within the same scope. I believe this was mostly done to avoid developer anger when trying to bridge between (e.g.) a java.util.List and a scala.collections.immutable.List. Having to fully qualify one or the other would bulk up your code. Instead, you can write:

import java.util.{List => JavaList}

Then, every time you say JavaList, the compiler knows that you mean java.util.List. Lacking this in Java bugs me regularly, since my job involves working with Lucene documents (org.apache.lucene.document.Document) and occasionally with XML DOM documents (org.w3c.dom.Document). On those rare occasions where I would like to use both in one file, only can can have the name Document. The other must be fully qualified. It would be so much nicer if I could import them as LuceneDocument and DOMDocument, regardless of what the third parties decided to call them.

Off-hand, I'm not sure why locally-scoped imports and import aliases haven't made it into Java yet. Looking at the output of javap, it looks like the bytecode doesn't actually contain imports. Instead, the bytecode references fully-qualified classes (that is, the imports are resolved statically). As a result, adding support for locally-scoped imports and import aliases would not break bytecode compatibility, and would give Java developers another (albeit minor) reason to like the language.

In my opinion, Scala's scoping rules are the logical next step to the scoping transition from C to C++, where C required that you list all of your local variables at the beginning of a function (and any for (i = 0; i < ...; i++) within the function was using the same i), but C++ allows you to declare variables in the scope in which they would be used (but ultimately compiles to pretty much the same machine code).

Functional Programming

Obviously, one of the main benefits of Scala is functional programming. I made use of the map method on the Map type in the trait example to transform the key/value entries into a collection of strings, without needing to write a for loop. Note that I mapped a static method directly (technically, methods on a Scala object aren't really static -- they're methods on a singleton), without needing to create an anonymous Function instance, as I've done in my previous posts in Java. (Behind the scenes, the Scala compiler did create an anonymous Function1[Tuple2[String,String], String] for me, but I don't have to care about that.)

I won't bother writing a bunch of examples of functional programming in Scala, since they would largely come down to showing how the stuff I implemented (verbosely) in Java in my previous posts already exists in Scala, and has much nicer syntax. For example, I believe all of the immutable data structures I've implemented in Java exist in some form in Scala (and have a much better, more unified API). Assuming I stick with writing Scala in future posts, there will be more functional programming examples.

Conclusions

These are a few of the features I like in Scala that I miss in my day-to-day work programming in Java. I have barely touched the surface of what's available in Scala (having ignored pattern matching, case classes, the REPL, implicits, parallel collections, and more). I chose these features to begin with, since they're not that foreign to Java developers. Indeed, just about everything here could be done in Java, but with a lot more code.

Learning Scala has reinforced my love of the JVM as a platform and my disdain for Java as a language (and the Java standard library -- I have the utmost respect for Joshua Bloch as the author of Effective Java and Java Puzzlers, but the Java collections API angers me regularly in terms of things I believe they could have done better, while retaining backwards-compatibility). That said, I am also hoping that that the .Net port of Scala matures, as a lot of code tends to target the compiler and the standard library, and should be portable across underlying runtimes.

If you're interested in learning more about Scala, I suggest reading Scala for Java Refugees (which is probably a little outdated now -- two major versions of Scala have been released since then) or the free chapters of Scala for the Impatient. There is a "Java to Scala" page on the scala-lang website with more resources for moving to Scala.

In September, there will be a free course given by Martin Odersky (the creator of Scala, and the guy who introduced generics to Java). I'm signed up and would love more classmates.

In terms of books, my favourite is Programming in Scala (I bought it, downloaded the .mobi version, and converted it to ePub using Calibre). A less-good, but still enjoyable book is Dean Wampler's Programming Scala (also a little outdated, but still relevant). As a followup book (once you're pretty comfortable with Scala), I recommend Josh Suereth's Scala in Depth. The preprint PDF I read had a lot of grammar/spelling/typographical mistakes, but the content was solid and understandable (and hopefully the mistakes will get fixed in a subsequent printing).

Finally, if you're a little warped in the head (like me) and you develop a taste for the hardcore functional programming features that Scala enables (and have been implemented in the Scalaz library), I suggest you learn some Haskell (via Real World Haskell or Learn You a Haskell for Great Good -- both great books, which I encourage you to buy, but which you can also read online). While Scala is an object-oriented/functional hybrid language (by design), where you can always fall back to mutable data structures and side-effects, Haskell feels (to me at least, with my predominantly imperative, object-oriented background) more like playing the piano with one hand tied behind your back. That said, I feel that programming in Haskell makes me a better Scala programmer (much as switching between C++ and Java tends to make me better at both than if I stuck with one or the other).