The rule-utils.scm defines the basic data structures and operations used in the forward and backward chainers; see the description. Please read about the format of rules (aka "knowledge") files. Note, in particular, that variables in the rules can be written as ?x or (? x) as you prefer. The match.scm file defines the function match and auxiliaries, essentially identical to that in PS 1 (without segment variables). The function match takes two lists, a pattern list and a data list. Both the pattern and the data can be arbitrarily nested lists. The pattern is allowed to have variables of the form (? var), where var is any symbol. If the two lists can be matched so that any non-variable part of the pattern matches an identical part of the data, then match returns a list of variable bindings (each binding of the form (var value)). Otherwise, it returns #f. The special "anonymous" pattern variable (? _) matches anything but creates no binding. Note that when match returns (bindings), i.e. the empty bindings, the match is successful but the pattern had no (named) variables that needed binding.

The forward.scm file defines the rule interpreter. Basically, the system keeps a global list of rules and a global list of assertions. The function call (chain) activates the interpreter with the current rules and assertions. Note that it uses try-first-rule and choose-first-instance to, respectively, compute the candidate triggered rule-instances and to choose one to fire. Other conflict-resolution strategies can be implemented by calling chain-internal with a different pair of functions, to generate rule instances and choose one.

Look at zoo.k to see how these are used to implement the Zookeeper system in the text. You can run the Zookeeper rules on Athena by (read-k-file "/mit/6.034/www/psets/ps3/zoo.k"), evaluate one of the assertion functions such as (make-swifty) and then (chain) followed by (display-assertions).

The Zookeeper rules are all IF-THEN (deduction) rules. Our Scheme program also supports production rules as illustrated in the Bagger system, e.g., the ability to delete as well as add assertions. It also supports a mechanism for calling arbitrary Scheme programs to perform arbitrary actions or perform tests, such as those checking the number of assertions that match a pattern, that go beyond the presence or absence of individual assertions. You can run the Bagger rules on Athena by (read-k-file "/mit/6.034/www/psets/ps3/bagger.k") and then (chain) followed by (display-assertions).

In summary, rules are of the form:

 (rule-name
    IF          antecedents
    [AND-IF     tests]
    [THEN       thens]
    [ADD        thens]
    [DELETE     deletes]
    [SAYING     sayings]
    [EVALUATING evals])

• IF antecedents -- the antecedents are patterns for match, all of which must match some assertion in the current set.
• AND-IF tests -- the tests are Scheme expressions that can contain the pattern variables present in the antecedents. Note that the rule variables in these expressions will usually need to be quoted. All the AND-IF tests must evaluate to a non-false value for the rule to be fired.
• THEN thens -- the thens are assertion patterns to be added to the current set.
• ADD is a synonym for THEN, normally used when rules are doing both additions and deletions. THEN and ADD should not both be used in the same rule (but this is not enforced).
• EVALUATING evals -- the evals are Scheme expressions that can contain the pattern variables present in the antecedents (remember to quote as appropriate).
• DELETE deletes -- the deletes are assertion patterns. Assertions matching these patterns (after instantiating variables in the antecedents) are to be deleted from the current set.
• SAYING messages-- the messages are usually strings and variables forming a message to print when the rule is fired. For example:
  SAYING "Rule 1 fired with x =" ?x "and y =" ?y