clojure備忘録[末尾再帰の最適化]
このエントリーはまとめようとしたら、
書いては消し書いては消しの繰り返しで時間がかかってしまいました。
理解はしていても人に伝える為に整理しようとするのは難しいもんですねぇ。
さて。
本エントリでは、Lisp方言であるschemeとclojureが、
「繰り返し」に対してどのような見方をしているかについて説明を試みます。
キーワードは「末尾再帰の最適化」です。
「再帰」
実は「繰り返し構文」というやつは言語に組み込むほどの機能ではありません。
単に「繰り返す」ことを実現するだけであれば、
「関数の再帰呼び出し」が可能であればOKです。
もう少し具体的に言うと、例えばある関数hogeというのがあるとして、
このhogeの定義の中で再びhogeを呼び出せると言うことです。
これは大抵の言語で可能になっています。
もちろんLisp系言語でも可能です。（というかむしろ本家？）
では、その再帰呼び出しが可能なclojureで、
指定した数までの自然数列を返却する関数のコードを書いてみましょう。
(defn natural-numbers-recursive [value] (if (<= value 0) [] (conj (natural-numbers-recursive (- value 1)) value)))
早速replで評価させてみましょう。
user=> (defn natural-numbers-recursive [value] (if (<= value 0) [] (conj (natural-numbers-recursive (- value 1)) value))) #'user/natural-numbers-recursive user=> (natural-numbers-recursive 5) [1 2 3 4 5] user=>
期待どおり、ちゃんと再帰で繰り返しが実行されています。
これで純粋なアルゴリズムという観点からすると、
繰り返し専用の構文が不要だということが示されました。
ところが、現実はそう単純な話にはなりません。
というのも関数呼び出しは自分が呼び出された時の諸々の状態情報の塊である、
「スタック」を呼び出し元に戻るまで保持する必要があるからなのです。
関数を呼べば呼ぶほどスタックを生成することになり、
メモリを食いつぶしていきます。
故に、アルゴリズム的にはOKでも、ハードウェア的にはNGになってしまうのです。
このハードウェア的問題を解決する為に、
単なる「再帰」をもう一段階昇華させた「末尾再帰の最適化」、
という言語処理系側の実装上のテクニックが登場します。
では次に「末尾再帰」とは何かについて説明します。
末尾再帰
「末尾再帰」とは、
再帰呼び出しになっている式が、その関数の最後に評価される式になっていること。
です。
では、先ほどのサンプルコードが「末尾再帰」になっているかどうかを確認してみます。
(defn natural-numbers-recursive [value] (if (<= value 0) [] (conj (natural-numbers-recursive (- value 1)) value)))
この関数のbody部分はまるごとif特殊形式です。
もしifが通常の関数であれば「条件式」「then式」「else式」が全て評価された後、
それらの評価値をifが評価することになるので、ifが「最後に評価される式」になります。
ところが、ifは特殊形式なのでまずif自身が評価され、
その後に条件式が評価され、その結果によってthen式、またはelse式が評価される、
という評価順序になります。
即ち、このnatural-numbers-recursive関数において、
「最後に評価される式」を含んでいる可能性があるのは次のどちらかです。
then式 : [] else式 : (conj (natural-numbers-recursive (- value 1)) value)
then式は空のベクタを生成している式なので、
こちらがコールされた時は問題なくこれが「最後に評価される式」になります。
終了条件の時の式ですしね。
さて、else式ですが、conjの式になっています。
このconjは、第1引数のベクタの末尾に第2引数の要素を追加してその結果を返却します。
試しにconjの動きををreplで確認してみましょう。
user=> (conj [1 2 3] 4) [1 2 3 4] user=>
このようになります。ところでconjは関数でしょうか、特殊形式でしょうか。
関数であれば、前述した関数の評価順序のルールに従い、この関数がそのまま「最後に評価される式」になります。
特殊形式であれば、conjの引数が「最後に評価される式」になります。
結論からいうと、conjは関数です。
なので、このconjが「最後に評価される式」になります。
再帰呼び出しのnatural-numbers-recursive関数はどこにあるでしょうか。
conj関数の第1引数になっています。
故に、関数の評価順序のルールに従い、
再帰呼び出しのnatural-numbers-recursive関数が評価された後にconj関数が評価されるため、
この「natural-numbers-recursive関数」再帰呼び出しは「末尾再帰ではない」という結論になります。
ではこの関数を末尾再帰にするにはどうしたらよいでしょうか。
else式をまるごとこの関数の呼び出しにできれば良いのです。
こんな感じに。
(defn natural-numbers-recursive-tail-call [value answer] (if (<= value 0) (vec answer) (natural-numbers-recursive-tail-call (- value 1) (cons value answer))))
関数名がどんどん長くなっていたり、引数が増えていたり、
細かいロジックの変更がありますが、
先ほどの解析手法と同じやり方で最後に評価される式を調べてみると、
今度はnatural-numbers-recursive-tail-call関数自身になっていることがわかると思います。
スタックの状態を確認したいのですが、方法が分かりませんw
一応動作しているかどうかだけ確認するため、評価してみます。
ちゃんと期待した結果が出ています。
user=> (defn natural-numbers-recursive-tail-call
[value answer]
(if (<= value 0)
(vec answer)
(natural-numbers-recursive-tail-call (- value 1) (cons value answer))))
#'user/natural-numbers-recursive-tail-call
user=> (natural-numbers-recursive-tail-call 5 [])
[1 2 3 4 5]
user=>
末尾再帰の最適化
最後に「最適化」の正体について説明します。
末尾再帰でない再帰呼び出しは、再帰呼び出しから戻ってきたあと更に評価が必要(サンプルだとconj関数のこと)なため、
どうしてもその環境をスタックとして維持しておかなければなりません。
ところが末尾再帰の場合、戻った時の返却値はそのまま呼び出し元の返却値となります。
これが何を示唆するかというと、
戻った後に返却値を使用して何かを再計算する必要が無いため、
スタックを維持する必要がなくなるということなのです。
必要ないならスタックの維持なんてやめちまえということで、
内部的には呼び出し元にジャンプしてしまうことにより、
省リソースな繰り返し処理が実現できることになるわけです。
これが「末尾再帰の最適化」です。
Lisp方言の一つであるSchemeは、
言語仕様としてこの「末尾再帰の最適化」を要請していますので、
全てのScheme準拠の処理系はこの機能を実装しているはずです。
故に、上記のnatural-numbers-recursive-tail-callのような関数をscheme（の文法）で定義して評価させると、
スタックを消費せずに実質的には普通の言語の繰り返し構文と同じ効率で処理することができます。
clojureの場合・・・
ただ、ここまで説明しておいてアレですが、
clojureでは末尾再帰に合致したコードを記述しても最適化は行われません。
色々な情報を寄せ集めると、どうやらJVM側が末尾再帰の最適化を備えていないということが原因の一つのようです。
なので、仕方なく「末尾再帰の最適化」を陽に指定する為の「loop/recur特殊形式」が作られたのでしょう。
（でもJVM上で動作するScheme実装があるので、
やろうと思えばやれるんじゃないかなぁ。。
何か実用上の問題があったのかな。性能が出ないとか。）
<<2015/02/01 訂正>>
コメントを頂きまして、上記の内容は正確性に欠けるかもしれないと考えました。
現在調査する時間が確保できないので、ひとまず横線消去させて頂きます。
「末尾再帰の最適化」に関する説明は以上です。
書いてはみたものの・・・ご理解頂けるかどうかは自信がありません。。
説明って難しいなぁ。
