使用集时的core.logic stackoverflow [英] core.logic stackoverflow when using sets

问题描述

clojure.core.logic似乎在行走时出现问题.最小的失败示例:

It seems that clojure.core.logic has a problem walking sets. The minimal failing example:

(运行* [q](== q#{}))

产生

java.lang.StackOverflowError在clojure.core.logic.Substitutions.walk(logic.clj:344)在clojure.core.logic $ walk_STAR_ $ fn_ 2633.invoke(logic.clj:216)在clojure.core.logic $ eval2838 $ fn _2839.invoke(logic.clj:956)在clojure.core.logic.protocols $ eval1389 $ fn_ 1390 $ G _1380__1397.invoke(protocols.clj:55)在clojure.core.logic $ walk_STAR_.invoke(logic.clj:214)在clojure.core.logic $ walk_STAR_ $ fn_ 2633.invoke(logic.clj:218)在clojure.core.logic $ eval2838 $ fn _2839.invoke(logic.clj:956)在clojure.core.logic.protocols $ eval1389 $ fn_ 1390 $ G _1380__1397.invoke(protocols.clj:55)在clojure.core.logic $ walk_STAR_.invoke(logic.clj:214)在clojure.core.logic $ walk_STAR_ $ fn_ 2633.invoke(logic.clj:218)在clojure.core.logic $ eval2838 $ fn _2839.invoke(logic.clj:956)在clojure.core.logic.protocols $ eval1389 $ fn_ 1390 $ G _1380__1397.invoke(protocols.clj:55)在clojure.core.logic $ walk_STAR_.invoke(logic.clj:214)在clojure.core.logic $ walk_STAR_ $ fn_ 2633.invoke(logic.clj:218)在clojure.core.logic $ eval2838 $ fn _2839.invoke(logic.clj:956)在clojure.core.logic.protocols $ eval1389 $ fn_ 1390 $ G _1380__1397.invoke(protocols.clj:55)

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?与空白向量/列表/地图/其他类型统一可以正常工作.

Why does this generate a Stackoverflow? unifying with empty vectors/lists/maps/other types works as expected.

推荐答案

您从core.logic的原始作者那里得到了一个答案，即不支持集合，但我认为您可以说出您的问题更领先并且关于为什么不支持(还)或支持它们可能需要些什么，可能得到了更有趣的答复.至于为什么，我怀疑确实不需要它们，因为 distincto 和 permuteo 提供了可用于测试集合属性的目标.至于支持他们统一所需的内容，请按照下面的步骤进行粗略，丑陋，不完整和效率低下的初看起来.

You have an answer from the originating author of core.logic that sets aren't supported, but I think you could have phrased your question to be more leading and may have gotten a more interesting response as to why sets aren't supported (yet) or what it might take to support them. As to the why, I suspect they are really not needed because distincto and permuteo provide goals that can be used to test set properties. As to what it might take to support them in unification, follow along below for a rough, ugly, incomplete and inefficient first look.

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

The stack overflow occurs because sets are collections and collections are recursed into while walking. But since sets are not supported there is no walk implementation for sets and the default for objects is to return itself. The net result is that from the point of view of the walk sets contain themselves and the stack is blown trying to recurse to the bottom.

在查看源，让我们一起破解一些东西.

Join me on the REPL while looking at the source and let's hack together something.

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

让我们告诉core.logic使用现有的序列实现走路集.

Let's tell core.logic to walk sets by using the existing implementation for sequences.

(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 #{}))
;=> (#{})

到目前为止很好...

Good so far...

(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 传达缺乏秩序的情况.

Now we have a problem. Both of the last two should return (2) since sets have no order, but both return no results. We need to tell core.logic how to unify sets as well. Let's be lazy and try to use the existing permuteo to convey the lack of order.

(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 代替它

So we were a bit too sloppy using permuteo, let's try to kludge it with clojure.math.combinatorics instead

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

看起来很有希望.

这篇关于使用集时的core.logic stackoverflow的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！