Core.logic stackoverflow when using sets

Question

It seems that clojure.core.logic has problems with walk sets. Minimal unsuccessful example:

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

produces

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

Why does this create stackoverflow? merging with empty vectors / lists / maps / other types works as expected.

Answer 1

You have a response from the original author of core.logic that kits are not supported, but I think that you could formulate your question as a more leading one and perhaps received a more interesting answer about why the kits are not supported (for now) or what may be required to support them. Regarding why, I suspect that they are not really needed, because distincto and permuteo provide goals that can be used to test the properties of the set. As for what might be required to support them in a pool, follow below for a rude, ugly, incomplete, and ineffective first look.

Stack overflow occurs because sets are going and going while walking. But since sets are not supported, there is no transition implementation for sets, and by default for objects it is returning itself. The end result is that, from the point of view of sets, the drums contain themselves, and the stack is blown out, trying to put it to the bottom.

Join me on REPL, looking at the source and allow something to hack.

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

Tell core.logic to walk sets using the existing sequence implementation.

 (extend-protocol IWalkTerm clojure.lang.IPersistentSet (walk-term [vf] (with-meta (set (walk-term (seq v) f)) (meta v)))) (run* [q] (== q [])) ;=> ([]) (run* [q] (== q #{})) ;=> (#{}) 

Ok so far ...

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

Consistent but not very helpful

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

Now we have a problem. Both of the last two should return (2) , since the sets are not in order, but both do not return a result. We need to tell core.logic how to unify sets. Let them be lazy and try to use the existing permuteo to convey the lack of order.

 (extend-protocol IUnifyTerms clojure.lang.IPersistentSet (unify-terms [uvs] (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) 

Fine!

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

Very cool.

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

Nice ... but

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

So we were too permuteo using permuteo , try to reset it with clojure.math.combinatorics instead

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

And now...

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

It looks pretty promising.

Answer 2

Installations are not supported in core.logic.