标签: tail-call-optimization

当我写这个函数时,我知道我不会得到尾调优化.我仍然没有想出一个处理这个的好方法,并希望别人可以提供建议.

我有一棵树:

type Heap<'a> =
| E
| T of int * 'a * Heap<'a> * Heap<'a> 

我想要计算其中有多少个节点:

let count h =
    let rec count' h acc =
        match h with 
        | E -> 0 + acc
        | T(_, value, leftChild, rightChild) ->
            let acc = 1 + acc
            (count' leftChild acc) + (count' rightChild acc)

    count' h 0

由于添加了子节点的计数,因此未进行优化.如果树有100万个节点,任何想法如何制作这样的东西？

谢谢,德里克

这是使用CPS实现计数.它仍然吹响了堆栈.

let count h =
    let rec count' h acc cont =
        match h with
        | E -> cont …

所以我的问题的简短版本是,我们如何在Haskell 中编码循环呢？在Haskell中没有尾部优化保证,爆炸模式甚至不是标准的一部分(对吗？),并且折叠/展开范例不能保证在所有情况下都能工作.在这种情况下,只有爆炸模式才能让我在恒定的空间中运行(甚至没有使用$!帮助......虽然测试是在使用ghc-6.8.2的Ideone.com上完成的).

它基本上是一个嵌套循环,在列表范例中可以表示为

prod (sum,concat) . unzip $ 
    [ (c, [r | t]) | k<-[0..kmax], j<-[0..jmax], let (c,r,t)=...]
prod (f,g) x = (f.fst $ x, g.snd $ x)

或者在伪代码中:

let list_store = [] in
for k from 0 to kmax
    for j from 0 to jmax
        if test(k,j) 
            list_store += [entry(k,j)]
        count += local_count(k,j)
result = (count, list_store)

直到我添加了爆炸模式,我得到了内存爆炸甚至堆栈溢出.但爆炸模式不是标准的一部分,对吧？所以问题是,如何在标准的Haskell中对上面的代码进行编码,以便在恒定的空间中运行？

这是测试代码.计算是假的,但问题是一样的.编辑:该foldr-formulated代码是:

testR m n …

我正在使用F#规范的最终工作流程的修改版本,以便在Xbox上进行开发.看来,Xbox上的.net框架不支持尾调用.因此,我必须在编译时禁用尾调用优化.

虽然最初似乎这种限制会阻止在计算表达式中使用任何形式的循环,但我最初认为"步进"可以避免这个问题:计算表达式中的递归函数f不直接调用自身,而是返回一个包含lambda的最终值,该lambda调用f.

实验表明我对while循环是正确的(它们在计算表达式中使用时不会导致堆栈溢出),但不是关于递归函数.

为了澄清,这有效:

// Wait until "start" or "A" is pressed on one of the gamepads.
// Set "player" when that happens.
let player : PlayerIndex option ref = ref None
while (!player).IsNone do
    for p in all_players do
        let state = GamePad.GetState(p)
        if state.IsConnected
            && (state.Buttons.Start = ButtonState.Pressed
                || state.Buttons.A = ButtonState.Pressed) then
            player := Some p
    do! sys.WaitNextFrame()

这会导致堆栈溢出:

// Wait until "start" is pressed on the controlling gamepad.
let rec wait() = task {
    input.Update()
    if …

请考虑以下代码:

int fac_aux( int x, int res ) {
    if( x == 1 ) return res;
    else return fac_aux( x - 1, res * x );
}

int fac( int x ) {
    return fac_aux( x, 1 );
}

int main() {
    int x = fac( 50 );

    std::cout << x;
    return 0;
}

根据生成的asm文件一切正常,尾调用优化.

尝试更换

int x = fac( 50 );

同

int x = fac_aux( 50, 1 );

奇怪,但尾调用优化消失了.据我所知,在VS2008中没有这么奇怪的编译器行为.任何有关这些事情发生的想法以及如何确保尾部调用优化都已完成？

; 函数编译标志:/ Ogtp

尝试了/ O2和/ Ox优化标志.是否有其他重要的编译器选项？

编辑:VS2012设法进行优化

以下博客文章展示了如何foldBack使用延续传递样式使F#尾部递归.

在Scala中,这意味着:

def foldBack[T,U](l: List[T], acc: U)(f: (T, U) => U): U = {
  l match {
    case x :: xs => f(x, foldBack(xs, acc)(f))
    case Nil => acc
  }
} 

通过这样做可以使尾递归:

def foldCont[T,U](list: List[T], acc: U)(f: (T, U) => U): U = {
  @annotation.tailrec
  def loop(l: List[T], k: (U) => U): U = {
    l match {
      case x :: xs => loop(xs, (racc => k(f(x, racc))))
      case Nil => k(acc)
    }
  }
  loop(list, u …

如果我进行尾调用递归(而不是for (;;)...break循环),我的函数可以更简单地编写.但是,如果编译器无法优化它,我恐怕会遇到性能问题,特别是因为它将由最终用户编译.

1. 有没有办法告诉编译器"确保你优化这个尾调用,否则给我一个错误"(例如Scala支持这个)

2. 如果编译器无法优化它,那么性能限制是什么？关于有多少尾调用可以在不打破堆栈的情况下运行？

更新:

编译器是gcc和MSVC.

通常,我会期待大约十几个尾调用.但极端情况下可能有数千人.平台是典型的低端笔记本电脑(例如Core i3或i5).

让我们从 的简单定义开始foldRight：

def foldRight[T, U](base: U)(f: (T, => U) => U)(as: Seq[T]): U = {
  as match {
    case Nil => base
    case head +: next => f(head, foldRight(base)(f)(next))
  }
}

这种组合器的优点之一是它允许我们编写类似的内容（我使用 anif来使 的短路行为||更加明确）：

def containsElement[T](e: T)(as: Seq[T]): Boolean = {
  foldRight(false)((el: T, acc) => if (el == e) true else acc)(as)
}

然后它适用于无限结构：

val bs = 0 #:: 1 #:: 2 #:: 3 #:: LazyList.continually(1)
containsElement(3)(bs)

然而，它不适用于非常长的序列，因为我们正在炸毁堆栈：

val veryLongList = List.fill(1_000_000)(0) …

在这次演讲中,在前8分钟,Runar解释说Scala在消除尾部呼叫方面存在问题,这让我想知道F#是否有类似的问题？如果没有,为什么不呢？

Mono(2.11)上的尾调用优化(TCO)实现的当前状态是什么？在某处读取需要修改所有代码库以使用callee-pops-arguments约定.这种变化的状态如何？ARM/Linux端口是否是最新的？

谢谢!

我从尾调优化问题中获得了动力什么是尾部调用优化？

所以,我决定看看如何在平原C中做到这一点.

所以,我编写了2个阶乘程序,第1个可以应用尾部调用优化.我把这个事实函数称为事实(n,1).

unsigned long long int fact(int n, int cont)
{
      if(n == 0)
            return cont;

      else return fact(n-1, n * cont);
}

2nd是需要多个堆栈帧的正常递归.

unsigned long long int fact(int n)
{
    if(n == 0)
        return 1;

    else return n * fact(n-1);
}

这是由32位编译器为前者生成的-02组件

0x8048470 <fact>:   push   %ebp
0x8048471 <fact+1>: mov    %esp,%ebp
0x8048473 <fact+3>: mov    0x8(%ebp),%edx
0x8048476 <fact+6>: mov    0xc(%ebp),%eax
0x8048479 <fact+9>: test   %edx,%edx
0x804847b <fact+11>:    je     0x8048488 <fact+24>
0x804847d <fact+13>:    lea    0x0(%esi),%esi
0x8048480 <fact+16>:    imul   %edx,%eax
0x8048483 <fact+19>: …