Есть ли техническая причина, по которой C# не выдает "хвост". Инструкция CIL?

Question

Возможный дубликат:
Почему.net/C# не устраняет хвостовую рекурсию?

Возьмите следующий код C#:

using System;

namespace TailTest
{
    class MainClass
    {
        public static void Main (string[] args)
        {
            Counter(0);
        }

        static void Counter(int i)
        {
            Console.WriteLine(i);
            if (i < int.MaxValue) Counter(++i);
        }
    }
}

Компилятор C# (в любом случае мой) скомпилирует метод Counter в следующий CIL:

.method private static hidebysig default void Counter (int32 i) cil managed 
{
.maxstack 8
IL_0000:  ldarg.0 
IL_0001:  call void class [mscorlib]System.Console::WriteLine(int32)
IL_0006:  ldarg.0 
IL_0007:  ldc.i4 2147483647
IL_000c:  bge IL_0019
IL_0011:  ldarg.0 
IL_0012:  ldc.i4.1 
IL_0013:  add 
IL_0014:  call void class TailTest.MainClass::Counter(int32)
IL_0019:  ret 
}

Проблема с приведенным выше кодом заключается в том, что он вызовет переполнение стека (примерно на i=262000 на моем оборудовании). Чтобы обойти эту проблему, некоторые языки делают то, что называется устранением хвостовых вызовов или оптимизацией хвостовых вызовов (TCO). По сути, они превращают рекурсивный вызов в цикл.

Насколько я понимаю, 64-разрядная реализация.NET 4 JIT теперь выполняет TCO и избегает переполнения кода, подобного приведенному выше CIL. Однако 32-битный JIT этого не делает. Моно тоже не похоже. Интересно, что JIT (который находится под влиянием времени и ресурсов) выполняет TCO, а компилятор C#- нет. Мой вопрос: почему сам компилятор C# не знает больше TCO?

Существует инструкция CIL, которая указывает JIT выполнить TCO. Например, компилятор C# может вместо этого генерировать следующий CIL:

.method private static hidebysig default void Counter (int32 i) cil managed 
{
.maxstack 8
IL_0000:  ldarg.0 
IL_0001:  call void class [mscorlib]System.Console::WriteLine(int32)
IL_0006:  ldarg.0 
IL_0007:  ldc.i4 2147483647
IL_000c:  bge IL_001c
IL_0011:  ldarg.0 
IL_0012:  ldc.i4.1 
IL_0013:  add 
IL_0014:  tail.
IL_0017:  call void class TailTest.MainClass::Counter(int32)
IL_001c:  ret 
}

В отличие от оригинала, этот код не будет переполнен и будет выполняться до конца даже на 32-битном JIT (как.NET, так и Mono). Магия в tail. CIL инструкция. Компиляторы, такие как F#, будут генерировать CIL, который включает эту инструкцию автоматически.

Поэтому мой вопрос: есть ли техническая причина, по которой компилятор C# не делает этого?

Я понимаю, что это исторически, может быть, просто не стоило того. Код как Counter() не было распространено в идиоматических C# и / или.NET Framework. Вы можете легко рассматривать TCO для C# как ненужную или преждевременную оптимизацию.

С появлением LINQ и других вещей кажется, что разработчики как на C#, так и на C# движутся в более функциональных направлениях. Поэтому было бы неплохо, если бы использование рекурсии не было таким небезопасным занятием. Но мой вопрос действительно более технический.

Я упускаю что-то, что делает TCO как это плохой (или рискованной) идеей для C#. Или есть что-то, что делает его особенно сложным, чтобы получить право? Это действительно то, что я надеюсь понять. Любое понимание?

РЕДАКТИРОВАТЬ: Спасибо за отличную информацию. Я просто хотел прояснить, что я не критикую отсутствие или даже требование этой функции. Я не очень заинтересован в рациональной расстановке приоритетов. Мое любопытство заключается в том, какие препятствия я не могу воспринимать или понимать, которые делают это трудным, опасным или нежелательным занятием.

Возможно, другой контекст поможет сосредоточить разговор...

Допустим, я собирался реализовать свой собственный C#-подобный язык в CLR. Почему бы мне (кроме альтернативных издержек) не включить автоматическую и прозрачную эмиссию "хвоста". инструкция где уместно? С какими проблемами я столкнусь или с какими ограничениями я бы столкнулся при поддержке этой функции на языке, очень похожем на C#.

Еще раз спасибо (и заранее) за ответы.

Answer 1

Проверьте следующие ссылки

Почему.NET/C# не оптимизируется для рекурсии хвостового вызова?/ 491463 # 491463
http://social.msdn.microsoft.com/Forums/en-US/netfxtoolsdev/thread/67b6d908-8811-430f-bc84-0081f4393336?StatusCode=1
https://connect.microsoft.com/VisualStudio/feedback/ViewFeedback.aspx?FeedbackID=166013&wa=wsignin1.0

Следующее утверждение является официальным MS (диспетчер программ компилятора Visual C# Люка Хобана) и скопировано с последней ссылки

Спасибо за предложение. Мы рассмотрели возможность использования команд хвостового вызова в ряде моментов при разработке компилятора C#. Однако, есть некоторые тонкие проблемы, которые подтолкнули нас к тому, чтобы избежать этого до сих пор: 1) На самом деле нет нетривиальных накладных расходов на использование инструкции.tail в CLR (это не просто инструкция перехода, поскольку конечные вызовы в конечном итоге становятся во многих менее строгих средах, таких как среды выполнения функциональных языков, где хвостовые вызовы сильно оптимизированы). 2) Существует немного реальных методов C#, в которых было бы законно выдавать хвостовые вызовы (другие языки поощряют шаблоны кодирования, которые имеют большую хвостовую рекурсию, и многие, которые в значительной степени полагаются на оптимизацию хвостовых вызовов, действительно выполняют глобальную переписывание (например, преобразования Continuation Passing).) увеличить количество хвостовой рекурсии). 3) Частично из-за 2) случаи, когда методы C# переполняют стек из-за глубокой рекурсии, которая должна была быть успешной, довольно редки.

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

Answer 2

Хороший вопрос. У меня нет конкретного ответа, но у меня есть мысли, которые могут вас заинтересовать. (Мне уже говорили, что я не должен публиковать такие вещи, как ответы, но эй...) Ответ Яхии выглядит наиболее точным из тех, которые вы можете получить, хотя я также пингую Эрика Липперта, чтобы узнать, он хочет присоединиться.

Часть поста в блоге, на который ссылается Ганс в комментариях, вероятно, расскажет о некоторых его мыслях, но я уверен, что есть и другие:

Меня спрашивают "почему C# не реализует функцию X?" все время. Ответ всегда один и тот же: потому что никто никогда не проектировал, не определял, не реализовывал, не тестировал, не документировал и не поставлял эту функцию. Все шесть из этих вещей необходимы для реализации какой-либо функции. Все они стоят огромных затрат времени, сил и денег. Функции недешевы, и мы очень стараемся, чтобы мы поставляли только те функции, которые дают наилучшие возможные преимущества нашим пользователям, учитывая наши ограниченные затраты времени, усилий и денег.

---

Теперь вернемся к моим собственным мыслям:

Я подозреваю, что это никогда не было приоритетом, но есть веская причина не быть слишком фанатичной: если разработчики собираются полагаться на это, это нужно гарантировать. Вы написали:

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

Теперь посмотрите на сообщение в блоге, объясняющее, когда применяется оптимизация хвостовых вызовов. Это было еще в 2007 году, и в нем прямо говорится:

Обратите внимание, что эти утверждения относятся к JIT таким же, каким они были, когда Грант и Фэй просматривали кодовую базу, и подвержены изменениям прихоти. Вы не должны принимать зависимости от этого поведения. Используйте эту информацию только для личного досуга.

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

Вы абсолютно правы в том, что было бы неплохо, если бы при определенных обстоятельствах использование рекурсии было безопасным, но я полагаю, что это только в том случае, если можно было бы гарантировать безопасность. Если бы это было безопасно в 95% случаев, но 5% было трудно предсказать, у нас было бы множество ошибок "работ на моей машине".

Я хотел бы, чтобы язык C# позволил мне сформулировать требование оптимизации хвостового вызова. Затем компилятор может проверить, что это правильно, и в идеале предоставить JIT больше, чем просто подсказку, что такое поведение требуется. По сути, если я собираюсь сделать рекурсивный контроль, я бы лучше знал, что это сработает. Можете ли вы представить, что сборка мусора была включена только в некоторых конфигурациях? Ик!

Итак, +1 к идее о том, что хвостовая рекурсия является полезной концепцией, но я думаю, что нам нужно больше поддержки со стороны языка, JIT и компилятора, прежде чем его действительно можно будет считать "безопасным".