# Multi-prompt delimited continuations in terms of single-prompt delimited continuations

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.

• 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. – Dan Doel May 7 '19 at 1:36

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.