Будет ли правильно реализованная рекурсивная ленивая функция итератора никогда не переполнять стек?

TL;DR;

В С# у вас есть гарантии, что ленивая функция итератора, которая ничего не вызывает, кроме самой себя и не имеет допустимого условия выхода из рекурсии, не приведет к переполнению стека?

Подробный вопрос:

Я знаю, что, как правило, вы не получаете гарантий от команды Tail Call Optimization (TCO), генерируемой компилятором С# (или JIT), поэтому, пока вы можете получить TCO, никаких гарантий нет.

Учитывая это признание TCO, мне интересно, работают ли ленивые функции итератора (используя yield return и т.д.) из-за их природы в качестве сопрограммы - каждый хвостовой вызов в одном даже занимает пространство стека? Моя интуиция сопрограмм из-за их повторного входа состоит в том, что каждый хвостовой вызов оптимизируется по умолчанию, поскольку способность выпрыгивать из функции и в следующую из родительского кадра вместо создания нового кадра кажется естественным.

Является ли это поведение в С# или рекурсивными вызовами функций С# -тератора С# создает новый кадр из текущего, а не появляется в родительский фрейм и повторно вводится с новыми параметрами?

Пример:

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, что она является функцией итератора), и, следовательно, немедленно выскочить из этого текущего кадра и расширить вычисление кучи в новый фрейм - не обойдя лишнее пространство стека над тем, что было до попытки рекурсивного вызова...

Эта интуиция может быть абсолютно необоснованной...

Ответ 1

Итак, пусть откроется с помощью примерного метода, так что у нас есть что-то для ссылки:

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

Здесь наш рекурсивный блок итератора. Я просто хочу воспользоваться моментом, чтобы вызывать несколько свойств этого метода, которые могут (или не могут) оказаться релевантными.

Существует рекурсивный вызов, но рекурсивный вызов выполняется после yield.
Когда мы достигаем нашего рекурсивного вызова, единственное, что мы делаем после этого момента, - это результат всех его результатов. Нет проекции на каждый элемент, блок finally, ничего после этих выходов и т.д.

Итак, что происходит, когда идет какой-то код, и записывает следующее?

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

Ну, первое, что происходит, когда мы достигаем этого утверждения, - это оценить Foo() значение. В этом случае создается машина состояний, которая представляет генератор последовательности. Однако мы фактически не выполнили какой-либо код в модуле метода.

Далее, мы называем MoveNext. Мы попали в наш первый блок yield, дали значение и распечатали его.

После этого внешний уровень больше всего вызывает MoveNext. Здесь наш метод состояния MoveNext достигает своего собственного блока foreach. Он, подобно методу Main, оценит значение Foo() на значение, создав второй конечный автомат. Затем он немедленно вызовет MoveNext на этом конечном автомате. Этот второй конечный автомат достигнет его сначала yield, он даст значение первому итератору, что приведет к возврату к основному методу, который будет печатать его.

Затем основной метод снова вызывает MoveNext. Первый итератор запрашивает у второго итератора второй элемент, второй итератор достигает его foreach, создает третий итератор и получает от него значение. Значение передается полностью.

Как мы видим здесь каждый раз, когда мы, как наш итератор верхнего уровня для другого элемента, стек всегда на один уровень глубже, чем раньше. Несмотря на то, что мы используем государственные машины, и что создание итераторов не требует много места в стеке, получение следующего элемента в последовательности будет потреблять все больше и больше пространства стека, пока мы не закончим.

При запуске кода мы видим, что все работает точно так, как описано здесь, и стек будет переполняться.

Итак, как это можно оптимизировать?

Хорошо, что мы надеемся сделать здесь, для этого итератора верхнего уровня, чтобы понять, что, когда он доберется до foreach, который "отныне, остальные элементы в моей последовательности идентичны всем элементы в рекурсивном вызове". Это очень похоже на типичную ситуацию с TCO.

Итак, на данный момент у нас есть два вопроса, которые нужно решить. Во-первых, если мы осознаем, что мы находимся в этой ситуации, можем ли мы фактически избежать создания дополнительных состояний машин и, следовательно, постоянно увеличивать пространство стека. Это было бы не так просто, скорее всего, не так просто, как традиционная не-итераторная блочная TCO. Вам нужно будет установить все поля экземпляра конечного автомата на все поля экземпляра конечного автомата, которые будут созданы, если вы вызвали Foo. Я просто буду махать руками в этот момент и сказать, что это звучит возможно, но не совсем супер.

Тогда у нас есть другая проблема. Как мы можем признать, что мы действительно находимся в этой должности, где действительна ТШО? Нам нужно рекурсивно называть себя, мы должны ничего не делать с этим вызовом метода, кроме как итерации всего предмета и получения каждого элемента в точности, как он есть, нам не нужно быть в блоке try или using (иначе блок finally будет потерян), и после этой итерации не может быть никаких методов.

Теперь, если бы существовал оператор yield foreach, тогда это было бы не так уж плохо. Вы просто установили правило, что если последний оператор в блоке итератора является оператором yield foreach с рекурсивным вызовом метода в самом конце, примените TCO. К сожалению, в С# (в отличие от некоторых других языков .NET) у нас нет оператора yield foreach. Нам нужно напечатать весь оператор foreach, а также не делать ничего, кроме того, что он дает именно то, что ему нужно. Кажется... немного неудобно.

Повторить:

Возможно ли, чтобы компилятор использовал оптимизацию Tail Call для рекурсивных блоков итератора?
- Скорее всего.
Это делается компилятором?
- Это не так.
Было бы особенно целесообразно добавить эту поддержку в компилятор?
- Возможно, нет.