26

重複の可能性:
.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)と呼ばれるものを実行します。基本的に、再帰呼び出しをループに変えます。

私の理解では、.NET 4 JITの64ビット実装はTCOを実行し、上記のCILのようなコードのオーバーフローを回避します。ただし、32ビットJITはそうではありません。モノもそうではないようです。JIT(時間とリソースのプレッシャーにさらされている)がTCOを実行するのに対し、C#コンパイラーは実行しないのは興味深いことです。私の質問は、C#コンパイラ自体がTCOに対応していないのはなぜですか?

JITにTCOを実行するように指示するCIL命令があります。たとえば、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フレームワークでは一般的ではありませんでした。C#のTCOは、不要または時期尚早の最適化と簡単に見なすことができます。

LINQなどの導入により、C#とC#の両方の開発者がより機能的な方向に進んでいるようです。したがって、再帰を使用することがそれほど危険なことではなかったとしたら、それは素晴らしいことです。しかし、私の質問は実際にはもっと技術的なものです。

このようなTCOをC#にとって悪い考え(または危険な考え)にする何かが欠けています。それとも、正しく理解するのが特に難しいものはありますか?それが私が理解したいと思っていることです。何か洞察はありますか?

編集:素晴らしい情報をありがとう。この機能の欠如を批判したり、要求したりしていないことを明確にしたかっただけです。私は優先順位付けに関する合理性にはあまり興味がありません。私の好奇心は、これを困難、危険、または望ましくないものにする障害を認識または理解できない可能性があることです。

おそらく、別のコンテキストが会話に集中するのに役立ちます...

CLRに独自のC#のような言語を実装しようとしていたとしましょう。なぜ私は(機会費用以外に)「尾」の自動で透明な放出を含めないのでしょうか。必要に応じて指示?C#に非常によく似た言語でこの機能をサポートする際に、どのような課題に直面したり、どのような制約を導入したりしますか。

返信ありがとうございます(そして事前に)。

4

2 に答える 2

12

次のリンクを確認してください

.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の公式(Luke Hoban Visual C#コンパイラプログラムマネージャー)であり、最後のリンクからコピーされています

提案をありがとう。C#コンパイラの開発では、いくつかのポイントで末尾呼び出し命令を発行することを検討しました。ただし、これまでのところこれを回避するように促している微妙な問題がいくつかあります。1)CLRで.tail命令を使用すると、実際には重要なオーバーヘッドコストが発生します(末尾呼び出しが最終的にはジャンプ命令になるだけではありません)。末尾呼び出しが大幅に最適化されている関数型言語ランタイム環境など、それほど厳密ではない多くの環境で)。2)末尾呼び出しを発行することが合法である実際のC#メソッドはほとんどありません(他の言語では、末尾再帰が多いコーディングパターンが推奨されます。また、末尾呼び出しの最適化に大きく依存している多くのユーザーは、実際にはグローバルな書き換え(継続渡し変換など)を実行して、末尾再帰の量を増やしています。3)2)の理由もあり、成功するはずの深い再帰が原因でC#メソッドがスタックオーバーフローするケースはかなりまれです。

とはいえ、私たちはこれを引き続き検討しており、コンパイラの将来のリリースで、.tail命令を発行することが理にかなっているいくつかのパターンを見つける可能性があります。

于 2011-08-17T16:24:57.347 に答える
7

良い質問。具体的な答えはありませんが、おもしろいと思います。(以前、回答などを投稿するべきではないと言われましたが、ちょっと...)Yahiaの回答は、Eric Lippertにpingを送信して確認しますが、最も確実な回答のように見えます。彼はチャイムを鳴らしたいと思っています。

コメントでリンクされているハンスのブログ投稿の一部は、おそらく彼の考えのいくつかをカバーしているでしょうが、もっとあると確信しています:

「なぜC#は機能Xを実装しないのですか?」と尋ねられます。いつも。答えは常に同じです。その機能を設計、指定、実装、テスト、文書化、および出荷した人は誰もいないからです。機能を実現するには、これら6つすべてが必要です。それらはすべて、膨大な時間、労力、およびお金を要します。機能は安くはありません。時間、労力、費用の制約を考慮して、ユーザーに可能な限り最高のメリットをもたらす機能のみを出荷するように努めています。


さて、私自身の考えに戻りましょう。

私はそれが決して優先事項ではなかったと思うが、それについてあまりガンホーにならないのには十分な理由がある:開発者がそれに依存するつもりなら、それは保証される必要がある。あなたが書いた:

したがって、再帰を使用することがそれほど危険なことではなかったとしたら、それは素晴らしいことです。しかし、私の質問は実際にはもっと技術的なものです。

次に、末尾呼び出しの最適化がいつ適用されるかを説明するブログ投稿を見てください。それは2007年にさかのぼり、次のように明示的に述べています。

これらのステートメントは、GrantとFeiがコードベースを調べたときと同じようにJITに適用され、気まぐれに変更される傾向があることに注意してください。この動作に依存してはなりません。この情報は、個人的な娯楽にのみ使用してください。

次に、末尾呼び出しが適用される前に必要な条件の長いリストがあります。それらの多くは、コーダーの観点から推測するのは簡単ではありません。

特定の状況で再帰を使用することが安全であるとよいのは間違いありませんが、それが安全であることが保証された場合にのみ当てはまると思います。95%のケースで安全であったが、5%を予測するのが困難だった場合、「私のマシンで動作する」バグがたくさんあります。

私が望んでいるのは、C#言語で、末尾呼び出しの最適化の要件を述べることができるようにすることです。次に、コンパイラーはそれが正しいことを検証し、理想的には、この動作が必要であるという単なるヒント以上のものをJITに提供することができます。基本的に、私がやや制御されていない方法で再帰する場合は、それが機能することを知っている方がよいでしょう。ガベージコレクションが一部の構成でのみ有効になっていると想像できますか?えっ!

したがって、末尾再帰が有用な概念であるという考えに+1しますが、実際に「安全」と見なされるには、言語、JIT 、およびコンパイラからのサポートがさらに必要だと思います。

于 2011-08-17T16:31:03.250 に答える