8 A Multitasking Application

8.1 The application database

This application maintains a small database whose data consist of facts, which are lists of words that compose a statement about the world:

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

The process of storing facts in the database is called assertion. You can retrieve a fact through a query, which is a method of matching a fact with a pattern. For example, if you query with the pattern(THE COLOR OF ?WHO IS ?WHAT) and the facts listed above are currently stored in the database, the two facts(THE COLOR OF CLYDE IS GREY)and(THE COLOR OF TWEETY IS YELLOW) are found.

A fact matches a pattern if the two lists are identical except for the variables, which are preceded by a question mark (?) in the pattern. Variables can be matched like a wildcard to any symbol in the corresponding position of the fact. The process of associating a variable with a matching symbol is called binding the variable to the symbol. Matching a fact to a pattern requires finding a binding for each variable in the pattern. By replacing each variable in the pattern with its associated symbol through binding, a pattern can be transformed into a list that is identical with a fact.

The application can also use rules to deduce new facts based on facts currently stored in the database. A rule is a list of the following form:

(IF premises THEN conclusions)

Both the premises and the conclusions are one or more fact patterns. These patterns have the same form as query patterns.

For example, you can write a rule about an elephant as follows:

RULE-1: (IF (?ANIMAL IS AN ELEPHANT) THEN (THE SIZE OF ?ANIMAL IS LARGE))

If the database already contains the fact(CLYDE IS AN ELEPHANT) and you execute the call(QUERY '(THE SIZE OF ?WHO IS LARGE)), the application usesRULE-1 to deduce the following fact:

(THE SIZE OF CLYDE IS LARGE)

Rules can be linked together like a chain. For example, assume that you have the following additional rule:

RULE-2 (IF (?ANIMAL HAS A BIG TRUNK) THEN (?ANIMAL IS AN ELEPHANT))

If the database already contains the fact(DUMBO HAS A BIG TRUNK), the application can deduce the additional fact(THE SIZE OF DUMBO IS LARGE). In effect, these rules have been chained together to perform the deduction. Since the rules are linked based on their conclusions and not on their premises, they are invoked in a somewhat backwards direction. Consequently, this procedure is called backward chaining.

You can view backward chaining as follows. Assume thatfact-1 is contained in the database, along with the following rules:

(if fact-1 then fact-2)
(if fact-2 then fact-3)
(if fact-3 then fact-4)

You want to determine whetherfact-4 is true. From the rules, you know thatfact-4 would be true iffact-3 were true, andfact-3 would be true iffact-2 were true, andfact-2 would be true iffact-1 were true.

Sincefact-1 is in the database, it must be true. The application determines the truthfulness offact-4 as follows:

fact-1 is true, sofact-2 is true.
fact-2 is true, sofact-3 is true.
fact-3 is true, sofact-4 is true.

For the purposes of this discussion, the application being described can be called the backward chainer.

The Advanced User's Guide - 9 SEP 1996

Generated with Harlequin WebMaker