为什么不能在基于JVM的Lisps中优化尾调用？ [英] Why can't tail calls be optimized in JVM-based Lisps?

问题描述

主要问题：我认为尾调用优化（TCO）最重要的应用是将递归调用转换为循环（在递归调用具有某种形式的情况下）。更确切地说，当被翻译成机器语言时，这通常将被翻译成某种系列的跳跃。一些编译为本地代码（例如SBCL）的Common Lisp和Scheme编译器可以识别尾递归代码并执行此翻译。基于JVM的Lisps如Clojure和ABCL有麻烦这样做。它是什么关于JVM作为一个机器，防止或使这个困难？我不明白。 JVM显然对循环没有问题。这是编译器必须弄清楚如何做TCO，而不是编译它的机器。

Main question: I view the most significant application of tail call optimization (TCO) as a translation of a recursive call into a loop (in cases in which the recursive call has a certain form). More precisely, when translated into a machine language, this would usually be translation into some sort of series of jumps. Some Common Lisp and Scheme compilers that compile to native code (e.g. SBCL) can identify tail-recursive code and perform this translation. JVM-based Lisps such as Clojure and ABCL have trouble doing this. What is it about the JVM as a machine that prevents or makes this difficult? I don't get it. The JVM obviously has no problem with loops. It's the compiler that has to figure out how to do TCO, not the machine to which it compiles.

相关问题：Clojure 可以 递归代码转换为循环：如果程序员用关键字 recur 替换对函数的尾调用，它就像执行TCO一样。但是如果可以得到一个编译器来识别尾调用，例如SBCL和CCL，那么为什么Clojure编译器不能知道它应该以尾部调用的方式处理 recur ？

Related question: Clojure can translate seemingly recursive code into a loop: It acts as if it's performing TCO, if the programmer replaces the tail call to the function with the keyword recur. But if it's possible to get a compiler to identify tail calls--as SBCL and CCL do, for example--then why can't the Clojure compiler figure out that it's supposed to treat a tail call the way it treats recur?

（抱歉 - 这无疑是一个常见问题，我相信上面的说法显示了我的无知， ）

(Sorry--this is undoubtably a FAQ, and I'm sure that the remarks above show my ignorance, but I was unsuccessful in finding earlier questions.)

推荐答案

Real TCO适用于尾部位置的任意调用，而不仅仅是自调用，下面的代码不会导致堆栈溢出：

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))

显然，您需要JVM支持，因为在JVM上运行的程序无法操作调用堆栈。 （除非你愿意建立自己的调用约定，并将相关的开销强加在函数调用上; Clojure旨在使用常规的JVM方法调用。）

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 因其明确性而受到好评。

As for eliminating self calls in tail position, that's a simpler problem which can be solved as long as the entire function body gets compiled to a single JVM method. That is a limiting promise to make, however. Besides, recur is fairly well liked for its explicitness.

这篇关于为什么不能在基于JVM的Lisps中优化尾调用？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！