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 Mark Engelberg.

See mimir.test.parse for examples (but an absolute lack of proper tests). Many things doesn't work properly yet, and the theoretical foundations are shaky to say the least. It doesn't support left-recursion - and a few things are broken. I'm currently backing off to read a few papers, so the references list will hopefully be updated in a few days, once I understand more about what I don't understand.

The idea is to eventually fold this together with Mímir's normal matcher so rules can descend into strings as well, inspired by OMeta.

(def right-recursive                   ;; Note: right associative.
  (create-parser                       ;; This returns a parser function.
   {:suppress-tags true}               ;; Options, can also be given when invoking, see below.

   :goal   :expr                       ;; A rule which is just an alias.
   :expr   #{[:term #"[+-]" :expr]     ;; Sets are (unordered) choices. Keywords refer to rules.
             :term} op                 ;; op is the action, invoked with the result of the parse.
   :term   #{[:factor #"[*/]" :term]
             :factor} op               ;; op resolves the regexp match to clojure.core/* etc.
   :factor #{#"[0-9]+" #"\w+"} #'*read-string*))

(let [x 1 y 3]
  (right-recursive "x - 2 * y" :read-string (dynamic-reader))) ;; dynamic-reader wraps read-string + local scope.
;=> -5

This example is (somewhat changed) from these lecture notes form Univeristy of Maryland.

References

Production Matching for Large Learning Systems Robert B. Doorenbos, 1995

Jess in Action: Java Rule-based Systems Ernest Friedman-Hill, 2003

OPS5 "This Common Lisp version of OPS5 is in the public domain. It is based in part on based on a Franz Lisp implementation done by Charles L. Forgy"

Clara "Clara is a forward-chaining rules engine written in Clojure" Ryan Brush, 2013

Rule-Based Expert Systems: The MYCIN Experiments of the Stanford Heuristic Programming Project Bruce G. Buchanan and Edward H. Shortliffe, 1984. Full out-of-print book free online.

Relational Programming in miniKanren: Techniques, Applications, and Implementations William Byrd, 2009

Transliterating Prolog into Scheme Matthias Felleisen, 1985. Great, short paper, the "Prolog" fits on one page. Most my projects could be said to have been inspired by this transliterate style (into Clojure) - if only I had read it earlier.

core.logic - A Tutorial Reconstruction David Nolen, 2012

HANSEI as a Declarative Logic Programming Language Oleg Kiselyov, 2010-12

Rule Solver: Constraint Programming with OpenRules Jacob Feldman, 2012

• JSR-331

Paradigms of AI Programming Peter Norvig, 1997

Artificial Intelligence: A Modern Approach Stuart Russell and Peter Norvig, 2011

• "Pseudo-code algorithms from the book in pdf"
• aima-java Ravi Mohan et al.

Approaches to Automatic Programming Charles Rich and Richard C. Waters, 1992

• "Myths and Prosopects" 1988, original IEEE Computer article

Experimenting with Programming Languages Alessandro Warth, 2009

PEG-based transformer provides front-, middleand back-end stages in a simple compiler Ian Piumarta, 2010

Instaparse Mark Engelberg, 2013 - "What if context-free grammars were as easy to use as regular expressions?"

Parsing Expression Grammars Brian Ford, 2004

Packrat Parsers Can Support Left Recursion Alessandro Warth et al, 2008

Left Recursion in Parsing Expression Grammars Sergio Medeiros et al, 2012

Scannerless Generalized-LR Parsing Eelco Visser, 1997

Generalized Parser Combinators Daniel Spiewak, 2010

Metafor: Visualising Stories as Code Hugo Liu and Henery Lieberman, 2005

Subtext Jonathan Edwards, 2005 ..

Natural Language, Semantic Analysis and Interactive Fiction Graham Nelson, 2005, revised 2006

A Conceptual Overview of Prism (Languages Beyond Ada and Lisp) David Fisher and David Mundie et al, 1991 - "Our means of achieving this integrated framework is a language emphasizing expressivity and serving as a medium for dialogue, rather than one-way communication, between user and machine."

Patterns of Software Richard Gabriel, 1996

Aramis or the Love of Technology Bruno Latour, 1996

Notes

The letter í in Mímir can conveniently be typed using C-x 8 ' i in Emacs.

License

Mímir, Copyright © 2012-2013 Håkan Råberg

Distributed under the Eclipse Public License, the same as Clojure.

Mimir image from Valhalla Comics Copyright © Peter Madsen

ᚠᚢᚦᚬᚱᚴ