Mímir

The god Odin carries around [Mímir's head](http://clojure.org/lazy#Making Clojure Lazier--Don't hang (onto) your head) and it recites secret knowledge and counsel to him.

Mímir is an experimental rule engine written in Clojure.

Marginalia

Mímir aims to implement a Rete network as a base. I don't vouch for its correctness, soundness or anything, actually. Like Mímir surely would attest, using it would be somewhat headless. Here's how it looks:

  ; The first example from chapter 2, "The Basic Rete Algorithm" in Doorenbos:
  (facts B1 on B2
         B1 on B3
         B1 color red
         B2 on table
         B2 left-of B3
         B2 color blue
         B3 left-of B4
         B3 on table
         B3 color red)

  (rule find-stack-of-two-blocks-to-the-left-of-a-red-block
        ?x on ?y
        ?y left-of ?z
        ?z color red
        =>
        ?x is on-top)

  (match? B1 is on-top)

This example uses basic triplets, where each value in a fact is a Clojure atom, and in a rule a condition an atom or a var, prefixed with ?. This mode is the raw mode the Rete network is operating in, but is somewhat limited in it's applicability. In theory, other representations are possible to compile into this format, but no work has been done on making it so, as I'm doubtful about the practical use case for the triplets.

The test macro match? uses mimir.well/run under the hood, which keeps running (potentially forever) until the working memory is stable. The values returned by run are the returned values of the right hand side bodies, which may not have been added to the working memory. When using triplets, a bare triplet returned on the right hand side is automatically asserted into the working memory, but this isn't the case when returning normal Clojure data structures.

  ; Dudeney's SEND + MORE = MONEY:
  (integers)

  (rule send-more-money
        (base 10    S E N D
                  + M O R E
                = M O N E Y)

        (all-different S E N D M O R Y)

        =>

        (str S E N D '+ M O R E '= M O N E Y))

   (match? "9567+1085=10652")

This example uses real Clojure code as its conditions. The left hand side, before the =>, contains of one or more conditions, which all must be satisfied for the rule to fire the right hand side, the code after =>. The right hand side is normal Clojure code, which will be invoked once for each matching set of variables found by the left hand side (in this case, only once). (integers) fills the working memory with 10 single digit facts.

base is a macro that expands into many more conditions, and introduces variables for the reminders of the addition to limit the amount of unknown variables that has to be found at any given moment. all-different is just distinct?, but could also be written as a macro expanded into to several sub conditions.

  ; N Queens
  (chessboard *n*)

  (rule n-queens

        (take-unique *n*)
        (different #{file rank})
        (not-same diagonal?)

        =>

        (map file *matches*))

  ; n = 5
  (match? [4 2 5 3 1] [3 5 2 4 1] [5 3 1 4 2] [4 1 3 5 2] [5 2 4 1 3]
          [1 4 2 5 3] [2 5 3 1 4] [1 3 5 2 4] [3 1 4 2 5] [2 4 1 3 5])

This example demonstrates a group of *n* queens that are selected by the take-unique macro. This expands into several conditions to ensure that the set of working memory elements picked are unique regardless of variable "position". This is done using compare behind the scenes in the expanded conditions.

different is a macro expanding into a distinct? call for each fn. not-same is a binary predicate which ensures diagonal? isn't true for any combinations of queens. This could be expanded into several conditions, but isn't at the moment; there's a balance between brute force search and the overhead of doing more joins - still to be explored.

Evaluation of mimir.well/run-once is lazy, so you can do: (take 1 (n-queens)) when calling a rule directly. In contrast, all results are realized by mimir.well/run each iteration to figure out if another run is needed.

And as Martin pointed out, this example is "at least two orders of magnitude" too slow!

  ; Rosencrantz' problem from chapter 1, "Rules to the Rescue" in Jess in Action:
  (doseq [name ["Fred" "Joe" "Bob" "Tom"]
          pants-color [:red :blue :plaid :orange]
          position (range 1 (inc 4))]
    (fact {:name name :position position :pants-color pants-color}))

  (rule find-solution
        {:name "Fred"
         :position fred}

        {:name "Joe"
         :position 2}

        {:name "Bob"
         :pants-color :plaid}

        {:name "Tom"
         :position (not-in #{1 4})
         :pants-color (is-not :orange)}

        (constrain {:position (inc ?fred)
                    :pants-color :blue})

        (different #{:position :pants-color})

        =>

        (set *matches*))

  (match? #{{:name "Fred", :position 1, :pants-color :orange}
            {:name "Joe", :position 2, :pants-color :blue}
            {:name "Bob", :position 4, :pants-color :plaid}
            {:name "Tom", :position 3, :pants-color :red}})

This example is demonstrating the pattern matcher (see below) operating on normal Clojure maps. not-in and is-not are predicates for the values. Keys not specified in the match are ignored. The maps introduces new (anonymous) variables, matching the working memory, while the constrain and different macros works on the current set of matches, not the working memory itself.

For more, see mimir.test.

Pong

This example is an attempt to write something less trivial where the working memory keeps changing. It doesn't fully work yet but has shown a few weaknesses in the assumptions made in Mímir which needs addressing. It uses clojure-lanterna for text UI.

lein trampoline run -m mimir.test.pong

Known Issues

The computer occasionally gets stuck or can only move in one direction
Some variations of conditions that seem valid just doesn't work as expected (potentially related to the above).
The match vars are bound to normal vars using a simple aliasing hack, hence the name mismatch (dx vs ?dx).
Using :swing doesn't work properly.
Resizing the window resets the game, and leaves some noise on the screen.

Pattern Matching

Mimir contains an even more experimental pattern matcher, which can be seen in action on maps in the Rosencrantz golfers example and in Pong above. This pattern matcher and it's relationship and influence on Mimir proper is still a bit up in the air. It can be used on it's own:

(defm member? [x & y]
  [x & _ ]  true
  [_ & xs]  (member? x xs))

(defm filter-m [pred & coll]
  [^x pred & xs] (cons x (filter-m pred xs))
  [_       & xs] (filter-m pred xs)
  empty?         ())

(defm map-m [f & coll]
  [x & xs] (cons (f x) (map-m f xs)))

(defm reduce-m [f val & coll]
  [x & xs] (reduce-m f (f x val) xs)
  empty?   val)

(defn factorial [x]
  (condm x
         0 1
         x (* x (factorial (dec x)))))

It currently performs the match on the var arg by an arbitrary convention, and can use meta data tags to introduce new bindings in a match. A symbol which isn't already bound will also introduce a binding, like in member? above, x matches the actual x argument to the fn, but xs creates a new var bound to the rest.

When used inside rules, the bindings currently has to be referenced with a ? prefix in other conditions, for examples, see Pong.

No performance tuning has been made - partly because there are no tests for this beast yet.

Goals: mímirKanren

Mímir contains some initial functionality to write goals in "mímirKanren", based on miniKanren, using Mimir's matcher to unify. This was inspired by seeing David Nolen's unsession on core.logic at StrangeLoop 2012. There's currently no clear way to use this together with Mimir proper, early days.

(run* [q w z]
  (consᵒ q w z)
  (firstᵒ z 1))
           ⇒ '(1 –₀ (1 . –₀))

(run 3 [q]
  (memberᵒ 3 q))
           ⇒ '((3 . –₀) (–₀ 3 . –₁) (–₀ –₁ 3 . –₂))

(run* [q]
  (appendᵒ [1 2] q [1 2 3 4]))
           ⇒ '((3 4))

Parsing

Mímir now also contains an experimental parser, inspired by the awesome Instaparse by Ma

Mimir

Install / Use

README