clojure備忘録[clojureの基本的な特殊形式 その７（loop/recur特殊形式）]
loop/recur特殊形式は「末尾再帰最適化」を行います。
何のこっちゃかと思うかもしれませんが、繰り返しの制御を行う為の特殊形式です。
手続き型言語に慣れた方は驚くかもしれませんが、
clojureには明示的な繰り返し制御用の式がありません。
実は繰り返しのフロー制御は言語そのものに備えるほどのものではありません。
アルゴリズム的には「再帰」ができれば事足ります。
しかし単なる「再帰」での関数呼び出しではハードウェア的に問題があります。
関数は呼び出す度にスタックを消費し、どんどんメモリを圧迫していきます。
これを解決するのが「末尾再帰最適化」という概念と実装であり、
これによってスタックを消費せず、効率的に繰り返し処理を実現できます。
この思想を突き進んでいるのがSchemeです。
Schemeは「言語仕様」としてこの末尾再帰の最適化を要請しています。
clojureもこの思想に従っているようでして、
繰り返しを実現したい場合は「loop/recur特殊形式」を使用します。
・・・。
「そもそも末尾再帰最適化とは何ぞや」と思われる方は多いと思います。
これについては結構な量の内容になるので別エントリでまとめます。
ここではloop/recur特殊形式の使い方についてのみ説明します。
表記
他の特殊形式と違って、S式の形が不定なのでものすごく説明しづらいです。
とりあえず、次の条件を満たすS式になります。
＜パターン１＞
・関数定義の中でrecur特殊形式が呼び出されていること。
・関数内に終了条件が存在すること。
・recur特殊形式の呼び出しは、該当関数の最後に評価される式になっていること。
または、
＜パターン２＞
・loop特殊形式の中でrecur特殊形式が呼び出されていること。
・loop特殊形式内に終了条件が存在すること。
・recur特殊形式の呼び出しは、loop特殊形式の最後に評価される式になっていること。
ややこしいですね。
＜パターン１＞から記載してみます。
とは言っても関数内なので、
これ以外でも関数定義の表記に従っていさえすれば、
至る所にS式を埋め込むことができます。
(defn recursive-function [value & values] (if predicate-form return-value (recur next-value & next-values)))
次に＜パターン２＞です。
(loop [value init-value & value-pairs] (if finish-predicate-form return-value (recur next-value & next-values)))
ちなみに、recurが再帰呼び出しを行うポイントで、
recurの行き先が、関数だったりloopだったり、という感じです。
実際にどのように使用するかを見た方が理解できるかもしれません。
実例
＜パターン１＞から行ってみましょう。
1〜Nまでの数列をベクタで生成する関数です。
ちなみに、関数名に含まれている「tco」は、
「Tail Call Optimization」の頭文字で、
要するに「末尾再帰最適化」です。
(defn tco-function [i max ans] (if (< max i) ans (recur (+ 1 i) max (conj ans i))))
conj関数は第１引数のリスト（の類）に、第2引数の要素を追加する関数です。
replに食わせて使ってみましょう。
user=> (defn tco-function [i max ans] (if (< max i) ans (recur (+ 1 i) max (conj ans i)))) #'user/tco-function user=> (tco-function 1 10 []) [1 2 3 4 5 6 7 8 9 10] user=>
ばっちり動いてます。
スタックを消費していないかどうかは分かりませんが、
ここでは「使い方」が論点なので、まぁいいでしょう。
＜パターン１＞は関数そのものを末尾再帰していましたが、
「ここでだけ繰り返し処理した結果が欲しいけど、関数定義までしたくない」、
というときに使用できるのが＜パターン２＞になります。
こんな真似ができます。
(def tco-value (loop [i 1 max 10 ans []] (if (< max i) ans (recur (+ 1 i) max (conj ans i)))))
実際に評価してみましょう。
user=> (def tco-value (loop [i 1 max 10 ans []] (if (< max i) ans (recur (+ 1 i) max (conj ans i))))) #'user/tco-value user=> tco-value [1 2 3 4 5 6 7 8 9 10] user=>
