4
$\begingroup$

Let's call the two languages in question (untyped lambda calculus with single or multiple prompt delimited continuations) L_delim and L_prompt.

Is it possible to express multi-prompt delimited continuations in terms of single-prompt delimited continuations

By express I mean the macro-expressible sense (to provide some kind of translation that doesn't involve interpreter overhead), of course it's possible to write an interpreter for multi-prompt delimited continuations even in pure lambda calculus.

I expected a negative result for this, that it's not possible but I don't know how that would be shown. Thanks for any input on this.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ I suspect it might be possible, though I'm unsure. For instance, I believe Oleg Kiselyov showed that it's possible to implement the more 'dynamic' delimited operators (like shift0 and control(0)) in terms of shift, which seems implausible at first. Those let you break out of delimiters, so from there it seems like a matter of managing a token at each delimiter to determine whether you should continue shifting, which seems possible. If I find a conclusive reference, I'll link it. $\endgroup$ Commented May 7, 2019 at 1:36

1 Answer 1

Reset to default
4
$\begingroup$

So, it turns out, the paper describing the construction I mentioned in the comments answers in the affirmative:

Our technique of removing a dynamic prompt is rather general and thus can be used for the design of many other delimited control operators, which permit capturing the continuation up to an arbitrary (not necessarily the closest one) enclosing delimiter. It becomes entirely up to the user which delimiters to skip and how the captured frames are to be composed or used separately.

If you look at their method, it seems like the idea would be to tag the H and HV values with tokens that specify the different prompts involved, and have the h and h' functions compare those tokens to decide what to do. This isn't terribly surprising, because the multi-prompt implementation I'm familiar with uses (representations of) stacks with frames tagged with the prompt, and their technique uses 'static' shift/reset (and macros) to hide explicit manipulation of the stack implementation of e.g. control/prompt, more or less.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.