Relationale Maps für core.logic

Die zentrale Idee ist dieselbe wie beim Rest einer Liste. Eine nur teilweise bekannte Map ist eine Menge bekannter Einträge plus ein ungebundener Rest:

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

Lies (lmap {:a 1} | _0) als "eine Map mit :a → 1, plus was auch immer _0 enthält". _0 ist ebenfalls eine Map, und sie darf :a nicht enthalten: Einträge und Rest überlappen nie. Verlangt man mehr, wächst die offene Map:

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

Geschlossen wird sie, indem man sagt, welches alle Keys sind:

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

Eine offene Map, an der nichts mehr offen ist, ist einfach eine Clojure-Map. Antworten kommen als gewöhnliche Maps zurück, wann immer das geht.

geto ist get. Vorwärts schlägt es nach; ist der Key unbekannt, zählt es auf; ist der Wert bekannt, sucht es:

(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 ist assoc. Rückwärts findet es jede Map, aus der assoc die Ausgabe erzeugt haben könnte:

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

Die zweite Antwort ist wichtig. m hatte entweder kein :b, oder es hatte :b mit irgendeinem Wert, den assoc überschrieben hat. Beides sind echte Antworten, und ein relationales assoc, das nur die erste lieferte, wäre falsch.

dissoco ist dissoc, genauso herum:

(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 ist merge. Rückwärts zerlegt es eine Map auf jede Weise, wie merge sie gebaut haben könnte, einschließlich der überschriebenen Werte:

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

Für verschachtelte Daten gibt es get-ino und assoc-ino, mit dem Pfad als weiterem Argument. Wer nach dem Pfad fragt, fragt, wo ein Wert steht:

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

Mehr davon, durch Maps und Vektoren, in Teil 4.

Eine Relation hat kein Gegenstück in clojure.core, weil die offene Map aus ihr besteht: (lmapo m entries rest), m ist entries plus eine Map rest, die keinen ihrer Keys hat. Das ist conj für Maps, ohne Überschreiben. (conj r [:a 1]) ersetzt ein :a, das r schon hatte, und hat rückwärts deshalb zwei Fälle. lmapo sagt, dass r kein :a hat, also gibt es einen, so wie (cons x xs) nie etwas verdrängt:

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

Sie baut auch: Ist alles unbekannt, antwortet (lmapo m {:a 1} r) sofort mit der offenen Map (lmap {:a 1} | _0), und diese gedruckte Form ist genau diese Relation: diese Einträge, plus ein Rest ohne ihre Keys.

Der Rest der 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 antwortet mit einem Set, wo Clojures keys eine Seq liefert. Die Reihenfolge der Seq ist die, in der die Map ihre Einträge gerade hält, und sie bedeutet nichts: {:a 1 :b 2} und {:b 2 :a 1} sind dieselbe Map. Eine Relation kann keine Reihenfolge auswählen, ohne an einer Anfrage nach einer anderen zu scheitern, also müsste eine Seq von Keys jede Reihenfolge aufzählen: n! Antworten für eine Tatsache, 3,6 Millionen bei zehn Keys. Die Keys einer Map sind ein Set, also sagt keyso das und hat eine Antwort. Sets sind relational (Teil 7), also kann das Key-Set teilweise bekannt sein, und unbekannte Keys paaren sich mit denen der Map. Die Kehrseite: (keyso m [:a :b]) scheitert, so wie (= #{:a :b} [:a :b]) falsch ist. valso bleibt eine Seq in beliebiger Reihenfolge, weil Werte sich wiederholen können.

Der Teil, über den ich mich am meisten freue: Man braucht keine dieser Relationen, um relationale Maps zu bekommen. Gewöhnliche Clojure-Maps unifizieren relational, auch wenn ihre Keys logische Variablen sind:

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

Die letzte Anfrage hat zwei Antworten, weil beide Zuordnungen echt sind. Upstream-core.logic schlägt Keys so nach, wie sie sind. Die Variablen k1 und k2 sind also selbst die Keys und werden nie gebunden; sie passen weder zu :a noch zu :b, und die Anfrage scheitert.

Eine Clojure-Map kann keine zwei gleichen Keys haben, und das gilt hier auch, selbst wenn die Keys erst später gleich werden:

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

Die letzte Anfrage ist der schwierige Fall: Die Map wurde gebaut, als ihre Keys noch verschiedene Variablen waren, und erst danach wurden beide an :a gebunden. Im nächsten Beitrag geht es darum, wie das erkannt wird, ohne alles andere langsam zu machen.

Manche Anfragen haben noch keine endliche Antwort. "Irgendeine Map enthält 1 unter irgendeinem Key" ist so eine. Statt zu raten, wartet das Goal und taucht in der Antwort als Constraint auf:

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

Das ist die Regel, auf der dieser Fork aufbaut: Eine Relation antwortet entweder korrekt, oder sie sagt, worauf sie noch wartet. Sie antwortet nie stillschweigend falsch.

Abwesenheit ist ein echter Constraint, und er gilt, egal welches Goal zuerst läuft:

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

Weiter: Kein nicht unterstütztes Verhalten, über das Design hinter all dem.

Generiert von Claude im Auftrag von Benjamin Schwerdtner.