Cut The Knot!An interactive column using Java applets
by Alex Bogomolny
Alex Bogomolny's May 2004 column will be his last (for now, we hope).
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.
The problem could be restated in the language of boolean algebra as:
where, for example, N1 is a shorthand for the statement "Nancy was first", M2 represents "Minnie was second", with other symbols having similar interpretations. The dot (·) here stands for the logical conjunction (AND), the plus sign (+) stands for the disjunction (OR), the tilde (~) means negation (NOT), and 1 indicates the boolean "true". Using algebra and some reasoning, this reduces to
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:
The facts are called "placement" and have slots for a (girl's) name and the place achieved by that girl. So, for example,
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:
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
The rule is given a name (ProblemFromIngenuityInMathematics), and
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,
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:
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
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.
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,000th visitor. The site is a recipient of the 2003 Sci/Tech Award from the editors of Scientific American.
Copyright © 1996-2004 Alexander Bogomolny