Wednesday, August 1, 2012

Continuation marks

Continuation marks are a mechanism for attaching key-value data to continuation frames. There are two primitives:

(call/cm key value thunk) --- calls thunk with a new continuation mark binding key to value. If the current innermost continuation frame already has a mark with that key, it is overwritten.

(current-marks key) --- returns the list of values of current marks with the given key, from innermost to outermost continuation frame.

Example:

(call/cm 'foo 12 (lambda () (current-marks 'foo))) ---> (12)

So, continuation marks are an obvious mechanism for implementing dynamic binding. That duplicate marks on the same frame overwrite each other makes them play nice with TCO.

I've implemented CMs in the Kernel implementation I'm currently playing with. Every continuation frame has a marks dictionary mapping keys to values. Current-marks walks the continuation chain in the obvious way, collecting matching marks into a list. Call/cm clones the current continuation frame (including the marks dictionary) and updates the binding for the given key. I'm not entirely sure if that's the correct way to implement CMs, but it seems so.

I'm currently trying to implement delimited dynamic binding on top of continuation marks (using the metacontinuation approach from A Monadic Framework), but this seems slightly above my pay grade.

3 comments:

Mariano Montone said...

Very interesting.

Here is a paper describing a mechanism that uses continuation marks to implement RESTful continuation based web applications.

http://faculty.cs.byu.edu/~jay/static/icfp065-mccarthy.pdf

It may be cool to try something like that in the Kernel language.

John Shutt said...

How do continuation marks compare to Kernel's keyed dynamic variables?

Andres Navarro said...

Well, if I understood correctly from Manuel's post, this should be definable in terms of Kernel keyed dynamic variables and vice versa. Only a little care is needed in implementing this in Kernel, to avoid creating long chains of continuations with single marks when a single continuation with all the marks would do (not unlike the trick needed for type checking the result of the last operand to $and?).

Going the other way, Kernel dynamic variables could be easily implemented with this, using the last mark only (I am not sure what type the key parameter has, but there's probably a way to make new unique ones).

I still have to read the dissertation, so I may be off. Anyway, it seems pretty interesting.