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:
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:
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:
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:
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:
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:
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:
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:
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:
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 time:
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:
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")):
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?).