没有调用堆栈的架构中的尾部调用

Question

我最近的回答 关于GOTO和尾递归的问题 以调用堆栈的形式表述。我担心它不够通用，所以我问你：尾部调用（或等效概念）的概念在没有调用堆栈的体系结构中有何用处？

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

编辑：根据 ”到底是什么：连续传球风格 (CPS)”（以及下面的 Alex），延续传递下的尾部调用的等效项不是“被调用函数替换调用函数”，而是“调用函数传递给定的延续，而不是创建新的延续”。这种类型的尾部调用很有用，与我断言的不同。

另外，我对在较低级别使用调用堆栈的系统不感兴趣，因为较高级别不需要调用堆栈。此限制不适用于 Alex 的答案，因为他正在写其他调用架构（这是正确的术语吗？）通常有一个等效的调用堆栈，而不是它们在幕后的某个地方有一个调用堆栈。在连续传递的情况下，结构就像 树状, ，但边缘方向相反。调用堆栈等效项与我的兴趣高度相关。

Answer 1

在关闭的机会，这个问题利益的其他人比我，我有一个 扩大的回答 对于其他问题，还回答这一个。这概括地说，非严格的版本。

当一个计算系统执行子计算(即一开始计算，并且必须暂停，而另一个执行计算，因为首先取决于结果的第二)，一个依赖性之间的关系执行分自然地就出现了。在呼叫堆的基础架构的关系拓扑上了 路径图.在CPS，这是一棵树，其中每一个路径之间的根源和节点是一个延续。在消息传递和线，它是一个集中的路径图。同步处理事件基本上是信息的传递。原子计算中涉及延长的依赖关系，除非在结尾呼吁它取代了一片树叶，而不是附加给它。

把尾巴打电话异事件的处理更为复杂，所以不考虑一个更一般的版本。如果一个订阅的一个事件频道1、B是订购的同一事件在频道2和B的处理程序仅仅是火灾事件在频道1(这意味着该事件的跨渠道)，那么可以订阅的事件频道上的2，而不是订阅B。这是更大，因为相当于一个尾呼吁要求

• A的订阅通道1被取消，当是订阅月2频道
• 处理程序是自我取消订阅(调用时，它们取消订阅)

现在有两个系统不执行子计算:氧微积分(或术语改写系统)和RPN.为氧微积分，尾呼吁大致对应于一系列的减少其期长度是O(1)(见迭代过程中 Sic颗粒部分的1.2).采取RPN使用的数据堆和一个行动组(而不是一流的行动；操作那些尚未加工)和环境地图符号，以顺序的行动。尾的呼吁可以对应流程O(1)堆的增长。

Answer 2

“没有调用堆栈的架构”通常在某种程度上“模拟”调用堆栈 - 例如，早在 IBM 360 时代，我们就使用了 S型联动约定 按照惯例，使用由某些通用寄存器指示的寄存器保存区域和参数列表。

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

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