代码之家 › 专栏 › 技术社区 › outis

没有调用堆栈的体系结构中的尾部调用

tail-call-optimization callstack functional-programming

outis · 技术社区 · 15 年前

我对最近一次事件的回答 question about GOTOs and tail recursion

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

编辑:根据“ What the heck is: Continuation Passing Style (CPS) “(和下面的Alex),延续传递下的尾部调用的等价物不是“被调用函数替换调用函数”,而是“调用函数传递给定的延续,而不是创建新的延续”。这种尾部调用很有用,与我所断言的不同。

另外,我对在较低级别使用调用堆栈的系统不感兴趣,因为较高级别不需要调用堆栈。这个限制不适用于Alex的回答,因为他写的是其他调用架构( is this the right term? )通常有一个等价的调用堆栈,而不是在引擎盖下的某个地方有一个调用堆栈。在连续传递的情况下,结构类似于 arborescence ,但边缘方向相反。调用堆栈等价物与我的兴趣高度相关。

2 回复 | 直到 7 年前

Alex Martelli 15 年前

“没有调用堆栈的体系结构”通常在某种程度上“模拟”调用堆栈——例如,在IBM360时代,我们使用 S-Type Linkage Convention

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

因此,例如,尾部调用优化可能意味着不在用于此目的的任何链表上追加恢复执行所需的延续。。。我喜欢将其视为一种“调用堆栈模拟”(在某种程度上,虽然这显然是一种更灵活的安排——不想让连续通过的粉丝们对我的答案一头雾水;-)。

Community CDub 7 年前

如果这个问题不可能引起我以外的人的兴趣,我有一个 expanded answer 另一个问题也回答了这个问题。这是一个简单的、非严格的版本。

当计算系统执行子计算时(即,由于第一次计算取决于第二次计算的结果,因此在执行另一次计算时,计算开始并必须暂停),执行点之间的依赖关系自然产生。在基于调用堆栈的体系结构中,这种关系在拓扑上是 path graph

将尾调用转换为异步事件处理更为复杂,因此应考虑更一般的版本。如果A订阅了通道1上的事件,B订阅了通道2上的同一事件,B的处理程序只在通道1上触发事件(它跨通道转换事件),那么A可以订阅通道2上的事件,而不是订阅B。这是更一般的,因为尾部调用的等效要求

当A在频道2上订阅时,A在频道1上的订阅将被取消
处理程序自行取消订阅(调用时,它们会取消订阅)

SICP section 1.2 )。使用RPN来使用数据堆栈和操作堆栈(与操作流相反;操作是尚未处理的操作),以及将符号映射到操作序列的环境。尾部调用可能对应于具有O(1)堆栈增长的进程。