副作用がないからキャッシュできる

素数判定をmemoizeしても、ちっとも速くなっていないような気がして変だなと思っていたけど、どうもClojureは関数の計算結果をデフォルトでキャッシュするような機構があるらしい。

% clj
Clojure 1.1.0
(defn prime? [n]
  (cond
   (> 2 n) false
   (== 2 n) true
   (even? n) false
   (not-any? zero? (map #(rem n %) (range 3 (inc (Math/sqrt n))))) true
   :else false))
#'user/prime?
user=> (time (count (map prime? (range 10000 100000))))                         
"Elapsed time: 1083.465 msecs"
90000
user=> (time (count (map prime? (range 10000 100000))))
"Elapsed time: 557.008 msecs"
90000
user=> (time (count (map prime? (range 10000 100000))))
"Elapsed time: 545.796 msecs"
90000
user=> (time (count (map prime? (range 10000 100000))))
"Elapsed time: 540.716 msecs"
90000
%

『プログラミングClojure』によると、関数に副作用がないことと、データが永続的であることは、切っても切れない関係にあって、それは遅延評価を可能とし、参照透過性を担保している。

関数に副作用がないということは入力が同じなら、いつも結果が同じ。そしてデータ永続的であるとすれば、計算はどのタイミングでしてもいいということになり、遅延評価をデフォルトとできる。プログラマは計算のタイミングを制御する必要がなく、状態に依存したバグは起こりえない。

さらに、計算結果は常に変わらないので、ある関数の中身をまるまる結果を返すだけの関数に置き換えても大丈夫。これはキャッシュとかメモ化と言われるテクニックそのもので、関数型はメモ化と相性がいい。

ちょっと待てよ、じゃあ関数を書く意味って何だろうといえば、そうか、ある計算結果に至るロジックをあえて残して置いて、現実世界の要求にあわせて柔軟に変更できるようにしてるということか、という気もしてくる。つまり、動的言語が物事の決定を遅らせるのと同じで、あるデータに対する関数の適用決定を初回実行時に遅らせている。

小さな関数群は、小川の表面に出た石のようなイメージで、その間を値としての水が流れるような、そんな絵が目に浮かぶ。流れは動的だけど、みる時刻によらず同じ形をしている、というような。インプットとしての水かさが増せば流れの形は変わる。

すごく綺麗な世界だ……。コードの再利用性も高そう。けど時間の抽象化って速度やメモリ使用量といった効率という点から見ると、結構深い理解がないとやばそうな気もする。

Amazon EC2はストレージが永続的でなくて、そもそもサーバに状態を残すようなシステムを作るなということを彼らは言っている。MapReduceもそうだけど、クラウドってつまり関数型のように作れってことかしら。「そうはいってもねー、ローカルにマウントできるストレージがないとサーバで何か作るのめんどいしー」ということと、「関数型プログラミング言語は書きづらい」という話ってパラレルな現象のように思えた。