Continuations Passing Style (poorly) Explained II: Java 7 BGGA Closures Prototype

Update: Like many people, I've been grappling with trying to understand continuations. In these posts, I tried to reduce continuations to their absolute essence. But in doing so, I may have missed the mark widely. I might have reduced and twisted them to the point where they aren't continuations at all, but something else entirely. As the joke goes, "Why isn't an elephant small, round, and white? Because then it would be an aspirin." Maybe all that is left of this post is a strange clever trick/ugly hack. Sorry if I've added to your confusion and misinformation... it was fun to write.

Update #2: This post is pretty much a disaster. I mangled the return statements within the closures because I didn't understand the non-local return "return" keyword.

Learning a new language opens your mind to new ways of solving old problems, and so I found myself staring at my Java IDE this afternoon thinking, "What I really need is continuation passing style and recursion." To fully convince myself, I came home and spent Friday night writing a continuation passing style solution to my problem four different times: in Java 4 (no generics), in Java 5 (with generics), in Java 7 (using Neal Gafter's closures prototype, and in Groovy.

This is Part II of the post, in which I attempt to show how continuation passing style can be used in Java 7 with the current BGGA closures prototype. If you're new to the style you might read Part I for a broader background on the topic and to see the Java 4 and 5 examples. If you're a continuation expert, you might do the same, but then leave a slew of corrections to the post in the comments section. Part III details the Groovy version, and is available at http://hamletdarcy.blogspot.com/2008/02/continuations-explained-iii-groovy.html.

So a continuation is a function that represents "the rest of the computation given a point in the computation". Continuation passing style is, roughly, passing a function into another function which calls the passed function as the return statement. In a sense, the passed function "receives" the result of method call. In the previous post, I explained how a method to find the first element of a list and a collector can be combined to emulate the standard foreach-loop. They can also be combined to emulate a for-every-other loop, or a for-multiples-of-3-loop, or a for-first-matching, or anything you want. That's the power of moving the flow control to the continuation and out of the language (foreach) or enclosing code (Strategy/Template Patterns).

The original Java 5 examples combined an interface representing a function (Continuation) and another function (findFirst) which finds the first element of a list and calls the continuation, passing that first element and the rest of the list without that first element:

interface Continuation<T, U> {
    U call(T first, List<T> rest);
}

<T, U> U findFirst(List<T> list, Continuation<T, U> continuation) {
    if (list.isEmpty()) return continuation.call(null, list);
    T first = list.get(0);
    return continuation.call(first, list.subList(1, list.size()));
}

If you want a foreach-loop then you make sure your continuation recursively calls back findFirst on the rest of the list. If you want a for-every-other loop then you have the continuation remove the first element of the "rest" parameter and then call back findFirst recursively. Any iteration strategy is allowed because it is left up to the calling code to specify it. In this way we can define an evens( ) method which will generate a list of the even numbers from a source list, which normally requires a foreach-loop:

List<Integer> evens(final List<Integer> numbers) {
    return findFirst(numbers, new Continuation<Integer, List<Integer>>(){
        public List<Integer> call(Integer first, List<Integer> rest) {
            if (first == null) return Collections.emptyList(); //no more elements
            List<Integer> result = new ArrayList<Integer>();
            if (first % 2 == 0) result.add(first); //match!
            result.addAll(evens(rest));
            return result; //process rest of list
        }
    });
}

You can also define an exists( ) method that would normally require a for-first-loop:

Boolean exists(final Integer needle, List<Integer> haystack) {
    return findFirst(haystack, new Continuation<Integer, Boolean>(){
        public Boolean call(Integer first, List<Integer> rest) {
            if (first == null) return false; //never found
            if (first.equals(needle)) return true; //match!
            return exists(needle, rest); //process rest of list
        }
    });
}

I won't go into detail because I want to spend more time on the Java 7 version, which theoretically should be simpler and easier to read. It's also more fully explained in Part I.

So in Java 7 there is no need to declare the Continuation interface or create an anonymous inner class. The findFirst function can simply declare that it accepts a closure:

<T, U> U findFirst(List<T> list, {T, List<T>=>U} continuation) {
    if (list.isEmpty()) return continuation.invoke(null, list);
    T first = list.get(0);
    return continuation.invoke(first, list.subList(1, list.size()));
}

So reading left to right...

• <T, U>... this is a function that requires two generic types: T and U


• U... this function will return an object of type U


• findFirst... this function is named "findFirst"


• List<T> list... the first parameter is a List containing elements of type T
  


• {T, List<T>=>U} continuation.... ooohh, the fun begins. The second parameter is a function, declared using the curly braces. The parameters to this function are a T object and a List of T objects. This function returns an object of type U, and the function is named "continuation". The => thing separates the parameter list from the return type.
  

Other than that, there is no difference in implementation of findFirst in Java 5 vs. Java 7. If the list passed to findFirst is empty, then the continuation is invoked with null to signal the end of the computation. Otherwise, the first element and the rest of the list are passed to "continuation" for final processing. For a foreach-loop, the continuation will do something and the call back findFirst with the rest of the list as a parameter. For a find-first-matching-loop, the continuation will simply return true on a matching element and end the looping right there.

Have a look at the evens( ) implementation:

List<Integer> evens(final List<Integer> numbers) {
    return findFirst(numbers, { Integer first, List<Integer> rest => 
            List<Integer> result; 
            if (first == null) {
                result = Collections.emptyList(); //no more elements
            } else {
                result = new ArrayList<Integer>();
                if (first % 2 == 0) result.add(first); //match!
                result.addAll(evens(rest));
            }
            result //process rest of list
        }
    );
}

What's missing is the anonymous inner class. It's been replaced by { Integer first, List<Integer> rest =>... removing the class declaration and the method definition reduces the lines of code by 2! (That's by two, not by half). But why is the semi-colon missing off the last line? The original version I wrote used the "return" keyword, which doesn't behave the same way inside and outside of a closure. If you want to return a value from a closure, then it must be the last line of the closure, have no return statement, and lack a semi-colon. This means you can't return from multiple places within a closure, and you can't easily move code in and out of closures without some IDE help. I don't feel bad about getting it wrong the first time.

The exists( ) method becomes similarly changed:

Boolean exists(final Integer needle, List<Integer> haystack) {
    return findFirst(haystack, { Integer first, List<Integer> rest =>
        boolean result = false; 
        if (first == null) result = false; //never found
        else if (first.equals(needle)) result = true; //match!
        else result = exists(needle, rest); //process rest of list
        result
        }
    );
}

Et voila. You have used a collector to define your own flow control. One function worries about how elements in a list are found, and another function worries about what to do with those elements.

The purpose of this post is to answer how to do this in Java 7, not whether you should do this. But I can't resist providing a couple thoughts...

• I wrote this code with only a basic understanding of recursion
  
• ...but I love closures in Groovy, so I already comfortable using closures
  
• The generics involved were not difficult to write
  
• ...but at work, I'm the guy people go to with generics questions (sometimes I wonder why)
  
• With minimum effort, a Java developer could learn functional programming
  
• ...but the same can be said of generics, which many Java developers refuse to adopt. I certainly got a lot wrong about continuations in this series of posts.
  
• The first revision of the code used the return statement, which does not do what I thought it would do
  
• ... maybe using "return" for a non-local return by default isn't the right default
  
• Finally, without tail call optimization (http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4726340), it would be risky to deploy this code. You'll run out of memory quickly.
  

After doing this work, I'm impressed with how easy it was for me, personally, to adopt the new closures features. And this isn't the simplest use of closures. I'm also surprised how easy it was to get core concepts wrong, like what "return" does and how continuations work. Some people are asking the question of whether a functional style has any place within Java. I've started to think more about this... and those critics might have a point. It's not entry level code for many beginning programmers. They have my sympathy. But that seems like an issue that businesses can address within a development team rather that within a language feature. After all, beginner programmers will go to extraordinary lengths to do the wrong thing. If you don't want your developers using a language feature then make a policy to forbid it. Easier said then done, though.

This blog post probably won't descend into a closures debate simply because my readership hovers near zero most days... thanks for listening all the same.

Full executable source is available at: http://www.hamletdarcy.com/files/2008/continuations.zip (requires Junit 4 to run). Have fun!