OCamlとTail Call

JavaScriptを有効にしてください

OCamlとTail Call

📅 2021/10/8 · ☕ 2 min read

末尾再帰について一度整理しておく.
→ OCaml, Haskell, Scala など多くの関数型言語の処理系は末尾再帰を最適化.

末尾呼び出し

1
2
3
4
5
6
7
8


fn f(x: T) {
    if isTrue(hoge) { // not 末尾呼び出し
        return g(); // 末尾呼び出し
    }
    else {
        return x * h(); // not 末尾呼び出し
    }
}

末尾再帰

1
2
3
4
5
6
7
8


fn f(x: T) {
    if isTrue(hoge) {
        return f(x); // 末尾再帰
    }
    else {
        return x * f(x); // not 末尾再帰
    }
}

→ 末尾再帰はコールスタックを食いつぶさない

コールスタック

通常のプログラムの実行モデルでは、関数を呼び出すと、関数自身のローカル変数（引数や局所変数）や戻り先情報を保持するスタックフレーム（アクティベーションレコード）が生成されてコールスタックと呼ばれるスタックにpushされます。

→ 末尾再帰だとそのままスタックフレームを再利用できる
(末尾再帰じゃないと再利用できない)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


// 階乗を計算する関数（末尾再帰バージョン）
function factorial(n) {

    // 末尾再帰関数
    function factorialTailCall(n, accum) {
        if (n === 0) {
            return accum;
        }
        return factorialTailCall(n - 1, n * accum); // 自分自身を末尾呼び出し
    }

    var result = factorialTailCall(n, 1);

    return result;
}

console.log(factorial(3));

OCamlの例

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


# let rec f n =
    let rec iter i =
      if i < n then begin
        print_int i;
        iter (i + 1)
      end
    in
    iter 0;;

val f : int -> unit = <fun>

参考: https://qiita.com/pebblip/items/cf8d3230969b2f6b3132#末尾呼び出しと末尾呼び出し最適化

著者

YuWd (Yuiga Wada)

機械学習・競プロ・iOS・Web

OCamlとTail Call

関連記事