clojure - 使用集合时的 ​​core.logic stackoverflow

Question

clojure.core.logic 的行走集似乎有问题。最小的失败示例:

(run* [q] (== q #{}))

产生

java.lang.StackOverflowError at clojure.core.logic.Substitutions.walk(logic.clj:344) at clojure.core.logic$walk_STAR_$fn_2633.invoke(logic.clj:216) at clojure.core.logic$eval2838$fn_2839.invoke(logic.clj:956) at clojure.core.logic.protocols$eval1389$fn_1390$G_1380__1397.invoke(protocols.clj:55) at clojure.core.logic$walk_STAR_.invoke(logic.clj:214) at clojure.core.logic$walk_STAR_$fn_2633.invoke(logic.clj:218) at clojure.core.logic$eval2838$fn_2839.invoke(logic.clj:956) at clojure.core.logic.protocols$eval1389$fn_1390$G_1380__1397.invoke(protocols.clj:55) at clojure.core.logic$walk_STAR_.invoke(logic.clj:214) at clojure.core.logic$walk_STAR_$fn_2633.invoke(logic.clj:218) at clojure.core.logic$eval2838$fn_2839.invoke(logic.clj:956) at clojure.core.logic.protocols$eval1389$fn_1390$G_1380__1397.invoke(protocols.clj:55) at clojure.core.logic$walk_STAR_.invoke(logic.clj:214) at clojure.core.logic$walk_STAR_$fn_2633.invoke(logic.clj:218) at clojure.core.logic$eval2838$fn_2839.invoke(logic.clj:956) at clojure.core.logic.protocols$eval1389$fn_1390$G_1380__1397.invoke(protocols.clj:55)

为什么这会产生 Stackoverflow？与空向量/列表/ map /其他类型的统一按预期工作。

Answer 1

您从 core.logic 的原作者那里得到了一个答案，即不支持集合，但我认为您可以将您的问题表述得更具引导性，并且可能会得到更有趣的答复为什么 集(尚)不受支持，或者需要什么才能支持它们。至于原因，我怀疑它们确实不需要，因为 distincto 和 permuteo 提供了可用于测试集合属性的目标。至于如何支持它们统一，请跟随下面的粗略、丑陋、不完整和低效的初步了解。

发生堆栈溢出是因为集合是集合，并且集合是在行走时递归的。但由于不支持集合，因此没有集合的 walk 实现，并且对象的默认值是返回自身。最终结果是，从遍历集的角度来看，它们包含了它们自己，并且堆栈在尝试递归到底部时被炸毁。

跟我一起加入 REPL，同时查看 source让我们一起来破解一些东西。

(use 'clojure.core.logic)
(use 'clojure.core.logic.protocols)

让我们告诉 core.logic 通过使用现有的序列实现来遍历集合。

(extend-protocol IWalkTerm 
  clojure.lang.IPersistentSet 
  (walk-term [v f] (with-meta (set (walk-term (seq v) f)) (meta v))))

(run* [q] (== q []))
;=> ([])
(run* [q] (== q #{}))
;=> (#{})

到目前为止还不错...

(run* [q] (== q [1 2 3]))
;=> ([1 2 3])
(run* [q] (== q #{1 2 3}))
;=> (#{1 2 3})

一致，但不是很有用

(run* [q] (== [1 q 3] [1 2 3]))
;=> (2)
(run* [q] (== #{1 q 3} #{1 2 3}))
;=> ()
(run* [q] (== #{1 3 q} #{1 2 3}))
;=> ()

现在我们遇到了问题。最后两个都应该返回 (2) 因为集合没有顺序，但两者都不返回结果。我们还需要告诉 core.logic 如何统一集合。让我们偷懒一下，尝试使用现有的 permuteo 来表达缺乏秩序的情况。

(extend-protocol IUnifyTerms 
  clojure.lang.IPersistentSet 
  (unify-terms [u v s] (bind s (permuteo (seq u) (seq v)))))

(run* [q] (== #{1 q 3} #{1 2 3}))
;=> (2)
(run* [q] (== #{3 1 q} #{1 2 3})) 
;=> (2)

非常好!

(run* [q] (fresh [a1 a2 a3] (== #{a1 a2 a3} #{1 2 3}) (== q [a1 a2 a3])))
;=> ([1 2 3] [2 1 3] [1 3 2] [3 1 2] [2 3 1] [3 2 1])

非常酷。

(run* [q] (== #{1 2 [3 q]} #{1 2 [3 4]}))
;=> (4)

不错...但是

(run* [q] (== #{1 2 #{3 q}} #{1 2 #{3 4}}))
;=> IllegalArgumentException No implementation of method: :walk of protocol:  #'clojure.core.logic.protocols/ISubstitutions found for class: clojure.core.logic$permuteo$fn...

所以我们使用 permuteo 有点太草率了，让我们尝试用 clojure.math.combinatorics 来拼凑它

(use 'clojure.math.combinatorics)

(extend-protocol IUnifyTerms 
  clojure.lang.IPersistentSet 
  (unify-terms [u v s]
    (when (set? v)
      (let [u (seq u)
            v (seq v)]
        (reduce #(mplus % (-inc %2)) 
                (for [p (permutations u)] (unify s p v))))))) 

现在...

(run* [q] (== #{1 2 #{3 q}} #{1 2 #{3 4}}))
;=> 4

(run* [q] (== #{ #{ #{q} :bar} :baz}  #{:baz #{:bar #{:foo} } }))
;=> (:foo)

看起来再次很有希望。