8 A Multitasking Application

8.2 Trees

A natural way to store data in Lisp is by using trees. In Lisp, a tree is usually a list that contains other lists, which might contain other lists. Each nested list represents a branch of the tree. This application uses trees to store facts in the database, to implement the rule-matching system, and to link goals and subgoals.

the fact database tree

: Assume you have the following facts in the database:

(COLOR CLYDE GREY) 
(COLOR TWEETY YELLOW)
(STATUS WATER-PUMP BROKEN)

: The facts are stored in the tree as follows:

(*ROOT* (COLOR (CLYDE (GREY))
               (TWEETY (YELLOW)))
        (STATUS (WATER-PUMP (BROKEN))))

: Trees provide an efficient means of storing and retrieving fact lists because the elements that are common to several facts are consolidated. Thus, it takes the same number of steps to find Tweety's color as it does to find Clyde's color. Since the search is not sequential, the search time does not depend on the order of the stored facts.
: A given fact is read from left to right. For each word read, a matching subtree must be found. If no subtree matches, the fact is not contained in the database. If the fact is being asserted, the remaining words of the fact are inserted as a new subtree at that position.
: This approach is sometimes called a discrimination net because each branch represents a point of discrimination between the facts.

the conclusion pattern tree for rule matching

: The same discrimination net technique is also used to implement the rule-matching mechanism. The process of matching a query pattern or a rule premise to a rule conclusion is similar to matching a query pattern to a fact in the database. The conclusions of the rules are stored in a tree, along with a pointer to the rule. When looking for a matching rule, the application traverses the tree until it finds a pattern that matches; it then returns the pointer to the rule.

the decision tree of goals and subgoals

: As the rules are linked together, they form a decision tree. Each node in the tree represents a goal that can be used to infer a fact pattern at some point in the decision process. Conceptually, each set of branches from some node in this tree represent subgoals to which that node's goal has been reduced. Each one of these nodes is actually a process created through the Multitasking Facility. Consequently, the system must maintain a tree of processes.

The Advanced User's Guide - 9 SEP 1996

Generated with Harlequin WebMaker