懒递归定义导致结果错误

Question

如果您在一个全局数据变量中使用懒序列引用该变量，那么您可能会根据构建集合所使用的函数的懒加载程度不同，得到不同的结果。

Clojure 的懒序列不承诺支持这一点，但它们不应该返回错误的结果。在http://groups.google.com/group/clojure/browse_thread/thread/1c342fad8461602d（以下重复）中给出的示例，Clojure 不应返回错误数据。错误消息会很好，即使无限循环也比当前行为更合理。

(在https://groups.google.com/d/topic/clojure/yD941fIxhyE/discussion中报告了类似问题)

(def nums (drop 2 (range Long/MAX_VALUE)))
(def primes (cons (first nums)
             (lazy-seq (->>
               (rest nums)
               (remove
                 (fn [x]
                   (let [dividors (take-while #(<= (* % %) x)
primes)]
                     (println (str "primes = " primes))
                     (some #(= 0 (rem x %)) dividors))))))))
(take 5 primes)

它打印出
(primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
2 3 5 7 9)

Answer 1

评论由：导入者

从http://www.assembla.com/spaces/clojure/tickets/457 转换而来

Answer 2

评论由：aaron

Stu 和 Rich 讨论过将其视为错误，但这会破坏一些现有的代码。

Answer 3

评论由：richhickey 提出

对此有什么具体问题吗？

Answer 4

评论由：aaron

Stu，我和你讨论过这个问题，但我记不清楚确切的问题是什么了。

Answer 5

评论由：cgrand 提出

附件：已提出一个尝试性的补丁。
你有这样的补丁导致现有代码破坏的例子吗？（如 Aaron Bedra 提到的）

Answer 6

评论由：richhickey 提出

这个补丁打算做什么？我们只有问题描述和代码。请列出计划，而不要让我们去解码补丁。

作为一个基本原则，我不希望 Clojure 承诺递归定义的值是可能的。

Answer 7

评论由：cgrand 提出

这里的建议是在遇到递归序列实现（即计算懒序列体时尝试访问同一个序列）时抛出异常。

目前，当这种情况发生时，递归访问序列返回 nil。这导致看似正确的代码产生了不正确的结果，甚至是在运气好时，在不正确的代码中产生了正确的输出（请参考 https://groups.google.com/d/topic/clojure/yD941fIxhyE/discussion 中的此类示例）。

所以这个补丁在所有可能触发递归方法调用的修改都进行之前，移动到 LazySeq 状态（f、sv 和 s 字段）上，在重新进入时，LazySeq 的状态是一致的，并且能够传达序列已经在被计算的事实。

目前，递归调用可能发现 f 和 sv 已清除，并得出结论计算已完成，结果已存在于 s 中，尽管 s 尚未受到影响。

目前
|状态|f|sv|s|
| :-- | :-- | :-- | :-- | :-- |
未实现|非空|空|空|
已实现|空|空|任何内容|
正在实现/从fn.invoke的递归调用|非空|空|空|
正在实现/从ls.sval的递归调用|空|空|空|
请注意，“正在实现”的状态与“未实现”或“已实现”的状态重叠。
（注意：“任何内容”包括空）

使用补丁
|状态|f|sv|s|
| :-- | :-- | :-- | :-- | :-- |
未实现|非空|空|空|
已实现|空|空|除了这个以外的任何内容|
正在实现|空|空|这个|

Answer 8

评论者：jafingerhut

那个最后的评论，Christophe，至少让我对这个想法有了深刻的理解。是否有机会将类似内容的评论作为补丁的一部分添加？

Answer 9

评论由：cgrand 提出

包含说明预期状态的补丁。
注意：我已经整理了状态表。

在调用用户代码（sval中的f.invoke()和在seq中的((LazySeq)ls).sval()，甚至在seq中的RT.seq()）之前，确保LazySeq状态处于以下状态之一： // // 状态 f sv // ================================ // 未实现 非空 空 // 已实现 空 空 // 正在实现 空 这个

CLJ-1119也因为这个补丁而修复。

Answer 10

评论者：jafingerhut

补丁clj-457-3.diff与Christophe的CLJ-457-2.diff相同， except它已更新，不再与2013年11月22日为CLJ-949提交的commit冲突，该commit基本上删除了sval()方法中的try/catch。它已经通过了测试，我没有发现任何错误，但如果Christophe也能看一下的话那就更好了。

Answer 11

评论者：alexmiller

不再可复制

Answer 12

_评论者：bronsa_

Alex，发布的示例不再可复制，因为`(range)`不再生成chunked-seq。
另一方面，用`(range n)`替换`(range)`在ticket描述中的代码示例中的`(range Long/MAX_VALUE)`就足够使错误再次出现。




Clojure 1.8.0-master-SNAPSHOT
user=> (def nums (drop 2 (range Long/MAX_VALUE)))
#'user/nums
(def primes (cons (first nums)
             (lazy-seq (->>
               (rest nums)
               (remove
                 (fn [x]
                   (let [dividors (take-while #(<= (* % %) x)
primes)]
                     (println (str "primes = " primes))
                     (some #(= 0 (rem x %)) dividors))))))))
#'user/primes
user=> (取5个素数)
(primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
primes = (2)
2 3 5 7 9)

Answer 13

参考：https://clojure.atlassian.net/browse/CLJ-457（由 alex+import 报告）