Continuations Passing Style Explained III: Groovy

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.

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 based 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 III of the post, in which I attempt to show how continuation passing style can be used in Groovy. If you're new to continuations 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 II might be of interest of you're keen to see the closures prototype in action.

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 first function in the return statement. In the previous post, I explained how a method to find the first element of a list and a continuation 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 Groovy version, which theoretically should be simpler and easier to read. It's original is more fully explained in Part I.

So in Groovy 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:

def findFirst = { list, continuation ->
    if (list.isEmpty()) return continuation.call(null, list);
    def first = list.get(0);
    def rest = list.subList(1, list.size())
    return continuation.call(first, rest);
}

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 the "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:

def evens = {numbers ->
    return findFirst(numbers, { first, rest ->
            if (first == null) return []; //no more elements
            def result = [];
            if (first % 2 == 0) result.add(first); //match!
            result.addAll(evens(rest));
            return result; //process rest of list
        }
    );
}

What's missing is the anonymous inner class. It's been replaced by a closure declaration. The exists( ) method becomes similarly slimmed:

def exists = { needle, haystack ->
    return findFirst(haystack, {Integer first, List rest ->
            if (first == null) return false; //never found
            if (first.equals(needle)) return true; //match!
            return exists(needle, rest); //process rest of list
        }
    );
}

Et voila. You have used continuation passing style 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 Groovy version almost seems like a let down after the previous Java 7 post. If you understand recursion then there just isn't much "to get"... whereas the Java 7 version required a bullet list of explanations on how to declare a closure. Interesting...

And remember, without tail call optimization, it would be risky to deploy this code. You'll run out of memory quickly.

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

Thanks!