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

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 以获取此类示例）。

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

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

目前
|状态|f|sv|s|
| :-- | :-- | :-- | :-- | :-- |
|未实现|不为null|null|null|
|已实现|null|null|任何东西|
|正在实现/来自fn.invoke的递归调用|不为null|null|null|
|正在实现/来自ls.sval的递归调用|null|null|null|
请注意，“正在实现”状态与未实现或已实现状态重叠。
（注：“任何东西”包括null）

有了这个补丁
|状态|f|sv|s|
| :-- | :-- | :-- | :-- | :-- |
|未实现|不为null|null|null|
|已实现|null|null|但不是这个|
|正在实现|null|null|这个|

Answer 8

评论者：jafingerhut

最后一个评论，Christophe，对我解释这个想法非常有帮助。是否有机会将类似内容的评论作为补丁的一部分添加？

Answer 9

评论由：cgrand 撰写

带有解释预期状态的注释的新补丁。
注意：我整理了状态表。

// 在调用用户代码之前（sval中的f.invoke()和，间接地，// seq中的((LazySeq)ls).sval() -- even RT.seq() in seq)，确保// LazySeq状态处于以下这些状态之一：// // 状态 f sv // ================================== // 未实现 不为null null // 已实现 null null // 正在实现 null this

CLJ-1119也由这个补丁修复。

Answer 10

评论者：jafingerhut

Patch 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)` 现在不再生成 chunked-seq，已发布的示例无法再重现。
另一方面，将票证描述中的代码示例中的 `(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 报告）