Really simple datalog

gistfile1.clj

(ns datalog.core
  [:use matchure])

(defn compile-rule [head patterns]
  (let [inputs (gensym "inputs__")
        outputs (gensym "outputs__")]
    (letfn [(execute [patterns]
              (cond-match patterns
                []
                `(swap! ~outputs conj ~head)
                [?pattern & ?patterns]
                `(doseq [input# ~inputs]
                   (when-match [~pattern input#]
                               ~(execute patterns)))))]
      `(fn [~inputs ~outputs]
         (let [~outputs (atom ~outputs)]
           ~(execute patterns)
           (deref ~outputs))))))

(defmacro rule [head & patterns]
  (compile-rule head patterns))

(defmacro defrule [name head & patterns]
  `(def ~name (rule ~head ~@patterns)))

(defn expand [inputs rules]
  (let [outputs (reduce (fn [inputs rule] (rule inputs inputs)) inputs rules)]
    (if (= inputs outputs)
      inputs
      (recur outputs rules))))

(defn run [inputs rules query]
  (query (expand inputs rules) #{}))

; eg

(defrule rule-1 [a :path b]
  [?a :edge ?b])

(defrule rule-2 [a :path c]
  [?a :edge ?b]
  [b :path ?c])

(defrule rule-3 [a :connected b]
  [?a :path ?b])

(defrule rule-4 [a :connected b]
  [?b :path ?a])

(defrule rule-5 [a :connected a]
  [?a :edge _])

(defrule rule-6 [a :connected a]
  [_ :edge ?a])

(defrule query a
  [?a :connected 5])

(run
 #{[1 :edge 2] [2 :edge 3] [3 :edge 3] [4 :edge 5] [5 :edge 4]}
 [rule-1 rule-2 rule-3 rule-4 rule-5 rule-6]
 query)