今時 OCaml で非末尾再帰呼び出し使うなんて
非 し! -── ‐- 、 , -─-、 -‐─_ノ O 小 末 // ̄> ´  ̄  ̄ `ヽ Y , ´ ) C え 学 尾 L_ / / ヽ a | 生 再 / ' ' i m マ ま 帰 / / く l ジ で 許 l ,ィ/! / /l/!,l /厶, で だ さ i ,.lrH‐|'| /‐!-Lハ_ l /-!'|/l /`'メ、_iヽ よ れ l | |_|_|_|/| / /__!__ |/!トi i/-- 、 レ!/ / ,-- レ、⌒Y⌒ヽ ね る _ゝ|/'/⌒ヽ ヽト、|/ '/ ̄`ヾ 、ヽト、N'/⌒ヾ ,イ ̄`ヾ,ノ! l の 「 l ′ 「1 /てヽ′| | | 「L! ' i'ひ} リ は ヽ | ヽ__U, 、ヽ シノ ノ! ! |ヽ_、ソ, ヾシ _ノ _ノ -┐ ,√ !  ̄ リ l !  ̄  ̄ 7/ レ'⌒ヽ/ ! | 〈 _人__人ノ_ i く //! 人_,、ノL_,iノ! /! ヽ r─‐- 、 「 L_ヽ r─‐- 、 u ノ/ / / lト、 \ ヽ, -‐┤ ノ キ 了\ ヽ, -‐┤ // ハ キ { / ヽ,ト、ヽ/!`hノ ) モ |/! 「ヽ, `ー /) _ ‐' ハ ャ ヽ/ r-、‐' // / |-‐ く | > / / `'//-‐、 / ハ ハ > /\\// / /ヽ_ ! イ ( / / // / `ァ-‐ ' ハ ハ / /! ヽ レ'/ ノ > ' ∠ -‐  ̄ノヽ / { i l ! / フ / -‐ / ̄/〉 〈 \ /!
いやまあ、そこまで言い切れるものでもないが。
OCaml プログラマの皆さんご機嫌いかがでしょうか。 今日も必死に目を皿のようにして自分の定義した再帰関数が末尾再帰か どうかチェックされてますかぁ?
コンパイラが末尾だと言ってたら末尾だ!それ以外は全部非末尾だ!!
何が末尾再帰かって?そりゃー自分で調べてくれぃ。 判別するのは難しくはないし、(いや実は、、、)慣れればスグ。でも、メンドーだよね!
OCaml で思いついたまま、再帰関数を書いて、そのままなのはただの OCaml プログラマ。そんな奴はスタックに火がついて爆発する。 書いた後で、これは末尾呼び出しだな、って頑張って確認するのが訓練された OCaml プログラマ! 書く時点で自然と末尾再帰になっているとなお良し!
でも、ちょっと待て、ほんとにその再帰関数は末尾再帰なワケ?そう思っているだけで実は違うんじゃ… いやいや、あなたの判断が間違ってるとは申しません(まあ多分そうだけど)。そう、もしホントに末尾再帰だったとしても、コンパイラ様が何かの拍子に末尾だと判断してなかったら、 末尾再帰最適化が行われない。だから爆発する!きっと爆発する! Kabooom! どうしたらいいんだ…
いや、まあそんな拍子は無いと思うんだけど、最終的に爆発するかどうかはコンパイラ様に かかってんだから、素人判断はやめて、コンパイラに聞く、これが 21世紀の洗練された 思考停止 OCaml プログラマだ!
今時 OCaml で -annot 使わないなんて(ry
ocamlc や ocamlopt で -annot オプションを付けて hogehoge.ml をコンパイルすると、 hogehoge.annot というありがたいファイルが出来上がる。ここには部分式の型が全部 記載されている他、コンパイラが、すべての関数呼び出しに関して、末尾(tail)か 非末尾(stack)か、判断した記録も入ってる。
さて、この .annot ファイルを OCaml に同梱の caml-types.el という elisp を 使えば、 caml-types-show-call で Emacs の画面から、カーソルのとこにある 呼び出しが末尾かどうか、教えてくれるワケ。便利だね! でもでも、試験や面接でこの関数は末尾再帰になってる?とか、これ末尾再帰にしてちょ、 とか聞かれて答えられないようじゃクリティカルに困るんで、頼り過ぎに注意しましょう。(不安になったら CPS変換ごにょごにょ と唱えれば何とかなるかもしれんよ! 余計に墓穴を掘るかもしれんがね!
欲を言うと、非末尾の再帰呼び出しは自動的に全部色を付けてほしいんだが、 それは無理みたいだ! 誰か作って。 末尾か、非末尾かはすぐにわかるんだけど、それが再帰定義と関係しているかは 現在の .annot の情報だけでは調べられないんだよね…
追記
プログラマに取って興味があるのは非末尾呼出自身ではなくて、非末尾呼出によってスタックを食い尽くす可能性のある再帰なのですが、これを判定するのは実は難しい:
let rec fact = function | 0 -> 0 | n -> let g = fact in n * g (n-1)
例えば上の例は非末尾の fact をちょっと書き換えたものだけど、 fact は 文面上は再帰呼出されていない。だからこの性質は syntactic には解析できないってことですね。当然、 caml-types-show-call を使っても fact の使用は関数適用でさえないので、駄目。g は fact 使ってるのが判ってれば、その g が非末尾かどうか調べるのには使えるケド。
さらに OCaml の副作用を使うと、 let rec を使っていない非再帰関数定義にも 簡単に再帰を導入することができる:
let g = ref (fun _ -> assert false) let fact = function | 0 -> 0 | n -> n * !g (n-1) g := fact
なんで、自動的にこれがヤヴァいんじゃないかね?と完璧に推論させるのは無理だし、 十分実用上に推論させるのも、まあ、なんというか無理っぽい。
じゃあどうするか、というと、全ての非末尾呼出しを末尾呼出しに変えてしまう CPS変換によるコンパイルが考えられる。例えば:
let mult k x y = k (x * y) let rec fact k = function | 0 -> k 0 | n -> let g = fact in g (fun res -> mult k n res) (n-1)
そうすりゃスタック溢れはそもそも気にしなくていい訳ですな。 でも OCaml はそんなコンパイルはしてくれない… なんでかって? よく知らない。適当に言っちゃうと、 そもそも OCaml はスタックマシンベースなのに CPS変換とかやっちゃうなんて共産主義称えつつ資本主義、 みたいで本末転倒じゃね?とか無理に変換すると遅くなるでよ (事実、stdlib の map とかが非末尾再帰で爆発しがちなのはスピードの為)、 とかがある、はず。(誰か教えてください…
まあ、ぶっちゃけ、そんな事気にしようが気にしまいが、 現状 OCaml では (ちなみに諸君の愛する Haskell でも。なぜだ!) プログラマは非末尾再帰呼出しには気をつけなきゃいけない、そういうことで!