Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to translate shift/reset into delimcc?

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)
like image 964
rgrinberg Avatar asked Jan 21 '13 01:01

rgrinberg


1 Answers

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)))
like image 60
gasche Avatar answered Sep 21 '22 09:09

gasche