为什么不能在基于JVM的Lisps中优化尾调用?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (31)

我将tail call optimization(TCO)作为递归调用转换成循环的最重要的应用(在递归调用具有特定形式的情况下)。更确切地说,当翻译成机器语言时,这通常会翻译成某种连续的跳转。某些编译为本地代码的Common Lisp和Scheme编译器(例如SBCL)可以识别尾递归代码并执行此翻译。基于JVM的Lisp如Clojure和ABCL在执行此操作时遇到了麻烦。作为一台防止或使之变得困难的机器,JVM是什么?我不明白。JVM显然对循环没有问题。编译器必须弄清楚如何执行TCO,而不是它编译的机器。

相关问题:Clojure 可以将看起来递归的代码转换为循环:如果程序员用关键字替换尾部调用函数,它就像执行TCO一样recur。但是,如果可以让编译器识别尾部调用(例如SBCL和CCL),那么为什么Clojure编译器不知道它应该按照对待方式处理尾部调用recur

提问于
用户回答回答于

真正的TCO适用于尾部位置的任意调用,而不仅仅是自我调用,以便类似以下的代码不会导致堆栈溢出:

(letfn [(e? [x] (or (zero? x) (o? (dec x))))
        (o? [x] (e? (dec x)))]
  (e? 10))

显然你需要JVM支持,因为在JVM上运行的程序不能操纵调用堆栈。(除非你愿意建立你自己的调用约定并在函数调用中强加相关开销; Clojure旨在使用常规的JVM方法调用。)

至于消除尾部位置的自我调用,这是一个更简单的问题,只要将整个函数体编译为单个JVM方法即可解决。然而,这是一个有限的承诺。此外,recur它的明确性也非常受欢迎。

用户回答回答于

通过滥用堆内存和一些一手通过CPS转换文件中解释的欺骗手段可以解决这个问题; 它由Chris Frisz和Daniel P. Friedman在Clojure中实现。

现在Rich Hickey可以选择默认做这样的优化,Scala在某些时候会这样做。相反,他选择依靠最终用户来指定它们可以通过Clojure trampoline或其loop-recur构造进行优化的情况 。该决定已在此解释:https//groups.google.com/d/msg/clojure/4bSdsbperNE/tXdcmbiv4g0J

扫码关注云+社区