0 译者前言

本文译自浅井健一先生的《shift/reset プログラミング入門（Introduction to Programming with Shift and Reset）》。找了一圈之后发现整个知乎上都没人教怎么使用 delimited continuation，遂翻译。

一些说明：

  • 虽然文中说有任意函数式编程语言的经验即可，但例子和练习题用的是一个 Caml 变体，所以想要获得最佳阅读体验还是要了解 OCaml 或其他 ML 系编程语言的基础语法。
  • Rust 不算。
  • 译文同时参考日语和英语版本，两版本如有不同则以正确/易懂一方为准。
  • 部分译者的评论或解释用〔〕标注。原文的引用和注释则尽量还原（但由于知乎的限制只能混在一起了）。
  • 译者翻译相关文献的经验并不丰富，如有任何错漏或可改进处请务必指出。

接下来开始正文内容。

摘要

Continuation 是在各种编程语言中都普遍存在的概念。条件语句是根据条件从两个 continuation（未来）中选择一个的操作，异常则可看作是丢弃一部分 continuation 的操作。还有，尾调用（goto 语句）就是执行 continuation 的操作。尽管 continuation 是这样一个无处不在的、十分自然的概念，目前为止，显式地使用 continuation 编程仍然一直被认为是困难的。

本教程使用 delimited continuation 操作符 shift 和 reset 来演示如何显式地使用 continuation，从零开始讲解关于 continuation 的基础知识，并在过程中指导读者实现简单的协程和非确定性搜索。本教程同时也能作为 CW 2011 演讲内容的引子。

本教程需要读者熟悉 OCaml、Standard ML、Scheme 或 Haskell 等函数式编程语言，但不需要读者在阅读本文前有任何有关 continuation 的知识。教程中穿插了各种练习问题，推荐读者随读随做。

1 引言

Continuation 就是表示「之后的计算」的概念。它可以看作是异常处理的一种推广，但远比异常处理要强力。实现复杂的计算时，实现者有时会发现需要使用在通常的程序结构中难以写出的控制结构。如果能操作 continuation，则可以在不影响程序整体可读性的前提下实现它们。

想要显式地使用 continuation，一种传统的方式是对整个程序进行 CPS1变换〔continuation passing style，指把 continuation 作为参数显式传递的编程风格〕，但这样就不能保留程序的原有结构。为了在引入 continuation 的同时保持程序的正常结构，我们就需要使用 continuation 操作符。

Continuation 操作符中，最有名的就是 Scheme 和 Standard ML 中的 call/cc 了。但是，call/cc 把未来的所有计算都作为 continuation 取出，因此难以使用。实际上，CPS 程序中所用到的 continuation 大多也只是未来的计算中的一部分。而这种有着范围限定的 continuation 就称作 delimited continuation。

操作 delimited continuation 的操作符有很多种，比如 Felleisen 的 control/prompt2，Danvy 和 Filinski 的 shift/reset3，Gunter、Rémy 和 Riecke 的 cupto/prompt4等等。本文选择 shift/reset，因为它有健全完备的公理体系5、存在多态的类型系统6、和 CPS 程序之间有严格的对应关系，并有着各种实际应用。

1.1 实现

〔2011 年原文写作时〕能使用 shift/reset 的编程环境大致有以下这些。

  • Filinski 展示了在支持 call/cc 和可变 cell 的语言中可以通过它们来模拟 shift/reset7。在 Scheme 和 Standard ML 中可以这样来使用这两个操作符。但是，这种实现中 answer type 只能预先确定为固定类型。
  • Gasbichler 和 Sperber 在 Scheme48 上直接实现了 shift/reset8。据报告称这个实现比使用 call/cc 的方法性能更好。
  • Racket 支持包括 shift/reset 在内的一系列 delimited continuation 操作符。
  • Kiselyov 在 Delimcc 库中为 OCaml、Scheme 和 Haskell 实现了一系列的 delimited continuation 操作符9。
  • 有研究10对 MinCaml 进行了扩展，为其添加了 shift 和 reset 操作符，并支持可变、多态的 answer type。还有使用了相同实现方法，但基于通用性更强的 Caml Light 语言的 OchaCaml11。

本文使用 OchaCaml 演示 shift/reset 的各种应用。

1.2 本文的结构

下一节从基础知识开始讲解 shift/reset 编程。对于希望了解更基础的理论的读者，第 3 节简述了 shift/reset 的理论基础。更多细节请参考相关论文。

1.3 前置知识

本文假定读者有 OCaml、Standard ML、 Scheme 或 Haskell 等函数式编程语言的通用知识，但不需要读者阅读前有 continuation 的相关知识。还有，第 3 节假定读者对支持 let 多态的有类型 λ 演算、它的求值规则和类型系统有所了解。

那么第一节的内容就到这里。由于知乎的编辑器过于池沼，本文以节为单位拆分发布。

第二节：

Spore：【译】shift/reset 编程入门 (2)：应用

参考

  1. Plotkin, G. D. “Call-by-name, call-by-value, and the λ-calculus,” Theoretical Computer Science, Vol. 1, No. 2, pp. 125–159 (December 1975). ↩︎

  2. Felleisen, M. “The Theory and Practice of First-Class Prompts,” Conference Record of the 15th Annual ACM Symposium on Principles of Programming Languages, pp. 180–190 (January 1988). ↩︎

  3. Danvy, O., and A. Filinski “Abstracting Control,” Proceedings of the 1990 ACM Conference on Lisp and Functional Programming, pp. 151–160 (June 1990). ↩︎

  4. Gunter, C. A., D. R ́emy, and J. G. Riecke “A Generalization of Exceptions and Control in ML-Like Languages,” Proceedings of the Seventh International Conference on Functional Programming Languages and Computer Architecture (FPCA’95), pp. 12–23 (June 1995). ↩︎

  5. Kameyama, Y., and M. Hasegawa “A Sound and Complete Axiomatization of Delimited Continuations,” Proceedings of the eighth ACM SIGPLAN International Conference on Functional Programming (ICFP’03), pp. 177–188 (August 2003). ↩︎

  6. Asai, K., and Y. Kameyama “Polymorphic Delimited Continuations,” Proceedings of the Fifth Asian Symposium on Programming Languages and Systems (APLAS’07), LNCS 4807, pp. 239–254 (November 2007). ↩︎

  7. Filinski, A. “Representing Monads,” Conference Record of the 21st Annual ACM Symposium on Principles of Programming Languages, pp. 446–457 (January 1994). ↩︎

  8. Gasbichler, M., and M. Sperber “Final Shift for Call/cc: Direct Implementation of Shift and Reset,” Proceedings of the ACM SIGPLAN International Conference on Functional Programming (ICFP’02), pp. 271–282 (October 2002). ↩︎

  9. Kiselyov, O. “Delimited Control in OCaml, Abstractly and Concretely: System Description,” In M. Blume, N. Kobayashi, and G. Vidal, editors, Functional and Logic Programming (LNCS 6009), pp. 304–320 (April 2010). ↩︎

  10. Masuko, M., and K. Asai “Direct Implementation of Shift and Reset in the MinCaml Compiler,” Proceedings of the 2009 ACM SIGPLAN Workshop on ML, pp. 49–60 (September 2009). ↩︎

  11. Masuko, M., and K. Asai “Caml Light + shift/reset = Caml Shift,” Theory and Practice of Delimited Continuations (TPDC 2011), pp. 33–46 (May 2011). ↩︎