Abstracting control
Abstracting control
复制标题
抽象控制
DOI：
10.1145/91556.91622
复制
发表时间：
1990
期刊：
影响因子：
--
通讯作者：
Andrzej Filinski
中科院分区：
文献类型：
--
作者：
O. Danvy;Andrzej Filinski
在过去的几年中，人们对表达编程语言的高级控制结构的连续性产生了重新兴趣，并且已经提出了诸如抽象连续性之类的新模型来捕获这些维度。本文调查了一种替代配方，利用标准延续风格（CPS）的潜在表达能力，而不是引入其他新概念。我们以单个基础为基础：将控制作为连续性的层次结构，每个人都将特定语言功能建模为在嵌套评估上下文上。
我们展示了如何迭代通过延续的转换使我们能够指定广泛的控制行为。例如，两次转换产生了序法式回溯的抽象。同样，在此框架中也可以表达许多其他构造。每个都是独立于其他定义的，但所有这些都以层次结构为单位上，使它们之间的任何相互作用都明确。
这种方法保留了有关CP的所有传统结果，例如其评估顺序独立性。因此，我们的语义是直接使用逐个呼叫语言（例如方案或ML）实现的。此外，由于控制运算符表示CPS中简单，典型的lambda-terms，因此它们本身可以静态键入。与直觉相反，迭代的CPS转换不会产生巨大的结果：除非明确需要，否则第一个超出第一个的延续由于扩展性原理（＆eegr; - 还原）而消失。
除了提出对控制操作员的新动机外，本文还描述了改进到适用级别CP的转换。转换在翻译时通过执行所有管理减少而在一次通行证中运行；有趣的是，它可以使用新的控制操作员非常简洁。本文还提供了一些直接风格的非确定编程的示例。
The last few years have seen a renewed interest in continuations for expressing advanced control structures in programming languages, and new models such as Abstract Continuations have been proposed to capture these dimensions. This article investigates an alternative formulation, exploiting the latent expressive power of the standard continuation-passing style (CPS) instead of introducing yet other new concepts. We build on a single foundation: abstracting control as a hierarchy of continuations, each one modeling a specific language feature as acting on nested evaluation contexts.
We show how iterating the continuation-passing conversion allows us to specify a wide range of control behavior. For example, two conversions yield an abstraction of Prolog-style backtracking. A number of other constructs can likewise be expressed in this framework; each is defined independently of the others, but all are arranged in a hierarchy making any interactions between them explicit.
This approach preserves all the traditional results about CPS, e.g., its evaluation order independence. Accordingly, our semantics is directly implementable in a call-by-value language such as Scheme or ML. Furthermore, because the control operators denote simple, typable lambda-terms in CPS, they themselves can be statically typed. Contrary to intuition, the iterated CPS transformation does not yield huge results: except where explicitly needed, all continuations beyond the first one disappear due to the extensionality principle (&eegr;-reduction).
Besides presenting a new motivation for control operators, this paper also describes an improved conversion into applicative-order CPS. The conversion operates in one pass by performing all administrative reductions at translation time; interestingly, it can be expressed very concisely using the new control operators. The paper also presents some examples of nondeterministic programming in direct style.