What is a Continuation?

https://logicgrimoire.files.wordpress.com/2012/04/wpid-star-spring.jpg

This week we explore the continuation, that noble construct of the mind – O bright, shining tool in the aspiring wizard’s toolchest! Half of what you shall read here is paraphrase, half allegory, and the rest? Sprinkled with a few potent grains of Scheme code.

Continuations are constructs that give a programming language the ability to save the execution state at any point and return to that point at a later time in the program’s execution.

Note that continuations do not save program data, only execution context. Taking a function f as its only argument, call/cc takes the current continuation (i.e., a “snapshot” of the current control context or control state of the program) as an object and applies f to it.

As you might imagine, the Grand Wizards Sussman and Steele themselves (all hail!) were the first to bring this power to the hands of the humble. Since then continuations have been implemented in a number of other languages, though in my biased opinion Scheme is the most lovely of them all.

Yet another way to think of a continuation is as “that thing that is waiting for the current computation to finish.” When we say “computation,” we really just mean “function” or more loosely “whatever the program is doing at the moment.”

For the more magically inclined, the continuation can be imagined as a jump, or “non-local exit,” that allows the practitioner to teleport from one computational place to another (or from one computational palace to another, even!).

Suppose for example that you are a Sorceror’s Apprentice (as I am). You’ve been asked to clean the Master’s tower while he’s away, but it’s quite boring and will take a long time. Lazy apprentice (and aspiring wizard programmer) that you are, you’d much rather be writing on your obscure programming blog or doing logic proofs. Or even writing Scheme programs!

The state of the tower could best be described as “abysmal”. It turns out that he’s a total slob, though of course he’d probably describe himself as an eccentric genius who’s concerned with things other than housecleaning. Whatever the reasons, the place is a wreck.

How do continuations fit in? Let’s say you’re thinking about writing up a new post for your aforementioned obscure programming blog. You’d like to write about continuations, in part as a teaching exercise for yourself, and in part because it’s just good, clean fun. Now you take a continuation (i.e., save the current execution state of this little program we call “Life”1) – let’s call our saved program state “The Master’s Tower is a wreck and I’m thinking about a post on continuations for my obscure programming blog” for short (or long). Let’s call this time T_1.

Having thus taken the continuation, you merrily go about the business of cleaning the Master’s tower, or more precisely, attempting to write Scheme programs that will somehow result in the cleanliness of said tower. Hours later, you invoke the continuation you saved earlier, and you wake up to find yourself thinking about writing up a new post for your blog. You look around and see that the tower is clean (for the moment), leaving you free to go and procrastinate in front of your computer and call it blogging.

Are you tired from having cleaned (or taught Scheme to clean) the whole messy tower? No! Remember that we saved the current execution state at T_1, and you were feeling energetic then. Hours later, we’re at T_2, and you’re not so fresh anymore. However, you are a Sorceror’s Apprentice, tired or not, and you know a few tricks, such as how to jump back to the continuation you saved at T_1.

That’s how you come to find yourself sitting at your tiny desk in the corner of the Master’s tower, surrounded by orderliness, calm, and quiet. The tower is clean, you’re feeling refreshed, and you have an idea for something to write about. Ain’t life grand?

But wait! What the hell does this have to do with anything? Is there any actual code we can look at? Of course!

Our motivating example is taken from a couple of earlier posts regarding a little Scheme problem. (See here for details.) The following procedure was implemented the first time around using good-ol’-fashioned recursion. You can see its implementation and a trace of its output here. I thought it would be fun to play around a bit with continuations, and so I wrote the following:

(define (gather-next-batch-cc pred seq)
  (let ((result '()))
    (call-with-current-continuation
     (lambda (return)
       (for-each (lambda (elem)
                   (if (pred elem)
                       (set! result (cons elem result))
                       (return (reverse result))))
                 seq)))))

As you can see, we’re doing a simple iteration over a list using for-each, but we’ve wrapped it in the call-with-current-continuation form. According to the venerable R5RS:

procedure: (call-with-current-continuation /proc/)

Proc must be a procedure of one argument. The procedure call-with-current-continuation packages up the current continuation (see the rationale below) as an “escape procedure” and passes it as an argument to proc.

In our example above, call-with-current-continuation (which I’ll refer to as “call/cc” from here on out) takes a lambda with one argument, return. We then iterate over seq, checking to see if elem matches our predicate. If it does, we push it onto result. Because we know the format of the list that gather-next-batch-cc will be dealing with, e.g.,

'(1 2 3 b 4 5 c 6 7)

We know that, as we move down the list, we can jump to return as soon as we start seeing elements of the list that don’t match our predicate (number? in this case), rather than iterating down the whole thing.

But don’t take my word for it! Let’s trace that puppy! I must return once again to my lovely Scheme 48 REPL. First, we’ll run a trace using our recursive implementation of gather-next-batch:

> (plist->alist gather-next-batch L)
[Enter (gather-next-batch #{Procedure 585 number?} ‘(1 2 3 b 4 5 c 6 —))
[Enter (gather-next-batch #{Procedure 585 number?} ‘(2 3 b 4 5 c 6 d —))
[Enter (gather-next-batch #{Procedure 585 number?} ‘(3 b 4 5 c 6 d e))
[Enter (gather-next-batch #{Procedure 585 number?} ‘(b 4 5 c 6 d e))
Leave gather-next-batch ‘()]
Leave gather-next-batch ‘(3)]
Leave gather-next-batch ‘(2 3)]
Leave gather-next-batch ‘(1 2 3)]
[Enter (gather-next-batch #{Procedure 585 number?} ‘(4 5 c 6 d e))
[Enter (gather-next-batch #{Procedure 585 number?} ‘(5 c 6 d e))
[Enter (gather-next-batch #{Procedure 585 number?} ‘(c 6 d e))
Leave gather-next-batch ‘()]
Leave gather-next-batch ‘(5)]
Leave gather-next-batch ‘(4 5)]
[Enter (gather-next-batch #{Procedure 585 number?} ‘(6 d e))
[Enter (gather-next-batch #{Procedure 585 number?} ‘(d e))
Leave gather-next-batch ‘()]
Leave gather-next-batch ‘(6)]
[Enter (gather-next-batch #{Procedure 585 number?} ‘(e))
Leave gather-next-batch ‘()]
[Enter (gather-next-batch #{Procedure 585 number?} ‘())
Leave gather-next-batch ‘()]
‘((a (1 2 3)) (b (4 5)) (c (6)) (d ()) (e ()))

As we expect, we’re recurring down through the list, banging on the empty list at the bottom, and then building back up from that. Easy-peasy.

Now let’s trace the version under discussion, the continuation-powered gather-next-batch-cc:

> (plist->alist gather-next-batch-cc L)
[Enter (gather-next-batch-cc #{Procedure 585 number?} ‘(1 2 3 b 4 5 c 6 —))
Leave gather-next-batch-cc ‘(1 2 3)]
[Enter (gather-next-batch-cc #{Procedure 585 number?} ‘(4 5 c 6 d e))
Leave gather-next-batch-cc ‘(4 5)]
[Enter (gather-next-batch-cc #{Procedure 585 number?} ‘(6 d e))
Leave gather-next-batch-cc ‘(6)]
[Enter (gather-next-batch-cc #{Procedure 585 number?} ‘(e))
Leave gather-next-batch-cc ‘()]
[Enter (gather-next-batch-cc #{Procedure 585 number?} ‘())
Leave gather-next-batch-cc #{Unspecific}]
‘((a (1 2 3)) (b (4 5)) (c (6)) (d ()) (e #{Unspecific}))

As you can see (and if the trace output is to be believed), we’re performing significantly fewer operations here. I count 5 procedure entries using this implementation, compared to 11 for the recursive version. I performed this same test using a list with 8 separate groups of numbers, totalling 28 numbers in all. The recursive version called itself 36 times, whereas the “call/cc’d” version came in at 8. In both these cases, gather-next-batch-cc is only called as many times as there are groups of numbers, since it only iterates until it runs out of numbers, and then jumps back.

(Image courtesy Melisande under Creative Commons license.)

Footnotes:

1 Yes, I know about Conway’s Game of Life.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s