そろそろClojureでのloop/recurによる末尾再帰最適化に慣れてきたんじゃないでしょうか。
Clojureでは相互再帰も最適化されません。例えばこんな例
;; ちょっと変わったみんな大好きFizzBuzz
(declare fizz buzz)
(defn fizz-buzz [n]
(when (> n 0)
(print n " = ")
(fizz n)))
(defn- fizz [n]
(if (zero? (rem n 3))
(print 'fizz))
(buzz n))
(defn- buzz [n]
(if (zero? (rem n 5))
(print 'buzz))
(println)
(fizz-buzz (dec n)))
このような再帰もスタックを消費します。手元の環境ではn = 2000
でjava.lang.StackOverflowError
が発生しました。
このような状況を最適化するために用意されている関数は。。。trampoline
です。
プログラミングClojureをお持ちの方はP.149を開いてください。さらっと説明されていますw
trampolineで最適化したコード
trampoline
化させるには返り値の括弧の前に#
をつけてクロージャ(closureの方)を返すように修正します。
(declare fizz buzz)
(defn fizz-buzz [n]
(when (> n 0)
(print n " = ")
#(fizz n)))
(defn- fizz [n]
(if (zero? (rem n 3))
(print 'fizz))
#(buzz n))
(defn- buzz [n]
(if (zero? (rem n 5))
(print 'buzz))
(println)
#(fizz-buzz (dec n)))
呼び出すときは(trampoline f & args)
です。
user> (trampoline fizz-buzz 2000) ; これでjava.lang.StackOverflowErrorが発生しなくなりました!
部分適用でインタフェース改善
このままだと使うとき毎回trampoline
を書かなくてはいけなくて面倒ですね。本来渡したいのfizzbuzzの引数だけです。こんなときのためにpartial
部分適用があります!
プログラミングClojureをお持ちの方はP.146を開いてください。trampoline
の第一引数がfizz-buzz
である新しい関数を作っちゃいます。
(declare fizz buzz)
;; rename
(defn- fizz-buzz-1 [n]
(when (> n 0)
(print n " = ")
#(fizz n)))
(defn- fizz [n]
(if (zero? (rem n 3))
(print 'fizz))
#(buzz n))
(defn- buzz [n]
(if (zero? (rem n 5))
(print 'buzz))
(println)
#(fizz-buzz-1 (dec n)))
;; 部分適用
(def fizz-buzz (partial trampoline fizz-buzz-1))
user> (fizz-buzz 2000) ; これでもともと期待していたインタフェースで最適化できました!