用 26 行代码编写有史以来最差的 Datalog

Today's Activity: To move away from heavy interop and frameworks, do light coding exercises and implement a very amateur datalog engine by taking shortcuts. There's also an offer to help with Clojure and work on getting the app Paktol (The positive spending tracker where money goes up!) off the ground.
Data Representations:
- Facts: Represented by a vector of simple values (no symbols, reserved for variables), e.g. [:father :bart :homer].
- Rules: Represented by a list of patterns. The first pattern is the head (conclusion), and the rest is the body. A pattern is a vector of simple values (including symbols for variables), e.g. ;; parent(c, p) :- father(c, p) ([:parent c p] [:father c p]) ;; parent(c, p) :- mother(c, p) ([:parent c p] [:mother c p]).
- Database: Conceptually split into EDB (extensional database) and IDB (intensional database), but lumped together as a single set of facts.
Matching Patterns Against Facts: The result is nil (no match) or a map of variables to their values (bindings or environment). The match function takes a pattern, a fact, and an environment and returns the updated environment or nil. It compares the lengths of the pattern and fact and then reduces over them to update the environment. Predicate names are treated like other slots of fact vectors.
Matching Rules and Producing New Facts: Use match-patterns to match a pattern chain against all known facts and get environments. Then use match-rule to turn these environments into new facts by replacing vars in the head with their values in the environments.
Running All Rules until Saturation: Repeatedly apply all rules until no new facts can be derived. Detected by comparing sizes instead of equality check.
Query: A query is an anonymous rule run after others to get only its results. The q function takes facts, a query, and rules and returns the set of results.
Example: With the Simpsons family facts and some sample rules, running queries shows the results. (q edb '([gp] [:grand-parent :bart gp]) rules) gives #{[:mona] [:abe]}, and (q edb '([anc] [:ancestor :bart anc]) rules) gives #{[:homer] [:marge] [:mona] [:abe]}.
Conclusion: Datalog is minimal and needs careful extension. This is a seed implementation with a starting point for further growth. Share if interested in more open-ended exploratory code.

Appendix: The 26 lines of code for the datalog functions:

(defn match [pattern fact env]
  (when (= (count pattern) (count fact))
    (reduce (fn [env [p v]]
              (let [p-or-v (env p p)]
                (cond
                  (= p '_) env
                  (= p-or-v v) env
                  (symbol? p-or-v) (assoc env p v)
                  :else (reduced nil))))
      env (map vector pattern fact))))
(defn match-patterns [patterns facts]
 (reduce
   (fn [envs pattern]
     (-> (for [fact facts env envs] (match pattern fact env))
       set (disj nil)))
   #{{}} patterns))
(defn match-rule [facts [head & patterns]]
 (for [env (match-patterns patterns facts)]
   (into [] (map #(env % %)) head)))
(defn saturate [facts rules]
 (let [facts' (into facts (mapcat #(match-rule facts %)) rules)]
   (if (< (count facts) (count facts'))
     (recur facts' rules)
     facts)))
(defn q [facts query rules]
 (-> facts (saturate rules) (match-rule query) set))