标签: tail-call-optimization

我想看看.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？

我曾尝试在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 …

是否有可能在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是否正在做一些阻止堆栈溢出发生的事情？

我编码了3个因子算法:

1. 首先,我希望Stack Overflow失败.没问题.
2. 其次,我尝试尾部重用调用,将先前的算法从递归转换为迭代.它不起作用,但我不明白为什么.
3. 第三,我使用trampoline()方法,并按照我的预期正常工作.

def factorial

factorial = { BigInteger n ->
    if (n == 1) return 1
    n * factorial(n - 1)
}
factorial(1000)  // Stack Overflow

factorial = { Integer n, BigInteger acc = 1 ->
    if (n == 1) return acc
    factorial(n - 1, n * acc)
}
factorial(1000)  // Stack Overflow, why???

factorial = { Integer n, BigInteger acc = 1 ->
     if (n == 1) return acc
     factorial.trampoline(n …

以下程序打击堆栈:

__find_first_occurrence :: (Eq b) => b -> [b] -> Int -> Int
__find_first_occurrence e [] i = -1
__find_first_occurrence e (x:xs) i
    | e == x = i
    | otherwise = __find_first_occurrence e xs (i + 1)

find_first_occurrence :: (Eq a) => a -> [a] -> Int
find_first_occurrence elem list =   
    __find_first_occurrence elem list 0

main = do
    let n = 1000000
    let idx = find_first_occurrence n [1..n]
    putStrLn (show idx)

失败了

堆栈空间溢出:当前大小为8388608字节.使用`+ RTS -Ksize -RTS'来增加它.

但是,据我所知,可能的递归调用__find_first_occurrence是最后评估的事情 …

我在课堂上被告知,由于在递归调用之后计算了布尔运算符,因此以下函数不是尾递归的:

let rec exists p = function
    [] -> false
  | a::l -> p a || exists p l

但是这并没有将堆栈放在1000万大小的列表中,更重要的是,它是标准库中的实现.如果它不是尾递归,则没有理由使用这种形式而不是看似等效且明确的尾递归

let rec exists p = function
    [] -> false
  | a::l -> if p a then true else exists p l

所以看起来OCaml编译器能够在这样的简单情况下优化布尔运算,以利用尾递归.但是我注意到如果我像这样切换操作数的顺序

let rec exists p = function
    [] -> false
  | a::l -> exists p l || p a

然后堆栈确实在10米元素上爆炸.因此,当递归调用出现在右侧时,OCaml似乎只能利用这一点,这让我怀疑所有编译器都会用等效if表达式替换boolean op .有人可以确认或反驳这个吗？

我正在尝试编写一个Scheme解释器,但发现TCO很难实现.我不确定函数必须具有哪些属性才能使TCO启动.

1)在定义结尾处具有自递归调用的函数:

(define (sum-list list accum)
  (if (null list) accum
      (sum-list (cdr list) (+ accum 1))))

2)具有自递归调用的函数,该函数不在定义的末尾:

(define (sum-list list accum)
  (cond ((not (null list))
         (sum-list (cdr list) (+ accum 1)))
        (else accum)))

3)在返回变量之前将递归调用存储在变量中的函数:

(define (sum-list list accum)
  (let ((sum
         (if (null list)
             accum
             (sum-list (cdr list (+ accum 1))))))
    sum))

4)相互递归函数:

(define (sum-list list accum)
  (if (null list)
      accum
      (other-function (cdr list) (+ accum 1))))

(define (other-function list accum)
  (sum-list list accum))

5)在函数定义的末尾简单地调用另一个不相关的函数:

(define (foo)
  (bar))

6)我能想到的最棘手的案例是闭包.如果我坚持对范围变量的引用怎么办？

(define (sum-list …

你有一个递归函数,如:

Blah.prototype.add = function(n) {
    this.total += n;
    this.children.forEach(function(child) {
        child.add(n);
    });
};

是child.add()尾巴吗？如果不能这样写的话呢？

尝试尾调用优化(tco),我偶然发现了以下奇怪的例子:

unsigned long long int fac1(unsigned long long int n){
  if (n==0)
    return 1;
  return n*fac1(n-1);
}

实际上,我印象深刻,gcc能够在这里执行tco(带-O2标志),因为它不是那么直接:

fac1(unsigned long long):
        testq   %rdi, %rdi
        movl    $1, %eax
        je      .L4
.L3:
        imulq   %rdi, %rax
        subq    $1, %rdi
        jne     .L3
        rep ret
.L4:
        rep ret

但是,从返回类型更改unsigned long long int为unsigned intgcc后无法执行tlo:

unsigned int fac2(unsigned long long int n){
  if (n==0)
    return 1;
  return n*fac2(n-1);
}

我们可以清楚地看到生成的程序集中的递归调用:

fac2(unsigned long long):
        testq   %rdi, %rdi
        jne …

我有以下Clojure代码来计算具有某种"可以考虑"属性的数字.(代码究竟做了什么是次要的).

(defn factor-9
  ([]
    (let [digits (take 9 (iterate #(inc %) 1))
          nums (map (fn [x] ,(Integer. (apply str x))) (permutations digits))]
      (some (fn [x] (and (factor-9 x) x)) nums)))
  ([n]
      (or
        (= 1 (count (str n)))
        (and (divisible-by-length n) (factor-9 (quot n 10))))))

现在,我进入TCO并意识到如果使用recur关键字明确告知Clojure只能提供尾递归.所以我重写了代码来做到这一点(用recur代替因子9是唯一的区别):

(defn factor-9
  ([]
    (let [digits (take 9 (iterate #(inc %) 1))
          nums (map (fn [x] ,(Integer. (apply str x))) (permutations digits))]
      (some (fn [x] (and (factor-9 x) x)) nums)))
  ([n]
      (or
        (= 1 …