末尾再帰最適化

末尾再帰がちゃんと最適化されるのかどうか気になったので、出来上がった実行ファイルを逆アセンブルして眺めていました。いちごオレを飲みながら。予想通りですが以下のような結果に。（VS2010βまだ入れてないので、例のごとくF#CTP）

書いたコード：

#light

let stopwatch = new System.Diagnostics.Stopwatch()
let gettime (f:Lazy<'a>) =
    stopwatch.Reset() ;
    stopwatch.Start() ; ignore (f.Force()) ; stopwatch.Stop() ;
    stopwatch.Elapsed

(* 通常の斉木さん *)
let rec sum_a = function
    | [] -> 0
    | x :: xs -> x + (sum_a xs)

(* 末尾再帰版 *)
let rec sum_b lst acc =
    match lst with
    | [] -> acc
    | x :: xs -> sum_b xs (x + acc)

(* 畳み込み *)
let sum_c = List.fold_left (+) 0
let sum_d lst = List.fold_right (+) lst 0

let _ =
    let lst = [1..25000]
    let p = printfn "%A ms"
    p <| gettime (lazy (sum_a lst))
    p <| gettime (lazy (sum_b lst 0))
    p <| gettime (lazy (sum_c lst))
    p <| gettime (lazy (sum_d lst))

実行例：

00:00:00.0019770 ms

00:00:00.0005890 ms

00:00:00.0020887 ms

00:00:00.0041452 ms

ビルドして出来上がった実行ファイルを、逆アセンブル。
ただ僕はMSIL読めないダメな子なので、それをさらにC#に変換・・・。
すると次のようになります。

// 普通の斉木さん
public static int sum_a(List<int> _arg1)
{
    if (_arg1 is List<int>._Cons)
    {
        List<int> list = ((List<int>._Cons) _arg1).get___Tail();
        return (((List<int>._Cons) _arg1).get___Head() + sum_a(list));
    }
    return 0;
}

// 末尾再帰（ちゃんとループに置き換わっている）
public static int sum_b(List<int> lst, int acc)
{
    while (lst is List<int>._Cons)
    {
        List<int> list = ((List<int>._Cons) lst).get___Tail();
        int num = ((List<int>._Cons) lst).get___Head();
        acc = num + acc;
        lst = list;
    }
    return acc;
}

次にfold(r|l)ですが、これも予想通り展開のされ方が違う。
しかし何が起こっているのか良く分からない・・・汗

// 先にfold_rightから。まあ普通。
public static int sum_d(List<int> lst)
{
    return ListModule.fold_right<int, int>(new clo@109(), lst, 0);
}

// 次にleft. 色々複雑なことになっている
public static FastFunc<List<int>, int> sum_c
{
    get
    {
        return $Program.sum_c@108;
    }
}
// "sum_c@108" って誰？　別の場所を探してみる・・・
// 〜〜
FastFunc<int, FastFunc<int, int>> func = new Program.clo@108();
sum_c@108 = new Program.clo@108_1(func);
// "clo@108"の中にこいつを見つけた
// 〜〜
public override int Invoke(List<int> arg@108_2)
{
    return ListModule.fold_left<int, int>(this.arg@108, 0, arg@108_2);
}

こんな感じ。
FastFuncは名前からして速そうなので、こいつが何かしてる/されてるのかな。
時間もないし面倒なので（蹴）FastFuncの中身までは追っていない。

ということでおしまい！
On Lispで末尾再帰の練習とかしてたから、末尾再帰の関数はあまり違和感なく書けるなぁ（´ー｀）