Clojure勉強日記（その１５ 関数型プログラミングの概念
こんにちは。シーケンスについて一段落し、ついに本筋っぽい個所に入ってきます。
関数型プログラミング＝ＦＰとして以後書きます。
ＦＰによるコードが書きやすく、読みやすく、テストしやすく、再利用しやすい理由として、
下記の理由があげられています。
- 純粋な関数
- 永続的なデータ構造
- 遅延評価と再帰
- 参照透過性
- 純粋な関数
純粋な関数とは副作用を持たない関数。
引数以外のものに依存せず、外界に影響を及ぼすのは返り値を通してのみという関数のことをさす。
何かに出力することでも副作用となるため、出来ることはある意味限られる。
但し、非常に読みやすく強固な関数になるのは確かでしょうね。
「引数以外のものに依存せず」とあるため、引数以外の変数を使うと当然ながら崩れます。
変数の値によって引数の値が同じであっても返り値が変わる可能性があるわけですから。
- 永続的なデータ構造
永続的＝変更不可なデータ構造はＦＰと並行性に関わってくる。
ＦＰでは純粋な関数はデータ構造を変更できないし、
並行性としてはスレッドセーフな操作を実装するために個々のデータ構造は変更できないことが必要となる。
ただ、当然気になるのは性能。データが変更不可である場合、
「データを更新する」＝「元データから変えたい部分のみを更新したコピーを作成する」になるためである。
・・・なのですが、Clojureでは全てコピーするというアプローチではなく、
「更新前後のバージョンの構造を共有する」ことで効率をあげているようです。
user=> (def alist '(1 2)) #'user/alist user=> alist (1 2) user=> (def blist (cons 0 alist)) #'user/blist user=> blist (0 1 2)
上記のケースの場合、
(1 2)をa用の構造として確保し、bを作成した際にはその前に0を連結した構造を作ってaを部分集合として含んだ部分をbとしているとのこと。
各シーケンスが永続的であるために逆にこのような効率化が実現できているようです。
- 遅延評価と再帰
ＦＰにおいては再帰と遅延評価が多用される。
（遅延評価として後になって評価されて具体化されることを式の現実化と呼ぶそうです）
ですが、Clojureでは関数と式は遅延評価されません。
シーケンスが多くの場合遅延評価（LazySeq）となるのみのようです。
ただ、この「遅延評価」というものは関数が純粋であることを前提としているとのこと。
純粋な関数は常に同じ値を返すため、呼び出すタイミングを気にしないで済むため。
なので、入出力等が伴うシーケンス処理を行う際には即時評価などを併用して問題を発生させないようにする必要があるとのこと。
- 参照透過性
上記の遅延評価は関数の呼び出しをいつでもその結果の値と置き換えることが可能という性質に依存しています。
つまりは関数を値に挿げ替えてもプログラムのふるまいは一切変わらないこととなる。
定義上純粋な関数は参照透過となるが、それ以外の関数のほとんどは異なる。
ん。なんかこれまでは単なる性質の説明であって、何故いいかを示す内容ではないようですね（汗
その後に一応こういう記述が。
- 関数型のコードが書きやすいのは必要な情報が全て引数の形で目の前にあるため。（読みやすいのも同じ理由）
- 引数以外の条件を整える必要がないため、テストが非常に容易。
- 副作用がないため、システムのどこに組み込もうとも常に同じように動作する。故に再利用しやすい。
・・・確かに、関数型言語プログラミングに対して一定以上のレベルに達した人にとってはこれは非常に当てはまりそうです。
後は、勉強によってその一定以上のレベルに達するまでどれくらいかかるか、なんですが（汗 まぁ、それはそれで。
その上で、「ClojureのFPにおける６つのポイント」としては下記があるとのこと。
- 直接の再帰を避ける。（・・・直接？）
- スカラ値や要素数が決まっていてそれほど多くないシーケンスを返す関数ではrecurを使う。
- 巨大な、または要素数が変動するシーケンスを使う場合は常に遅延評価を使う。（recurを使ってはいけない）
- 遅延シーケンスを必要以上に現実化しない。
- シーケンスライブラリをよく知る。
- 問題を分割する。
特に５番目６番目が重要とのことです。
1.再帰的定義を活用する
フィボナッチ数を用いて再帰のパターンを試してみます。
単純再帰
とりあえず、今まででわかっている単純な再帰を用いてn番目のフィボナッチ数を求める関数を記述すると下記のようになる。
(defn calc-fibo [n] (cond (= n 0) 0 (= n 1) 1 :else (+ (calc-fibo (- n 1)) (calc-fibo (- n 2))))) ; 動作を確認・・・なのだが、nが大きくなると処理時間がすさまじい勢いで増していく・・・ user=> (calc-fibo 20) 6765 user=> (time (calc-fibo 20)) "Elapsed time: 0.591918 msecs" 6765 user=> (time (calc-fibo 30)) "Elapsed time: 63.952961 msecs" 832040 user=> (time (calc-fibo 40)) "Elapsed time: 7793.344523 msecs" 102334155 user=> (time (calc-fibo 41)) "Elapsed time: 12652.872456 msecs" 165580141
実際、計算量もn番目のフィボナッチ数を算出する計算量＝（n-1番目算出計算量）＋（n-2番目算出計算量）となるわけでして。
実際のフィボナッチ数の値だけ計算量がかかるという計算になります。ほぼ指数関数的に増大します。
このあたり、Clojureでは単純に関数呼び出しによる再帰はそれだけスタックを確保するため性能が恐ろしく低下するようです。
これが「直接の再帰」というやつですかね。
末尾再帰
関数型プログラミングでは「末尾再帰」でスタック消費の問題を解決することができるそうですが・・・なんですか、それは（汗
「再帰的な定義を持つが、再帰呼び出しが関数の末尾に制限されている」とのことですが・・・
とりあえずこうしておけば言語処理系が最適化を行う模様。
というわけで前の関数を確認してみると、calc-fiboの内部でcalc-fiboを２回呼び出して加算しているため、末尾再帰ではないのは確か。
そんなわけで末尾再帰化。
なんですが、やっていることは「末尾で関数呼び出し１発で返り値が返るようにする」のみだったりします。
これで変わる・・・？
user=> (defn calc-fibo-tail [n] (letfn [(fib [current next n] (if (zero? n) current (fib next (+ current next) (dec n))))] (fib 0N 1N n))) user=> (time (calc-fibo-tail 20)) "Elapsed time: 0.118203 msecs" 6765N user=> (time (calc-fibo-tail 30)) "Elapsed time: 0.159416 msecs" 832040N user=> (time (calc-fibo-tail 40)) "Elapsed time: 0.203346 msecs" 102334155N user=> (time (calc-fibo-tail 100)) "Elapsed time: 0.435678 msecs" 354224848179261915075N ; 1000のフィボナッチ数を求めても時間はわずかで済む。 user=> (time (calc-fibo-tail 1000)) "Elapsed time: 6.519762 msecs" 4346655768693745643568852767504062〜 user=> (time (calc-fibo-tail 2000)) "Elapsed time: 7.271102 msecs" 4224696333392304878706725602341482〜 ; だが、落ちる・・・ user=> (time (calc-fibo-tail 10000)) StackOverflowError java.lang.Integer.numberOfLeadingZeros (Integer.java:1096)
とりあえず速度は劇的に改善したため、「末尾再帰」が適用されたのだろうと推測されますが、やはり落ちます。
本によると、JVMが関数型言語向けに設計されていないため、どうしても無理が来ている模様。
recurを使った自己再帰
先ほどの呼び出しをfibという「関数自体」で記述するのではなく、recurで実行することで「自己再帰」というモードになるようです。
なので試してみます。
但し、この「自己再帰」は関数を呼び出す際に他の関数呼び出しが挟まると上手く動作しない模様。
user=> (defn calc-fibo-recur [n] (letfn [(fib [current next n] (if (zero? n) current (recur next (+ current next) (dec n))))] (fib 0N 1N n))) #'user/calc-fibo-recur user=> (time (calc-fibo-recur 10000)) "Elapsed time: 6.154282 msecs" 33644764876431783266621〜 user=> (time (calc-fibo-recur 100000)) "Elapsed time: 407.521367 msecs" 25974069347221724166155〜 user=> (time (calc-fibo-recur 1000000)) "Elapsed time: 27892.895833 msecs" 19532821287077577316320〜
とりあえずこれで時間こそかかりますが、それなりの桁のフィボナッチ数は算出可能になりました。
ただ、これはnを指定したら結果のキャッシュとかはできずにフィボナッチ数を算出するのみ。
複数のフィボナッチ数を算出するには毎回関数を呼び出す必要があります。
・・・とはいえ、どの値を保持するとかは関数側からはわからないので、その辺りも必然的に引数で渡す必要が出てきます。
ここで遅延シーケンスが登場するとのことですが・・・どーやるんでしょうね。
遅延シーケンスによるフィボナッチ数算出
遅延シーケンスを用いるとフィボナッチ数算出の定義は下記のように書かれる模様。
(defn calc-fibo-lazy ([] (concat [0 1] (calc-fibo-lazy 0N 1N))) ([a b] (let [n (+ a b)] (lazy-seq (cons n (calc-fibo-lazy b n))))))
引数未指定部分[]で初期値である[0 1]と0と1を指定して実行した結果を結合
後は二つ引数(aとb)が指定されたパターンにおいて「a + b」をベースに再度フィボナッチ算出関数を呼び出し、
「a + b」と結合する処理を繰り返しています。
・・・なるほど。という感じです。
これまでのフィボナッチ算出関数とは正反対で、「小さい値から積み上げる」というアプローチになっています。
結果、下記の性質が生じる。
- 計算状態として保持するのは「現在のフィボナッチ数シーケンス」のみ。それ以外はnを用いて後に追加し続けるのみ。
結果、余計なスタックや途中状態、変数などを一切使わなくなっている。
- 「いつまで計算し続けるか」を考えなくていいため、無限の値を生成する。
余計な変数・・・というわけではありませんが、「いつまで計算し続けるか」を考えなくていいため、キリがない動作となる。
上記の結果を遅延評価（lazy-seq）によって問題なく活用できるようにしているわけですか。
再帰を遅延評価で置き換えることでこういうことが可能になるわけですね。
ただ、残念ながら（？）すごい、と思った解決方法よりより簡単な記述法があるそうです。
user=> (take 5 (map 1 (iterate (fn [[a b]] [b (+ a b)]) [0 1]))) ([0 1] [1 1] [1 2] [2 3] [3 5]) (user=> (take 5 (map first (iterate (fn [[a b]] [b (+ a b)]) [0 1]))) (0 1 1 2 3) (defn calc-fibo-seqlib (map first (iterate (fn [[a b]] [b (+ a b)]) [0N 1N])))
「次の要素を前の要素を用いて算出する」という関数を組んで、それをiterateで
たどれば同じように一定の法則にしたがった無限シーケンスは容易に作れるわけなんですね。
かつ、map とiterate はそれぞれ遅延シーケンスを返すので、
calc-fibo-seqlibが返すものも遅延シーケンスとなり、メモリ溢れは発生しないという。
遅延シーケンスを使うことで、無限のシーケンスの中から必要な要素だけを取得し、
性能の負荷も抑えることができる・・・というのはよくわかりました。
要素数がいくつになるかわからないケースにおいては、loop/recurを使うより・・
というか、iterateを使用したパターンの方がより直観的ですね。覚えておきましょう。
で、遅延シーケンスを使うと実際に中の値を使うケースにおいてのみ評価されるという性質を考えると、
以前シーケンスライブラリの確認を行った際にほとんどLazySeqが返る理由もわかった気がします。
あの時は不自然に感じましたが、言語系として遅延させられるものは極力遅延させて評価しているわけなんですね。
