I have made a decision to discontinue the Cut The Knot column. The column has a distinction of having straddled two decades, two centuries, and in fact, two millennia. It was never meant to last that long. I thank all the readers who cared to send me their suggestions and point out typos and inevitable errors. Most of all, I owe an unrepaid debt to Fernando Gouvêa, the editor of the MAA Online, for his unwavering support and continuing editorial assistance. My Erdös number is still 3.

The theme of this year's math awareness month was The Mathematics of Networks. As was pointed out in the announcement, the networks arise in a variety of disciplines: Genome sequencing, physics, sociology, epidemiology, economics. Below, I shall outline an additional circumstance in which network architecture plays a remarkably dominant role.

Rete (pronounced "ree-tee" (in English)) is Latin (and also modern Italian) for net. Since its inception at Carnegie Mellon University in 1979, the Rete algorithm became the basis for several generations of rule-based (also known as production) system shells. The attraction of the Rete algorithm stems from the fact that its performance is asymptotically independent of the number of rules comprising the production system. Many of the present day production systems shells derive from CLIPS (C Language Integrated Production System) developed in 1984 at NASA's Johnson Space Center. (For a historical outline see, for example, What is CLIPS?, The Jess FAQ, Rule-based Languages for Expert Systems.) As my example, I shall be using Jess (Java Expert System Shell), a production rule shell designed and implemented by E. Friedman-Hill at Sandia National Laboratories in Livermore, California. In Jess, the language of the rules is derived from Lisp, the venerable veteran tool of expert system research. (For an introduction to Lisp, see [Hofstadter, Ch. 17-19].) As in Lisp, the fundamental construct in Jess is the list. A list is a sequence of syntactic tokens enclosed in a pair of parentheses. Lists themselves naturally serve as syntactic tokens. Following are a few examples of valid lists:

In a first approximation, a production is an IF-THEN construct:

whose Jess analogue looks like

(Comments in Jess start with a semicolon and continue to the end of the line. Thus the above is just an empty rule.) The most important difference between the conventional usage of IF-THEN and Jess rules is not syntactic. Conventionally, condition is a boolean proposition, something that may be either true or false. In Jess, the left-hand side (LHS) of a rule is a pattern to be matched. Patterns are matched by facts. Facts may or may not be present. If they are, and some of them match the LHS of a rule, the rule fires, i.e. the action in its RHS is executed. Many rules may be activated by the same facts; the same facts may also activate a single rule more than once.

Let's consider a logical problem from [Honsberger, Essay 4; Pedoe, pp. 74-76]:

Additional reasoning reveals that the only possible placement order is Nancy, Lucy, Opey, Minnie. Let's see now how the problem might be approached in Jess.

We start with the specification of facts that our production system will work with:

(deftemplate placement
  (slot name)
  (slot place))

The facts are called "placement" and have slots for a (girl's) name and the place achieved by that girl. So, for example,

(placement (name Nancy) (place 3))

says that Nancy took the third place. Next we prepare to place (assert) all possibly relevant facts in Jess' working memory with a single rule:

(defrule AllThePossibleFacts
=>
  (foreach ?name (create$ Nancy Minnie Lucy Opey)
    (foreach ?place (create$ 1 2 3 4)
      (assert (placement (name ?name) (place ?place))))))

Variable names in Jess start with ?, and, above, we have two of them: ?name and ?place. ?name ranges over the four pieces of the list (Nancy Minnie Lucy Opey) created with the function create$. ?place takes values from the list (1 2 3 4) similarly created. The LHS of the rule AllThePossibleFacts is empty. It is matched right away with no facts in memory. As soon as Jess begins processing our production system, the rule fires and causes 16 different facts to be asserted — something for the next rule to work with. This is a long rule that begins with

(defrule ProblemFromIngenuityInMathematics
  (placement (name Nancy) (place ?n))

The rule is given a name (ProblemFromIngenuityInMathematics), and

  (placement (name Nancy) (place ?n))

is its first pattern. This pattern can be matched by any fact that claims Nancy's placement. The first rule asserts four such facts. If and when a match occurs, Nancy's claimed placement is stored in the variable ?n. We add patterns for other girls, too. The next pattern, now for Minnie,

  (placement (name Minnie) (place ?m&~?n))

looks a little more complicated. It matches any fact claiming Minnie's placement different from ?n, i.e., Nancy's placement. Two more patterns introduce successively more placement restrictions:

  (placement (name Lucy) (place ?l&~?n&~?m))
  (placement (name Opey) (place ?o&~?n&~?m&~?l))

The placements of Minnie, Lucy, and Opey are stored in variables ?m, ?l, and ?o, respectively, and all four (i.e. including ?n) are required to be different. There are of course 4! = 16 such combinations. There are further three patterns that reflect on the pronouncements of three girls. The first of these is

  (or (and (placement (name Nancy) (place ?n&1))
        (not (placement (name Minnie) (place ?m&2))))
      (and (not (placement (name Nancy) (place ?n&1)))
        (placement (name Minnie) (place ?m&2))))

which exactly corresponds to Honsberger's

and the other two are explained similarly. The LHS is separated from the RHS by a simulated arrow "=>". The RHS simply prints out the result to the standard output (t). If you run our production system in Jess, you'll see the result:

To obtain the result, Jess must be instructed to process the rules, which is accomplished with the (run) command. (reset) should precede (run) for technical reasons. (In particular, because of the presence of a rule with an empty LHS. While parsing the rules, Jess inserts an (initial-fact) pattern into the empty LHS and also asserts that fact.)

Note an interesting fact: while all three conditions of the problem are essential for there being a single solution, one is more important than the other two. If we discard either Minnie's or Nancy's statement, the problem will have two solutions. However, disregarding Lucy's assertion leads to four different solutions.

A slightly more complex example is available online. This implements a restricted version of Scoring Misère expediently called Sticks. Now, Jess has been implemented in Java and allows to call methods of Java objects by productions as well as manipulating the Jess' working memory from Java. To test this feature, I made (with permission from Sandia Laboratories) some modifications to the original code of Sticks. I verified my modifications in Windows XP with IE 6.0 and Netscape 7.1. The latter also works in Windows 98. Unfortunately, the older versions of the browsers (4.61 for Netscape, and 5.0 for IE) fail miserably. In all circumstances, Jess requires Java 2 installed, which, however, should not be a problem. The Java 2 runtime comes standard with the recent crop of computers and browsers. With these caveats, I include the modified applet below

How facts are matched to patterns? An obvious approach is to loop through all the rules and test in turn the LHS of each against the facts in working memory (the place where the facts reside.) The problem with that is that, as the term suggests, the working memory often contains transient information: facts come and go. With any introduction or removal of a fact, the matching procedure is getting executed all over again. This is an expensive enterprise which is addressed by the Rete algorithm. As a matter of fact, changes of the working memory are usually small compared to its size: a change usually affects only a few rules among many. The Rete algorithm makes use of several data structures to keep to a minimum the number of the running matches. The fundamental among those data structures is the graph: a network of interconnected nodes. The graph is directed: each node has zero, one, or two inputs (links from other nodes) and any number of outputs (links to other nodes).

Nodes with no inputs correspond to various templates. All nodes remember the facts they match. When a new fact arrives, it settles at one of the input nodes and is passed on to the nodes attached to the outputs of this one. Nodes with a single input perform matches on individual facts; double input nodes perform joint matches. In case of a match, they pass the fact (or now a group of facts) to their outputs. The nodes with no outputs correspond to individual rules. A match at this level results in a rule activation.

There is more to the Rete algorithm than could be described in two paragraphs. I have not mentioned the NOT-nodes corresponding to the absence of a fact or, say, the fact removal. All this and more could be found at various sources on the Web (some references have been mentioned earlier) and print form. But this must be said.

The interest in expert system and the excitement about the promise of artificial intelligence probably crested in the 1980s. During a recent visit to a Borders bookstore I could not locate a single book with "Expert System" in the title. However, it is a verifiable fact and a matter of experience that various production systems are being currently used in a multitude of industries and applications. This is mainly due to the availability of the Rete algorithm which made the use of production systems feasible.

References

1. C. L. Forgy, Rete: A Fast Algorithm for the Many Pattern / Many Object Pattern Match Problem, Artificial Intelligence, 19 (1982), 17-37.
2. E. Friedman-Hill, Jess In Action, Manning, 2003
3. D. Hofstadter, Metamagical Themas, Basic Books, 1985
4. R. Honsberger, Ingenuity In Mathematics, MAA, 1970.
5. D. Pedoe, The Gentle Art of Mathematics, Dover, 1973.

Alex Bogomolny has started and still maintains a popular Web site Interactive Mathematics Miscellany and Puzzles to which he brought more than 10 years of college instruction and, at least as much, programming experience. He holds M.S. degree in Mathematics from the Moscow State University and Ph.D. in Applied Mathematics from the Hebrew University of Jerusalem. In March 2004, his site has welcomed its 9,000,000^th visitor. The site is a recipient of the 2003 Sci/Tech Award from the editors of Scientific American.

Copyright © 1996-2004 Alexander Bogomolny