#007 再帰の泣き所

今回のPPLサマースクール （ココも参照）は非常に参考になった． 関数型言語の実装についてはある程度分かった気でいたのだが， 自分の中で大きな勘違いをしていたようだ． それはコンパイルにおけるクロージャ変換のフェーズである．

これまで，OCaml でプログラミングをする際， 関数呼び出しの際に渡される変数を少なくするべく ローカルな関数定義を多く記述するようにしていたが， 実はそれは殆ど無意味な努力であったようだ． 例えば，

let rec loop i acc x = if i > 0 then loop (pred i) (acc+x) x else acc
let f x =
  loop max_int (-1) x
let _ = print_int (f 1)

よりも，loop 関数の定義を f の定義の中に入れて

let f x =
  let rec loop i acc = if i > 0 then loop (pred i) (acc+x) else acc in
  loop max_int (-1)
let _ = print_int (f 1)

とした方が効率がよいものだと思い込んでいたのだ． 後者では loop 関数の引数が少ないため，

let f x =
  let acc = ref (-1) in
  for i = max_int downto 1 do acc := !acc + x done;
  !acc
let _ = print_int (f 1)

のような雰囲気のコードを吐いてくれるものだと信じていた． しかし，loop 関数を用いた上の 2 つのプログラムは， クロージャ変換の結果，どちらも同じコードを吐くのだという． 実際にベンチマークをとってみると， loop 関数を用いた 2 つのプログラムはどちらも同じ速度であり， for ループを用いたときより約 30 ％遅いことが分かる． ただし，誤解のないように補足しておくと，この結果が意味するのは for ループ が末尾再帰より効率がいいということではない． あまり参照型を多用してしまうと，むしろ遅くなってしまう． 今回は，ループ関数の定義に自由変数が含まれていたために効率が悪くなってしまっただけである．

というわけで，今回のサマースクールは非常に有意義なものであった． ただ，圏論についてはもう少し深いところまで進んでもよかったように思う． 対象や時間の関係上仕方がなかったのかもしれないが…．