为什么这个 Clojure 素数生成器会引发 StackOverflowError？
Why does this Clojure prime generator raises a StackOverflowError?
我刚刚开始学习 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)))
)
)
)
对于小数字，它工作得很好并且非常快，但对于大输入，会引发 WhosebugError，并带有可疑的短堆栈跟踪，例如：
(primes 100000)
Execution error (WhosebugError) at (REPL:1).
null
(pst)
WhosebugError
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 最后以 loop 形式求值，它会实现尾递归，我的第一个问题是，如果这里确实是这种情况。我的第二个问题是为什么 WhosebugError 的堆栈跟踪如此短。我在解释堆栈跟踪时也有问题，即。什么行对应什么形式
我只对更好或更像 Clojure 的解决方案感兴趣，如果它们能为这些问题提供见解，否则我想自己找到它们。谢谢！
这是一个有效的版本：
(ns tst.demo.core
(:use tupelo.core tupelo.test))
(defn primes
"Calculate all primes up to the given number"
[n]
(loop [result []
numbers (range 2 (inc n))]
(if (empty? numbers)
result
(let [[new-prime & candidate-primes] numbers]
(recur
(conj result new-prime)
(filterv (fn [n] (not= 0 (mod n new-prime)))
candidate-primes))) )))
(dotest
(spyx (primes 99999))
)
结果：
-------------------------------
Clojure 1.10.1 Java 13
-------------------------------
Testing tst.demo.core
(primes 99999) => [2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61
67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163
167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263
269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373
379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479
487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601
...<snip>...
99401 99409 99431 99439 99469 99487 99497 99523 99527 99529 99551 99559
99563 99571 99577 99581 99607 99611 99623 99643 99661 99667 99679 99689
99707 99709 99713 99719 99721 99733 99761 99767 99787 99793 99809 99817
99823 99829 99833 99839 99859 99871 99877 99881 99901 99907 99923 99929
99961 99971 99989 99991]
我稍微重命名了你的变量，使它们更清晰。如果仔细观察，您会发现唯一实质性的区别是从懒惰 filter 到急切 filterv.
的变化
在此更改之前，它对 9999 的 N 有效，但对 99999 无效。
我不确定惰性 filter 函数的实现，但这显然是问题所在。
像这样的奇怪（和不可预测的）问题加深了我对 Clojure 代码中过度惰性的厌恶。您似乎遇到了 Clojure Don'ts: Concat 问题的变体。在这种情况下，您的代码如下所示：
(filter ...
(filter ...
(filter ...
(filter ...
...<many, many more>... ))))
惰性序列作为嵌套函数调用实现。由于查找素数 99991 的最后一个循环依赖于查找素数 2 的第一个调用，因此无法释放较早的惰性序列（及其在堆栈上的嵌套函数调用），最终会破坏堆栈。
在我的电脑上，阶乘(N) 的简单递归实现在 N=4400 左右爆炸。上面找到了 9592 个质数，所以它的具体原因似乎比每个质数 1 个堆栈帧更复杂。
可能 N=32 分块可以发挥作用。
为了避免不必要的懒惰导致的错误，您可能有兴趣将 concat 替换为 glue, and replacing for with forv. You can also see the full API docs。
略作修改，用注释描述每一行发生的事情，这是你的功能：
(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 添加另一层惰性序列，如下所示：
(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 个对象堆叠起来，每个对象都持有对前一个对象的引用。
对于大多数惰性序列，换行并不重要，因为它们会在您请求一个值时自动 "unwrap"。这发生在 LazySeq.seq.
这是 重要的一种情况，因为您的循环构建了太多层的惰性序列对象，以至于嵌套调用了 LazySeq.seq 和 .sval 溢出 JVM 允许的最大堆栈大小。这就是您在堆栈跟踪中看到的。
（这也有内存影响，因为对序列开头的引用会阻止任何其他序列被垃圾回收，Clojure 程序员将序列称为 "holding on to the head"。）
此函数更普遍的问题是混合惰性 (filter) 和非惰性 (loop) 操作。这通常是问题的根源，因此 Clojure 程序员会出于习惯学会避免它。
正如 Alan 所建议的，您可以通过仅使用非惰性操作来避免此问题，例如 filterv 而不是 filter，这会强制将惰性序列转换为向量。
几乎任何类型的懒惰求值都可以表现出这个问题的一些变体。我在 Haskell 中的 Clojure don'ts: concat. For another example see foldr versus foldl 中描述了它。
即使没有懒惰，深度嵌套的对象树也会导致 Whosebug，例如 Java 我发现 xstream#88 or circe#1074.
我刚刚开始学习 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)))
)
)
)
对于小数字，它工作得很好并且非常快，但对于大输入，会引发 WhosebugError，并带有可疑的短堆栈跟踪，例如：
(primes 100000)
Execution error (WhosebugError) at (REPL:1).
null
(pst)
WhosebugError
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 最后以 loop 形式求值，它会实现尾递归，我的第一个问题是，如果这里确实是这种情况。我的第二个问题是为什么 WhosebugError 的堆栈跟踪如此短。我在解释堆栈跟踪时也有问题，即。什么行对应什么形式
我只对更好或更像 Clojure 的解决方案感兴趣，如果它们能为这些问题提供见解，否则我想自己找到它们。谢谢！
这是一个有效的版本：
(ns tst.demo.core
(:use tupelo.core tupelo.test))
(defn primes
"Calculate all primes up to the given number"
[n]
(loop [result []
numbers (range 2 (inc n))]
(if (empty? numbers)
result
(let [[new-prime & candidate-primes] numbers]
(recur
(conj result new-prime)
(filterv (fn [n] (not= 0 (mod n new-prime)))
candidate-primes))) )))
(dotest
(spyx (primes 99999))
)
结果：
-------------------------------
Clojure 1.10.1 Java 13
-------------------------------
Testing tst.demo.core
(primes 99999) => [2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61
67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163
167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263
269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373
379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479
487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601
...<snip>...
99401 99409 99431 99439 99469 99487 99497 99523 99527 99529 99551 99559
99563 99571 99577 99581 99607 99611 99623 99643 99661 99667 99679 99689
99707 99709 99713 99719 99721 99733 99761 99767 99787 99793 99809 99817
99823 99829 99833 99839 99859 99871 99877 99881 99901 99907 99923 99929
99961 99971 99989 99991]
我稍微重命名了你的变量，使它们更清晰。如果仔细观察，您会发现唯一实质性的区别是从懒惰 filter 到急切 filterv.
在此更改之前，它对 9999 的 N 有效，但对 99999 无效。
我不确定惰性 filter 函数的实现，但这显然是问题所在。
像这样的奇怪（和不可预测的）问题加深了我对 Clojure 代码中过度惰性的厌恶。您似乎遇到了 Clojure Don'ts: Concat 问题的变体。在这种情况下，您的代码如下所示：
(filter ...
(filter ...
(filter ...
(filter ...
...<many, many more>... ))))
惰性序列作为嵌套函数调用实现。由于查找素数 99991 的最后一个循环依赖于查找素数 2 的第一个调用，因此无法释放较早的惰性序列（及其在堆栈上的嵌套函数调用），最终会破坏堆栈。
在我的电脑上，阶乘(N) 的简单递归实现在 N=4400 左右爆炸。上面找到了 9592 个质数，所以它的具体原因似乎比每个质数 1 个堆栈帧更复杂。
可能 N=32 分块可以发挥作用。
为了避免不必要的懒惰导致的错误，您可能有兴趣将 concat 替换为 glue, and replacing for with forv. You can also see the full API docs。
略作修改，用注释描述每一行发生的事情，这是你的功能：
(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 添加另一层惰性序列，如下所示：
(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 个对象堆叠起来，每个对象都持有对前一个对象的引用。
对于大多数惰性序列，换行并不重要，因为它们会在您请求一个值时自动 "unwrap"。这发生在 LazySeq.seq.
这是 重要的一种情况，因为您的循环构建了太多层的惰性序列对象，以至于嵌套调用了 LazySeq.seq 和 .sval 溢出 JVM 允许的最大堆栈大小。这就是您在堆栈跟踪中看到的。
（这也有内存影响，因为对序列开头的引用会阻止任何其他序列被垃圾回收，Clojure 程序员将序列称为 "holding on to the head"。）
此函数更普遍的问题是混合惰性 (filter) 和非惰性 (loop) 操作。这通常是问题的根源，因此 Clojure 程序员会出于习惯学会避免它。
正如 Alan 所建议的，您可以通过仅使用非惰性操作来避免此问题，例如 filterv 而不是 filter，这会强制将惰性序列转换为向量。
几乎任何类型的懒惰求值都可以表现出这个问题的一些变体。我在 Haskell 中的 Clojure don'ts: concat. For another example see foldr versus foldl 中描述了它。
即使没有懒惰，深度嵌套的对象树也会导致 Whosebug，例如 Java 我发现 xstream#88 or circe#1074.