LINQメソッドのストリーミングと非ストリーミング

この前私の無知ゆえにTwitterで議論を起こしてしまったのでここにまとめておきます。

LINQの基本的な思想として遅延評価というものがあります。

Console.WriteLine("Start");
var e = Enumerable.Range(0, 10).Select(p => { Console.WriteLine(p); return p; });
Console.WriteLine("foreach Starting");
foreach(int i in e)
    Console.WriteLine("foreach " + i);

例えばこんなプログラムを実行したらどのような結果が出力されるでしょう。

Start
foreach Starting
0
foreach 0
1
foreach 1
2
foreach 2
3
foreach 3
4
foreach 4
5
foreach 5
6
foreach 6
7
foreach 7
8
foreach 8
9
foreach 9

こんな出力がされます。Select()メソッドが呼ばれたときではなく、値が必要になったときに値が列挙されています。これが遅延評価です。
では、次のようなコードの場合どうなるでしょう。Select()の後ろにReverse()が付きました。

Console.WriteLine("Start");
var e = Enumerable.Range(0, 10).Select(p => { Console.WriteLine(p); return p; }).Reverse();
Console.WriteLine("foreach Starting");
foreach(int i in e)
    Console.WriteLine("foreach " + i);

実行結果はこんな感じになります。

Start
foreach Starting
0
1
2
3
4
5
6
7
8
9
foreach 9
foreach 8
foreach 7
foreach 6
foreach 5
foreach 4
foreach 3
foreach 2
foreach 1
foreach 0

先ほどと違って、foreachで各値が列挙されるごとに1回ずつSelect()に与えたデリゲートが呼ばれるのではなく、foreachが始まるときに全ての値が評価されたうえで逆順に列挙されています。
というのも割と当然で、IEnumerator<T>は現在の値を示すCurrentプロパティと次の値へ移動するMoveNext()メソッドしか持っていません（まあReset()とかDispose()とかありますがここでは関係ないので置いておきます）。すなわち、コレクションを逆順にたどることができないので、Reverse()が返すIEnumerable<T>のオブジェクトは、いったん全ての値を評価して配列とかにストックしておき、それを逆順に返すことでその機能を実現しています。

私は、これを遅延評価とは言わないと思ってしまっていました。
最初の例のように、その値を使用しようとしたときに初めて評価するような機構が遅延評価であり、そうすることで分散してデータベースにアクセスすることができるメリットが享受できるところまで含めて遅延評価の定義だと認識していました。そのため、いったん全ての値を評価しないと最初の値を提供できないReverse()メソッドは遅延評価に当たらないと思っていました。

しかし、上記のWikipediaを見ていただくとわかるように、遅延評価そのものの定義には分散といったような言葉は出てきません。遅延評価では分散して実行できることは保証されておらず、都合が良いデータならもしかしたら分散して処理できるかもしれないくらいのもののようです。いわば、分散して処理ができるのは遅延評価の効果でしかなく、あくまでも「必要になった時に必要最低限の評価をする」が遅延評価です。

後者の場合もforeachが始まるまで値は評価されていません。なので遅延評価です。ただし、始まった瞬間に全ての値を評価しないと逆転させた時の最初の値（＝元のコレクションの最後の値）がわからないので、必要最小限の評価として全ての値を評価しているというだけのことです。

私のこのもともとの発想は実は遅延評価とは若干違ったところで存在していたようです。

実行方法による標準クエリ演算子の分類

LINQには「即時評価」と「遅延評価」の2種類のメソッドがあり、その遅延評価のメソッドはさらに「ストリーミング」と「非ストリーミング」に分類できるようです。私がもともと遅延評価の定義だと勘違いしていた「実行時に分散的に評価を行う」メソッドがここでいうストリーミングに分類されます。逆に遅延評価ではあるけど、評価開始時にすべての値を評価してしまうのが「非ストリーミング」に分類されています。
例えばSelect()はストリーミングですが、Reverse()は非ストリーミングになっています。なるほど納得です。
ちなみに、ストリーミングと非ストリーミングの両方にチェックが付いているものがあります。例えばExcept()なんかがそれです。2つ以上のコレクションを扱うメソッドのときは両方の特性が付く場合があるようで、Except()の場合は例えばsecondで与えたコレクションを全て評価しないとその値を持つかどうかがわからないので、そういった仕様になっているということです。firstの値そのものはストリーミングで実行されます。


これでまた一つ賢くなりました。
今後LINQを使うときは単に「遅延評価」だけでなく、この辺も意識しながら使いたいですね。