lazy-seq in Clojure (翻訳)

https://medium.com/lazy-eval/lazy-seq-in-clojure-da06f6d35971 の雑な翻訳。

lazy-seqはどのような仕組みで動くのか、なぜ必要とされるのか？

根本的な概念： 値が必要になるまで、式の評価を遅らせる

遅延評価を実現するための方法は以下の２つ

・ ランタイムにラムダ関数を使う

・コンパイルにマクロ/特殊なフォームを使う

ラムダ、クロージャ、再帰を使った遅延評価のテクニックで、無限のデータ構造を作ることができる。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] はこの問題の基本ケースである。フィボナッチ数列の最初２つの値は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番目の要素である１と [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-seq
user> (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/