CS 4341 Project #1: A Rule Interpreter

Due Monday, March 31

Write a simple rule interpreter and demonstrate its capabilities for a simple situation-recognition problem. A rule-based system has 3 parts: a database (Working Memory) which is modified by the rules, a set of Rules, and an Inference Engine which executes the rules.

Working Memory

The database can be stored any way you want. A list of facts, such as

(defvar database '((thing-1 is-a dog) (thing-1 weight 55) ...))

is fine. More advanced techniques include property lists and hash lists, but you need not use them. In fact, the database component will be replaced by a frame system in Project 2, so it is not a good idea to spend too much time on it now.

You might want to define interface functions such as assert-dband query-db to assert facts to the database and to try to perform a pattern match on the database.

Rules

Each rule should be of the form ``situation recognized leads to action executed causing change in situation,'' or Situation-Action for short. An inference engine acting on a set of rules will transform an initial situation into some ``terminal'' situation, probably some form of answer. The situation is described in the Working Memory.

The Left Hand Side (LHS) or ``situation'' side of a rule can be expressed as a boolean expression of arbitrary predicates. These predicates will generally be pattern-matched against the database, possibly instantiating variables in the process. The Right Hand Side (RHS), or ``action'' side can be any sequence of actions. These actions will generally be database assertions, although they may also include I/O. It is best if the RHS can refer to variables instantiated by the LHS. Or vice versa. The actions act on the working memory, thus, when the inference engine recognizes that the situation on the LHS of some rule holds true, the rule ``fires,'' performing the action(s) specified in the RHS.

In the example below the action form (A v) means ``set the value of the attribute A to v.'' So ``(Plant Yes)'' means ``set the value of the attribute Plant to Yes;'' i.e., It is a plant. The ``Green?'' below is a short form for ``Does the attribute Color have the value Green?'' Similarly for other predicates.

Here is a sample set of rules. Yours do not have to follow this format.

Green? AND NOT Heavy?  =>  (Type Grape) 
Round? AND (Red? OR Green?)  =>  (Type Apple) 
Red?  =>  (Type Tomato) 
Tomato?  =>  (Plant Yes) & (Height Short) 
NOT Ripe?  =>  (Color Green) 
CanCarry?  =>  (Heavy No)

Defining rules can be simplified using Lisp macros. A Lisp macro looks like a Lisp function, but the value returned from the body of the macro is evaluated one extra time. That is, the body of a macro should be a function to be evaluated. Using macros, one can eliminate the need to put single quotes throughout one's rules. The syntax of a macro is

(defmacro macro-name (arg1 arg2 ...) body)

One can define a defrule macro as follows:

(defvar rule-list ())

(defmacro defrule (name text lhs rhs)
  (list 'setf 'rule-list
        (list 'cons (list 'quote (list name text lhs rhs))
                    'rule-list)))

(defun first-rule (rules) (first rules))

(defun rest-rules (rules) (rest rules))

(defun rule-name (rule) (first rule))

(defun rule-text (rule) (second rule))

(defun rule-lhs (rule) (third rule))

(defun rule-rhs (rule) (fourth rule))

(defrule unripe-tomato
      "If it is green and not ripe, then it is a tomato"
      (and (green? x) (not (ripe? x)))
      (tomato x))

(defrule ripe-tomato
      "If is is red, then it is a tomato"
      (red? x)
      (tomato x))

Although the defmacro might look mysterious, you don't have to understand its details. Briefly, when the unripe-tomato rule is defined, the defrule macro expands into

(setf rule-list 
      (cons '(unripe-tomato
              "If it is green and not ripe, then it is a tomato"
              (and (green? x) (not (ripe? x)))
              (tomato x))
            rule-list))

This just adds the rule to the front of the rule-list. Rules are accessed from the rule list using first-rule andrest-rules, and individual parts of a rule are accessed using rule-name, rule-text, rule-lhs, and rule-rhs.

Note for advanced Lisp programmers: Lisp's backquote mechanism (Lisp, 3rd edition, p. 170) can greatly simplify writing macros. Using the backquote, macro defrule can be written as

(defmacro defrule (name text lhs rhs)
  `(setf rule-list
         (cons '(,name ,text ,lhs ,rhs)
               rule-list)))

Keep in mind that this is just one way to define rules. You do not have to follow this format, either!

It is more flexible if you actually interpret the rules rather than treat them as executable code. That way, you can do anything you want with them. If the rules are executable code, you might have problems if the names you want conflict with Lisp, as in

(RULE PEA-P
      "Is it a pea?"
      (AND (LIGHT (? X)) (GREEN (? X)))
      (ASSERT-DB (? X) IS-A PEA))

you might have trouble if AND is a special form, which it is. But if you are careful, either approach can be made to work.

Notice that in this rule, pattern matching variables are in the form (? variable-name). The intent is that variable-name can be instantiated in one part of the rule and be referenced elsewhere in the rule. Your rules do not have to follow this format, either!

Inference Engine

Here is one suggested strategy for the control of rule selection and execution: All of the rules are examined to see if one or more matches the situation. If only rule one matches, then the action (RHS) of that rule is executed. If more than one rule matches, the one that is most ``specific'' is used. Specificity is up to you to define, but it probably has something to do with the length of the LHS. If there are two or more rules with the same specificity then the one chosen is the earlier one in the user-specified rule list. You will have to worry about the same rule firing again in an unchanged situation. You may decide to use another rule selection strategy instead of this one.

Question 1: What is your rule selection strategy and why are you using it?

A potential difficulty with this scheme is that the same rule may continuously match the current situation, and try to fire repeatedly.

Question 2: How can you prevent this? Do so.

In order to be useful, an inference engine must be able to chain inferences. That is, the result of one rule firing can influence subsequent rules. For example, if A => B and B => C are rules, then it should be possible to deduce C from A (if using forward chaining) or ask about or otherwise use A in order to determine C (if using backward chaining). You must demonstrate that your inference engine can chain rules.

You can design your rule-based system to work in either forward or backward chaining mode (or both!). In forward chaining, you will typically start with an initial set of assertions in the working memory. As the rules are executed, new assertions are added and/or old assertions removed. You should show the initial set of assertions, the rule execution trace and the final set of assertions.

For backward chaining, one possibility is to start with an initial set of assertions and a goal that is to be deduced (if possible). Alternatively, you can start with an empty set of assertions, but ask the user a question (which is then asserted) if it is not possible to deduce that assertion.

Question 3: Does your system use forward or backward chaining or both? Note: Implementing both (selectable by the user or system) is liable to earn style credit.

Demonstration

For the demonstration of your system, you could use a simple working memory consisting of records of attributes and values. For example:

Attribute	Value
Type
Plant
Vegetable
Fruit
Ripe	No
Shape	Round
Heavy
Carry	Yes
Weight

To perform the most general and effective pattern matching, you will need an explicit variable binding mechanism. You may want to appropriate some of the pattern matching functions from class for this purpose. You may use the code in /cs/cs4341/ai3/match.lsp, but be sure to tell us that you have done so.

Here is an example using a slightly different syntax:

(IF (> (WEIGHT (? y)) 10) THEN ((? y) HEAVY))
(IF (Value? Vegetable) THEN (PRINT "Not a fruit!"))
(IF (AND (EQUAL (Color (? z)) Green) ((? z) HEAVY))
    THEN (Type (? z) Watermelon))

The problem that you are to solve as a demonstration is up to you. A set of about 20 rules will be adequate for a two-person project; larger project teams should have correspondingly larger rule sets. If the problem doesn't show the capabilities of your system fully then include an example, not necessarily meaningful, that does.

The input to the system should include the rules and the state of the working memory. The program handles input, output, rule selection and rule execution.

Questions

Several questions are scattered throughout this document -- you should answer them in a file, such as answers.txt, which should be submitted (see next).

Submitting your project

It is a good idea to place different modules into separate files. For example, the inference engine, pattern matcher, rules, working memory, etc. The submitted files should be self-explanatory. Submit them using turnin together with examples of your system running. Use an assignment of "proj1" to turnin, as in

/cs/bin/turnin submit cs4341 proj1 *.*

Grading

This project will be graded based on:

Correctness (40%): Does the project do what was asked? Were all the questions in the problem statement answered correctly?
Documentation (25%): Is the code understandable? Is the overall approach described well?
Examples (25%): Is every feature exercised? No bugs? Lots and lots of examples?
Style (10%): Original or unusual features. Doing more than was asked, or doing it much better than is expected.

Originality

You might find potentially relevant code from various sources: previous CS 4341 students, textbooks, /cs/cs4341/, etc. While it is perfectly legal to look at the work of others, the project team must submit its own work. Simply changing variable and function names from others' work is not considered original and is likely to be detected.

Exception: For this and subsequent projects, you are allowed to use the pattern-matching code in /cs/cs4341/ai3/match.lsp, provided that you so state.

CS 4341 Home Page

CS 4341 Projects

[CS] WPI CS Home Page

[WPI] WPI Home Page