leah blogs: shift, reset and streams

As everyone using and understanding continuations (hopefully) knows, there is no way to return from a continuation once it is called. This “problem” (actually more of an restriction) can be solved using “partial continuations” which can return, as they only save a certain part of the stack.

There are many ways to implement and describe partial continuations, A Library of High Level Control Operators by Christian Queinnec gives a nice overview on them. Personally, I think shift/reset is the most easiest to grasp and to use, YMMV. Recently it also has been proven that shift/reset can be expressed in terms of control/prompt, see How to remove a dynamic prompt for an analysis; if you are interested in such things, also read Shift to Control by Ken Shan.

Now, really, how do shift and reset work? Well, this is actually rather easy. reset introduces a new scope, in which you can call shift to get a partial continuation. Calling this partial continuation will result in starting at reset again. At the end of the shift, shift will return from the reset.

What maybe is a bit more suprising, is that partial continuations can be implemented using “ordinary” continuations, if the language allows for side-effects (which lambda calculus doesn’t). I have written shift and reset in Ruby, here is the code:

# Modeled after Andrzej Filinski's article "Representing
# Monads" at POPL'94, and a Scheme implementation of it.
# http://citeseer.ist.psu.edu/filinski94representing.html

module ShiftReset
  @@metacont = lambda { |x|
    raise RuntimeError, "You forgot the top-level reset..."
  }

  def reset(&block)
    mc = @@metacont
    callcc { |k|
      @@metacont = lambda { |v|
        @@metacont = mc
        k.call v
      }
      x = block.call
      @@metacont.call x
    }
  end

  def shift(&block)
    callcc { |k|
      @@metacont.call block.call(lambda { |*v|
                                   reset { k.call *v } })
    }
  end
end

You aren’t really expected to understand this code; still, anyone learning about (partial) continuations may take this as a koan to meditate about. :-) Please note that above implementation is rather inefficient, not at least since callcc is quite slow in Ruby anyway. A proper partial continuation supporting language would provide these methods natively, of course. This can be done very easily if you use continuation style passing, see above papers for detail.

Now, let’s implement something nifty using our new partial continuations, I decided to convert enumberators like each to lazy streams, look here how this can be done:

include ShiftReset

def each_to_stream(collection)
  reset {
    collection.each { |v|
      shift { |k|
        lambda { |&block|
          block.call v
          k.call
        }
      }
    }
    nil
  }
end

As you can see, this is rather simple code, written in purely functional style. (You need to use Ruby 1.9/CVS for lambda with blocks, sorry. If you don’t want to, rewrite the code and explicitly pass the block. This is left as an exercise for the reader.)

Here’s an example on how to use it:

iter = each_to_stream [1,2,3,4,5,6]

Now, on each call of iter, a block will be called with the current value, and a new iter is returned which will return the next value on it’s call, ad infinitum. The nifty thing is that you can fork the stream, resulting in having two ends:

iter = iter.call { |v| p v }
iter = iter.call { |v| p v }
iter2 = iter                    # Fork
iter = iter.call { |v| p v }
iter = iter.call { |v| p v }

As expected, above code will print:

However, note that we forked iter2 when 2 was the current value. To prove that this worked, try this:

iter2 = iter2.call { |v| p v }  while iter2

This will output the following; the fork was sucessful and our implementation of partial continuations work:

If your brain hurts now, don’t worry. :-)

NP: Bob Dylan—Hurricane

leah blogs

13apr2005 · shift, reset and streams