Y箱

前にclojureのmemoize関数の動きがだめだっていう話を書きました。
このポストも関心のある方がいらっしゃるようなので、ちょっと追加の情報を。
べつに目新しいものではありませんけど、日本語の情報が無いみたいなので。

さて、 何がだめなのかをくりかえすと、再帰で定義されている関数をmemoizeを使ってメモ化しても、内部での 再帰呼び出しにメモ化が効かないという現象です。
実はこれ、clojureの1.2からのことで、1.1では問題なく動きます。 

これは、以下に出てくる解決策から考えると、1.2で、関数の名前の解決方法に変更があったためだと思われます。

以下ちょっと長くなります。




例によってフィボナッチ数を求める関数を再帰を使ってで定義して、1.1環境で実行してみます。

user> (clojure-version)
"1.1.0"

(defn fib [n]
  (do
     (println "Called with : " n)
     (if (<= n 1)
        n
        (+ (fib (dec n)) (fib (- n 2))))))


user> (fib 5)
Called with :  5
Called with :  4
Called with :  3
Called with :  2
Called with :  1
Called with :  0
Called with :  1
Called with :  2
Called with :  1
Called with :  0
Called with :  3
Called with :  2
Called with :  1
Called with :  0
Called with :  1
5

再帰的に呼ばれているのが分ります。 これを、memoize関数でメモ化しして、同様に呼んでみます。

(def fib (memoize fib))

user> (fib 5)
Called with :  5
Called with :  4
Called with :  3
Called with :  2
Called with :  1
Called with :  0
5

1.2で実行したときに出て来ていた(fib 1),(fib 2),(fib 3) が出てきません。メモにヒットして関数が呼ばれなくなったためです。memoizeちゃんと動いています。

同じことを1.2でやると、このようにはなりません。 (前のポスト参照)

この問題について、前回僕はマクロを作って解決したわけですが、他にこんな方法もあります。 

まず、メモ化する関数の定義を変更します。

(defn fib2 [n]
  (do
     (println "Called with | " n)
     (if (<= n 1)
        n
        (+ (#'fib2 (dec n)) (#'fib2 (- n 2))))))

このように再帰で呼ばれる関数名に「#'」をつけます。(なんでこうするのかについての考察は後で) そして1.1の時と同様にメモ化すればOKです。

やってみます。

user> (clojure-version)
"1.2.1"

(defn fib2 [n]
  (do
     (println "Called with : " n)
     (if (<= n 1)
        n
        (+ (#'fib2 (dec n)) (#'fib2 (- n 2))))))

user> (fib2 5)
Called with :  5
Called with :  4
Called with :  3
Called with :  2
Called with :  1
Called with :  0
Called with :  1
Called with :  2
Called with :  1
Called with :  0
Called with :  3
Called with :  2
Called with :  1
Called with :  0
Called with :  1
5

(def fib2 (memoize fib2))

user> (fib2 5)
Called with :  5
Called with :  4
Called with :  3
Called with :  2
Called with :  1
Called with :  0
5

この通り 

さて、じゃあ、これはなんでうまく行くんでしょう
 以下の説明は僕の推測です。1.2の変分を見てもよくわからなくて、 なんとなくしか理解できてなくて、今一つ現象を性格に捉えられていない。 
 間違っていたら指摘ください 


 関数が再帰的に呼ばれるとき、1.1では、「関数が評価される時点でこの名前を持っている関数を呼ぶ」という仕組みだったものが、1.2では「定義時点この名前が差している関数を呼ぶ」という方式に変更になった。
そのため、1.2では、初めの関数そのものが再帰で呼ばれてしまい、memoizeがうまく動かなくなってしまった。 

この解決策でつかった「#'」はリーダーマクロで(var xxx)の略。「この名前のvarを取得する」ということを意味している。 なので、1.1の時と同じ定義をさせることができるのです。

推測ここまで


 さて、この方式はちょっと気に入らない。
だって、メモ化するつもりの関数はあらかじめ定義をそれ用に書いておけってことになってしまうわけで、 たとえば、あとから、「あ、これメモ化してほうがいいな」と思った場合、関数定義に手を入れることになってしまう。
だったら、僕の作ったマクロで再定義しちゃったほうが手間は少ない。 

ということで、僕はこの方法は却下。
勉強にはなったけどね。