Assignment 4
Due: Friday, Oct. 13
|
|
CS 232
Assignment 4 Due: Friday, Oct. 13 |
|
Complete the questions in Lab #5 on the MYCIN system.
Part a: In this part of the problem, you will implement a Common
LISP function to perform forward-chaining reasoning using a set of if-then rules for
identifying animals. The following code file provides a starting point for this task:
~cs232/download/zoo.lisp. Each rule is stored in a structure
that has three fields: num, if-clauses and then-clause.
From the definition of the rule structure, the following functions are
created automatically: make-rule, rule-num, rule-if-clauses and
rule-then-clause. The function make-zoo-rules assigns the
global variable *rules* to a list of 15 rule structures.
The following expression illustrates the construction of the rule for identifying
a penguin:
(make-rule :num 14
:if-clauses '((? is a bird) (? does not fly)
(? swims) (? is black and white))
:then-clause '(? is a penguin))
The zoo.lisp file also contains a global variable *assertions*
that serves as the working memory that stores the initial assertions and any new
assertions that are made during the reasoning process. There are four functions,
make-stretch, make-swifty, make-splashy and make-sandy that
assign *assertions* to an initial set of assertions for four animals.
The ? in the if-clauses and then-clause of the
rules is replaced with a name in the initial assertions created in these four functions.
Each of these functions calls the function display-assertions, which
prints the assertions currently stored on the *assertions* list.
Recall the English description of the algorithm for forward-chaining:
Loop through the rule base until no rule produces a new assertion
or the goal is reached
For each rule:
Try to match each
of the rule's antecendents by matching
it to known facts in working memory
If all the rule's
antecendents are
supported, assert each
consequent unless there is an identical assertion
already
The rule base for this problem does not distinguish rules that achieve a "goal", so
the reasoning process can continue until no new assertions are generated during a
loop through the rules. You should complete the function forward-chain
whose skeleton appears in zoo.lisp. This function can refer to the list
of rules stored in the global variable *rules*, and should update the
global variable *assertions* as new assertions are created from the
application of the rules. The forward-chain function can be implemented
using recursion, and it is ok to write separate helper functions. forward-chain
should keep track of the numbers of the rules that lead to new assertions, and
print the numbers of these rules during each pass through the
rule list. The following is a sample printout from an implementation of the
forward-chain function:
> (make-zoo-rules)
...
> (make-stretch)
...
> (forward-chain)
Looping through the rules ... used rules (1 8 11) to add assertions
Looping through the rules ... no more assertions added
(STRETCH HAS HAIR)
(STRETCH CHEWS CUD)
(STRETCH HAS LONG LEGS)
(STRETCH HAS LONG NECK)
(STRETCH HAS TAWNY COLOR)
(STRETCH HAS LONG NECK)
(STRETCH IS A MAMMAL)
(STRETCH IS A GIRAFFE)
NIL
The built-in subsetp may be helpful in your definition of
forward-chain. (subsetp list1 list2) returns T
if all of the elements in list1 are contained in list2,
and returns NIL otherwise. By default, the function eql is
used to compare elements, but the :test keyword argument can be used
to change the equality predicate used, similar to the member function.
For example:
> (subsetp '(b c) '(a b c d))
T
> (subsetp '((a b) (d e)) '((a b) (c d) (d e)))
NIL
> (subsetp '((a b) (d e)) '((a b) (c d) (d e)) :test #'equal)
T
When complete, test your forward-chain function with the sample
assertions created for each of the animals. Then set the *rules* list
to its reverse and again run the forward-chain function with a
sample set of assertions. How does the behavior change? What does this suggest
about how you should order the rules in a rule base in order to increase the
efficiency of forward chaining?