Quiz Answer: Continuation Passing Style for Converting Visitors to Iterators

by

Here’s the answer to the question raised in my previous post, Java Quiz: Iterating over Binary Tree Elements. The answer is surprisingly easy once you see it. What’s really cool is that it’s an instance of a general programming technique called continuation passing style (CPS). In the form discussed here, CPS is a general technique to convert recursion into iteration.

Enough of the generalities, here’s my answer:

public class TreeIterator implements Iterator<Integer> {

    private final Stack<Tree> mStack = new Stack<Tree>();

    public TreeIterator(Tree tree) {
        stackLeftDaughters(tree);
    }

    public boolean hasNext() {
        return !mStack.isEmpty();
    }

    public Integer next() {
        if (mStack.isEmpty())
            throw new NoSuchElementException();
        Tree t = mStack.pop();
        stackLeftDaughters(t.mRight);
        return t.mVal;
    }

    public void remove() {
        throw new UnsupportedOperationException();
    }

    private void stackLeftDaughters(Tree t) {
        while (t != null) {
            mStack.push(t);
            t = t.mLeft;
        }
    }
}

I now add the following to the main() from the last post:

        Iterator it = new TreeIterator(t);
        while (it.hasNext())
            System.out.println(it.next());

and here’s what I see:

Iteration Order:
1
2
3
4
5
7
8

Conceptually, the way the program works is very simple. The main idea is to keep track of the information that would be on the call stack in the recursive implementation in an explicit programmatic stack data structure. The elements in the queue represent the continuations. They essentially tell the program where to pick up processing when called next, just like the stack does in recursion.

Envious Aside: Continuation passing (literally, not just in style) is what lets Python implement the super-cool yield construction. Yields in Python are a general way to turn visitors into iterators. They’re possible because continuations in Python are first-class object. You can even write completely stackless Python.

Back to Java. Our code maintains a stack of the nodes whose values are left to be printed, in order of how they should be printed. Because you print the left daughters before the root, you always queue up the entire set of left daughters for a node. After initialization, the stack consists from bottom to top of the root, the root’s left daughter, the root’s left daughter’s left daughter, and so on, down to the lower “left corner” of the tree. The iterator has more elements if the stack’s not empty. The next element is always the value on the top of the stack. After returning it, you need to push it’s right daughter, as the descendants of the current node’s right daughter all have to be output before the other elements on the stack.

One thing to look at is how I implemented the recursive add using iteration (I probably would’ve used a for-loop, but thought the while loop easier to undertsand). You could’ve also done this recursively:

    private void stackLeftDaughters(Tree t) {
        if (t == null) return;
        mStack.push(t);
        stackLeftDaughters(t.mLeft);
    }

The recursive version’s clearer (at least to me), but programming languages tend to be much better at iteration than recursion (even languages designed for recursion, like Lisp and Prolog). Java has relatively small stack sizes (typically, they’re configurable), and miniscule maximum depths (usually in the thousands). Of course, if your binary tree is 1000 nodes deep, you have bigger problems than Java’s stack!

Also check out the little details. I made variables final that could be final, kept the class’s privates to itself, and implemented the proper exceptions.

To see that it satisfies the performance constraints, first note that the amount of memory used is never greater than the depth of the tree, because the elements of the stack always lie on a single path from the bottom of a tree up. Constant time per element is a bit tricky, and you might want to call me on it, because it requires an amortized analysis. For each element returned, its node was pushed onto the stack once and popped off the stack once. That’s all the work that happens during next(). You also do tests for every value’s returned daughters, which is still only a constant amount of work per element.

Extra Credit: Use java.util.AbstractSet to implement SortedSet<Integer>. The only methods that need to be implemented are size() and iterator(), so you’re mostly there.

Extra Extra Credit: Discuss the problem of concurrent modification and implement a solution for the iterator like Java’s.

You might also want to note that the tree should be balanced somehow, but that seems like an orthogonal problem to me from the issue with iterators. Check out Java’s own java.util.TreeSet implementation. The code for the collections framework is very useful as a study tool.

5 Responses to “Quiz Answer: Continuation Passing Style for Converting Visitors to Iterators”

  1. Stuart Sierra Says:

    Clojure has a cool form called “recur”. It looks like recursion, but it compiles to a simple loop. The compiler won’t allow “recur” in a position that can’t be tail-call optimized.

  2. lingpipe Says:

    Nope, Clojure wasn’t a typo. It’s a clever name for a new language that compiles tot he JVM. Closures are like continuations in that they hold a function pointer and a stack for later execution. This is enough to make me want to put my compiler hat back on!

    The implicit connection in Stuart Sierra’s post for those of you who aren’t compiler geeks is that you usually write in continuation passing style when your compiler can’t unfold your (elegant) recursions into (efficient) iterations. For most recursion-oriented languages (like Lisp or Prolog), tail recursion optimization is built in. Specifically, if the last call in a function/method definition is recursive, the compiler avoids creating a new stack frame because it’ll never be needed.

    Unfortunately, tail recursion optimization is not availabe in Sun’s JDKs. It is availabe in Clojure.

  3. Jochen L. Leidner Says:

    Nice post.

    One thing worth mentioning is that a continuation is essentially a “promise” to do something (later), and there’s a connection to lazy (evaluation) languages like Haskell.

    Hence, you should give extra credit to people who manage implement the notion of Continuations in Java independent of the tree iteration problem (in the Scheme variant of LISP it’s already built in, of course…).

  4. lingpipe Says:

    That’s a very good point. You can actually do continuations more generically in Java by passing in java.lang.Runnable implementations as the continuations.

    The efficient way to code with continuations is to unfold all the runnables and only store the data, with the operations implicit.

    There are all sorts of opportunities to exploit laziness in Java, but given its call-by-value nature, you have to do it manually, like continuations (unless the kind of laziness you want comes from static class loading). A good example in java.lang is String’s hash code computation, which isn’t done until it’s needed, and then it’s cached.

    There are nice discussions of both laziness and continuation passing style in the AI programming textbooks: O’Keefe’s Craft of Prolog, and Norvig’s AI Programming in Lisp.

  5. Luke Nezda Says:

    Tiny (unmeasured) performance nit: stack is a Vector which adds synchronization overhead. You might consider an ArrayList-based Stack. Anyway, clever solution.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s