一个正确实现的递归惰性迭代器函数永远不会堆栈溢出吗？

Question

TL;博士;

在C#中,你是否保证一个懒惰的迭代器函数只调用它本身并且有一个有效的递归退出条件不会导致堆栈溢出？

---

详细问题:

我知道通常你不能保证由C#编译器(或JIT)生成的尾调用优化(TCO)指令,所以虽然你可能得到TCO,但是没有保证.

鉴于TCO的这种认识,我想知道懒惰的迭代器函数(使用yield return等)是否因为它们作为协程的性质 - 每个尾部调用一个甚至占用堆栈空间？由于它们的重新进入,我对协同程序的直觉是默认情况下每个尾调用都被优化为跳出函数并从父框架跳到下一个函数而不是创建新框架的能力似乎很自然.

这是C#中的行为,还是C#迭代器函数的递归调用是从当前创建一个新帧而不是弹出到父帧并使用新参数重新输入？

---

例:

public static IEnumerable<IEnumerable<T>> GeneratePermutations<T>(this IEnumerable<T> choices, int numberToChoose)
{
    if (numberToChoose == 1)
    {
        foreach (var choice in choices)
            yield return new T[] { choice };
        yield break;
    }

    var subPermutations = choices.SelectMany(choice =>
        choices.Where(elem => !EqualityComparer<T>.Default.Equals(elem, choice))
            .GeneratePermutations(numberToChoose - 1)
            .Select(permutation => (new T[] { choice }).Concat(permutation)));
    foreach (var perm in subPermutations)
        yield return perm;
}

我的直觉基于上面的例子subPermutations只是一个堆积的计算,它似乎在调用迭代它,它可以知道它是一个堆积的计算(它是函数sig的一部分,它是一个迭代器函数),因此立即跳转超出它的当前帧并将堆积的计算扩展到一个新的帧 - 在尝试递归调用之前没有额外的堆栈空间...

这种直觉可能完全没有根据......

Answer 1

所以,让我们打开一个示例方法,以便我们可以参考:

public static IEnumerable<int> Foo()
{
    yield return 1;
    foreach (var n in Foo())
        yield return n;
}

这是我们的递归迭代器块.我只想花一点时间来说出这种方法的一些属性,这些属性可能(或可能不)最终具有相关性.

• 有一个递归调用,但递归调用是在a之后yield.

• 当我们这样做达到我们的递归调用,我们那点之后做的唯一的事情是得到它的所有结果.每个项目没有投影,没有finally块,没有任何产量,等等.

那么,当某些代码发生并写下以下内容时会发生什么？

foreach(var n in Foo())
    Console.WriteLine(n);

那么,当我们达到这个陈述时发生的第一件事就是评估Foo()一个值.在这种情况下,这将创建表示序列生成器的状态机.我们实际上并没有执行方法体中的任何代码.

接下来,我们打电话MoveNext.我们点击了第一个yield块,产生了一个值并将其打印出来.

在那之后,最外面的级别MoveNext再次调用.这里我们的状态机的MoveNext方法到达它自己的foreach块.它将像Main方法一样,计算Foo()值,创建第二个状态机.然后它会立即调用MoveNext该状态机.第二个状态机将首先到达它yield,它将产生第一个迭代器的值,这将产生备份到主方法,将打印它.

然后main方法MoveNext再次调用.第一个迭代器向第二个迭代器询问它的第二个项,第二个迭代器到达它的foreach方法,创建第三个迭代器,并从中获取一个值.价值一直向上传递.

正如我们在这里看到的那样,每当我们作为另一个项目的顶级迭代器时,堆栈总是比以前更深一层.尽管我们正在使用状态机,并且创建迭代器不会消耗大量的堆栈空间,但是获取序列中的下一个项目会占用越来越多的堆栈空间,直到我们用完为止.

在运行代码时,我们可以看到完全按照此处所述的方式运行,堆栈将溢出.

那么,这怎么可能被优化呢？

好吧,我们希望在这里做的是让顶级迭代器意识到当它foreach"从现在开始,我的序列中的其余项目与递归调用中的所有项目相同"时.这听起来很像典型的TCO情况.

所以在这一点上我们有两个问题需要解决.首先,如果我们认识到我们处于这种情况,我们是否可以真正避免创建额外的状态机,从而不断增加堆栈空间.它不会那么容易,可能不像传统的非迭代器块TCO那么容易.你需要设置所有的状态机的任何实例字段的实例字段的将是,如果你曾要求将被创建的状态机Foo.我只是在这一点上挥手说这听起来有可能,但并不完全超级.

然后我们有另一个问题.我们如何才能认识到我们实际上处于TCO有效的位置？我们需要以递归方式调用自己,我们需要对该方法调用不做任何事情,除了迭代整个事物并完全按原样产生每个项目,我们不需要在一个try或using块中(否则finally块将丢失) ,迭代后不能有任何方法.

现在,如果有一个yield foreach运营商,那么这不会那么糟糕.您只需设置规则,如果迭代器块中的最后一个语句是一个yield foreach对最终方法进行递归调用的运算符,则应用TCO.遗憾的是,在C#中(与其他一些.NET语言不同),我们没有yield foreach运算符.我们需要输出整个foreach运算符,同时除了完全按原样生成项目之外也不做任何其他操作.这似乎......有点尴尬.

回顾一下:

• 编译器是否可以将Tail Call Optimization用于递归迭代器块？
  • 最有可能的.
• 它是由编译器完成的吗？
  • 它似乎不是这样.
• 将此支持添加到编译器中是否特别可行？
  • 可能不是.