C# 3.0 と不動点演算子

C# 3.0 とラムダ計算のお話.
英語圏の C# 系 blog では,ラムダ計算が周期的に話題に上り,相互にゆるやかなクラスタを形成しているように感じます.『New Series on Closures in Visual Basic 9.0』というエントリが良い感じに Hub になっていますので,ここを出発点にすると良いでしょう.
今回は Mads Torgersen 氏の『Recursive lambda expressions』を参考に不動点演算子 Fix を作ってみます.

public static class ExprUtil
{
    public static class Fun<T>
    {
        public delegate U SelfApplicable<U>(SelfApplicable<U> self);
        public static SelfApplicable<Func<Func<Func<T, T>, Func<T, T>>, Func<T, T>>>
            Y = y => f => x => f(y(y)(f))(x);
        public static Func<Func<Func<T, T>, Func<T, T>>, Func<T, T>> Fix = Y(Y);
    }
    public static Func<T,T> Fix<T>(Func<Func<T, T>, Func<T, T>> func)
    {
        return Fun<T>.Fix(func);
    }
    public static Func<T, T> Fix<T>(T dummy, Func<Func<T, T>, Func<T, T>> func)
    {
        return Fun<T>.Fix(func);
    }
}

よくあるように階乗計算を書いてみましょう.

var fact1 =
    ExprUtil.Fix<int>(
        fac => x => x == 0 ? 1 : x * fac(x - 1)
    );
Console.WriteLine("10! = {0}", fact1(10));

型推論とダミー引数を利用すれば,匿名型を引数にすることもできます.

var fact2 =
    ExprUtil.Fix(new { N = 0, Ret = 0 },
        fac => arg => arg.N == 0 ?
            new { N = 0, Ret = arg.Ret } :
            fac(new { N = arg.N - 1, Ret = arg.Ret * arg.N })
    );
Console.WriteLine("10! = {0}", fact2(new { N = 10, Ret = 1 }).Ret);

もっとも,ここで定義した Fix は再帰呼び出しのたびにスタックを消費しますので,実用上このままではループの代用にはなりません.
一方,F# コンパイラは末尾再帰をループに変換してくれるようです.例えば以下のような F# のコードを考えます.
(追記) なんか if 文が気持ち悪かったのでパターンマッチに書き換えました.

#light
let fact n = 
    let rec factInner (n, ret) =
        match (n, ret) with
        | (0, ret) -> (0, ret)
        | (n, ret) -> factInner (n-1, n*ret)            
    let (_, result) = factInner (n, 1)
    result
    
let ret = fact 10
print_int ret

このコードをコンパイルし,.NET Reflector を使って計算のコア部分がどうなっているかを見てみましょう.C# コードに再変換してみます.

internal static Tuple<int, int> factInner$detupled@4@4(int y0, int y1)
{
    while (true)
    {
        switch (y0)
        {
            case 0:
                return new Tuple<int, int>(0, y1);
        }
        y1 = y0 * y1;
        y0--;
    }
}

F# コンパイラによって,末尾再帰がループに変換されていることが分かります.
さてさて,それでは C# で再帰的なラムダ式を書くことに意味はないかというと,Expression Trees を通してその部分だけ隔離計算してしまうという可能性が考えられます.が,これについてはまた今度.