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

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

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

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);
        }
    }
}

Компилятор С# (мой в любом случае) скомпилирует метод 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 
}

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

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

Существует инструкция CIL, которая сообщает JIT выполнять TCO. Например, компилятор С# мог бы сгенерировать следующий 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, который включает эту инструкцию автоматически.

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

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

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

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

EDIT: Спасибо за отличную информацию. Я просто хотел быть ясным, что я не критикую отсутствие или даже требование этой функции. Я не очень заинтересован в рациональном распределении приоритетов. Мое любопытство - это то, что препятствия я не могу понять или понять, что делает это трудным, опасным или нежелательным делом.

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

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

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

Ответ 1

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

Почему .NET/С# не оптимизируется для рекурсии хвоста? /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 (Luke Hoban Visual С# Program Manager) и скопирован из последней ссылки

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

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

Ответ 2

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

Часть сообщения . Ханс, связанный с комментариями, вероятно, рассмотрит некоторые из его мыслей, но я уверен, что есть больше:

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

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

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

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

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

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

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

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

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

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