惰性递归定义导致结果错误

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

评论由：importer 制作

从 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 添加

此提议是捕获递归序列实现（即当在计算惰性序列的具象时尝试访问同一序列时）并抛出异常。

目前，在这种情况下，对序列的递归访问返回空值。这导致代码看似正确运行，但产生不正确的结果，甚至可能由于机会而导致正确的结果（请参阅https://groups.google.com/d/topic/clojure/yD941fIxhyE/discussion中的示例）。

因此，这个补丁将LazySeq状态（f、sv和s字段）的修改转移到了所有可能递归方法调用（.seq中的.sval和.sval中的.invoke）之前，这样在重新进入时，LazySeq的状态是一致的，并且能够传达序列已经正在计算的事实。

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

目前
状态 | f | sv | s
| :-- | :-- | :-- | :-- | :-- |
未实现 | 不为空 | 空值 | 空值
已实现 | 空值 | 空值 | 任何值
正在实现/由fn.invoke触发的递归调用 | 不为空 | 空值 | 空值
正在实现/由ls.sval触发的递归调用 | 空值 | 空值 | 空值
注意，"正在实现"的状态与"未实现"或"已实现"重叠。
（NB："任何值"包括空值）

使用该补丁
状态 | 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相同，但已更新以避免与2013年11月22日为CLJ-949提交的补丁冲突，该补丁基本上从方法sval()中删除了try/catch。它通过了测试，我没有发现任何问题，但如果Christophe能看看它也会很好。

Answer 11

评论者：alexmiller

不再可重复

Answer 12

_评论者：bronsa_

Alex，发布的示例现在无法重现，因为`(range)`不再生成分块-seq。
另一方面，`(range n)`可以这样做，即在工单描述中的代码示例中将`(range)`替换为类似`(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=> (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 13

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