Relational maps for core.logic

The central idea is the same as the list tail. A map that is only partly known is a set of known entries plus an unbound rest:

(run* [m] (geto m :a 1))
;;=> ((lmap {:a 1} | _0))

Read (lmap {:a 1} | _0) as "a map with :a → 1, plus whatever _0 holds". _0 is a map too, and it is constrained not to contain :a: the entries and the rest never overlap. Ask for more and the open map grows:

(run* [m] (geto m :a 1) (geto m :b 2))
;;=> ((lmap {:b 2, :a 1} | _0))

Close it by saying what all the keys are:

(run* [m] (geto m :a 1) (geto m :b 2) (keyso m #{:a :b}))
;;=> ({:a 1, :b 2})

An open map with nothing left open is just a Clojure map. Answers come back as ordinary maps whenever they can.

geto is get. Forwards it looks up; with the key unknown it enumerates; with the value known it searches:

(run* [v] (geto {:a 1 :b 2} :b v))      ;;=> (2)
(run* [k v] (geto {:a 1 :b 2} k v))     ;;=> ([:a 1] [:b 2])
(run* [k] (geto {:a 1 :b 2} k 2))       ;;=> (:b)

assoco is assoc. Run backwards, it finds every map that assoc could have produced the output from:

(run* [out] (assoco {:a 1} :b 2 out))          ;;=> ({:a 1, :b 2})
(run* [m] (assoco m :b 2 {:a 1 :b 2}))         ;;=> ({:a 1} {:a 1, :b _0})
(run* [k v] (assoco {:a 1} k v {:a 1 :b 2}))   ;;=> ([:b 2])

The second answer matters. m either had no :b, or had :b with any value that assoc overwrote. Both are real answers, and a relational assoc that returned only the first would be wrong.

dissoco is dissoc, the same way round:

(run* [out] (dissoco {:a 1 :b 2} :a out))  ;;=> ({:b 2})
(run* [m] (dissoco m :a {:b 2}))           ;;=> ({:b 2} {:b 2, :a _0})
(run* [k] (dissoco {:a 1 :b 2} k {:b 2}))  ;;=> (:a)

mergeo is merge. Backwards it splits a map every way merge could have built it, including the overwritten values:

(run* [m1] (mergeo m1 {:b 2} {:a 1 :b 2}))
;;=> ({:a 1} {:a 1, :b _0})

Nested data has get-ino and assoc-ino, with the path as one more argument. Asking for the path asks where a value is:

(run* [p] (get-ino {:users [{:name "ada"} {:name "bob"}]} p "bob"))
;;=> ((:users 1 :name))

More of that, through maps and vectors, in part 4.

One relation has no counterpart in clojure.core, because it is what the open map is made of: (lmapo m entries rest), m is entries plus a map rest that has none of their keys. It's conj for maps, without the overwriting. (conj r [:a 1]) replaces an :a that r already had, so run backwards it has two cases. lmapo says r has no :a, so there is one, the way (cons x xs) never displaces anything:

(run* [r] (conjo r [:a 1] {:a 1 :b 2}))      ;;=> ({:b 2} {:b 2, :a _0})
(run* [r] (lmapo {:a 1 :b 2} {:a 1} r))      ;;=> ({:b 2})
(run* [x r] (lmapo {:a 1 :b 2 :c 3} {:a x} r))  ;;=> ([1 {:b 2, :c 3}])

It also builds: with everything unknown, (lmapo m {:a 1} r) answers the open map (lmap {:a 1} | _0) at once, and that printed form is this relation: these entries, plus a rest without their keys.

The rest of the API:

(run* [ks] (keyso {:a 1 :b 2} ks))                  ;;=> (#{:a :b})
(run* [out] (selectso {:a 1 :b 2 :c 3} [:a :c] out)) ;;=> ({:c 3, :a 1})

keyso answers a set, where Clojure's keys returns a seq. The seq's order is whatever the map happens to hold, and it means nothing: {:a 1 :b 2} and {:b 2 :a 1} are the same map. A relation can't pick one order without failing a query that asks for another, so a seq of keys would have to list every order: n! answers for one fact, 3.6 million for ten keys. The keys of a map are a set, so keyso says so and has one answer. Sets are relational (part 7), so the key set can be partly known, and unknown keys pair up with the map's. The flip side: (keyso m [:a :b]) fails, as (= #{:a :b} [:a :b]) is false. valso stays a seq in any order, since values can repeat.

The part I'm happiest with: you don't need any of the relations to get relational maps. Plain Clojure maps unify relationally, even when their keys are logic variables:

(run* [k] (== {k 1 :b 2} {:a 1 :b 2}))          ;;=> (:a)
(run* [k1 k2] (== {k1 1 k2 2} {:a 1 :b 2}))     ;;=> ([:a :b])
(run* [k1 k2 v] (== {k1 v k2 v} {:a 1 :b 1}))   ;;=> ([:a :b 1] [:b :a 1])

The last one has two answers because both pairings are real. Upstream core.logic looks keys up as they are, so the variables k1 and k2 are themselves the keys, never bound; they match neither :a nor :b, and the query fails.

A Clojure map can't have two equal keys, and that holds here too, even if the keys only become equal later:

(run* [k1 k2] (== {k1 1 k2 1} {:a 1}))                ;;=> ()
(run* [k1 k2] (== k1 k2) (== {k1 1 k2 2} {:a 1 :b 2}))  ;;=> ()
(run* [k1 k2]
  (fresh [m] (== m {k1 1 k2 2}) (== k1 :a) (== k2 :a)))  ;;=> ()

The last query is the hard case: the map was built when its keys were still distinct variables, and only afterwards were both bound to :a. The next post is about how that is caught without making everything else slow.

Some queries have no finite answer yet. "Some map holds 1 under some key" is one. Instead of guessing, the goal waits and shows up in the answer as a constraint:

(run* [m] (fresh [k] (geto m k 1)))
;;=> ((_0 :- (clojure.core.logic/geto _0 _1 1)))

That is the rule this fork is built on: a relation either answers correctly, or it says what it is still waiting for. It never quietly answers wrong.

Absence is a real constraint, and it holds no matter which goal runs first:

(run* [m] (lacks-keyo m :a) (geto m :a 1))                    ;;=> ()
(run* [q] (fresh [m] (lacks-keyo m :a) (== m {:a 1})) (== q 1)) ;;=> ()

Next: No unsupported behaviour, on the design behind all this.

Generated by Claude on Benjamin Schwerdtner's behalf.