2007-04-01

コードジェネレータとしての C# イテレータ

.NET

前回 (id:NyaRuRu:20070331:p1) C# のイテレータで「列挙前」の処理を書ける，つまり Enumerator のコンストラクタに実装コードを流し込めると書きましたが，たぶんそういう事実は無いので訂正しておきます．
どういうことかを示すために，次のようなコードを考えましょう．

static IEnumerable<int> Test()
{
    try
    {
        Trace.WriteLine("try Level 0");
        yield return 0;
        try
        {
            Trace.WriteLine("try Level 1");
            yield return 1;
            try
            {
                Trace.WriteLine("try Level 2");
                yield return 2;
            }
            finally
            {
                Trace.WriteLine("finally Level 2");
            }
        }
        finally
        {
            Trace.WriteLine("finally Level 1");
        }
    }
    finally
    {
        Trace.WriteLine("finally Level 0");
    }
}

このコードは，以下のように振る舞うと考えれば良いでしょう．

初めて MoveNext() が呼ばれたとき，イテレータ先頭から最初の yield 文までが実行される．
初回以降は，MoveNext() が呼ばれるたびに，前回停止した yield 文直後から次の yield 文までが実行される．
yield break やイテレータ終端にたどり着いたり，外部から Dispose() が呼ばれた場合は，現在の yield 文直後から return で脱出したかのように finally 句が順番に実行される．

これを確かめてみます．

static void Main(string[] args)
{
    IEnumerable<int> enumerable = Test();
    //(何も表示されていない)
    IEnumerator<int> e = enumerable.GetEnumerator();
    //(何も表示されていない)
    e.MoveNext();
    //(次の文が表示されている)
    // "try Level 0"
    e.MoveNext();
    //(次の文が表示されている)
    // "try Level 0"
    // "try Level 1"
    e.Dispose();
    //(次の文が表示されている)
    // "try Level 0"
    // "try Level 1"
    // "finally Level 1"
    // "finally Level 0"
}

これがつまり，「列挙前」のコードを書けないという意味です．
C# イテレータに書いたコードが初めて実行されるのは，GetEnumerator() 実行時ではなく，初めて IEnumerator<T>.MoveNext() が実行されたときということになります．

2007-04-01

LINQ の世界: deferred query evaluation と immediate query evaluation

.NET

C# のイテレータの振る舞いを理解したところで，次のコードを見てみましょう．

static IEnumerable<int> Rand()
{
    Trace.WriteLine("Generated");
    Random rand = new Random();
    while (true)
    {
        yield return rand.Next();
    }
}

このイテレータは，見ての通り無限に疑似乱数列を返すというものです．先ほど述べたように，"Generated" と表示されるのは初めて MoveNext() が実行されたときであることに注意しておきましょう．
さて，C# 3.0 LINQ の Take メソッドを使用し，この疑似乱数列から 10 個の要素を取り出してみます．と，ここでクイズです．

static void Main(string[] args)
{
    var seq = Rand().Take(10);
    // Q1: ここで "Generated" と表示されているか？
    var x = seq.First();
    var y = seq.First();
    // Q2: ここで何回 "Generated" と表示されているか？
    // Q3: x == y は成り立つか？
    int i = 0;
    foreach (var val in seq)
    {
        ++i;
    }
    // Q4: i の値はいくら？
}

結果はこうなります．

"Generated" は表示されていない．
"Generated" は 2 回表示されている．
x == y は必ずしも成り立たない
i は 10

LINQ の用語*1で言えば，Rand().Take(10) は deferred query evaluation (遅延クエリ評価) に該当し，First() や foreach などで評価されるたびに「疑似乱数列から 10 回取り出し，それを出力する数列」が新しく生成されています．Q1 で "Generated" が出力されていないのも，First() の結果が一致しないのも，seq が評価されるたびに新しい列 (シーケンス) を返すためです．
deferred query evaluation と対になる形で，即座に値を確定させるクエリは immediate query evaluation と呼ばれています．
結局この手の話になるということは，関数型言語の使用経験がある方ならまあ予想はついていたかと思います．
個人的な意見ですが，enumerate することで deferred query evaluation が起きるような変数は，それをハンガリアン記法で明記しておくのもアリだと思います．

次のコードは，評価するたびに「疑似乱数列から 1000 回取り出し，それを昇順ソートした結果を出力する数列」を返すようなクエリです．

var seq2 = from n in Rand().Take(1000) orderby n select n;

ソートといえば，関数型言語の記述の簡潔さを示すために qsort の実装例がしばしば示されます．IList<T> に対する qsort を LINQ で書いてみました．(変更: List<T> → IList<T>)

using System.Linq;
public static IList<T> qsort<T>(IList<T> list)
    where T : IComparable<T>
{
    if (list.Count < 2)
    {
        return list;
    }
    T pivot = list.First();
    var rest = list.Skip(1);
    var first = from x in rest
                where Comparer<T>.Default.Compare(pivot, x) >= 0 select x;
    var second = from x in rest
                 where Comparer<T>.Default.Compare(pivot, x) < 0 select x;
    return qsort(first.ToList())
        .Concat(Enumerable.Repeat<T>(pivot, 1))
        .Concat(qsort(second.ToList()))
        .ToList();
}
var seq3 = qsort( Rand().Take(10).ToList() );

上のクエリは即時評価が行われ，seq3 には List<int> が入ります．これを遅延クエリ評価の形に書き直すとしたら，例えばこういう感じでしょうか？

public static IEnumerable<T> queryQsort<T>(IEnumerable<T> source)
    where T : IComparable<T>
{
    List<T> list = source.ToList();
    foreach (T t in qsort(list))
    {
        yield return t;
    }
}
var seq4 = queryQsort( Rand().Take(10) );

*1:CTP 付属のヘルプの LINQ Glossary 参照のこと