Racket是否使用尾递归？

Question

如果我在Racket中尝试这个：

(expt 2 1000)

我得到的数字比宇宙中所有原子大许多倍：

10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376

我甚至可以使用(expt 2 10000)变得更加疯狂，这在我的T450笔记本电脑上只需要一秒钟。据我了解，这只能因为尾递归而成为可能。它是否正确？如果是这样，Racket的尾递归是纯函数式编程，还是幕后隐藏的副作用？另外，当我看到Common Lisp的loop时，它是否基于引擎盖下的尾递归？一般来说，我想我想知道这些递归/循环的功能是如何实现的。

Answer 1

Racket使用C库来实现大整数（bignums）。该库名为GMP：

https://gmplib.org/manual/Integer-Exponentiation.html

现在2 ^ n的情况很容易在二进制表示中实现。你只需要一个1后跟n个零。也就是说，GMP可以非常快速地计算数量。

Answer 2

尾调用是一件很棒的事情，但重要的是要理解它不能计算那些不可计算的东西。通常，任何用尾部调用编写的（例如）函数语言的代码都可以使用循环以另一种语言编写。尾调用语言的优点是程序员不需要重写对循环的递归调用以允许其程序运行。

看起来你关注的是Racket（和Scheme）用非常大的数字计算的能力。这是因为默认情况下，Racket和Scheme使用“bignums”来表示整数。具有bignum功能的包可用于许多语言，包括C，但它们可以在没有垃圾收集的语言中进行额外的工作，因为它们的表示形式不是有限的。

Answer 3

另外，当我看到Common Lisp循环时，它是否基于引擎盖下的尾递归？

这是一个实现细节，但很可能不是。首先，CL已经允许使用TAGBODY块，这使得LOOP可以用CL构造表达。

例如，如果我宏扩展一个简单的LOOP：

(loop)

我在实现中获得了相当统一的结果。

;; SBCL
(BLOCK NIL (TAGBODY #:G869 (PROGN) (GO #:G869)))

;; CCL
(BLOCK NIL (TAGBODY #:G4 (PROGN) (GO #:G4)))

;; JSCL
(BLOCK NIL (TAGBODY #:G869 (PROGN) (GO #:G869)))

;; ECL
(BLOCK NIL (TAGBODY #:G109 (PROGN) (GO #:G109)))

;; ABCL
(BLOCK NIL (TAGBODY #:G44 (GO #:G44)))

实现通常用具有跳转或循环的语言编写，或者可以轻松地模拟它们。此外，编译了许多CL实现，并且可以定位具有跳转原语的汇编语言。通常，不需要有一个经过尾递归函数的中间步骤。

话虽这么说，实现带尾递归的TAGBODY似乎可行。例如，对于每个标签，JSCL将tagbody中的表达式切割成不同的方法，并且在使用go时调用这些方法：https://github.com/jscl-project/jscl/blob/db07c5ebfa2e254a0154666465d6f7591ce66e37/src/compiler/compiler.lisp#L982

而且，如果我让loop运行一段时间，就不会发生堆栈溢出。在这种情况下，这不是由于尾部调用消除（其中，AFAIK，并未在所有浏览器上实现）。看起来tagbody的代码总是有一个隐含的while循环，并且go抛出了tagbody的异常捕获。