lazy-seq in Clojure (翻訳)
https://medium.com/lazy-eval/lazy-seq-in-clojure-da06f6d35971 の雑な翻訳。
lazy-seqはどのような仕組みで動くのか、なぜ必要とされるのか?
根本的な概念: 値が必要になるまで、式の評価を遅らせる
遅延評価を実現するための方法は以下の2つ
・ ランタイムにラムダ関数を使う
・コンパイルにマクロ/特殊なフォームを使う
ラムダ、クロージャ、再帰を使った遅延評価のテクニックで、無限のデータ構造を作ることができる。clojureだと、lasy-seq
とcons
を使えばよい。
Clojure docs for lazy-seqの例を見てみよう。
user> (def fib-seq
(lazy-cat [0 1] (map + (rest fib-seq) fib-seq)))
;; => #'user/fib-seq
laz-cat
は遅延シーケンスを連結するためのマクロである。 上の書き方はlazy-seq
を使ったものと同様である。
user> (def fib-seq (concat (lazy-seq [0 1]) (lazy-seq (map + (rest fib-seq) fib-seq))))
;; => #'user/fib-seq
user> (doall (take 2000 fib-seq))
lazy-seq
を使えば、OutOfMemoryException/StackOverFlowErrorが発生せずに、巨大なインデックスを評価できる。
内部のしくみ:
・ lazy-seq
はアクセスされて初めて、一度だけbodyを実行する
・結果がキャッシュされ、将来、関数が呼ばれる時はいつでも使える
例に戻る:
[0 1]
はこの問題の基本ケースである。フィボナッチ数列の最初2つの値は0と1である。それぞれの値の連続する計算結果は1つ前の値、もう1つ前の値の合計である。そのため、計算プロセスを始めるために少なくとも2値必要である。
(map + (rest fib-seq) fib-seq)
rest
は fib-seq
の先頭以外を返す。 map
は +
で2つのシーケンスを合計し、次のシーケンスを生成する。 fib-seq-temp
でフィボナッチ数列を求めてみよう。
user> (def fib-seq-temp [0 1 1 2 3])
user> (map + (rest fib-seq-temp) fib-seq-temp)
;; => (1 2 3 5)
map
に適用したシーケンスは base sequence
の一部である。最初のシーケンスの (rest [seq])
は base sequence
の先頭を除いたものである。二番目のシーケンスは base sequence
自体で最初の値を含んでいる。
ここで言っている base sequence
とは何か?
フィボナッチ数の定義は A(n) = A(n-1) + A(n-2)
である。シーケンスを拡張するために、事前に計算された値にアクセスしなければならない。前の計算結果にアクセスするために fib-seq
への再帰的な参照を利用している。 base sequence
は概して [0 1]
で始まるものである。
上記の手順に従い、プロセスを実行しよう。
fib-seq
の最初の要素は0、fib-seq
の 2番目の要素は1 、 fib-seq
の3番目の要素は?ここでは map
を使って残りの値のシーケンスを生成する。 rest [0 1]
、つまり、1と [0 1]
の最初の要素の0の合計は以下のとおり、1である。
user> (map + (rest [0 1]) [0])
;; => (1)
同様に4番目の要素を生成するためのプロセスを繰り返そう。
base sequence
を生成するために再び map
を使う。 rest [0 1]
の2番目の値、つまり上で計算した結果の (1)
と [0 1]
の2番目の要素の合計を計算する。
user> (map + (rest [0 1]) [1])
;; => (2)
これで4番目の要素を生成できた。 rest [0 1]
の3番目の要素である1と [0 1]
から生成された4番目の要素である2を合計し、3が得られる。
より理解するために、print文を追加しよう。
user> (def fib-seq
(lazy-cat [0 1]
(map
(fn [a b]
(println (format "%d + %d" a b)
(+ a b))
(rest fib-seq) fib-seq)))
;; => #'user/fib-sequser> (doall (take 10 fib-seq))
1 + 0
1 + 1
2 + 1
3 + 2
5 + 3
8 + 5
13 + 8
21 + 13
;; => (0 1 1 2 3 5 8 13 21 34)
lazy-seq
マクロ
シーケンスを生成する計算を貯めておくためのthunkを使っている。
・シーケンスの要素やチャンクが必要になったとき、その値を取り出すために次のthunkが呼び出される
・thunkはシーケンスの末尾を示すために次のサブルーチンを生成する
・thunkはシーケンスのインターフェースを実装していて、それぞれの thunkは一度だけ呼ばれ、その際にキャッシュされる。つまり、realized portionはただの値のシーケンスである。
シーケンスの先頭を保持する
ランダムな無限の遅延シーケンスを生成するために2つの方法がある
user> (defn infinite[] (lazy-seq (cons (rand) (infinite))))
;; => #'user/infinite--user> (defn infinite-1[] (lazy-seq (cons (rand) (infinite-1))))
;; => #'user/infinite-1
user> (def zyx (infinite-1))
もし (last (infinaite))
を実行すれば、クラッシュしないが、処理が終わることはない。一方、 (last zxy)
は OurOfMemoryError
ですぐにクラッシュする。
これは“holding onto the head”のためである。
(last (infinite))
の中で、Clojureは使用しないシーケンスのメンバーを判断できるので、シーケンスの使用しないメンバーを破棄する。そのため、メモリ不足にならない。一方、 (last zyz)
の中では、定義(def)を保持しているので、メモリを解放できず、 OutOfMemoryError
が発生する。
lazy-seq
の重要点
lazy-seq
は遅延シーケンスを生成する数多くの方法のうちの1つである。clojureだと、様々な方法で遅延シーケンスを生成できる。
もしシーケンスが遅延評価でない場合、シーケンスがシーケンスの先頭を保持し続け、ヒープ領域を多く消費してしまう。もしシーケンスが遅延評価であれば、今後の計算で使用されない分を捨てて、シーケンスを処理する。遅延シーケンスは巨大なシーケンスを処理する際や、シーケンシャルな計算のごく一部だけを使用する際に有用である。
参考:
https://purelyfunctional.tv/lesson/what-are-lazy-sequences/
http://theatticlight.net/posts/Lazy-Sequences-in-Clojure/
http://www.thesoftwaresimpleton.com/blog/2014/09/08/lazy-seq/