How to translate shift/reset into delimcc?

Question

I'm studying Oleg's and Asai's delimited continuations "for dummies" paper(http://pllab.is.ocha.ac.jp/~asai/cw2011tutorial/main-e.pdf) but this paper uses the shift/reset formalism instead of the prompt stuff available in Oleg's delimcc. So I have a few questions:

First of all, what is a prompt? And why is passed down in shift and other functions?. Knowing what is subcont would be nice as well but I'm willing to skip that since I Just want to get through the paper. Also, what is the difference between shift and shift0 and how do they correspond to shift in the paper.

Also, what is reset in delimcc? My gut feeling is telling me that new_prompt and push_prompt somehow correspond to reset. But I need some clarification here as well.

EDIT: I was able to translate a simple example from the paper and my intuition turned out right. However I'd like a real explanation of the differences and why is delimcc is they way it is. Here's both versions in case anyone is interested

Paper:

reset (fun () -> 3 + shift (fun _ -> 5 * 2) - 1)

Delimcc:

let _ = let open Delimcc in
  let np = new_prompt () in
  push_prompt np (fun () -> 3 + (shift np (fun _ -> 5 * 2)) - 1)

Erigeron

Shit/reset? I'm not familiar with that concept. – Inclose

Is there not an [oleg] tag on SO? – Cavorelievo

It looks as if the shift operator is implementing syntactic sugar for partial evaluation. Namely, shift has an argument, but it's made implicit, and its insertion is denoted by an underscore in the body next to it. If someone is struggling with the shift/reset concept, this additional sugar may add a layer of difficulty. – Leprous

The explicit prompt pushing is only there because this delimcc is purely a library, and the host language lacks macros. With some meta-programming, there could be reset NAME (.... shift NAME (...)) which generates the lower-level code where NAME is dynamicaly bound to an explicitly allocated prompt, which is then pushed. I'm planning on porting the delimcc implementation concepts to a Lisp dialect, where I'm of course not going to make the coder go through a two step prompt allocation process, because I have defmacro. – Leprous

Answer 1

I would recommend that you read the beginning of this paper, which is the journal version of Oleg's presentation of delimcc. This would get you a reasonable understanding of delimcc that would let you port the shift/reset example of your article to delimcc's multi-prompt setting.

Two quotes that may interest you. The first is from the journal version I pointed above:

The reader already familiar with delimited control may view delimcc as a generalization of the ordinary shift/reset to control delimiters of arbitrarily many ‘flavors’. The function new_prompt creates a control delimiter – or prompt – of a new, unique flavor. The expression push_prompt p (fun () -> e), the generalization of reset e, puts the control delimiter p on the stack and then evaluates e; take_subcont p f removes the prefix of the stack up to the closest stack frame marked with the given p. The removed portion of the stack, with the terminating delimiter p cut off, is packaged as a continuation object of the abstract type subcont and passed to take_subcont’s argument f. The function push_subcont puts the removed stack frames back on the stack, possibly in a different context, thus reinstating the captured delimited continuation.

The second is from GNU Guile's documentation

Still here? So, when one implements a delimited control operator like call-with-prompt, one needs to make two decisions. Firstly, does the handler run within or outside the prompt? Having the handler run within the prompt allows an abort inside the handler to return to the same prompt handler, which is often useful. However it prevents tail calls from the handler, so it is less general.

Similarly, does invoking a captured continuation reinstate a prompt? Again we have the tradeoff of convenience versus proper tail calls.

These decisions are captured in the Felleisen F operator. If neither the continuations nor the handlers implicitly add a prompt, the operator is known as –F–. This is the case for Guile's call-with-prompt and abort-to-prompt.

If both continuation and handler implicitly add prompts, then the operator is +F+. shift and reset are such operators.

To conclude: you're right that calling new_prompt to get a prompt and then push_prompt to install it is the way to get reset. In fact, you only need to call new_prompt once, and can push always to this same global prompt, and get the usual shift/reset behavior (declaring different prompts only give you some more freedom).

Finally, shift is definable with the primitives of delimcc, and this is what is done in the library. shift calls take_subcont, immediately reinstalls the (same) prompt, and provides to the user a function that would restart the aborted computation. shift0 does the same thing, except it does not reinstall the prompt. In the delimcc code:

let shift p f = take_subcont p (fun sk () ->
  push_prompt p (fun () -> (f (fun c -> 
    push_delim_subcont sk (fun () -> c)))))

let shift0 p f = take_subcont p (fun sk () ->
  f (fun c -> push_delim_subcont sk (fun () -> c)))

Locale