Wednesday, August 1, 2012

Understanding metacontinuations for delimited control

Metacontinuations arise in some implementations of delimited control such as in A Monadic Framework for Delimited Continuations.

In addition to the usual continuation register K, an interpreter with metacontinuations has a metacontinuation register MK.

Initially, K points to an empty continuation KDone, and MK points to an empty metacontinuation MKDone:

Ordinary computations influence only the continuation K - they push continuation frames while the metacontinuation MK stays the same: 

Control operations such as pushing a prompt (continuation delimiter) influence the metacontinuation. A segment metacontinuation frame MKSeg stores the continuation segment at which the control effect occurred and a pointer to the next metacontinuation. A prompt metacontinuation frame MKPrompt remembers the prompt and points to the segment frame (the reason for splitting this operation into two metacontinuation frames is that it makes the code simpler; see the paper). MK now points to the prompt metaframe, and K points to a new empty continuation KDone:

Further non-control computations occur in the new continuation, while the metacontinuation stays the same, as before:

Further control operations push frames onto the metacontinuation, and create new empty continuations, as before:

When the ordinary continuation reaches KDone, we look at the metacontinuation: if it's MKDone, the program is finished and we return its result. Otherwise, we underflow the metacontinuation by reestablishing the next continuation segment as the current continuation and the next metacontinuation as the current metacontinuation.

1 comment:

Johnicholas said...

Yup, that's my understanding too.

I don't entirely understand how to use control operators (shift/reset) in ordinary programming practice, but perhaps the way forward for (my) understanding is to write directly in continuation passing style (which is feasible with practice.

Then converting back from continuation passing style to direct style mostly works but hits "snags" where you're actually doing something clever with continuations - and at those points you introduce control operators.

When someone expert (like Kiselyov) does it, the control operators end up buried in only a few domain-specific primitives, and the vast majority of the code reads really well.