使用集合时的core.logic stackoverflow

Question

似乎clojure.core.logic在行走集方面存在问题.最小的失败例子:

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

产生

位于clojure.core.logic上的clojure.core.logic.Substitutions.walk(logic.clj:344)的java.lang.StackOverflowError $ clo_ure上的$ walk_STAR_ $ fn_ 2633.invoke(logic.clj:216)$ 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 )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.一世 在clojure.core.logic.protocols上的nvoke(logic.clj:956)$ eval1389 $ fn_ 1390 $ G _1380__1397.invoke(protocols.clj:55)

为什么会生成Stackoverflow？与空矢量/列表/地图/其他类型统一工作按预期工作.

Answer 1

你有一个来自core.logic的原始作者的答案,不支持这些集合,但我认为你可以将你的问题提到更加领先,并且可能已经得到了一个更有趣的回答,为什么不支持集合(但是)或支持它们可能需要什么.至于为什么,我怀疑他们是真的没有必要,因为distincto并permuteo提供了可用于测试组属性的目标.至于在统一中支持它们可能需要做些什么,请按照下面的说明进行粗略,丑陋,不完整和低效的初看.

发生堆栈溢出是因为集合是集合,集合在行走时被递归.但是由于不支持集合,因此集合没有walk实现,对象的默认值是返回自身.最终的结果是,从步行集的角度来看,包含自己并且堆栈被吹向试图递归到底部.

在查看源代码的同时加入我的REPL ,让我们一起破解.

(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)

看起来很有希望了.