clojure - 为什么这个 Clojure 素数生成器会引发 StackOverflowError？

Question

这个问题已经有答案了:

Recursive function causing a stack overflow (2 个回答)

已关闭 3 年前。

我刚刚学习 Clojure，像往常一样学习新的编程语言，我尝试的第一件事就是实现埃拉托斯特尼筛法。

我想出了以下解决方案:

(defn primes
 "Calculate all primes up to the given number"
 [n]
 (loop
   [
    result []
    numbers (range 2 (inc n))
    ]
   (if (empty? numbers)
     result
     (let [[next & rest] numbers]
       (recur (conj result next) (filter (fn [n] (not= 0 (mod n next))) rest)))
     )
   )
 )

对于较小的数字，它工作得很好并且相当快，但对于较大的输入，会引发 StackOverflowError 并带有可疑的短堆栈跟踪，例如:

(primes 100000)
Execution error (StackOverflowError) at (REPL:1).
null
(pst)
StackOverflowError 
    clojure.lang.LazySeq.sval (LazySeq.java:42)
    clojure.lang.LazySeq.seq (LazySeq.java:51)    
    clojure.lang.RT.seq (RT.java:531)
    clojure.core/seq--5387 (core.clj:137)    
    clojure.core/filter/fn--5878 (core.clj:2809)
    clojure.lang.LazySeq.sval (LazySeq.java:42)
    clojure.lang.LazySeq.seq (LazySeq.java:51)
    clojure.lang.RT.seq (RT.java:531)
    clojure.core/seq--5387 (core.clj:137)
    clojure.core/filter/fn--5878 (core.clj:2809)
    clojure.lang.LazySeq.sval (LazySeq.java:42)
    clojure.lang.LazySeq.seq (LazySeq.java:51)
=> nil

我的印象是，如果recur最后以循环形式进行评估，那么recur就实现了尾递归，我的第一个问题是这里是否确实如此。我的第二个问题是为什么 StackOverflowError 的堆栈跟踪如此短。我在解释堆栈跟踪时也遇到问题，即。哪一行对应什么形式。

我只对更好或更像 Clojure 的解决方案感兴趣，如果它们为这些问题提供了见解，否则我想自己找到它们。谢谢!

Answer 1

稍微修改一下，用注释来描述每一行发生的事情，这是你的函数:

(defn primes
  "Calculate all primes up to the given number"
  [n]
  ;; `loop` is not lazy, it runs until it produces a result:
  (loop [result []
         ;; a lazy sequence implemented by clojure.lang.LongRange:
         numbers (range 2 (inc n))]
    (if (not (nil? (seq numbers)))
      result
      (let [current (first numbers)
            remaining (rest numbers)]
        (recur
         ;; `conj` on a vector returns a vector (non-lazy):
         (conj result current)
         ;; `filter` on a lazy sequence returns a new lazy sequence:
         (filter (fn [n] (not= 0 (mod n next)))
                 remaining))))))

关键是最后的过滤器。

大多数惰性序列操作(例如filter)通过将一个惰性序列包装在另一个惰性序列中来工作。在循环的每次迭代中，filter 添加另一层惰性序列，如下所示:

(filter (fn [n] (not= 0 (mod n 5)))       ; returns a LazySeq
  (filter (fn [n] (not= 0 (mod n 4)))     ; returns a LazySeq
    (filter (fn [n] (not= 0 (mod n 3)))   ; returns a LazySeq
      (filter (fn [n] (not= 0 (mod n 2))) ; returns a LazySeq
        remaining))))

LazySeq 对象堆叠在一起，每个对象都保存对前一个对象的引用。

对于大多数惰性序列，包装并不重要，因为一旦您请求一个值，它们就会自动“展开”。这发生在 LazySeq.seq .

这是一种确实很重要的情况，因为您的循环构建了如此多的延迟序列对象层，以至于对 LazySeq.seq 和 的嵌套调用.sval 溢出 JVM 允许的最大堆栈大小。这就是您在堆栈跟踪中看到的内容。

(这也有内存影响，因为对序列开头的引用会阻止任何其他序列被垃圾收集，Clojure 程序员将其称为“保留序列的头部”。)

此函数更常见的问题是混合惰性(过滤器)和非惰性(循环)操作。这通常是问题的根源，因此 Clojure 程序员出于习惯而学会避免它。

正如 Alan 所建议的，您可以通过仅使用非惰性操作来避免该问题，例如 filterv 而不是 filter，这会强制将惰性序列转换为向量。

几乎任何类型的惰性求值都可能表现出此问题的一些变化。我在Clojure don'ts: concat中描述过它。另一个例子请参阅 foldr versus foldl在 haskell 。

即使没有惰性，深度嵌套的对象树也可能导致 StackOverflow，例如在 Java 中我发现 xstream#88或circe#1074 .