IK.AM

@making's tech note


Clojureで相互再帰最適化

🗃 {Programming/Lisp/Clojure}
🗓 Updated at 2010-03-23T16:38:59Z  🗓 Created at 2010-03-23T16:38:59Z   🌎 English Page

そろそろ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 = 2000java.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) ; これでもともと期待していたインタフェースで最適化できました!

面白いですねClojure!
まだプログラミングClojureを買っていない人はぽちりましょう!
プログラミングClojure


✒️️ Edit  ⏰ History  🗑 Delete