Mein core.logic-Fork

Jede Relation ist eine Clojure-Funktion, als Relation gelesen, also kann jedes Argument das unbekannte sein.

Maps. get, assoc, merge, conj und keys, vorwärts und rückwärts:

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

(run* [m] (assoco m :b 2 {:a 1 :b 2}))
;;=> ({:a 1} {:a 1, :b _0})                 ;; m hatte kein :b, oder ein :b, das assoc überschrieb

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

(run* [q] (fresh [v] (conjo q [:foo v] {:foo 1})))
;;=> ({} {:foo _0})                         ;; der Testfall aus dem Wiki, unten

(run* [k] (== {:a 1 k 2} {:a 1 :b 2}))      ;;=> (:b)          unbekannte Keys unifizieren
(run* [ks] (keyso {:a 1 :b 2} ks))          ;;=> (#{:b :a})

(run* [m] (geto m :a 1) (geto m :b 2))
;;=> ((lmap {:b 2, :a 1} | _0))             ;; eine offene Map: diese Keys, vielleicht mehr

Vektoren. nth, conj, concat, subvec, mit exakt gelösten Längen:

(run* [i] (ntho [:a :b :a] i :a))           ;;=> (0 2)
(run* [v x] (conjo v x [1 2 3]))            ;;=> ([[1 2] 3])
(run* [s e] (subveco [:a :b :c :d] s e [:b :c]))
;;=> ([1 3])                                ;; woher der Ausschnitt stammt

(run* [a b] (concato a b [1 2 3]))
;;=> ([[] [1 2 3]] [[1] [2 3]] [[1 2] [3]] [[1 2 3] []])

(run* [v] (counto v 2) (ntho v 0 :a))       ;;=> ([:a _0])

(run* [x] (fresh [l r] (concato x [1] l) (concato [1] x r) (concato r [2] l)))
;;=> ()                                     ;; |x| + 1 ≠ |x| + 2, ohne Suche

Sets. Literale mit unbekannten Elementen, conj, union, difference:

(run* [x y] (== #{x y} #{1 2}))             ;;=> ([1 2] [2 1])
(run* [s] (conjo s 3 #{1 2 3}))             ;;=> (#{1 3 2} #{1 2})
(run* [a] (uniono a #{2 3} #{1 2 3}))       ;;=> (#{1 3} #{1} #{1 3 2} #{1 2})
(run* [x] (subseto #{1 x} #{1 2 3}))        ;;=> (3 2)         x ist verschieden von 1

(run* [x] (differenceo #{1 2 3} x #{1}))
;;=> (((lset #{3 2} | _0) :- (clojure.core.logic/lackso _0 1)))
;; 2 und 3, plus ein Rest ohne 1

(run* [s] (containso s 1) (containso s 2))
;;=> ((lset #{1 2} | _0))

Zusammen. Die Relationen lassen sich über die Arten hinweg kombinieren, und auch Pfade sind Relationen:

(def db {:users [{:name "ada" :tags #{:admin}} {:name "bob" :tags #{}}]})

(run* [n] (fresh [us u tags]
            (geto db :users us) (ntho us (lvar) u)
            (geto u :name n) (geto u :tags tags) (containso tags :admin)))
;;=> ("ada")

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

;; dieselbe Frage als Muster: mindestens diese Keys, mindestens dieses Element
(run* [n] (fresh [i u] (get-ino db [:users i] u) (matcho u {:name n :tags #{:admin}})))
;;=> ("ada")

Eine Logiksprache nimmt ihre Terme von ihrer Wirtssprache. Der Term von miniKanren ist das Scheme-Paar, weil Schemes Daten das Paar sind: appendo und membero funktionieren so gut, weil eine teilweise bekannte Liste eine natürliche Form hat, einen bekannten Anfang und einen ungebundenen Rest. core.logic hat miniKanren nach Clojure gebracht, und das Paar kam mit. Clojures eigene Daten waren Bürger zweiter Klasse: Zwei Maps unifizierten nur, wenn sie genau dieselben Keys hatten, und außer featurec, das Werte an bekannten Keys liest, konnte nichts eine Map zerlegen oder eine bauen.

Aber die Daten sind das, was Clojure ausmacht. Literale, unveränderliche Maps, Vektoren und Sets, für alles benutzt: "just use maps", Daten vor Funktionen vor Makros, ein Programm ist eine Pipeline aus get, assoc, merge, conj und union. Clojure-Leute kodieren einen Datensatz nicht als Assoziationsliste oder ein Set als Liste ohne Duplikate; sie schreiben {:name "ada"} und #{1 2}.

Ein relationales Clojure sollte also über diese Daten relational sein. Diese Serie macht das wahr: get, assoc, merge, nth, concat, union und Verwandte, jeweils als Relation, die rückwärts läuft. Eine Anfrage kann fragen, aus welcher Map ein assoc kam, welcher Key-Pfad zu einem Wert führt oder welche zwei Sets diese Vereinigung haben, auf denselben Daten, die der Rest des Programms benutzt. Das ist der Teil von core.logic, den nur Clojure haben kann, und den miniKanren auf Listen nur kodieren kann.

Der Wunsch ist nicht neu. 2013 hat David Nolen ihn auf die Roadmap von core.logic selbst gesetzt. Die Wiki-Seite Constraints & modes beginnt mit: "core.logic unfortunately to this day continues to emphasize operating on sequence-like data structures due to its Prolog & Scheme roots", und wünscht sich "constraint versions of Clojure functions". Sie skizziert ein assocc, stellt fest, dass es rückwärts verzweigt, und nimmt conjo als Testfall:

(run* [q]
  (fresh [v o]
    (== o {:foo 1})
    (conjo q [:foo v] o)))

"So we should see the following results: ({} {:foo _0})." Genau das antwortet der Fork. Die Begleitseite CLP(Set) wünscht sich Sets mit unbekannten Elementen, (unionc #{:cat x y} #{:dog :bird z} o), und merkt an, dass so eine Vereinigung darüber verzweigt, welche Elemente zusammenfallen. Auch die läuft im Fork: Mit o = #{:cat :dog :bird} sind x und y in beliebiger Reihenfolge :dog und :bird, und z ist :cat. (Beim Schreiben habe ich dabei einen Bug gefunden: Der Fork hat x früher auch :cat sein lassen. Behoben.) Beide Seiten stehen noch auf der Roadmap im Wiki, unter "Immediate", und wurden nie gebaut. Die Maschinerie, die sie skizzieren, ist nicht die, die diese Serie baut (ein defc mit Modus-Deklarationen, Set-Domänen wie die FD-Domänen), aber ihre Testfälle sind die, die sie beantwortet.

Sie legt auch die Messlatte. Eine Relation, die nur in manche Richtungen funktioniert, ist eine Funktion mit Extraschritten. Deshalb hält die Serie jede Relation an eine Regel: Sie antwortet in jedem Modus korrekt, oder sie wartet, bis sie es kann (Teil 2).

1. Relationale Maps: ein Rundgang durch die API.
2. Kein nicht unterstütztes Verhalten: warum das Design neu gemacht werden musste, und wie unbekannte Keys, lazy Checks und suspendierte Goals zusammenpassen.
3. Schnell machen: von 33 s auf 8 ms, und was langsam war.
4. Vektoren: offene Vektoren, Längen exakt gelöst, und get-in als Abfragesprache.
5. Literatur und Parität mit miniKanren: wo das in der Forschung steht, und was core.logic noch fehlt.
6. Auf dem Weg zu relationalem hyperdimensionalem Rechnen: dieselben Datenstrukturen, als Hypervektoren kodiert.
7. Sets: Maps ohne Werte, und was das bringt.
8. Seite an Seite mit miniKanren: die Testsuite von faster-miniKanren auf core.logic, die Bugs, die sie gefunden hat, und Maps, Sets und Vektoren neben ihren Kodierungen in miniKanren.
9. Ein relationaler Clojure-Interpreter: evalo für eine Teilmenge von Clojure, mit relationalen Maps als Umgebung; was er rückwärts kann, und wo seine Suche noch langsam ist.

Als Nächstes vielleicht: Records als Typen, und ClojureScript. Siehe Future Work.

Generiert von Claude im Auftrag von Benjamin Schwerdtner.