functional-programming - 如何将移位/重置转换为delimcc？

Question

我正在研究Oleg和Asai的定界延续“傻瓜”论文(http://pllab.is.ocha.ac.jp/~asai/cw2011tutorial/main-e.pdf)，但是本文改用shift/reset形式主义Oleg的delimcc中提供的一些即时提示。所以我有几个问题:

首先，提示是什么？以及为什么在shift和其他函数中传递？知道什么是subcont也很好，但是我愿意跳过这一点，因为我只想阅读本文。此外，本文中的shift和shift0之间有什么区别以及它们与shift的对应关系如何。

另外，derimcc中的reset是什么？我的直觉告诉我new_prompt和push_prompt在某种程度上与reset相对应。但我在这里也需要澄清。

编辑:我能够从论文中翻译一个简单的例子，我的直觉就正确了。但是，我想对差异做一个真正的解释，为什么它们是delimcc的。这是两个版本，以防有人感兴趣

纸:

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)

Answer 1

我建议您阅读this paper的开头，它是Oleg的delimcc演示文稿的日记版本。这将使您对delimcc有一个合理的了解，从而使您可以将文章的移位/重置示例移植到delimcc的多提示设置。

您可能会感兴趣的两句话。首先是我上面指出的期刊版本:

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.

第二个来自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.

结论:您是正确的，调用new_prompt以获得提示，然后通过push_prompt安装它是获取reset的方法。实际上，您只需要调用一次new_prompt，并且可以始终将其推送到同一全局提示，并获得通常的shift/reset行为(声明不同的提示只会给您更多的自由)。

最后，shift是由delimcc的基元定义的，这是在库中完成的。 shift调用take_subcont，立即重新安装(相同)提示，并向用户提供将重新启动中止的计算的功能。 shift0做同样的事情，除了它不会重新安装提示。在delimcc代码中:

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)))