标签: tail-call-optimization

很简单,什么是尾部调用优化？更具体地说,任何人都可以显示一些可以应用的小代码片段,而不是在哪里,并解释为什么？

在jvm-prevent-tail-call-optimization之后两年,似乎有一个原型 实现,MLVM已经将该功能列为"proto 80%"一段时间了.

Sun的/ Oracle方面是否没有积极的兴趣支持尾调用,或者只是尾部调用" 在每个功能优先级列表中排在第二位 [...]"如JVM所述语言峰会？

如果有人测试了MLVM构建并且可以分享它的工作原理(如果有的话),我会非常感兴趣.

更新: 请注意,像Avian这样的某些虚拟机支持正确的尾部调用,没有任何问题.

我认为有一个@tailrec注释可以确保编译器优化尾递归函数.你刚才把它放在宣言面前吗？如果在脚本模式中使用Scala(例如:load <file>在REPL 下使用),它是否也有效？

我今天在unix中发现了"time"命令,并认为我会用它来检查Haskell中尾递归和正常递归函数之间运行时的差异.

我写了以下函数:

--tail recursive
fac :: (Integral a) => a -> a
fac x = fac' x 1 where
    fac' 1 y = y
    fac' x y = fac' (x-1) (x*y) 

--normal recursive
facSlow :: (Integral a) => a -> a
facSlow 1 = 1
facSlow x = x * facSlow (x-1)

这些都是有效的,记住它们只是用于这个项目,所以我没有费心去检查零或负数.

但是,在为每个编写一个main方法,编译它们,并使用"time"命令运行它们时,两者都具有相似的运行时,正常的递归函数使尾递归函数边缘化.这与我在lisp中关于尾递归优化的内容相反.这是什么原因？

这个问题的标题可能有点奇怪,但事实是,据我所知,根本没有什么可以反对尾部调用优化.但是,在浏览开源项目时,我已经遇到了一些主动尝试阻止编译器进行尾调用优化的函数,例如CFRunLoopRef的实现,这些函数充满了这样的黑客攻击.例如:

static void __CFRUNLOOP_IS_CALLING_OUT_TO_AN_OBSERVER_CALLBACK_FUNCTION__() __attribute__((noinline));
static void __CFRUNLOOP_IS_CALLING_OUT_TO_AN_OBSERVER_CALLBACK_FUNCTION__(CFRunLoopObserverCallBack func, CFRunLoopObserverRef observer, CFRunLoopActivity activity, void *info) {
    if (func) {
        func(observer, activity, info);
    }
    getpid(); // thwart tail-call optimization
}

我很想知道为什么这看起来如此重要,有没有我作为一个普通的开发人员应该保持这种想法呢？例如.尾调用优化有常见的陷阱吗？

特别是如果我有以下代码:

func sum(n: Int, acc: Int) -> Int {
  if n == 0 { return acc }
  else { return sum(n - 1, acc + n) }
}

Swift编译器会将它优化为循环吗？在下面一个更有趣的案例中是这样的吗？

func isOdd(n: Int) -> Bool {
  if n == 0 { return false; }
  else { return isEven(n - 1) }
}

func isEven(n: Int) -> Bool {
  if n == 0 { return true }
  else { return isOdd(n - 1) }
}

除非方法是最终的,否则为什么Scala编译器不会应用尾调用优化？

例如,这个:

class C {
    @tailrec def fact(n: Int, result: Int): Int =
        if(n == 0)
            result
        else
            fact(n - 1, n * result)
}

结果是

错误:无法优化@tailrec带注释的方法:它既不是私有的也不是最终的,因此可以被覆盖

如果编译器在这种情况下应用TCO,究竟会出现什么问题呢？

我正在尝试使用JavaScript中更实用的样式; 因此,我已经用for实用函数替换了for循环,例如map和reduce.但是,我没有找到while循环的功能替换,因为尾调用优化通常不适用于JavaScript.(根据我的理解,ES6可以防止尾调用溢出堆栈,但不会优化它们的性能.)

我解释了我在下面尝试过的内容,但TLDR是:如果我没有尾调用优化,那么实现while循环的功能方法是什么？

我尝试过的:

创建"while"实用程序功能:

function while(func, test, data) {
  const newData = func(data);
  if(test(newData)) {
    return newData;
  } else {
    return while(func, test, newData);
  }
}

由于尾调用优化不可用,我可以将其重写为:

function while(func, test, data) {
  let newData = *copy the data somehow*
  while(test(newData)) {
    newData = func(newData);
  }
  return newData;
}

但是在这一点上,感觉就像我让我的代码更复杂/混淆使用它的任何人,因为我必须使用自定义实用程序功能.我看到的唯一实际优势是它迫使我使循环变得纯净; 但似乎只是使用常规while循环并确保我保持一切纯净是更直接的.

我还试图找出一种方法来创建一个模拟递归/循环效果的生成器函数,然后使用像find或reduce这样的实用函数迭代它.但是,我还没有想出一种可读的方法.

最后,用实用函数替换for循环使得我想要完成的更明显(例如,对每个元素做一件事,检查每个元素是否通过了测试等).然而,在我看来,while循环已经表达了我想要完成的事情(例如,迭代直到我们找到素数,迭代直到答案得到充分优化,等等).

所有这一切之后,我的整体问题是:如果我需要一个while循环,我正在以函数式编程,而且我无法访问尾调用优化,那么什么是最佳策略.

Steve Yegge在一篇博客文章中提及它,我不知道这意味着什么,有人可以填写我吗？

它与尾部调用优化是一回事吗？

我经常听到人们说C不执行尾部呼叫消除.虽然标准不能保证,但是无论如何,它是否在实践中通过任何体面的实现来执行？假设你只针对成熟的,实现良好的编译器而不关心为模糊平台编写的原始编译器的绝对最大可移植性,那么在C中依赖尾调用是否合理呢？

另外,将尾部呼叫优化留在标准之外的理由是什么？