例外処理と末尾再帰（Re: OCamlの末尾再帰について） #OCaml

この記事はMLアドベントカレンダー23日目の記事です。22日目の記事は autotaker さんのOCamlの末尾再帰についてでした。この記事は autotaker さんの記事の read_ints 関数に対する別解です。前半は、既に autotaker さんの記事を読んでいる人は読み飛ばしても大丈夫です。

例外を投げる関数を呼び出しつつ末尾再帰的な関数を書こうとすると意外なほど落とし穴にはまる。

上記の記事と同じく、 End_of_file 例外が発生するまで read_int で標準入力から int の値を読み込み、読み込んだ値をリストにして返す関数を書こうとすると、最初は次のようなコードを書きがちだ（好みにより、 read_ints の引数に累積値を取るのではなくローカル関数を使うようにしている）。

let read_ints () =
  let rec loop acc =
    try
      let v = read_int () in
      loop @@ v::acc
    with End_of_file -> List.rev acc
  in loop []

だが、これは loop の再帰呼び出しから返ったあとに例外ハンドラをもとに戻すという処理があるため末尾再帰にはならない。

なので、元記事では、例外を option に変換した上で、 try 〜 with の外側で再帰呼び出しをするようにしている。

let read_ints () =
  let rec loop acc =
    let v = try Some (read_int ()) with End_of_file -> None in
    match v with
    | Some v -> loop @@ v::acc
    | None -> List.rev acc
  in loop []

で、これで末尾再帰にはなるのだが、末尾再帰にするためだけに一瞬だけ Some で包んですぐに剥がすのは何だか無駄な気がしてしまう。

実は OCaml 4.02.0 から match 式に exception パターンを書けるようになったので、もう少しスマートに書ける。

let read_ints () =
  let rec loop acc =
    match read_int () with
    | v -> loop @@ v::acc
    | exception End_of_file -> List.rev acc
  in loop []

マッチ対象の式（ここでは read_int ()）の評価中のみ例外ハンドラを設定し、例外が発生したら exception パターンと例外を照合し、例外が発生しなければ式の値を exception パターン以外のパターンと照合する。各場合の矢印の右側の式には例外ハンドラは設定されないので、この loop の呼び出しは末尾呼び出しになる。

下のような適当なエントリポイントをつけて、 yes 1 | head -n 10000000 | ./a.out などとしてコンパイルしたプログラムを実行するとスタックがあふれないことが確認できる。

let () =
  read_ints () |> List.length |> string_of_int |> print_endline