Racket是否使用尾递归？

作者: Let us fly
发布时间: 2024-08-16 07:47:42 (1月前)
转自：

4 条回复

0#
回复此人
早岁那知世事艰 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <BLOCKQUOTE> <P> 另外，当我看到Common Lisp的循环时，它是否基于引擎盖下的尾递归？ </p> </BLOCKQUOTE> <P> 这是一个实现细节，但很可能不是。首先，CL已经允许 <code> TAGBODY </code> 块，这使 <code> LOOP </code> 在CL构造方面可表达。 </p> <P> 例如，如果我宏扩展一个简单的LOOP： </p> <pre> <code> (loop) </code> </pre> <P> 我在实现中获得了相当统一的结果。 </p> <pre> <code> ;; 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))) </code> </pre> <P> 实现通常用具有跳转或循环的语言编写，或者可以轻松地模拟它们。此外，编译了许多CL实现，并且可以定位具有跳转原语的汇编语言。通常，不需要有一个经过尾递归函数的中间步骤。 </p> <P> 话虽如此，实施 <code> TAGBODY </code> 尾递归似乎可行。例如，JSCL切割a中的表达式 <code> tagbody </code> 对于每个标签，使用不同的方法，并在使用时调用这些方法 <code> go </code> ： <a href="https://github.com/jscl-project/jscl/blob/db07c5ebfa2e254a0154666465d6f7591ce66e37/src/compiler/compiler.lisp#L982" rel="nofollow noreferrer"> https://github.com/jscl-project/jscl/blob/db07c5ebfa2e254a0154666465d6f7591ce66e37/src/compiler/compiler.lisp#L982 </A> </p> <P> 而且，如果我让 <code> loop </code> 运行一段时间，没有发生堆栈溢出。在这种情况下，这不是由于尾部调用消除（其中，AFAIK，并未在所有浏览器上实现）。它看起来像代码 <code> tagbody </code> 总是有一个隐含的 <code> while </code> 循环，那 <code> go </code> 抛出异常 <code> tagbody </code> 去抓。 </p> </DIV>

编辑
1#
回复此人
薄情 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> Racket使用C库来实现大整数（bignums）。该库名为GMP： </p> <P> <a href="https://gmplib.org/manual/Integer-Exponentiation.html" rel="noreferrer"> https://gmplib.org/manual/Integer-Exponentiation.html </A> </p> <P> 现在2 ^ n的情况很容易在二进制表示中实现。你只需要一个1后跟n个零。也就是说，GMP可以非常快速地计算数量。 </p> </DIV>

编辑
2#
回复此人
大黑骡子王 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 尾调用是一件很棒的事情，但重要的是要理解它不能计算那些不可计算的东西。通常，任何用尾部调用编写的（例如）函数语言的代码都可以使用循环以另一种语言编写。尾调用语言的优点是程序员不需要重写对循环的递归调用以允许其程序运行。 </p> <P> 看起来你关注的是Racket（和Scheme）用非常大的数字计算的能力。这是因为默认情况下，Racket和Scheme使用“bignums”来表示整数。具有bignum功能的包可用于许多语言，包括C，但它们可以在没有垃圾收集的语言中进行额外的工作，因为它们的表示形式不是有限的。 </p> </DIV>

编辑

登录后才能参与评论