Very crude (monotonic) datalog interpreter

gistfile1.clj

(ns mist.logic.datalog
  (:use clojure.core.logic
        [clojure.set :only [union, difference]])
  (:require clojure.walk))

(defne allo [goal args]
  ([_ ()])
  ([_ [arg . rest]]
   (goal arg)
   (allo goal rest)))

(defn reify-rule [rule]
  (let [binding {:a (lvar :a) :b (lvar :b) :c (lvar :c)}]
    (clojure.walk/prewalk-replace binding rule)))

(defn is-rule [rule-var rules]
  (fn [substitutions]
    (to-stream
     (->> (for [rule rules]
            (unify substitutions rule-var (reify-rule rule)))
          (remove not)))))

(defn is-fact [rules facts]
  (with-local-vars [is-fact* nil]
    (var-set is-fact*
             (tabled [postulate]
                     (conde
                      [(membero postulate facts)]
                      [(fresh [rule rule-body]
                              (is-rule rule rules)
                              (conso postulate rule-body rule)
                              (allo is-fact* rule-body))])))
    (run* [fact] (is-fact* fact))))

(is-fact
 [[[:path :a :b] [:edge :a :b]]
  [[:path :a :b] [:edge :a :c] [:path :c :b]]]
 [[:edge :a :b] [:edge :b :c]])