Read-Eval-Print-λove

Read-Eval-Print-λove
Read-Eval-Print-λove
Buy on Leanpub

A note

Read-Eval-Print-Love is an N-monthly zine of original content and curation about the Lisp family of programming languages and little-languages in general.

Dedication

Allen Newell - March 19, 1927 to July 19, 1992
Allen Newell - March 19, 1927 to July 19, 1992

Felicitous Use

One day the master macrologist Pi Mu and his macrolyte were having a meal of saba roasted on a shichirin when Pi Mu suddenly reached in with his chopsticks and extracted a red hot coal. He presented to the macrolyte stating “for you.” The macrolyte not knowing what to do but also not wishing to burn himself pulled his sleeves down over his hands and grabbed for the coal. Of course, the intense heat still hurt and the student ran to the kitchen and drenched the coal under running water. The macrolyte was dismayed to find his sleeve stained and burned from the coal and was quite angry as a result. In his anger he went back to the dining room and reached into the fire with his own chopsticks and extracted a coal of his own and presented the coal to Pi Mu. Pi Mu immediately pull from his jacket a cigar and lit it on the coal, saying “thank you, I needed that.”

The student was enlightened.

Introduction

This article is the first in a series focused on logic programming implementation jokingly called “Kritik der reinen Vernunft” (translated as critique of pure reason). Specifically, I plan to write a few articles describing simple implementations of rules engines, query systems, provers, and inference engines using purely functional techniques. A long time ago I had an idea for a book that discussed the history of programming languages via the analysis of very small language implementations (I called them “fruit flies”), each weighing in at 100 lines of code or less. I like the idea of implementing seemingly complicated systems with very little code for two reasons. First, 100 lines is a reasonable goal to aim for using reasonably powerful programming languages. Using such languages allows me to leverage powerful capabilities rather than implementing them myself. That is, languages with robust abstractions can provide a lot of bang for the buck in very few lines of code. My second reason for this idea was that 100 lines is about the number of lines that I can fit on my computer screen which coincidentally corresponds to the number of lines that I can fully reason about at any given moment. In any case, the idea was to build up to logic programming gradually, but in the next few installments of Read-Eval-Print-Love I’ll jump around.

My first logical fruit fly, and the subject of this installment of Read-Eval-Print-Love is a simple production rules system. Simply put, a production rule is a reified construct that represents an if/then process performed against some data. For example, in a JavaScript system we might find a piece of code that checks the length of a password for conformance:

1 // JavaScript
2 if(password.length < reqs.MIN_LENGTH) {
3   errors += "password_length";
4 }

This snippet of code represents a rule for password construction and a hook into a more robust error reporting system. In a programming language providing production rules as first-class entities, this statement of fact can be reified. Such a rule as shown above might be written as follows in the programming language CLIPS (or even Jess):

1 ;; CLIPS
2 (defrule check-password-length
3   ?p <- (password $?pass)
4   (min-password-length ?len)
5   (test (< (length $?pass) ?len))
6 =>
7   (assert (error ?p "Password too short")))

The rule check-password-length above, while naive in its implementation, illustrates the way that production rules languages like CLIPS represent domain rules. The part of the rule above before the => keyword is known as the left-hand side (LHS) of the rule and it describes the conditions that must exist within a fact base (a database of facts) for this rule to execute. In order, the LHS of the rule above can be read as follows:

  1. IF there’s a password fact in the fact base
  2. AND there’s a min-password-length fact in the fact base
  3. AND the length of the password is less than the min-password-length

You can imagine that some process external to the rule above added facts to the fact base such that it might look like the following:

1 f-1     (password f o o)
2 f-2     (min-password-length 8)

The facts shown above match the conditions set forth by the check-password-length rule and would thus cause an execution of that rule. The part of the rule after the => keyword therefore is known as the right-hand side (RHS) and that is actually the part that will be executed. In the case of check-password-length only a single action would occur - a call to assert. The assert operation in CLIPS is a way to add facts to the fact base which may or may not cause the execution of other rules. For simplicity’s sake this little example only has one rule, so all rule executions would stop after check-password-length executes, modifying the fact base to look as follows:

1 f-1     (password f o o)
2 f-2     (min-password-length 8)
3 f-3     (error <Fact-1> "Password too short")

As shown, the new fact f-3 was created by check-password-length during its execution.

I’d like to use the following pages to dig down into the idea that production rules are a fundamental model of computation along the lines of the lambda calculus, stack-centric models, LISP, state machines, SECD, Turing machines and the like, albeit less general. I would also like to show that with a few primitives a production rules system can be built and understood completely. However, the goal of this installment is not to talk about implementing production rules based systems and best practices around their use. There are many books and case studies around production rules systems that do a far better job than I could in presenting best practices and techniques than I could - see the references section for some of my favorite choices. Additionally, I will not approach the topic of using production rules to implement expert systems. While I find the topic fascinating, I see production rules as a tool for creating such systems but I do not see them married to expert systems. Many of the books in the references also tackle this topic as well, but bear in mind that production rules are just one way of building expert systems.

Kritik der Reinen Vernunft: Production Rules

Allow me to kick off my “Kritik der reinen Vernunft” series with the implementation of a simple rules engine, specifically a production rules system. The implementation herein is approximately 30-35 lines1 of code that will show what lies at the heart of a production rules system. To facilitate the code below I’m going to use a few Clojure libraries:

1 (ns prodrules
2   (:require [clojure.core.unify :as u]
3             [clojure.set :as s]
4             [datomic.api :as d]))

First, the clojure.core.unify library provides a powerful form of pattern matching called unification that I’ll explain later. Second, the clojure.set library provides logical set operations that will form the core functionality of the production rules system. Finally, the datomic.api library is the API allowing me access to the Datomic database2 and its querying capabilities. Datomic is tangential to the discussion in this installment and a comprehensive understanding of its operation is not required.

“Plain Data”

Much of what we do in programming revolves around the data used to describe our problems and their solutions. For example, below you’ll find some Clojure code that describes the data schema comprising a very simple alarm system3.

 1 (def schema
 2   '[{:db/id #db/id [:db.part/db -1]
 3      :db/ident :emergency/type
 4      :db/valueType :db.type/ref
 5      :db/cardinality :db.cardinality/one
 6      :db/doc "The type of emergency signalled."
 7      :db.install/_attribute :db.part/db}
 8 
 9     {:db/id #db/id [:db.part/user -2]
10      :db/ident :emergency.type/fire}
11 
12     {:db/id #db/id [:db.part/user -3]
13      :db/ident :emergency.type/flood}
14 
15     {:db/id #db/id [:db.part/db -4]
16      :db/ident :response/type
17      :db/valueType :db.type/ref
18      :db/cardinality :db.cardinality/one
19      :db/doc "The type of emergency response."
20      :db.install/_attribute :db.part/db}
21 
22     {:db/id #db/id [:db.part/user -5]
23      :db/ident :response.type/activate-sprinklers}
24 
25     {:db/id #db/id [:db.part/user -6]
26      :db/ident :response.type/kill-electricity}
27 
28     {:db/id #db/id [:db.part/db -7]
29      :db/ident :response/to
30      :db/valueType :db.type/ref
31      :db/cardinality :db.cardinality/one
32      :db/doc "The emergency that the response refers to."
33      :db.install/_attribute :db.part/db}])

The schema above is a Clojure data structure intended for use with the Datomic database. Each map (the parts defined between the curly brackets {}) in the vector (the array-like thing defined by the square brackets []) describes a “fact” residing in a Datomic database. For example, observe the following snippet of the code:

1 {:db/id #db/id [:db.part/db -1]
2  :db/ident :emergency/type
3  :db/valueType :db.type/ref
4  :db/cardinality :db.cardinality/one
5  :db/doc "The type of emergency signalled."
6  :db.install/_attribute :db.part/db}

The map above defines a fact called :emergency/type that is used to describe a possible type of emergency that might occur in an alarm system. The types of possible emergencies are defined as the enumerations shown below:

1 {:db/id #db/id [:db.part/user -2]
2  :db/ident :emergency.type/fire}
3 
4 {:db/id #db/id [:db.part/user -3]
5  :db/ident :emergency.type/flood}

Where either of :emergency.type/fire or :emergency.type/flood might occupy the value for a :emergency/type fact. Likewise, in the schema I describe a :response/type fact with possible enumerations :response.type/activate-sprinklers and :response.type/kill-electricity. Finally, I define a fact :response/to fact that’s used to refer a :response/type that’s intended to reference back to its triggering :emergency/type fact.

Although the data schema describe facts that are interdependent, there is nothing in the data itself that explicitly ties one fact to another. Indeed, any ties between facts would need to exist wholly in the system code relying on this data.

Allow me to illustrate below:

1 (def all-facts #{[-50 :emergency/type :emergency.type/fire]
2                  [-51 :emergency/type :emergency.type/flood]})

Above I’ve described a value all-facts that contains two facts pertaining to both fire and flood emergencies. I can use Datomic to directly query this small fact set:

1 (d/q '[:find ?id
2        :where
3        [?id :emergency/type _]]
4      all-facts)
5 
6 ;;=> #{[-50] [-51]}

As shown, the two fact identifiers4 found are precisely those defined in the original fact set data structure. Of course, because my fact set only contained the :emergency/type facts, there are no :response/type facts:

1 (d/q '[:find ?response
2        :where
3        [_ :response/type ?response]]
4      all-facts)
5 
6 ;;=> #{}

The reason is that although there’s a fundamental relationship between a :emergency/type fact and a :response/type fact, this relationship is out of band and must be explicitly encoded via code, a skeleton of which is shown below:

1 (defmulti respond-to-emergency :emergency/type)
2 
3 (defmethod respond-to-emergency :emergency.type/fire
4   [ent]
5   "Assert a :response/type of :response.type/activate-sprinklers")
6 
7 (defmethod respond-to-emergency :emergency.type/fire
8   [ent]
9   "Assert a :response/type of :response.type/kill-electricity")

The mechanics of the pseudo-code above are unimportant. Instead, what’s important is to note that to tie a :emergency/type to an associated :response/type is something that would need to be performed post-facto5 whenever a new :emergency/type is created within the context of the system.

And this is exactly where production rules systems can help.

Rules rule

Production rules provide a way and an underlying process for describing fundamental relationships between data.6 This is done by creating a knowledge base7 consisting of facts and rules that when presented with certain conditions in the underlying data, performs certain processes based on the firing of rules present at that time.

With hardcore production rules systems like the aforementioned Jess and CLIPS, the processes that can occur based on rule firings are arbitrary because both of these systems are fully realized programming languages.8 However, for the sake of this article I’ll stick to a simple process that merely creates new facts in the knowledge base when rules fire.

This simplification allows me to represent rules as data structures, in this case maps, each having two privileged keys :antecedent and :consequent.

Antecedent

The :antecedent key in the rule map contains a sequence of 3-tuples (id, attribute, and value) with logical variables at key locations for the purpose of pattern matching. Here’s a simple example of an antecedent:

1 [[?id :person/name "Fogus"]
2  [?id :language/speaks ?lang]]

The patterns above could form a rule’s antecedent (also known as its if-clause or left-hand side) that could effectively state the following: there is someone named "Fogus" who speaks a language. The constant value "Fogus" matches to a subset of the total data. In the presence of this constant the pattern also binds the logic variable ?id to that particular value. The total data is further refined by the fact that the two tuples in the antecedent refer to the same value bound to the ?id variable. Therefore, we should only ever match this antecedent to the languages that people named "Fogus" speak. We can see this in action by using Datomic to query a small data set:

 1 (d/q '[:find ?lang
 2        :where
 3        [?id :person/name "Fogus"]
 4        [?id :language/speaks ?lang]]
 5    
 6      #{[:mf :person/name "Fogus"]
 7        [:b  :person/name "Billy"]
 8        [:mf :language/speaks "English"]
 9        [:b  :language/speaks "English"]
10        [:mf :language/speaks "Japanese"]})
11 
12 ;;=> #{["Japanese"] ["English"]}

The result from the Datomic query above shows that there were two results, each bound to the value of ?lang using the :find query clause, one for each language assigned to the ?id of :mf.

The antecedent of a rule works in a similar way that it does for a Datomic query: it defines the conditions in a data set by which the antecedent is matched. However, in a rule the antecedent is bound to an action, called a consequent.

Consequent

The consequent of a rule (also called the right-hand side, or RHS) are the actions that occur when a rule fires as the result of a match of its antecedents. In a general purpose rule-based programming language like CLIPS, a rule’s consequent can consist of multiple actions:

1 ;; CLIPS code
2 
3 (defrule found-person
4   "A rule that finds a person and greets them."
5   (person (name ?n))
6   (not (greeted ?n))
7   =>
8   (printout t "Hello " ?n "!" crlf )
9   (assert (greeted ?n)))

The rule found-person matches on the presence of a person fact containing a value for the name field and the non-existence of a greeted fact for that same value. The consequent of found-person firing is simply that a message is printed to stdout and a greeted fact is asserted. Because CLIPS is a general-purpose programming language, its rule consequent can contain and execute arbitrary code. However, for the purposes of this installment I prefer to keep my implementation simple by allowing only assertions in rule consequent.

Rules as data

While it might be interesting to encode a special syntax for rules in my production system, just to keep things simple I’ll just use the forms readily available in Clojure (my chosen implementation language) to encode rules:

  1. A rule set is simply a vector of rule definitions
  2. A rule definition is just a map containing :antecedent and :consequent keys
  3. An antecedent is simply a vector of 3-tuples representing an entity attribute
  4. An entity attribute is a vector of three elements: id, attribute, value
  5. A consequent is a vector of 3-tuples representing new attribute assertions

Observe a simple rule definition for the emergency response system:

1 [{:antecedent   [[?id   :emergency/type :emergency.type/fire]]
2   :consequent   [[-1000 :response/type  :response.type/activate-sprinklers]
3                  [-1000 :response/to    ?id]]}]

The vector above encodes a rule set with a single rule that matches on the :emergency.type/fire enumeration and asserts two facts relating for the :response/type and :response/to attributes.

There are other potentially useful keys that could be added to a rule’s definition (a name is an obvious first choice), but I’ll keep things simple for the sake of clarity. The rule set definition above holds only a single rule, but adding another might make for a more interesting example:

1 (def rules
2   '[{:antecedent   [[?id   :emergency/type :emergency.type/fire]]
3      :consequent 	[[-1000 :response/type  :response.type/activate-sprinklers]
4                      [-1000 :response/to    ?id]]}
5     {:antecedent   [[?id   :emergency/type :emergency.type/flood]]
6      :consequent 	[[-1002 :response/type  :response.type/kill-electricity]
7                      [-1002 :response/to    ?id]]}])

The rules binding holds two rules: one to handle :emergency.type/fire facts and another to handle those for :emergency.type/flood. Keep in mind that the logic variables (i.e. ?id) in the first rule refer to a different binding than same named variable in the second rule. Each rule defines its own lexical scope.

A simple implementation of a purely functional production rules system

In a production rules system, the amalgamation of the system’s rules and its facts comprises the knowledge base. In the case of a general purpose production rules language like CLIPS or Jess, the knowledge base is akin to a global environment in which the language run-time operates. This is fine in the case where the language itself is a programming shell, but I prefer to represent the knowledge base as a data structure and its run-time contexts calculable from the application of pure functions.

1 (def KB {:rules rules
2          :facts all-facts})

This pure computational model will aid in reasoning about how the production rules system operates at each stage.9 In this article I’ll implement a four stage system:

  1. Antecedent unifications
  2. Rule selection
  3. Consequent substitutions and assertion
  4. System quiessence

The first, and most fundamental, stage in the system implemented below is known as unification, which at a high-level is a way to perform bi-directional pattern matching between the rules and facts comprising the knowledge base.

Unification

Unification is a form of pattern matching that not only fills in “holes” on the matching side to a piece of data, but it also fills holes in the data also. Let me show some examples.

The simplest unification is one that occurs between a piece of data and a logic variable:

1 (u/unify '?x 'hello {})
2 ;;=> {'?x 'hello}

There are a few things to dissect in the example above. First, the u/unify function takes three arguments: a matching segment potentially consisting of or containing one or more logic variables, a piece of data to match against also potentially comprised of logic variables, and an environment providing a context for any potential matches to occur. The u/unify function returns a potentially augmented environment describing the context under which the matching and data segments are equal. So, in the example above, in order for the logic variable ?x and the symbol hello to be equal, the environment must contain a mapping from ?x to hello. We can see the contradiction of this equality by providing an environment in which that equality cannot happen:

1 (u/unify '?x 'hello {'?x 'world})
2 ;;=> nil

In other words, ?x and hello cannot be equal in the environment provided because it describes a universe[^uni] where ?x is instead equal to world. I mentioned earlier that the u/unify function will attempt to augment an environment to ensure that it describes a condition for equality between its arguments. Obviously then to provide an environment where the equality is already met should not change anything:

However, if I provide an environment that describes a universe that’s irrelevant to the equality under question then the returned environment should contain any augmentations that make it relevant (when possible or course):

1 (u/unify '?x 'hello {'?y 'world})
2 ;;=> {'?x 'hello '?y 'world}

What would you expect to happen if you attempt to unify two values that are already equal despite the given environment? Observe:

1 (u/unify 'hello 'hello {})
2 ;;=> {}

The answer is that u/unify provides an empty context as its return type, but a context it will return. On the other hand, if you try to unify two disparate values then you should expect that u/unify to not return a context of any kind.

1 (u/unify 'hello 'world {})
2 ;;=> nil

Unification along a single dimension is interesting, but it truly shines when you attempt to unify composite structures such as lists:

1 (u/unify '(father ?x b) '(father a b) {})
2 ;;=> {'?x 'a}
3 
4 (u/unify '(father ?x ?y) '(father a b) {'?y 'b})
5 ;;=> {'?x 'a, '?y 'b}

That is, the two lists (father ?x b) 10 and (father a b) can only ever be equal under an environment where ?x is bound to a. Observe:

1 (u/unify '(father ?x b) '(father a b) {'?x 'c})
2 ;;=> nil
3 
4 (u/unify '(father ?x ?y) '(father a b) {'?y 'c})
5 ;;=> nil

There are more interesting examples for unification, but I think for the sake of this article the basics should be sufficient for understanding. Unification in Clojure is covered in more detail in “The Joy of Clojure” – sold in fine bookstores near you. Unification becomes more interesting when its used as the building block for substitution, which is a technique leveraged heavily in my production rules system below.

Antecedent unifications

The use of unification is essential in determining if a given antecedent clause can match a given fact. Recall the an antecedent’s clauses are of the follow form:

1 [?id   :emergency/type :emergency.type/fire]

Now pretend that there exists a fact that might unify with such an antecedent clause:

1 (u/unify '[?id   :emergency/type :emergency.type/fire]
2          '[42    :emergency/type :emergency.type/fire]
3          {})
4 
5 ;;=> {?id 42}

In the implementation of production-ready rule-based systems such as CLIPS, Jess, or Drools, the implementation of the pattern matching across a large knowledge base is done via very fast and efficient pattern matching algorithms such as Rete, Rete II, and analogous methods. However, to keep this article short I’ll implement a naive matching algorithm over the total rule and fact sets, shown below:

1 (defn unifications [[clause & more :as clauses] facts context]
2   (if clause
3     (let [bindings (keep #(u/unify clause % context) facts)]
4       (mapcat #(unifications more facts %) bindings))
5     [context]))

The implementation of unifications is simplicity itself. Simply put, the function walks through all of the clauses in an antecedent (implied) and matches each against every fact provided. Running the unifications function with a known rule antecedent against all of the facts in the knowledge base should yield a sequence of unification contexts:

1 (unifications '[[?id :emergency/type :emergency.type/fire]]
2               (:facts KB)
3               {})
4 
5  ;;=> ({?id -50})

If the fact base had more matching facts within then you’d expect that unifications would return more contexts and indeed that is the case:

1 (unifications '[[?id :emergency/type :emergency.type/fire]]
2               (conj all-facts [-1000000 :emergency/type :emergency.type/fire])
3               {})
4 
5 ;;=> ({?id -50} {?id -1000000})

The interesting aspect of the implementation of unifications is that the bindings derived via unification are fed back into the recursive call so that any subsequent unifications occur within the contexts built via matching on previous clauses. This allows the reference of one logic variable later in an antecedent to refer back to a binding that was established in an earlier clause, as shown below:

1 (unifications '[[?id :emergency/type :emergency.type/fire]
2                 [?rid :response/to ?id]]
3               (conj all-facts [-5000000 :response/to -50])
4    	          {})
5 
6 ;;=> ({?id -50, ?rid -5000000})

Certainly recursively walking over the total fact set for every rule is a less than optimal way to operate.11 Indeed, modern production rules systems go to great pains to avoid unnecessary pattern matching. However, while the problem of efficiency in these systems is an interesting topic, it’s not the goal of this article. Instead, I’m more interested in outlining the ideas that lay at the core of production rules systems and show that the ideas around them are fundamentally simple and indeed a fundamental a model of computation. That said, now that I can find all of the contexts for matching against all of the rules and facts in the knowledge base I need to be able to trigger the firing of rules for contexts that cause complete substitutions in rule antecedents, which I’ll implement next.

Rule selection

Now that I have a way to derive the bindings of rule antecedents against the facts in the database I’d like a way to determine all of the rules that will match on the current rule set and execute one. The function select-rule implements the second stage of the system:

1 (defn select-rule [selection-strategy rules facts]
2   (let [possibilities 
3          (for [rule    rules
4                bindings (unifications (:antecedent rule) facts {})]
5           [rule bindings])]
6     (selection-strategy possibilities)))

The implementation of select-rule is such that it builds a sequence of bindings paired with each rule and then uses a selection function to execute one of the rules that matched:

 1 (select-rule identity
 2              (:rules KB)
 3              (:facts KB))
 4 
 5 ;;=> ([{:antecedent [[?id :emergency/type :emergency.type/fire]], 
 6 ;      :consequent [[-1000 :response/type :response.type/activate-sprinklers] 
 7 ;                   [-1000 :response/to ?id]]} 
 8 ;     {?id -50}] 
 9 ;
10 ;    [{:antecedent [[?id :emergency/type :emergency.type/flood]], 
11 ;      :consequent [[-1002 :response/type :response.type/kill-electricity] 
12 ;                   [-1002 :response/to ?id]]} 
13 ;     {?id -51}])

Using the identity as the selection function simply returns the entire set of possibilities. While this is useful to see the entire set, a more useful function in practice is one that returns a single rule:

1 (select-rule rand-nth
2              (:rules KB)
3              (:facts KB))
4 
5 ;;=> ([{:antecedent [[?id :emergency/type :emergency.type/flood]], 
6 ;       :consequent [[-1002 :response/type :response.type/kill-electricity] 
7 ;                    [-1002 :response/to ?id]]} 
8 ;     {?id -51}])

The use of rand-nth as the rule selection function turns out to be an expedient choice. While industrial production rules systems use far more elaborate selection schemes,12 it turns out that choosing a random rule can prove useful. However, I’ll hold off on explaining why for now and instead talk about what happens after a rule has been chosen.

Consequent substitutions and assertion

Using unification one can determine if two structures are effectively equal within a certain context. With that knowledge we can use the core.unify library to replace logical variables contained in data structures with values as specified in a given environment. Observe:

1 (u/subst '(hello ?a) '{?a world})
2 ;;=> '(hello world)

In the list (hello ?a) the logical variable ?a is substituted with the symbol world as found in the environment provided. As you might have guessed, if the given environment provides insufficient context for a substitution then nothing will happen:

1 (u/subst '(hello ?a) {})
2 ;;=> '(hello ?a)

The u/subst function will also substitute logic variables at arbitrarily deep positions in nested data structures[^nest]:

1 (u/subst '{:foo ?bar, :baz [{:qux ?lip}]}
2          '{?bar 42, ?lip "ZZZ"})
3 
4 ;;=> {:foo 42, :baz [{:qux "ZZZ"}]}

The relationship between unification (via u/unify) and substitution (via u/subst) fundamentally defines the relationship between a rule’s antecedent and its consequent.

More clearly, u/unify is used to build an environment and u/subst uses it to build new facts. This established binding is used to substitute the values bound via unification into the consequent’s assertions. A small function apply-rule implements stage 3 of the system:

1 (defn apply-rule [rule facts context]
2   (let [new-facts (set (for [rhs (:consequent rule)]
3                          (u/subst rhs context)))]
4     (s/union new-facts facts)))

The s/union function is a way to insert the new, substituted facts into the facts provided as an argument to apply-rule:

1 (let [[rule binds] (select-rule (:rules KB) (:facts KB) first)]
2   (apply-rule rule (:facts KB) binds))
3 
4 ;;=> #{[-51 :emergency/type :emergency.type/flood]
5  ;     [-50 :emergency/type :emergency.type/fire]
6  ;     [-1000 :response/type :response.type/activate-sprinklers]
7  ;     [-1000 :response/to -50]}

As shown, the set returned from apply-rule is augmented with the facts contained in the consequent of a single rule.

Now that I have a way to derive rule bindings, choose a rule, and apply it, I just need a simple driver that takes a set of rules and facts and returns a new fact base based on the application of single rule (the :emergency.type/fire rule):

1 (defn step [rules facts]
2   (when-let [[rule binds] (select-rule rand-nth rules facts)]
3     (apply-rule rule facts binds)))

This driver can now be used to implement the closing stages of the production rules system.

An infinite sequence of system states

The step function as written can be used to augment the fact base through the application of rules through a process of propagating changes forward from one rule application to another:

1 (defn states [kb] (iterate #(step (:rules kb) %)
2                            (set (:facts kb))))

The states function, through the use of Clojure’s iterate function, will apply the result of one rule firing to the fact base and feed the result forward into the next firing.13 You can see this in action below:

 1 (take 3 (states KB))
 2 
 3 ;;=> (#{[-51 :emergency/type :emergency.type/flood] 
 4         [-50 :emergency/type :emergency.type/fire]} 
 5       #{[-51 :emergency/type :emergency.type/flood] 
 6         [-50 :emergency/type :emergency.type/fire] 
 7         [-1000 :response/to -50] 
 8         [-1000 :response/type :response.type/activate-sprinklers]} 
 9       #{[-51 :emergency/type :emergency.type/flood] 
10         [-50 :emergency/type :emergency.type/fire] 
11         [-1000 :response/to -50] 
12         [-1000 :response/type :response.type/activate-sprinklers]
13         [-1002 :response/type :response.type/kill-electricity] 
14         [-1002 :response/to -51]})

As it turns out, the random application across the entire rule set for this tiny knowledge base happened to fire all of the available rules. However, running the same take operation again might not look the same. That is, the problem with random application of rules is that there’s no way to know how many iterations are required to ensure that all of the rules eventually fire. Therefore, the final component to this tiny production rules system is a function to check for system quiescence (i.e. no more new rules are firing). The driver function below will therefore use this function to determine when to stop:

1 (defn cycle [qf kb]
2   (qf (states kb)))

The cycle function performs one single task - it feeds the results of states into a function qf that is responsible for detecting when rule firings have stopped. But for such a system such as I’ve implemented above, what kind of quiescence function would suffice?

System quiescence

While my implementation exhibits the behavior of a production rules system, it does so in a way that’s computationally wasteful. Specifically, the repeated application of random rules is guaranteed to perform unnecessary rule firings and thus unneeded work. The reality of experimenting on fruit flies is that while such an act is instructive, scaling up to more robust organisms combinatorially increases the complexities inherent in the system. I do think that there’s one more lesson to learn from my little fruit fly:

1 (defn naive-qf [states]
2   (last (take 256 states)))

In production production rules (ha!) systems, the quiescence in the system is tracked via the observation of various rule conflict resolution strategies and rule firing agendas. However, the system implemented herein calls for a naive approach to detecting quiescence – that is, to not.14 As shown above, the quiescence function naive-qf simply takes the last environment in a long sequence of states in the hope that the sequence was long enough that all of the rules fired in creating it. It should be noted that like real production rules systems, there is a relationship between the rules, the selection strategies in play, and the facts in the system and system quiescence is a function of all of those things, and this is where a combinatorial explosion in complexity arises in actual implementation.15

And back to queries again

As I stated at the very beginning of this article, production rules are useful for defining relationships between data that typically exist only encoded in domain code. Indeed, the rules defined herein related emergency types to responses in the form of data and thus allowing me to selectively apply a set of rules to a set of data and observe the results:

1 (def facts' (cycle naive-qf KB))

The facts' set is an augmented fact set based on the application of the rules contained in the knowledge base. I can now query the augmented data to examine what occurred:

1 (d/q '[:find ?response
2        :where
3        [_ :response/type ?response]]
4      facts')
5 
6 ;;=> #{[:response.type/kill-electricity] [:response.type/activate-sprinklers]}

As shown, the augmented facts now contain two separate response types, one pertaining to killing the electricity and another for turning on the sprinklers16. We can use the linkages asserted via the rules to associate the emergencies with their responses with a richer query:

1 (d/q '[:find ?problem ?response
2        :where
3        [?id :response/type ?response]
4        [?id :response/to   ?pid]
5        [?pid :emergency/type ?problem]]
6      facts')
7 
8 ;;=> #{[:emergency.type/fire   :response.type/activate-sprinklers] 
9 ;      [:emergency.type/flood  :response.type/kill-electricity]}

And that’s that.

Production rules are fundamental

In their seminal work The 1.5 Programmer’s Manual, John McCarthy, Paul Abrahams, Daniel Edwards, Timothy Hart and Michael Levin showed that a fundamental model of computation could be implemented in half a page of code. Later, Alan Kay did the same for Smalltalk and message-oriented (colloquially OOP) programming by outlining a reflective object system in a page of code. While production rules may not provide the same coverage in terms of computational completeness as LISP 1.5 and Smalltalk-71, I believe the core model to be a fundamental one. As it goes with such thing in computer science, fundamental models should be described and implemented succinctly and, in my opinion, beautifully.

I hope that I was able to demonstrate at least one of the two.

Production Rules and OOP

Over the years I’ve come to implement my share of production rules systems of varying size, shapes, and capability. For a few years I’ve plunked along on a system named Apocryphal that integrates object-oriented ideas with production rules and marries the two in, what I think are interesting ways. I’ll talk just briefly about Apocryphal and show some examples.

The current syntax is inspired by early versions of Smalltalk (i.e. I was too lazy to make a richer syntax) and is definitely a work-in-progress.

Objects

Almost everything in Apocryphal is an object of some sort, but objects in Apocryphal are pretty lightweight, containing only information pertaining to its type and value. A few recognizable types in Apocryphal are:

  • <atom>: symbolic, atomic, self-referential, lexemes (similar to Clojure keywords) (ex. :msg)
  • <string>: aggregate lexemes (ex. "Hi there!")
  • <tuple>: non-nested containers of size N (ex. [1 2 :qux "nom"])
  • <number>: including <int> and <float> (ex. 1 and 1.2)

There are other types like Rules, Classes, Metaobjects, and the like that are not important for this discussion.

Classes

Apocryphal has a notion of classes that is used purely for specializing dispatch logic. That is, in the case of numbers, <float> :isa <number> and <int> :isa <number> and the dispatch logic will use this information to dispatch to custom handlers for each.

1 def :class <person> :isa <object>
2   [first :isa <string>]
3   [last  :isa <string>]
4   [age   :isa <int>].

To create a new instance of a <person> class:

1 send <person> :new {:first "Mike", :last "Fogus"}.

The curly braces {} denote a way to specify the constructor arguments to the <person> :new message.

Protocols

Apocryphal has a notion of protocols which are basically like Java interfaces and are used to define a cluster of related functionality:

1 def :protocol <greet>
2   :+ [formal   $ ...More]
3   :+ [informal $ ...More].

Behind the scenes, a protocol definition sets up a dispatch table for a <greet> protocol for two messages :formal and :informal. The $ symbol is just a name given to the receiving object. Think of it as something like self or this.

Messages

A message in Apocryphal is a named operation tied to a handler in a dispatch table:

1 send 1 :+ 2.
2 \\=> 3
3 
4 send "a" :cat "b"
5 \\=> "ab"

In the example above, the object 1 receives a message :+ with the argument 2.

Handlers

Handlers are functions bound to messages and objects in a dispatch table:

 1 def :handler <greet> :specialize <number>
 2   :to :formal :do 
 3   [$ ...More | 
 4     Full <- send $/first :cat " " ; :cat $/last
 5     send STDIO :print "Hello " ; :print Full ; :print "\n"!
 6     ^ Full]
 7 
 8   :to :informal :do
 9   [$ ...More | 
10     send STDIO :print "Hello " ; :print $/first ; :print "\n"!
11     ^ $/first].

The $/first syntax is just a shorthand way of saying (send $ :get :first). The use of the ; operator strings a bunch of sends together on a target object – the return of the previous method call in the chain.

Immutability

Because I wanted to play around with integrating object-orientation with production rules17 I tried to reduce the complexity of tracking changes to objects in the system. Therefore, I made objects somewhat limited in the way that they’re changed. Indeed, by default you cannot change an object’s data at all:

1 P <- send <person> :new {:first "Mike", :last "Fogus"}.
2 send P :set [:age 99]!
3 \\ error: :set message not supported

The only way to perform this action is to create a new object:

1 P <- send <person> :new {:first "Mike", :last "Fogus"}.
2 Q <- send <person> :new {:first P/first, :last P/last, :age 99}.

This simplification allows me to simplify the integration between the object system and the production rules machinery.

Knowledge bases

Knowledge bases (called Worlds) in Apocryphal are the only mutable types (currently) available. You can think of them as databases for objects and rules that allow instance queries and production rule executions. A World can be viewed as another name for a knowledge base with additional feature above and beyond just a repository for facts and rules. To get objects into the knowledge base they have to be committed:

1 KB <- send <kb> :new 
2   ; :commit (send <person> :new {:first "Mike", :last "Fogus"})
3   ; :commit (send <person> :new {:first "Bjork"})!

Knowledge bases can be queried:

1 [M B] <- send KB :q [{:kind <person> :first ?f}].
2 \\ [@1 @2]
3 
4 [M/first B/first]
5 \\=> ["Mike" "Bjork"]

The @1 symbol is basically a reference to the fact for the <person> Mike within the context of the knowledge base:

1 send KB :fetch M.
2 \\=> [<person> {:first "Mike", :last "Fogus", :age not-set}]

Based on what I’ve shown it might make sense to talk about rules within the Apocryphal language.

Rules

Objects in the Apocryphal live either inside or outside of a World. That said, I want to focus on rules and their role in managing the complexity of a typical object-oriented approach to software development. As I mentioned, objects are committed to a World. Once committed I can write rules to match on their attributes:

1 send KB :rule :find-names :lhs
2   [$p {:kind <person> :first ?f}]
3 :=>
4   send STDIO :print "Hello " ; :print $/first ; :print "\n"!

There are a few things happening here. First rules are declared with a name to ease debugging and rule tracing. Second, the tuple comprising the antecedent (tagged as :lhs here) contains a binding $p that effectively serves as a pointer to the actual fact for the object. Finally, the consequent is marked with the :=> tag. The only thing that this rule does is print an informal greeting:

1 send KB :run!
2 \\ Hello Mike
3 \\ Hello Bjork

However, I could have also mixed in the <greet> protocol to the World and used it instead:

1 send KB :mix <greet>!
2 
3 send KB :rule :find-names :lhs
4   [$p {:kind <person> :first ?f}]
5 :=>
6   send $p :informal!    

This is pretty straight-forward (especially if you’ve used something like Drools or COOL), but a more interesting feature is something called contextual methods.

Contextual methods

Every class definition automatically provides two implicit message handlers: :get and :set. However, as I showed the :set method cannot bet accessed and the reason is that it can only be enabled via the execution of a rule. Apocryphal allows protocol declarations to contain conditional methods, as is done with the base <accessible> protocol:

1 def :protocol <accessible>
2   :+ [get $ Tag]
3   :- [set $ Tag Val].

The :- flag declares that all :set message handlers are conditional, or accessible only within a rule:

1 send KB :rule :change-last-name :lhs
2   [$p {:kind <person> :last ?last :provides [:set]}]
3   [$a {:kind <amendment> :field :last :old ?last :val ?new-lname}]
4 :=>
5   ?amended <- send $p :set :last ?new-lname
6   retract $a
7   commit ?amended!

The :provides tag is the way to access conditional methods extended to a class and makes them usable within the context of a rule. This allows one to not only constrain object mutation to within rules, but also to establish richer relationships between method access and data.

Final thoughts

A theme of this installment of Read-Eval-Print-Love can be summarized as rules to encode relationships. Within a typical object-oriented system, the relationship between methods is encoded in an ad hoc fashion, perhaps as a delicate balancing act between method access and namespacing. However, perhaps there are other ways to encode method relationships not only between each other, but also as they relation to certain data conditions existing within the system at run time. Apocryphal is a fun little thought experiment and may one day prove a useful fruit-fly.

My 100 Favorite Jazz Albums

In no particular order.

  1 (def jazz-db #{
  2   {:album "Giant Steps" :artist "John Coltrane"}
  3   {:album "Live at Birdland" :artist "John Coltrane"}
  4   {:album "A Love Supreme" :artist "John Coltrane"}
  5   {:album "Blue Train" :artist "John Coltrane"}
  6   {:album "Sunday At The Village Vanguard" :artist "Bill Evans Trio"}
  7   {:album "Waltz For Debby" :artist "Bill Evans Trio"}
  8   {:album "The Essential Charlie Parker" :artist "Charlie Parker"}
  9   {:album "Bird of Paradise" :artist "Charlie Parker"}
 10   {:album "Journey in Satchidananda" :artist "Alice Coltrane"}
 11   {:album "Universal Consciousness" :artist "Alice Coltrane"}
 12   {:album "Black Fire" :artist "Andrew Hill"}
 13   {:album "Atlantis" :artist "Sun Ra"}
 14   {:album "Lanquidity" :artist "Sun Ra"}
 15   {:album "The Black Saint & The Sinner Lady" :artist "Charles Mingus"}
 16   {:album "Let My Children Hear Music" :artist "Charles Mingus"}
 17   {:album "Les Liaisons Dangereuses" :artist "Art Blakey"}
 18   {:album "Chamber Music Of The New Jazz" :artist "Ahmad Jamal"}
 19   {:album "The Awakening" :artist "Ahmad Jamal"}
 20   {:album "Solo Monk" :artist "Thelonious Monk"}
 21   {:album "Brilliant Corners" :artist "Thelonious Monk"}
 22   {:album "Monk's Dream" :artist "Thelonious Monk"}
 23   {:album "Sketches Of Spain" :artist "Miles Davis"}
 24   {:album "Kind of Blue" :artist "Miles Davis"}
 25   {:album "Stick Up!" :artist "Bobby Hutcherson"}
 26   {:album "Happenings" :artist "Bobby Hutcherson"}
 27   {:album "Nuits de la Fondation Maeght 1970" :artist "Albert Ayler"}
 28   {:album "Music Is The Healing Force Of The Universe" :artist "Albert Ayler"}
 29   {:album "Spirits Rejoice" :artist "Albert Ayler"}
 30   {:album "Money Jungle" :artist "Duke Ellington"}
 31   {:album "The Shape of Jazz to Come" :artist "Ornette Coleman"}
 32   {:album "Change of the Century" :artist "Ornette Coleman"}
 33   {:album "Somethin' Else" :artist "Cannonball Adderley"}
 34   {:album "Maiden Voyage" :artist "Herbie Hancock"}
 35   {:album "Cantaloupe Island" :artist "Herbie Hancock"}
 36   {:album "Open Sesame" :artist "Freddie Hubbard"}
 37   {:album "Concert by the Sea" :artist "Erroll Garner"}
 38   {:album "Live at Carnegie Hall" :artist "Benny Goodman"}
 39   {:album "Time Out" :artist "Dave Brubeck"}
 40   {:album "Duke Ellington Songbook" :artist "Ella Fitzgerald"}
 41   {:album "Roll Call" :artist "Hank Mobley"}
 42   {:album "The All Seeing Eye" :artist "Wayne Shorter"}
 43   {:album "Out to Lunch" :artist "Eric Dolphy"}
 44   {:album "Sweet Honey Bee" :artist "Duke Pearson"}
 45   {:album "Sonic Boom" :artist "Lee Morgan"}
 46   {:album "The Inflated Tear" :artist "Rahsaan Roland Kirk"}
 47   {:album "People in Sorrow" :artist "Art Ensemble Of Chicago"}
 48   {:album "Les Stances a Sophie" :artist "Art Ensemble Of Chicago"}
 49   {:album "The Complete Armstrong/Ellington Sessions" :artist "Louis Armstrong"}
 50   {:album "Song for My Father" :artist "Horace Silver"}
 51   {:album "Jazz At Massey Hall, Vol. 2" :artist "Bud Powell"}
 52   {:album "Sweet Beginnings" :artist "Mildred Bailey"}
 53   {:album "Inner Urge" :artist "Joe Henderson"}
 54   {:album "Blues in the Air" :artist "Sidney Bechet"}
 55   {:album "Mu" :artist "Don Cherry"}
 56   {:album "Quiet Kenny" :artist "Kenny Dorham"}
 57   {:album "Dipper Mouth Blues" :artist "King Oliver's Creole Jazz Band"}
 58   {:album "Eastern Sounds" :artist "Yusef Lateef"}
 59   {:album "Night Train" :artist "Oscar Peterson Trio"}
 60   {:album "In the Townships" :artist "Dudu Pukwana & Spear"}
 61   {:album "Black Woman" :artist "Sonny Sharrock"}
 62   {:album "Conquistador!" :artist "Cecil Taylor"}
 63   {:album "Destination Out" :artist "Jackie McLean"}
 64   {:album "Bad Benson" :artist "George Benson"}
 65   {:album "Idle Moments" :artist "Grant Green"}
 66   {:album "Midnight Blue" :artist "Kenny Burrell"}
 67   {:album "Contours" :artist "Sam Rivers"}
 68   {:album "Blacks and Blues" :artist "Bobbi Humphrey"}
 69   {:album "Cool Struttin'" :artist "Sonny Clark"}
 70   {:album "Percussion Bitter Sweet" :artist "Max Roach"}
 71   {:album "Djangology" :artist "Django Reinhardt"}
 72   {:album "Ella and Basie" :artist "Ella Fitzgerald & Count Basie"}
 73   {:album "Blues Walk" :artist "Lou Donaldson"}
 74   {:album "Moanin'" :artist "Art Blakey & The Jazz Messengers"}
 75   {:album "The Complete Blue Note Recordings" :artist "Herbie Nichols"}
 76   {:album "Midnight Blues" :artist "Coleman Hawkins"}
 77   {:album "Power of Soul" :artist "Idris Muhammad"}
 78   {:album "Cornell 1964" :artist "Charles Mingus Sextet With Eric Dolphy"}
 79   {:album "Kansas City Powerhouse" :artist "Count Basie"}
 80   {:album "Machine Gun" :artist "Peter Brötzmann"}
 81   {:album "Karma" :artist "Pharoah Sanders"}
 82   {:album "Things Are Getting Better" :artist "Adderley & Jackson"}
 83   {:album "Song For" :artist "Joseph Jarman"}
 84   {:album "In Sommerhausen" :artist "Marion Brown"}
 85   {:album "Stoned Soul Picnic" :artist "Roy Ayers"}
 86   {:album "Easy Does It" :artist "Lester Young"}
 87   {:album "Out of the Afternoon" :artist "Roy Haynes"}
 88   {:album "Get/Gilberto" :artist "Stan Getz & João Gilberto"}
 89   {:album "Music for K" :artist "Tomasz Stańko"}
 90   {:album "Free Form" :artist "Donald Byrd"}
 91   {:album "The Köln Concert" :artist "Keith Jarrett"}
 92   {:album "Lawrence Of Newark" :artist "Larry Young"}
 93   {:album "Firebirds" :artist "Prince Lasha & Sonny Simmons"}
 94   {:album "Blue Flame" :artist "Woody Herman"}
 95   {:album "Sound" :artist "Roscoe Mitchell"}
 96   {:album "Soul Junction" :artist "Red Garland"}
 97   {:album "Attica Blues" :artist "Archie Shepp"}
 98   {:album "Together Alone" :artist "Joseph Jarman & Anthony Braxton"}
 99   {:album "Memorial Album" :artist "Clifford Brown"}
100   {:album "The Great Summit" :artist "Louis Armstrong & Duke Ellington"}
101   {:album "Thelonious Monk with John Coltrane" :artist "Monk & Coltrane"}
102 })
103 
104 (defn explode [data id-field]
105   (set
106    (mapcat #(let [id (hash (get % id-field))]
107              (for [[k v] %] [id k v]))
108            data)))
109 
110 (d/q '[:find ?album
111        :where
112        [?id :artist "Alice Coltrane"]
113        [?id :album ?album]]
114      (explode jazz-db :album))
115 
116 ;;=> #{["Journey in Satchidananda"] ["Universal Consciousness"]}

References and Interesting Information

Books

  • Durken, J. 1994. Expert Systems: Design and Development – A good book about when to actual use rules systems and the design principles when you decide on doing so.
  • Friedman-Hill, E. 2003. Jess in Action: Rule-Based Systems in Java – Provides a nice integration between Java objects and rule systems. I’ve written a mountain of Jess code in my time. This book is grossly underrated.
  • Giarrantano, J. and Riley, G. 1989. Expert Systems: Principles and Programming – My favorite book on production rules and expert systems and the CLIPS programming language. The latest version is a masterpiece.

Papers

  • Doorenbos, Robert. 1995. “Production Matching for Large Learning Systems” – A very lucid explanation of Rete and a few variants.
  • Forgy, Charles. 1979. “On the efficient implementation of production systems.” – The paper that describes the Rete matching algorithm and its implementation.
  • Forgy, Charles. 1981. “OPS5 User’s Manual”
  • Robinson, J.A. 1965. “A Machine-Oriented Logic Based on the Resolution Principle”
  • Robinson, J.A. 1971. “Computational logic: The unification computation”

Code

  • clojure.core.unify: https://github.com/clojure/core.unify
  • Clara: (Clojure-based production rules) https://github.com/cerner/clara-rules

Videos

  • Brush, Ryan. Retaking Rules for Developers https://www.youtube.com/watch?v=Z6oVuYmRgkk
  • Fogus. Zeder - Production Rules Systems in Clojure https://www.youtube.com/watch?v=1E2CoObAaPQ
  • Gearon, Paula. Production Rules on Databases https://www.youtube.com/watch?v=8rRzESy0X2k
  • What is Rete III? http://dmblog.fico.com/2005/09/what_is_rete_ii.html

Systems

  • CLIPS (C-based expert system software) http://clipsrules.sourceforge.net/
  • Datomic (transactional, distributed database) http://www.datomic.com
  • Drools (Java-based rules management software) http://www.drools.org/
  • Jess (Java-based expert system software) http://herzberg.ca.sandia.gov/
  • OPS5 (Common Lisp based expert system software) https://github.com/johanlindberg/ops5

Fogus’ Fun Corner

Qaanaaq is a game of palindromic pattern building for two or three players needing only paper and pen. The player with the most points when the board fills wins.

Setup

Draw a 5x5 (or 7x7) grid on the paper with the center square blacked out. For two players one player plays the letter ‘Q’, the other plays ‘A’, and the letter ‘N’ is neutral. For three players each plays one of the three letters.

Gameplay

On each turn, players write one of each letter into any empty cell on the board (the center is not a playable cell). When the board fills up then the scoring begins.

Scoring

Palindromes are checked along the horizontal, vertical, and diagonal axes (for a simpler game do not score diagonals). For each palindrome containing your letter, score points equal to the palindrome’s size minus the number of opponent letters therein. The neutral ‘N’ (2p only) is not considered an opponent letter.

The player with the highest score wins.

Palindrome Examples
  • In the 2-player game the palindrome QAQ for the Q-player is worth 2pts. However, the palindrome QNQ is worth 3pts because it contains the neutral letter ‘N’ .
  • The palindrome QQQQ is worth 4-points, but also contains sub-palindromes QQQ, QQQ, QQ, QQ, and QQ, making it worth a total of 16-points.

Enjoy!

Appendix A - prodrules.clj

 1 (ns prodrules
 2   (:require [clojure.core.unify :as u]
 3             [clojure.set :as s]
 4             [datomic.api :as d]))
 5 
 6 (defn unifications [[clause & more :as clauses] facts context]
 7   (if clause
 8     (let [bindings (keep #(u/unify clause % context) facts)]
 9       (mapcat #(unifications more facts %) bindings))
10     [context]))
11 
12 (defn select-rule [selection-strategy rules facts]
13   (let [possibilities (for [rule     rules
14                             bindings (unifications (:antecedent rule) facts {})]
15 	                    [rule bindings])]
16 	(selection-strategy possibilities)))
17 
18 (defn apply-rule [rule facts context]
19   (let [new-facts (set (for [rhs (:consequent rule)]
20                          (u/subst rhs context)))]
21 	(s/union new-facts facts)))
22 
23 (defn step [rules facts]
24   (when-let [[rule binds] (select-rule rand-nth rules facts)]
25     (apply-rule rule facts binds)))
26 
27 (defn states [kb] (iterate #(step (:rules kb) %)
28 	                       (set (:facts kb))))
29 
30 (defn cycle [qf kb] (qf (states kb)))
31 
32 (defn naive-qf [states] (last (take 256 states)))

Though I use the clojure.core.unify library wholesale, the implimentation of unification and substitution would likely fit on this page also – with judicious spacing. I’ll reserve their implementation for a future installment.

Michael Fogus - a contributor to Clojure and ClojureScript. Creator of programming source codes.

An occasional blogger at Send More Paramedics and also co-author of the book, The Joy of Clojure and author of Functional JavaScript.

Author contact

Discussion and information

Thanks

Thanks go out to Russ Olsen and Michael Nygard for providing feedback and corrects.

Notes

1See the appendix for the full source listing.

2Fully disclosure: I work for the company that created Datomic.

3From the masterful book on Java-based production rule programming using the Jess programming system, “Jess in Action.”

4The actual value of these IDs are irrelevant as long as they remain mutually comparable. Using Datomic to query a data-structure composed in this way is very useful when creating systems built around it.

5Datomic provides a capability to trigger code on its transaction queue that could be used to make such a task reactive, but the logic of the tie would still need to reside in code.

6Of course, production rules can provide more capabilities that merely defining data relationships, but I’ve found a constrained use to be more prudent in many cases. In my experience, rules systems are difficult to manage as the knowledge bases become more complex. The siren song of a fully realized domain encoding has led many a project crashing into the shoals.

7In my experience, while rules-based languages are quite powerful they tend to be married to poor databases or even worse, limited in-memory fact storage solutions. The reason is that these systems are often created to be rules systems first and only databases as an afterthought. I’d love to see and learn about databases specifically designed for use as industrial strength knowledge bases. (pointers welcomed)

8Turing complete rules languages are double-edged flaming swords with little swords instead of a pommel and a dagger instead of a handle.

9I’ve created my share of production rules systems in my time and have tried the pure approach. It’s a beautiful thing when it works well, but wow can it be slow.

10This smells of a genealogy example… my apologies.

11Computer scientists like to call this approach “old school.”

12An interesting aspect of many rule selection strategies is that the precise execution order of rules in a production rules system is extremely difficult, if not impossible, to know until after execution. Therefore, many systems provide something called salience that effectively allows a rules engineer to assign “weights” to rules in order to add some level of execution sequence to the system. While salience can be very useful for building useful clean-up layers to a rule set, in practice their overuse devolves a production rules system in a procedural affair.

13Occasionally someone asks me what my favorite Clojure functions are and inevitably I answer with juxt or select-keys or maybe trampoline but iterate is the bee’s knees lately.

14A slightly less dumb quiescence function for this system would be one that could, minimally, pick a number more appropriate for the actual number of rules and facts in the system as 256 is likely two high for the what’s shown here and too low for a more complex knowledge base.

15While it might seem hypocritical, whenever someone asks me my thoughts on production rule systems my first comment is always “don’t implement one yourself if there’s an existing solution that works.” The reason is that such a system is really easy to implement in a naive way, but becomes shockingly difficult to scale, make robust, and debug for every incremental improvement in speed and efficiency needed in practice.

16I wonder if these two events are related? Hmmmm……

17There are other systems that attempt this integration also including, but not limited to, COOL, Jess, and Drools. All of these options are far more robust than Apocryphal, in every possible way.