読者です 読者をやめる 読者になる 読者になる

レガシーコード生産ガイド

私に教えられることなら

少しだけClojure 6

プログラミングClojure第2版を読みながら続き。

方針

  • 基本的に本の説明をそのままor自分の言葉に直しただけで書き直すようなことはしない
  • サンプルコードが長くて理解しづらい、練習したいなと思うものは細かく試して書いてみる
  • 読んだ時点で書かれてなかったり省略されているか、疑問に思ったことを調べて書く
  • 後から書かれていたら参照のために簡単にメモする

トランポリン

末尾再帰最適化が明示的な再帰(recur)を使わないとできない言語で相互末尾再帰を最適化する方法、でいいのかな?

動きを理解するために実装してみる。

まず、単純に相互再帰する版でスタックオーバーフローすることを確かめる。

(declare my-odd? my-even?)

(defn my-odd? [n]
  (if (= n 0)
    false
    (my-even? (dec n))))

(defn my-even? [n]
  (if (= n 0)
    true
    (my-odd? (dec n))))
user=> (my-odd? 1000)
false

user=> (my-odd? 10000)

StackOverflowError   clojure.lang.Numbers.equal (Numbers.java:214)

trampolineの動きは

  • recurで末尾再帰している
  • [fn & args]を受け取り、(apply fn args)の結果が関数なら再度それをfnにセットしてrecur、そうでなければそのまま値を返す

簡単そうだ。実装してみよう。

(declare my-odd? my-even?)

(defn my-odd? [n]
  (if (= n 0)
    false
    #(my-even? (dec n))))

(defn my-even? [n]
  (if (= n 0)
    true
    #(my-odd? (dec n))))

(defn my-trampoline [fn & args]
  (let [v (apply fn args)]
    (if (fn? v) (recur v nil) v)))

引数で[hoge & fuga]としている場合、recurでfugaの部分にnilを渡してやらないとエラーが出た。

試してみる。

user=> (my-trampoline + 1 2)
3

user=> (my-trampoline (fn [] #(+ 1 2)))
3

user=> (my-trampoline my-even? 100000)
true

user=> (my-trampoline my-even? 1000000)
true

user=> (my-trampoline my-even? 10000000)
true

上手くいった。

例えばClojure上にLisp実装するときに、evalで相互再帰するならtrampolineを使えばいいのかな?だいぶん混乱しそうだけど。

で、普通の呼び出しだけで末尾再帰最適化できる言語・処理系だと相互末尾再帰も最適化されるんだろうか?試してみよう。

まずGauche

gosh> (define (my-odd? n) (if (= n 0) #f (my-even? (- n 1))))
my-odd?
gosh> (define (my-even? n) (if (= n 0) #t (my-odd? (- n 1))))
my-even?
gosh> (my-odd? 1000000000)
#f

最適化されるんだ!SBCLはどうかな?

* (declaim (ftype function my-even-p my-odd-p))

* (defun my-even-p (n) (if (= n 0) t (my-odd-p (1- n))))

MY-EVEN-P
* (defun my-odd-p (n) (if (= n 0) nil (my-even-p (1- n))))

MY-ODD-P
* (my-even-p 10000000)

T

こっちも大丈夫だった。ついでに(もうひとつのLispの形だと思ってる)Factorでも試してみる。

IN: scratchpad :: my-even? ( n -- ? ) n 0 = [ t ] [ n 1 - my-odd? ] if ;

IN: scratchpad :: my-odd? ( n -- ? ) n 0 = [ f ] [ n 1 - my-even? ] if ;

IN: scratchpad 1000000000 my-odd? .
f

というわけで末尾再帰が最適化される言語・処理系、少なくともGaucheSBCLとFactorでは相互末尾再帰もループに最適化されるみたいだ。というか、trampolineはJVM上で関数型やってる言語特有のテクニックっぽい?いずれ末尾再帰の最適化の方法も調べてみよう。

メモ化で再帰を止める

ホッフスタッターの男女のシーケンスの動きをイメージしておかないとその後の説明を目が滑っていった。

F(1) = 1 - M(F(0))
  M(F(0))
    F(0) = 1
  M(1) = 1 - F(M(0))
    F(M(0))
      M(0) = 0
    F(0) = 1
  M(1) = 0
F(1) = 1


F(2) = 2 - M(F(1))
     = 2 - M(1)
     = 2 - 0
     = 2

M(2) = 2 - F(M(1))
     = 2 - F(0)
     = 2 - 1
     = 1

説明と併せて見ると、

  • F(n)やM(n)がメモ化されてるかどうかで一気に計算量が変わる
  • メモ化しても、キャッシュが空の区間が大きい場合は計算量増大・スタックオーバーフローしてしまう。n=1,2,...と順番に計算することでO(n)にできて、オーバーフローもしない

ということかな。

感想など

  • commuteの例まで進んだんだけど、チャットメッセージは実際の時間枠で見るとalterでもcommuteでも良いというのはわかった。で、どっちを選べばいいんだろう?普通はalterを使っておいて、ボトルネックになっていてかつcommuteでも良いと判明した場所だけそれに書き換える、って指針でいいのかな。
  • STMのありがたみがわかる簡単な(動く)例が欲しいところ。
広告を非表示にする