Showcase for coroutines

Posted on January 21, 2015

Coroutines are a very undervalued feature. One reason for this might be that programmers don’t know for what coroutines can be used. In this post, I want to show some examples that have a more intuitive solution that involves coroutines.

I will cover in this blog post a few examples that show off the value of coroutines. In a following post I will describe how coroutines can be implemented.

Java is a language that has no first class support for coroutines. There are some solutions that do byte-code manipulation to bake support for coroutines into the language, but I will use none of those. I will use pseudo syntax for coroutines derived from other languages that have proper support for coroutines.

One common design pattern in Java is the iterator pattern. The pattern allows to return elements of a collection step by step. The user of the iterator doesn’t have to know the internal structure of the collection in order to use the iterator.

Tree iteration without coroutines

My example calculates the sum of all elements of a rose tree (multi-way tree).

public class Tree<T> {
    private T payload;
    private List<Tree<T>> children;

    // ...
}

public class Sum {
    public int sum(Tree<Integer> tree) {
        int sum = 0;
        for(int x : tree)
            sum += x;
        return sum;
    }
}

This implementation is not to surprising. But if we try to implement the iterator interface for Tree without coroutines, things get more complicated than they should.

public class TreeZipper<T> {
    private List<Integer> position = new ArrayList<>();;
    private List<Tree<T>> parent = new ArrayList<>();;
    public TreeZipper(Tree<T> tree) {
        parent.add(tree)
    }

    public boolean down(int where) {
        Tree<T> c = current();
        if(c.getChildren().size() <= where) {
            return false;
        } else {
            push(position,where);
            push(parent,c.getChildren().get(where));
            return true;
        }
    }

    public boolean up() {
        if(parent.size() == 1) {
            return false;
        } else {
            pop(position);
            pop(parent)
            return true;
        }
    }

    public boolean left() {
        if(position.size() == 0 || last(position) == 0) {
            return false;
        } else {
            int p = last(position);
            up();
            down(p-1);
            return true;
        }
    }

    public boolean right() {
        if(position.size() == 0
            || last(position) >= current().getChildren().size() - 1) {
            return false;
        } else {
            int p = last(position);
            up();
            down(p-1);
            return true;
        }
    }

    public boolean isTop() {
        return position.getSize() == 0;
    }

    public Tree<T> current() {
        return last(parent);
    }
}

public class TreeIterator<T> implements Iterator<T> {

    private TreeZipper<T> zipper;
    private boolean end;

    public TreeIterator(Tree<T> t) {
        zipper = new TreeZiper(t);
        end = false;
    }

    public T next() {
        T t = zipper.current().getElement();
        if(!zipper.down(0) && !zipper.right()) {
            zipper.up();
            while(!zipper.right())
                zipper.up();
            if(zipper.isTop())
                end = true;
        }
        return t;
    }

    public boolean hasNext() {
        return end;
    }
}

This code would be much shorter and less error prone if we could use good old recursion. The problem is that during an iteration the control flow passes between the caller and the next method of the iterator. The next method is doesn’t have the control all the time, this prohibits the use of recursion.

Tree iteration with coroutines

In such a case a coroutine is the perfect fit. It looks like the coroutine has the control all the time, but under the hood it is suspended at certain points of the execution and it can be resumed. If this sounds to abstract, just look at the code of the same example but this time with coroutines.

<T> void iterate(Tree<T> tree) yields T {
    yield(tree.getElement());
    for(Tree<T> child : tree.getChildren())
        iterate(tree);
}

public class Sum {
    public int sum(Tree<Integer> tree) {
        int sum = 0;
        for(int x : iterate(tree))
            sum += x;
        return sum;
    }
}

At each yield in the coroutine the call stack of iterate is stored. The method sum gets the control and computes the next part of the sum and resumes iterate again until iterate terminates. To illustrate this, here are sequence diagrams of the example with and without coroutines.

Control Flow with coroutines Control Flow without coroutines

Example: Turn based game

A perfect other example is a turn based game. A colleague and I wrote such a game (gnome citadel) and the implementation looked very awful until we introduced coroutines.

A good example is the mine function that instructs an actor to mine a specific location. In more detail, if the actor hasn’t the appropriate tool at hand, he searches for the nearest mining tool and picks it up. Then he approaches the mining location and does the job.

mine block actor = do
  lvl <- await
  actorCoord <- getActorCoord actor
  unless minerHasTool actor lvl $
    case findTool Mining actorCoord lvl of
      Just t  -> pickup t actor
      Nothing -> throwError $ T.ToolMissing Mining
  blockCoord <- getItemCoord actor block
  approach blockCoord actor
  failOnMissingItem actor block blockCoord
  runTransformation $ T.mine actor block

Note that this looks like ordinary sequential code, but the function is executed stepwise. The caller of the function passes a level to the mine coroutine, the coroutine decides what to do next and either yields an updated level or terminates.

Conclusion

Coroutines allow the stepwise execution of code, while for the writer of the coroutine it looks like the code is executed continuously. The use of coroutines simplifies the implementation of certain programs (like iterators) immensely. I hope you find this show case useful and see the need for better coroutine support in your language of choice.

In the next post I will cover how coroutines can be implemented as a library instead of a first-class construct.