Allow unification with sequential in both directions

Question

Currently I can't find a way to enable a custom data type to do unification with sequential objects in both direction. You can use IUnifyTerms to make it work in one direction, but it isn't possible to make it work in the other direction (i.e. when the sequential object is first).

The problem seemes to be in the following code:

`
(defn unify-with-sequential* [u v s]
(cond

(sequential? v)
(if (and (counted? u) (counted? v)
      (not= (count u) (count v)))
  nil
  (loop [u u v v s s]
    (if (seq u)
      (if (seq v)
        (if-let [s (unify s (first u) (first v))]
          (recur (next u) (next v) s)
          nil)
        nil)
      (if (seq v) nil s))))

(lcons? v) (unify-terms v u s)
:else nil))

`

If the final nil could be replaced with a call to a protocol (IUnifyTermsReversed ???IUnifyWithSequential ???) then I believe it would make this extensible.

Answer 1

Comment made by: dnolen

I'm assume it's undesirable for your datatype to implement ISequential?

Answer 2

Comment made by: mikera

It's undesirable because an expression can be a leaf node as well:

(+ 3 X) ;; OK as sequential
7 ;; definitely not sequential!

Hence making Expression implement ISequential would be problematic and break all kinds of contracts.....

Trying to unify the leaf node with a sequential object should fail of course, but that's logic I need to implement myself (I think??)

Answer 3

Comment made by: dnolen

I'm still not following as there's some context about your use case that I'm missing. Do you have a concrete core.logic example that you should think should work?

Answer 4

Comment made by: mikera

Sure, here is my test case:

(let [ex1 (ex [+ 1 X])] ;; an expression containing (+ 1 X) (is (= [(ex X)] (run* [q] (fresh [op p] (== [op p q] ex1))))) ;; fails (is (= [(ex X)] (run* [q] (fresh [op p] (== ex1 [op p q]))))) ;; OK )

The first case fails (because of unify-with-sequential* returning nil as above). The second case is OK because it goes through my own implementation of IUnifyTerms. I may be wrong, but I don't think I can make it work without a change in core.logic itself.

Answer 5

Comment made by: dnolen

We used to support unifying in both directions but it made for a large number of protocols that had to be implemented. Recently I've been thinking it may be useful to provide coercion protocols, something like ICoerceToSequential.

Answer 6

Comment made by: mikera

I think it is necessary to be able to support unifying in both directions somehow if custom data structures are ever going to be first-class citizens in core.logic?

I see how you could achieve this with ICoerceToSequential however so that might be a good solution. We do something a bit similar in core.matrix (to handle coercions between different back-end matrix implementations).

Answer 7

Comment made by: dnolen

custom data structures are already first class. Whether we should allow overloading unification of custom types with core Clojure interfaces/protocols/types is another matter entirely.

And sorry for the confusion. It's not clear to me why you want sequential to work, from your examples it appears that you have a proper expression type, what advantage is there for you to unify with sequential?

Answer 8

Comment made by: mikera

I think it may be important if you have "sequence-like" data structures that aren't precisely sequential? but are conceptually equivalent to sequences. My custom Expression type is one example, and for interop reasons things like java.util.ArrayList spring to mind.

As it happens, I've switched back to using regular lists for the moment so the issue isn't a blocker for me. But it may still be worth thinking about.

Couple of advantages of doing this kind of unification would appear to be:
a) notational - you can use regular Clojure lists and vectors for unifying with something sequence-like
b) efficiency - avoid constructing a new custom object when it isn't needed (though the cost is probably too trivial to bother about in most cases....)

Of course, you may decide it is simpler and purer to avoid these complications, which is fine. But it seems a shame to have all the nice extensible protocols, and not quite be able to fully extend the functionality to custom types....

Answer 9

Reference: https://clojure.atlassian.net/browse/LOGIC-123 (reported by mikera)