没有调用堆栈的架构中的尾部调用
我对最近有关 GOTO 和尾递归的问题的回答 以调用堆栈的形式表述。我担心它不够通用，所以我问你：尾部调用（或等效）的概念在没有调用堆栈的体系结构中有何用处？
在连续传递中，所有被调用的函数都会替换调用函数，因此都是尾调用，因此“尾调用”似乎不是一个有用的区别。在基于消息传递和事件的架构中，似乎没有等效的东西，但如果我错了，请纠正我。后两种架构是有趣的案例，因为它们与 OOP 而不是 FP 相关。其他架构呢？旧的 Lisp 机器是基于调用堆栈的吗？
另外，我对在较低级别使用调用堆栈的系统不感兴趣，因为较高级别不需要调用堆栈。此限制不适用于 Alex 的答案，因为他正在撰写有关其他调用架构的事实（这是正确的术语吗？）通常有一个等效的调用堆栈，而不是它们在幕后的某个地方有一个调用堆栈。在连续传递的情况下，结构类似于 树状，但有边缘在相反的方向。调用堆栈等效项与我的兴趣高度相关。
My answer for a recent question about GOTOs and tail recursion was phrased in terms of a call stack. I'm worried that it wasn't sufficiently general, so I ask you: how is the notion of a tail call (or equivalent) useful in architectures without a call stack?
In continuation passing, all called functions replace the calling function, and are thus tail calls, so "tail call" doesn't seem to be a useful distinction. In messaging and event based architectures, there doesn't seem to be an equivalent, though please correct me if I'm wrong. The latter two architectures are interesting cases as they are associated with OOP, rather than FP. What about other architectures? Were the old Lisp machines based on call-stacks?
Edit: According to "What the heck is: Continuation Passing Style (CPS)" (and Alex below), the equivalent of a tail call under continuation passing is not "called function replaces calling function" but "calling function passes the continuation it was given, rather than creating a new continuation". This type of tail call is useful, unlike what I asserted.
Also, I'm not interested in systems that use call stacks at a lower level, for the higher level doesn't require a call stack. This restriction doesn't apply to Alex's answer because he's writing about the fact that other invocation architectures (is this the right term?) often have a call stack equivalent, not that they have a call stack somewhere under the hood. In the case of continuation passing, the structure is like an arborescence, but with edges in the opposite direction. Call stack equivalents are highly relevant to my interests.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
“没有调用堆栈的架构”通常在某种程度上“模拟”调用堆栈 - 例如，在 IBM 360 时代，我们使用 S-Type 链接约定，使用按惯例由某些通用寄存器指示的寄存器保存区域和参数列表。
因此，“尾部调用”仍然很重要：调用函数是否需要保留在调用点之后恢复执行所需的信息（一旦被调用函数完成），或者它是否知道调用点之后将不会执行，因此只需重用其调用者的“信息以恢复执行”即可？
因此，例如，尾部调用优化可能意味着不附加恢复执行所需的延续到任何用于此目的的链表上......我喜欢将其视为“调用堆栈模拟”（在某种程度上，尽管它是显然是一种更灵活的安排——不想让连续传递的粉丝跳过我的答案;-)。
"Architectures without a call stack" typically "simulate" one at some level -- for example, back in the time of IBM 360, we used the S-Type Linkage Convention using register-save areas and arguments-lists indicated, by convention, by certain general-purpose registers.
So "tail call" can still matter: does the calling function need to preserve the information necessary to resume execution after the calling point (once the called function is finished), or does it know there IS going to be no execution after the calling point, and so simply reuse its caller's "info to resume execution" instead?
So for example a tail call optimization might mean not appending the continuation needed to resume execution on whatever linked list is being used for the purpose... which I like to see as a "call stack simulation" (at some level, though it IS obviously a more flexible arrangement -- don't want to have continuation-passing fans jumping all over my answer;-).
如果这个问题除了我之外的其他人感兴趣，我有一个 另一个问题的扩展答案也回答了这个问题。简而言之，这是不严格的版本。
当计算系统执行子计算时（即，一个计算开始后必须暂停，同时执行另一个计算，因为第一个计算取决于第二个计算的结果），执行点之间自然会产生依赖关系。在基于调用堆栈的架构中，关系在拓扑上是一个路径图。在 CPS 中，它是一棵树，根和节点之间的每条路径都是延续。在消息传递和线程中，它是路径图的集合。同步事件处理基本上是消息传递。启动子计算涉及扩展依赖关系，尾部调用除外，它替换叶子而不是附加到叶子上。
将尾部调用转换为异步事件处理更为复杂，因此请考虑更通用的版本。如果 A 订阅了通道 1 上的事件，B 订阅了通道 2 上的同一事件，并且 B 的处理程序仅触发通道 1 上的事件（跨通道转换事件），则 A 可以订阅通道上的事件 不是订阅 B。这更通用，因为相当于尾部调用，要求
2而 两个不执行子计算的系统：lambda 演算（或一般术语重写系统）和 RPN。对于 lambda 演算，尾部调用大致对应于术语长度为 O(1) 的缩减序列（请参阅 SICP 第 1.2 节）。采用 RPN 来使用数据堆栈和操作堆栈（与操作流相反；操作是那些尚未处理的操作）以及将符号映射到操作序列的环境。尾部调用可以对应于具有 O(1) 堆栈增长的进程。
On the off chance that this question interests someone other than me, I have an expanded answer for the other question that also answers this one. Here's the nutshell, non-rigorous version.
When a computational system performs sub-computations (i.e. a computation starts and must pause while another computation is performed because the first depends on the result of the second), a dependency relation between execution points naturally arises. In call-stack based architectures, the relation is topologically a path graph. In CPS, it's a tree, where every path between the root and a node is a continuation. In message passing and threading, it's a collection of path graphs. Synchronous event handling is basically message passing. Starting a sub-calculation involves extending the dependency relation, except in a tail call which replaces a leaf rather than appending to it.
Translating tail calling to asynchronous event handling is more complex, so instead consider a more general version. If A is subscribed to an event on channel 1, B is subscribed to the same event on channel 2 and B's handler merely fires the event on channel 1 (it translates the event across channels), then A can be subscribed to the event on channel 2 instead of subscribing B. This is more general because the equivalent of a tail call requires that
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.