没有调用堆栈的体系结构中的尾部调用
对于最近的question about GOTOs and tail recursion，我的答案是调用堆栈。我担心它不够通用，所以我问你:尾部调用(或等效的)的概念在没有调用堆栈的体系结构中有什么用？
在连续传递中，所有被调用的函数都替换了调用函数，因此是尾部调用，因此“尾部调用”似乎不是一个有用的区别。在消息传递和基于事件的架构中，似乎没有等价物，但如果我错了，请纠正我。后两种架构是有趣的案例，因为它们与OOP而不是FP相关联。其他的架构呢？旧的Lisp机器是基于调用栈的吗？
编辑:根据"What the heck is: Continuation Passing Style (CPS)“(和下面的亚历克斯)，在延续传递下的尾部调用的等价物不是”被调用函数代替调用函数“，而是”调用函数传递给它的延续，而不是创建一个新的延续“。与我断言的不同，这种类型的尾部调用很有用。
此外，我对在较低级别使用调用堆栈的系统不感兴趣，因为较高级别不需要调用堆栈。这一限制不适用于Alex的回答，因为他写的是这样一个事实，即其他调用体系结构(is this the right term?)通常具有等效的调用堆栈，而不是它们在引擎盖下的某个地方具有调用堆栈。在连续传递的情况下，结构类似于arborescence，但具有相反方向的边缘。调用堆栈等效项与我的兴趣高度相关。
回答 2
Stack Overflow用户
发布于 2009-10-10 05:06:23
如果这个问题引起我以外的人的兴趣，我有另一个问题的expanded answer，也回答了这个问题。这是一个简单的、非严格的版本。
当计算系统执行子计算时(即，一个计算开始并且必须暂停，同时执行另一个计算，因为第一个依赖于第二个计算的结果)，执行点之间的依赖关系自然出现。在基于调用栈的体系结构中，这种关系在拓扑上是一种path graph。在CPS中，它是一棵树，其中根和节点之间的每条路径都是一个延续。在消息传递和线程化中，它是路径图的集合。同步事件处理基本上就是消息传递。启动子计算涉及扩展依赖关系，除了在替换叶而不是附加到叶的尾部调用中。
将尾部调用转换为异步事件处理更为复杂，因此请考虑使用更通用的版本。如果A订阅了通道1上的事件，B订阅了通道2上的相同事件，而B的处理程序仅在通道1上激发事件(它跨通道转换事件)，则A可以订阅通道2上的事件，而不是订阅B。这更一般，因为尾部调用的等价物需要
- A在通道1上的预订被取消当A在通道2上预订时
- 处理程序是自取消预订(调用时，它们会取消预订)
现在，对于两个不执行子计算的系统: lambda演算(或一般的术语重写系统)和RPN。对于λ演算，尾部调用大致对应于一系列缩减，其中术语长度为O(1) (请参阅SICP section 1.2中的迭代过程)。以RPN为例，使用数据堆栈和操作堆栈(与操作流相对；操作是那些尚未处理的操作)，以及将符号映射到操作序列的环境。尾部调用可以对应于堆栈增长为O(1)的进程。
Stack Overflow用户
发布于 2009-09-28 10:37:26
“没有调用堆栈的体系结构”通常在某种程度上“模拟”调用堆栈--例如，在IBM360时代，我们使用寄存器保存区和参数的S-Type Linkage Convention，按照惯例，这些列表由某些通用寄存器指示。
因此，“尾部调用”仍然很重要:调用函数是否需要保留在调用点之后恢复执行所需的信息(一旦被调用函数完成)，或者它是否知道在调用点之后将不再执行，因此只需简单地重用调用者的“信息来恢复执行”？
因此，例如，尾部调用优化可能意味着不附加恢复执行所需的延续，无论链表是用于什么目的……我喜欢把它看作是一种“调用堆栈模拟”(在某种程度上，尽管它显然是一种更灵活的安排--不希望继续传递的粉丝们在我的答案上跳来跳去；-)。
https://stackoverflow.com/questions/1485146
复制相似问题
腾讯云开发者
