たらい回し関数を書いてみる(1)

前説

たらい回し関数は有名な三引数の再帰関数で、膨大な回数呼ばれる関数です。
関数呼び出しのベンチマークとして使われるそうです。
いろいろな言語でこの関数を実装して実行にかかる時間を計ります。

$ time echo "20 10 0" | ./tarai

引数を標準入力から受け取れるようにします。見ての通り空白で区切って、一行の文字列にしておきます。

たらい回し関数は、三つ目の引数の計算を、必要になるまで遅らせることで実行にかかる時間が短くなることが知られています。
三つ目の引数を整数そのものではなく、整数を返す関数にすることで計算するタイミングを調節できます。

たらい回し関数をこういう風に書くことで、

• 標準入出力とのやりとり
• 関数、無名関数の書き方
• 条件分岐の書き方

を確認することができるので、たらい回し関数は Hello, world の次のお題としていいんじゃないかと個人的に思います。

OCaml

let rec tarai x y z =
  if x <= y then
    y
  else
    let fz = z () in
    let nx = tarai (x - 1) y z in
    let ny = tarai (y - 1) fz (fun () -> x) in
    let nz () = tarai (fz - 1) x (fun () -> y)
    in
    tarai nx ny nz

let () =
  Printf.printf "%d\n"
                (Scanf.scanf "%d %d %d "
                             (fun x y z ->
                              tarai x y (fun () -> z)))

ocamlopt を使うと実行可能なバイナリを生成できます。

$ ocamlopt -o tarai_ocaml tarai.ml
$ ls -lh tarai_ocaml
-rwxr-xr-x  1 hebiyan  staff   690K  1 22 00:13 tarai_ocaml*

サイズを小さくする以外の最適化に関するオプションはなさそう。

実行します。

$ time echo "20 10 0" | ./tarai_ocaml
20

real    0m0.007s
user    0m0.001s
sys     0m0.003s

思ったこと。

• コンパイルしたときに型の間違いがわかるのはありがたい
• 継続を渡す scanf が便利
• 再起関数には再起関数であることを表すキーワードが必要