Stackful generators: Same fringe problem

Stackfulness

While generators are have seen a resurgence in recent times, for example both Python and C# support them, most implementations require that a generator can only be yield from the main body: while it can call other functions (including other generators), they must all return before the generator can yield to the caller. That is, the generator's call stack must be empty when it yields. This type of coroutines is sometime called semi-coroutine ([Moura04]) or simply generators.

Boost.Coroutine provides stackful coroutines and generators that can yield from deep inside nested functions. This makes them much more powerful than more limited form of generators.

We will prefer the term semi-coroutine to refer to these limited coroutines and generators.

The term semi-coroutine is sometimes used to describe asymmetric coroutines, while symmetric coroutines are simply called coroutines. We will explain the difference between symmetric coroutines and asymmetric coroutines only in the advanced section

Same Fringe: the problem

Given two binary trees, they are have the same fringe if all leafs, read from left to right are equals. This is the classical coroutine killer application, because it is hard to solve in O(N) (with best case O(1)) in the number of leaves, without using stackful coroutines. The Portland Pattern Repository's wiki contains more details on the problem and solutions on many languages.

The solution presented here is an almost verbatim port of the version in the Lua language from the wiki

Solution

For this example a tree of integers will be represented by this recursive description:

a leaf is an integer.
a node is a pair of nodes or a leaf.
a tree is a node.

Or, in pseudo-C++:

typedef int leaf_type;
typedef boost::variant<std::pair<node_type, node_type>, leaf_type> node_type;
typedef node_type tree_type;

Note that the above typedefs aren't legal C++ because the syntax for a recursive variant is lightly different. For the sake of exposition we will pretend that the recursive typedef works. The function:

bool is_leaf(node_type)

will return true if the node is actually a leaf, false otherwise. This is the generator signature:

typedef generator<leaf> generator_type;

This is the generator body:

leaf tree_leaves
 (generator_type::self& self,
  const node_type& node) 
{
  if(is_leaf(node)) {
    self.yield(boost::get<leaf_type>(tree));
  } else {
    tree_leaves(self, boost::get<node_type>.first);
    tree_leaves(self, boost::get<node_type>.second);
  }
  self.exit();
}

tree_leaves recursively traverses the tree and yields each leave. In practice it gives a flattened view of the tree. Notice how yield() can be called from anywhere in the recursion stack.

bool same_fringe(const element& tree1, const element& tree2) {
  generator_type tree_leaves_a(boost::bind(tree_leaves, _1, tree1));
  generator_type tree_leaves_b(boost::bind(tree_leaves, _1, tree2));
  while(tree_leaves_a && tree_leaves_b) {
    if(tree_leaves_a() != tree_leaves_b())
      return false;
  }
  return true && (!tree_leaves_b && !tree_leaves_a);
}

Given two trees same_fringe creates two generator instances, each bound to one of the two trees. Then, as long as there are leaves in the two trees it check that the current leaf of first tree is equal to the one in the second tree.

The return value controls that both generators have reached the end: to have the same fringe, both trees must have the same number of leaves.

While a generator body can be recursive, a generator is never recursive: a generator cannot call itself directly nor indirectly: a generator can freely call other functions, even other generators, but these cannot call back to the calling generator. This make sense because a generator can only be reentered after it has yielded control, and it is resumed at the exact point where it had yielded. An hypothetical recursive generator wouldn't know were to resume if it called itself because it had not yielded.

Solutions without coroutines

To implement same_fringe without coroutines you need to follow one of these strategies:

Store a flattened view each tree before hand, then compare the views for equality. You lose the ability to do an early exit. The best case is O(N) instead of O(1).
Destructively traverse the first tree while traversing the second tree. The best case is O(1), but it is a destructive algorithm.
Use an explicit stack to track the traversal of the first tree. This has the same characteristics of the coroutine solution but requires explicit stack management and is much more complex.

Generators have the property of lazy evaluation (the tree is traversed only on request), simplicity (the recursion stack is implicit) and immutability (the trees are not modified) . All other solutions have to give up at least one of these properties.

Conclusions

The same_fringe problem is one of the simplest problems that can be easily solved with stackful coroutines. The coroutine stack is essentially used to store the current position in the tree. In general recursive algorithms are the ones that benefit the most from being able to yield from anywhere in the call stack.

For example, notice how the same_fringe function cannot be easily ported to Python generators.