2

我对最近关于 GOTO 和尾递归的问题的回答是用调用堆栈来表达的。我担心它不够通用，所以我问你：尾调用（或等效）的概念在没有调用堆栈的架构中如何有用？

在继续传递中，所有被调用的函数都会替换调用函数，因此是尾调用，因此“尾调用”似乎不是一个有用的区别。在基于消息传递和事件的体系结构中，似乎没有等价物，但如果我错了，请纠正我。后两种架构是有趣的案例，因为它们与 OOP 而不是 FP 相关联。其他架构呢？旧的 Lisp 机器是基于调用堆栈的吗？

编辑：根据“ What the heck is: Continuation Passing Style (CPS) ”（以及下面的 Alex），连续传递下的尾调用的等价物不是“被调用函数替换调用函数”而是“调用函数传递了它是给定的，而不是创造一个新的延续”。与我所断言的不同，这种尾调用很有用。

另外，我对在较低级别使用调用堆栈的系统不感兴趣，因为较高级别不需要调用堆栈。这个限制不适用于亚历克斯的回答，因为他写的是其他调用架构（这是正确的术语吗？）通常有一个等效的调用堆栈，而不是他们在引擎盖下的某个地方有一个调用堆栈。在连续通过的情况下，结构就像一个树状结构，但边缘方向相反。调用堆栈等价物与我的兴趣高度相关。

4

2 回答 2

4

“没有调用堆栈的架构”通常在某个级别“模拟”一个——例如，早在 IBM 360 时代，我们使用S-Type Linkage Convention使用寄存器保存区域和按约定指示的参数列表，通过某些通用寄存器。

所以“尾调用”仍然很重要：调用函数是否需要保留在调用点之后恢复执行所需的信息（一旦被调用函数完成），或者它是否知道在调用点之后不会执行，因此只需重用其调用者的“信息以恢复执行”吗？

因此，例如，尾调用优化可能意味着不附加在任何用于此目的的链表上恢复执行所需的继续......我喜欢将其视为“调用堆栈模拟”（在某种程度上，虽然它是显然是一种更灵活的安排——不想让继续传球的粉丝跳到我的答案上；-)。

于 2009-09-28T02:37:25.747 回答
2

如果这个问题对我以外的人感兴趣，我对另一个问题的扩展答案也可以回答这个问题。这是简而言之，不严格的版本。

当一个计算系统执行子计算时（即一个计算开始并且必须暂停，而另一个计算因为第一个取决于第二个的结果而执行），执行点之间的依赖关系自然会出现。在基于调用堆栈的体系结构中，关系在拓扑上是路径图。在 CPS 中，它是一棵树，其中根和节点之间的每条路径都是一个延续。在消息传递和线程中，它是路径图的集合。同步事件处理基本上是消息传递。开始子计算涉及扩展依赖关系，除了在尾调用中替换叶子而不是附加到它。

将尾调用转换为异步事件处理更复杂，因此请考虑更通用的版本。如果 A 订阅了通道 1 上的事件，B 订阅了通道 2 上的相同事件，并且 B 的处理程序仅触发通道 1 上的事件（它跨通道转换事件），则 A 可以订阅通道上的事件2 而不是订阅 B。这更通用，因为相当于尾调用需要

  • 当 A 在频道 2 上订阅时， A 在频道 1 上的订阅被取消
  • 处理程序是自行取消订阅的（调用时，它们会取消订阅）

Now for two systems that don't perform sub-computations: lambda calculus (or term rewriting systems in general) and RPN. For lambda calculus, tail calls roughly correspond to a sequence of reductions where the term length is O(1) (see iterative processes in SICP section 1.2). Take RPN to use a data stack and an operations stack (as opposed to a stream of operations; the operations are those yet to be processed), and an environment that maps symbols to a sequence of operations. Tail calls could correspond to processes with O(1) stack growth.

于 2009-10-10T05:06:22.850 回答