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

问题描述

主要问题:我认为尾调用优化 (TCO) 最重要的应用是将递归调用转换为循环(在递归调用具有特定形式的情况下).更准确地说，当翻译成机器语言时，这通常是翻译成某种系列的跳跃.一些编译为本机代码(例如 SBCL)的 Common Lisp 和 Scheme 编译器可以识别尾递归代码并执行此转换.Clojure 和ABCL 等基于JVM 的Lisps 很难做到这一点.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屋！