In the weekends I like to learn lisp (my favorite lisp is scheme), and, whilst I do it in a chaotic fashion, I end up actually learning. Today I'm reading about continuations, a theme that is mentioned over and over in schemeland and which I hadn't the guts to try and understand. Until I found this chapter in the book "Teach yourself scheme in fixnum days". As eye-opening as it is, what I found most surprising is that ruby also has continuation! So I'll sum up what I learned about continuations using ruby for the examples. All the examples and content are either paraphrased or taken directly from the above book.
The first example in the book is simple enough:
1 + callcc {|k| 2 + k.call(3) }
So, what is k? Well, you might see it like this: the point in the program we're leaving to go into the continuation block. Thus, k above would be:
1 + []
Where the "hole" expressed by the brackets is where we left off to go into the definition of the continuation.
Therefore, if we call this continuation, we'd be filling the hole with whatever parameter we pass, so, to our amazement, the above code would be equivalent to:
1 + 3
What we just did, fill the hole and forget what we where doing, is called an escaping continuation.
Not only can we escape from a continuation, but we can also store it and use it to our heart's content:
r = nil
1 + callcc do |k|
r = k
2 + k.call(3)
end
#=> 4
puts r.call(5)
#=>6
puts 3 + r.call(5)
#=>6
Note the last example, instead of 9, which could be expected, we get 6! Why? Calling a continuation always forgets what it was doing to fill the continuation's need. Kinda romantic, isn't it?
Now, let's define a recursive function which takes a list and returns the product of all of it's elements together:
def product(l)
return 1 if l.empty?
l.first * product(l.slice(1..-1))
end
Fair enough, but, what if one of the elements is a zero? Well, then we're in for lots of fruitless computations. Let's see how continuations could help here:
def product(l)
callcc do |exit|
return 1 if l.empty?
unless l.first.zero?
l.first * product(l.slice(1..-1))
else
exit.call 0
end
end
end
What's happening here? Well, remember how in school you learned about how a function is trapped when it makes recursive calls, waiting for them to end to finally die in peace? Well, here we stated that the whole function is a "hole" that wants fo be filled. In regular conditions, it just does the dreaded recursion. But, when it encounters a zero, it calls the continuation with zero and, what does that mean? Drum-doll... Exactly, the function forgets it was waiting for a recursion to end and just returns a zero, effectively avoiding useless calls! In more scientific terms, the whole call stack is sent to hell and the original function returns happily. So, again, we used an escaping continuation to leave a fruitless recursive call stack behind. Neat.
Now, to a more involved example.
Remember trees? You loved them, didn't you, with all those cool recursive algorithms all over the place? Well, let's simplify 'em a little and see them as nested lists. Ok, now, let's say that we have a function called same_fringe? that takes two nested lists (ahem, trees, remember?) and returns true if they have the same leaves in the same order, and false otherwise. Like this:
[1, [2,3]].same_fringe? [[1,2],3] #=> true
[1,2,3].same_fringe? [1, [3, 2]] #=>false
So let's hijack the Array class and put the method there. Remeber, we're being functional here, so let's flatten the lists and see if they match:
class Array
def same_fringe?(o)
self.flatten == o.flatten
end
end
This definition is deceptively more succinct than the scheme version of the example, granted; but the computational complexity remains: Clever as it is, the implementation for flatten in the ruby language still has to visit the whole array to flatten it, which is a waste of resources if we could somehow just go leaf by leaf, without flattening, and leave as soon as we have an answer.
The more clever among you could recognize this as an occasion to use a generator, but, in ruby, the closest thing we have is yielding to a block, which is hardly a proper generator; that is, we want to call a function that returns the next element in the collection after the last time we called it, anywhere, and not just inside a block. (Python does have generators, though, and in java, you can have them if you implement the iterator interface).
A continuation, however, could come in handy in this situation:
class Array
def rest
self.slice 1..-1
end
def tree_generator
caller = nil
generate_leaves = lambda do
loop = lambda do |tree|
if tree.is_a?(Array) and tree.empty?
nil #we reached the end of the array
elsif tree.is_a? Array
loop.call tree.first
loop.call tree.rest
else
callcc do |rest_of_tree|
#I just don't get this :(
generate_leaves = lambda{rest_of_tree.call(:resume)}
caller.call tree
end
end
end
loop.call(self)
end
lambda do
callcc do |k|
caller = k
generate_leaves.call
end
end
end
end
The above procedure is rather convoluted, and I must confess that, although I had to understand it to translate it to ruby, I didn't get the last bit about sending :resume to the generate_leaves lambda. But the gist of the method is mind-blowing: it defines an internal method will get the leaves one by one (generate_leaves) and returns a method that sets itself as a continuation for that internal method; the internal generator, for it's part, does something amazing: when it is inside of an array, it makes recursive calls to go inside that array's head an tail. And when we reach a leaf, we return a continuation that thinks that the whole tree is where we just were.
To further illustrate this point, here's a generator that can go through an array yielding one element at a date =
class Array
def each_one
control_state = lambda do |ret|
each do |elem|
callcc do |resume|
control_state = lambda do |r|
resume.call r
end
ret.call elem
end
end
ret.call :the_end
end
lambda do
callcc {|k| control_state.call(k)} }
end
end
end
This one is clearer: the method returns a procedure that will call, the first time, the control_state procedure, which is defined first as something that goes through each element of the original array, but it stores where it is the computation for the next time it is called. So each time we call whatever was returned to us in a call to each_one, we'll get the next element from where we left off!. That's more powerful that the each method, because we can obtain this procedure and call it wherever we want, not only inside a single block. Color me thunderstruck.
Well, let's redefine same_fringe? using this amazing new knowledge:
class Array
def same_fringe?(o)
gen1 = self.tree_generator
gen2 = o.tree_generator
loop do
leaf1 = gen1.call
leaf2 = gen2.call
if leaf1 == leaf2
if leaf1.nil?
return true
end
else
return false
end
end
end
end
Now, we could go a little further and generalize this generator thing with a method that creates coroutines, but this would mean being able to create a binding and then making it available for a method, but that seems impossible in ruby. To illustrate this, we could see the scheme macro that does this (in racket, remember to (require (lib "defmacro.ss")):
(define-macro coroutine
(lambda (x . body)
`(letrec ((+local-control-state
(lambda (,x) ,@body))
(resume
(lambda (c v)
(call/cc
(lambda (k)
(set! +local-control-state k)
(c v))))))
(lambda (v)
(+local-control-state v)))))
And we can do awesome things with it, like defining a coroutine that fetches a leaf and sends its leaves to another coroutine that can then match this leaf to another leaf, fetched by yet another instance of the same coroutine acting on the other tree. Hence, we could create a procedure that uses two instances of a fetcher coroutine and a matcher coroutine and puts all three to work to fetch leaf by leaf and compare them, all in different procedures that remember their interaction with each other. To see these little guys, see the original article, because in ruby, I can't find a way to simulate a way to mimic the letrec form to call the above macro on a function definition and give it the binding with the definition of resume to the function; the more we could do I guess could be a function that takes a block (the body in the above macro), but making that block recognize the resume method as part of its environment, well, there is when my ruby falls short (maybe we could use the rubinius ruby internals?).