This post originated from an RSS feed registered with Ruby Buzz
by Christian Neukirchen.
Original Post: shift, reset and streams
Feed Title: chris blogs: Ruby stuff
Feed URL: http://chneukirchen.org/blog/category/ruby.atom
Feed Description: a weblog by christian neukirchen - Ruby stuff
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:
1
2
3
4
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: