Clojureにおける遅延シーケンスとループ処理の組み合わせにひそむ罠
Clojureにおける遅延シーケンスは非常に便利だが、繰り返し処理の中で用いたときに気づきにくいバグを生み出すことがある。以前、この問題にはまったことがあるので、ここにまとめておく。
本稿でとりあげる問題はStuart Sierra氏の記事[1]でも触れられており、一部サンプルコードを参考にしている。なお、本稿ではClojure 1.8を利用している。
問題
例として、concat関数を用いる。concat
は、引数として2つのコレクションを受け取り、その中身をつなげて1つのシーケンスとして返す関数である。複数のコレクションをつなぎ合わせる処理はよく登場するため、Clojureを使っている人なら日常的に使用している関数のはずだ。
(concat [1 2] [3 4])
;; => (1 2 3 4)
しかしこの関数は、使う場所によっては非常に気づきにくいバグを生み出すことがある。その問題は、loop/recur
内でconcat
を用いたときに発生する。たとえば、
1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 6, ...
のようなFractal sequenceを生成する関数を次のように書いてみる。
(defn frac [n]
(loop [i 0, ret []]
(if (< i n)
(recur (inc i) (concat ret (range 1 i)))
ret)))
末尾最適化されないClojureでも、loop/recur
を使えばStackOverflowErrorを発生させずに済むはずだ。このfrac
関数は、小さいn
を与えた場合は問題なく動作する。
(frac 8)
;; => (1 1 2 1 2 3 1 2 3 4 1 2 3 4 5 1 2 3 4 5 6 1 2 3 4 5 6)
(take 21 (frac 100))
;; => (1 1 2 1 2 3 1 2 3 4 1 2 3 4 5 1 2 3 4 5 6 1 2 3 4 5 6)
しかし、大きなn
を与えると、
(first (frac 3000))
;; StackOverflowError clojure.core/seq--4357 (core.clj:137)
とStackOverflowErrorが発生してしまう。しかも、そのスタックトレースはseq
, concat
, LazySeq
がひたすら繰り返されていてわかりづらい。
1. Unhandled java.lang.StackOverflowError
(No message)
core.clj: 137 clojure.core/seq
core.clj: 706 clojure.core/concat/fn
LazySeq.java: 40 clojure.lang.LazySeq/sval
LazySeq.java: 49 clojure.lang.LazySeq/seq
RT.java: 521 clojure.lang.RT/seq
core.clj: 137 clojure.core/seq
core.clj: 706 clojure.core/concat/fn
LazySeq.java: 40 clojure.lang.LazySeq/sval
LazySeq.java: 49 clojure.lang.LazySeq/seq
RT.java: 521 clojure.lang.RT/seq
core.clj: 137 clojure.core/seq
core.clj: 706 clojure.core/concat/fn
LazySeq.java: 40 clojure.lang.LazySeq/sval
LazySeq.java: 49 clojure.lang.LazySeq/seq
RT.java: 521 clojure.lang.RT/seq
core.clj: 137 clojure.core/seq
...
原因
以下は、concat
のソースコードから今回の問題と関係のない部分を取り去って単純化したものだ。
(defn concat [x y]
(lazy-seq
(if-let [s (seq x)]
(cons (first s) (concat (rest s) y))
y)))
lazy-seq
マクロによって、concat
はLazySeq
オブジェクトを返しているのがわかる。 今回のケースではloop/recur
によって、concat
の入れ子構造、すなわちLazySeq
のfn
が別のLazySeq
を返す、という入れ子構造になってしまっている。
first
等の関数は中でseq
を呼び出すが、このseq
がLazySeq
を実体化させる。 その際、実体化した結果が再びLazySeq
だと、実値が変えるまで再帰的に実体化させていく。 そのため、末尾最適化されていない再帰関数のように、スタックがあふれてエラーが発生してしまう。
解決策
1. 遅延シーケンスを使わない
単純な解決方法はconcat
を使わないことだ。同様のつなぎ合わせる処理は、into
を使うことでlazyではないものに変えることができる。
(defn frac2 [n]
(loop [i 0, ret []]
(if (< i n)
(recur (inc i) (into ret (range 1 i)))
ret)))
この改良したfrac2
関数は、大きいn
に対しても問題なく動作する。
(first (frac2 3000))
;; => 1
2. doallを使う
実体化していないLazySeq
が入れ子になることが問題なので、都度doall
で実体化させる手もある。
(defn frac3 [n]
(loop [i 0, ret []]
(if (< i n)
(recur (inc i) (doall (concat ret (range 1 i))))
ret)))
ただし、著しくパフォーマンスが低下する。
(time (first (frac3 1000)))
;; "Elapsed time: 6800.704 msecs"
;; => 1
(time (first (frac 1000)))
;; "Elapsed time: 0.832 msecs"
;; => 1
3. concatの実装を変更する
concat
の実装自体を修正して、エラーが発生しないようにする方法を提案している人もいる[2]。ここでは説明しないがGistにコードがあるので、興味あれば見てみると面白いかもしれない。
4. 別解
今回の場合、mapcat
を用いることで次のように書くこともできる。
(defn frac4 [n]
(mapcat (partial range 1) (range 1 n)))
(frac4 8)
;; => (1 1 2 1 2 3 1 2 3 4 1 2 3 4 5 1 2 3 4 5 6)
(first (frac4 3000))
;; => 1
考察
concat
とloop/recur
の組み合わせにだけ注意していればよいという話ではない。結局のところ、concat
した結果にconcat
を行うようなループ処理が行われれば、同様の問題が発生する。たとえば、reduce
やiterate
といった高階関数と組み合わせるケースが考えられる。
(defn frac5 [n]
(reduce concat (map (partial range 1) (range 1 n))))
(frac5 8)
;; => (1 1 2 1 2 3 1 2 3 4 1 2 3 4 5 1 2 3 4 5 6)
(first (frac5 3000))
;; StackOverflowError clojure.core/seq--4357 (core.clj:137)
この問題を一般化するならば、「遅延シーケンスを返す関数を繰り返し適用する場合にこの問題が発生しうる」となる。回避するためには、Clojureプログラムを書く上で、ある関数が遅延シーケンスを返すのかそうでないのかを意識しておく必要がある。clojure.coreのシーケンス処理関数の仕様を全て把握しておくだけでも難しいが、本稿でとりあげたconcat
とloop/recur
の組み合わせは最も登場しやすいパターンだと思うので、特に注意しておきたい。実際、以前に筆者がはまったときもこの組み合わせだった。