core.logic stackoverflow when using sets

Question

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

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

produces

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)

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

Answer 1

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)

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

Consistent, but not terribly useful

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

Excellent!

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

And now...

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

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

Looks quite promising again.

Answer 2

Sets are not supported in core.logic.