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

Question

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

相关问题:Clojure 可以将看似递归的代码转换成循环:如果程序员用关键字替换对函数的尾调用,它就好像它正在执行TCO一样recur.但是,如果有可能让编译器识别尾调用 - 例如SBCL和CCL那样做 - 那么为什么Clojure编译器不能确定它应该按照它处理的方式处理尾调用recur呢？

(对不起 - 这无疑是一个常见问题解答,我确信上面的评论显示了我的无知,但我找不到早期的问题是不成功的.)

Answer 1

Real TCO works for arbitrary calls in tail position, not just self calls, so that code like the following does not cause a stack overflow:

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

Clearly you'd need JVM support for this, since programs running on the JVM cannot manipulate the call stack. (Unless you were willing to establish your own calling convention and impose the associated overhead on function calls; Clojure aims to use regular JVM method calls.)

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