Friday, July 12, 2013

Controlling Internal Iteration

Once upon a time, I read this post on iterators.  Yesterday, a solution struck me for absolutely no reason.

How do you stop internal iteration without non-local returns?  Channels!

func (t Tree) EachInOrder (sink chan) {
  if t.left != nil {
    t.left.EachInOrder(sink)
  }
  if sink {
    sink <- t.value
  }
  if ! sink {
    return
  }
  if t.right != nil {
    t.right.EachInOrder(sink)
  }
}
We generate values as long as the sink channel is open, and back out without generating further values otherwise.  Should the consumer wish to stop iteration early—for instance, it's the implementation of any() and the predicate matched—all it must do is close the channel.  There has to be a goroutine involved somewhere, but that detail can be left to the caller of EachInOrder.

That's lovely, but what about the "kitten-punch example" of interleaving two sequences with internal iterators?  It comes down to setting up two channels, launching the iteration of each sequence on each channel, then passing both channels into a function that takes values from each channel in turn.  It's solvable, at least, but it's not convenient to write into my post here.

Then I went back and actually re-read the post, and the corresponding part 2 that is now available.  The author wrote that the kitten-punch example wasn't solvable without using tools like threads or continuations, which is exactly what a goroutine is like.  Furthermore, part 2 explores deeper into the handling of iterator composition and ends up discussing Ruby's to_enum implementation, which splits off a fiber to run the internal iterator and yield its values back to the caller.

Yes, a fiber.  More concurrency.

The sole interesting observation remaining is that go's unbuffered channels synchronize, so the tree traversal I wrote can stop precisely when the channel consumer is finished, without requiring non-local return nor continuations.  It doesn't spend time or memory generating values that end up not being needed, but it does have to check before and after writing a value whether the channel is still open.

No comments: