June 29, 2016
このエントリーをはてなブックマークに追加

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マクロによって、concatLazySeqオブジェクトを返しているのがわかる。 今回のケースではloop/recurによって、concatの入れ子構造、すなわちLazySeqfnが別のLazySeqを返す、という入れ子構造になってしまっている。

first等の関数は中でseqを呼び出すが、このseqLazySeqを実体化させる。 その際、実体化した結果が再び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

考察

concatloop/recurの組み合わせにだけ注意していればよいという話ではない。結局のところ、concatした結果にconcatを行うようなループ処理が行われれば、同様の問題が発生する。たとえば、reduceiterateといった高階関数と組み合わせるケースが考えられる。

(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のシーケンス処理関数の仕様を全て把握しておくだけでも難しいが、本稿でとりあげたconcatloop/recurの組み合わせは最も登場しやすいパターンだと思うので、特に注意しておきたい。実際、以前に筆者がはまったときもこの組み合わせだった。


参考文献

  1. Clojure Don’ts: Concat – Digital Digressions by Stuart Sierra
  2. Concat implementation without stack overflow - Google Groups
Tags: Clojure