标签: tail-call-optimization

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

谢谢!

我看到了几个append向列表实现元素的例子,但都没有使用尾递归.如何在功能风格中实现这样的功能？

 (define (append-list lst elem) expr)

我在F#中使用定点组合器时遇到问题:

let rec fix f a = f (fix f) a

fix (fun body num -> 
    if num = 1000000 
    then System.Console.WriteLine "Done!" 
    else body (num + 1)
) 0

(此代码仅用于演示问题,它是专门编写的,因此生成的IL代码易于阅读.)

此代码 - 在使用优化和尾调功能进行编译时 - 会导致a StackOverflowException.我查看了IL代码,可以将问题跟踪到调用内的lambda fix:

.method assembly static void f@1 (class FSharpFunc`2<int32, class Unit> body,int32 num)
{
ldarg.1
ldc.i4 1000000
bne.un.s IL_0014

ldstr "Done!"
call void Console::WriteLine(string)
ret

IL_0014: ldarg.0 // Load the 'body' function onto the stack.
ldarg.1 // Load num onto the stack. …

我想看看.tailIL指令,但是我使用尾调用的简单递归函数显然已优化为循环.我实际上正在猜测这个,因为我不完全确定Reflector中的循环是什么样的.我绝对没有看到任何.tail操作码.我在项目的属性中检查了"生成尾调用".我也在Reflector中尝试了Debug和Release版本.

我使用的代码来自Chris Smith的Programming F#,第190页:

let factorial x =
// Keep track of both x and an accumulator value (acc)
let rec tailRecursiveFactorial x acc =
    if x <= 1 then
        acc
    else
        tailRecursiveFactorial (x - 1) (acc * x)
tailRecursiveFactorial x 1

任何人都可以建议一些简单的F#代码,它们确实会生成.tail？

我刚刚在2天前创建了Haskell,所以我还不确定如何优化我的代码.

作为练习,我已经改写foldl和foldr(我会给foldl这里却foldr是一样的,更换last用head和init用tail).

代码是:

module Main where

    myFoldl :: ( a -> ( b -> a ) ) -> a -> ( [b] -> a )

    myFoldl func = ( \x -> (\theList
        -> if (length theList == 0) then
            x
        else
            myFoldl func (func x (last theList) ) (init theList)
        ) )

我唯一关心的是我怀疑Haskell不能在这里应用尾调用优化,因为递归调用不是在函数结束时进行的.

如何优化尾调用？Haskell的内置foldl实现是否与我的实现方式不同？

我曾尝试在GCC 4.4.5在Linux在Mac OSX(4.2.1的Xcode)和下面的代码和gcc-LLVM 此.以下是相关功能的来源和生成的反汇编.(补充:编译gcc -O2 main.c)

#include <stdio.h>
__attribute__((noinline))
static void g(long num)
{
        long m, n;
        printf("%p %ld\n", &m, n);
        return g(num-1);
}
__attribute__((noinline))
static void h(long num)
{
        long m, n;
        printf("%ld %ld\n", m, n);
        return h(num-1);
}
__attribute__((noinline))
static void f(long * num)
{
        scanf("%ld", num);
        g(*num);
        h(*num);        
        return f(num);
}
int main(void)
{
        printf("int:%lu long:%lu unsigned:%lu\n", sizeof(int), sizeof(long), sizeof(unsigned));
        long num;
        f(&num);                 
        return 0;
}

08048430 <g>:
8048430:    55                   push   %ebp
8048431:    89 …

我来自函数式编程背景,首先考虑问题的递归解决方案而不是迭代解决方案.我开始使用Rebol(特别是R3),并使用带累加器的尾递归函数为primefactor kata编写了一个解决方案.但是如果有足够大的输入,我会把堆叠吹掉.我有一个名为"tail-func.r"的Rebol2脚本,它实现了AFAIK尚未移植到R3的尾调用优化版本.我知道在很多情况下Rebol 3的实现方式与R2不同,所以有没有办法在Rebol 3中获得TCO而不需要任何额外的代码？如果没有,是否有更简单的方法来获得它而不移植旧脚本？

编辑添加我的代码:

primefactors: function [n m factors] [
  either n > 1
    [ either (modulo n m) == 0
      [ primefactors (n / m) m (append factors m) ]
      [ primefactors n (m + 1) factors ] ]
    [ factors ]
  ]

  primefactors 30 2 (copy []) => [2 3 5]

是否有可能在Erlang中获得一个不是尾部调用优化函数的stackoverflow？例如,假设我有这样的功能

sum_list([],Acc) ->
   Acc;
sum_list([Head|Tail],Acc) ->
   Head + sum_list(Tail, Acc).

看起来如果在它中传递足够大的列表最终会耗尽堆栈空间并崩溃.我尝试过这样测试:

> L = lists:seq(1, 10000000).
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22, 23,24,25,26,27,28,29|...]
> sum_test:sum_list(L, 0).
50000005000000

但它永远不会崩溃!我尝试了一个100,000,000整数的列表,它花了一段时间才完成,但它仍然没有崩溃!问题:

1. 我正确测试了吗？
2. 如果是这样,为什么我无法生成stackoverflow？
3. Erlang是否正在做一些阻止堆栈溢出发生的事情？

见BlendingTable::create和BlendingTable::print.两者都具有相同形式的尾递归,但是虽然create将被优化为循环,但print不会导致堆栈溢出.

下来看一个修复,我从一个gcc开发人员的提示中得到了我的错误报告中的问题.

#include <cstdlib>
#include <iostream>
#include <memory>
#include <array>
#include <limits>

class System {
public:
    template<typename T, typename... Ts>
    static void print(const T& t, const Ts&... ts) {
        std::cout << t << std::flush;
        print(ts...);
    }

    static void print() {}

    template<typename... Ts>
    static void printLine(const Ts&... ts) {
        print(ts..., '\n');
    }
};

template<typename T, int dimension = 1>
class Array {
private:
    std::unique_ptr<T[]> pointer;
    std::array<int, dimension> sizes;
    int realSize;

public:
    Array() {} …

我正在试验Haskell中的外部函数接口.我想实现一个简单的测试,看看我是否可以进行相互递归.所以,我创建了以下Haskell代码:

module MutualRecursion where
import Data.Int

foreign import ccall countdownC::Int32->IO ()
foreign export ccall countdownHaskell::Int32->IO()

countdownHaskell::Int32->IO()
countdownHaskell n = print n >> if n > 0 then countdownC (pred n) else return ()

请注意,递归情况是对countdownC的调用,因此这应该是尾递归的.

在我的C代码中,我有

#include <stdio.h>

#include "MutualRecursionHaskell_stub.h"

void countdownC(int count)
{
    printf("%d\n", count);
    if(count > 0)
        return countdownHaskell(count-1);
}

int main(int argc, char* argv[])
{
    hs_init(&argc, &argv);

    countdownHaskell(10000);

    hs_exit();
    return 0;
}

这同样是尾递归.那我就做了

MutualRecursion: MutualRecursionHaskell_stub
    ghc -O2 -no-hs-main MutualRecursionC.c MutualRecursionHaskell.o -o MutualRecursion
MutualRecursionHaskell_stub:
    ghc -O2 -c MutualRecursionHaskell.hs

并编译 …