Description
In this homework you’ll implement a simple, specialized forward chaining (FC) or backward
chaining (BC) system in the context of ZOOKEEPER.
You are free to choose either FC or BC (but first see the caveat at the end of this document).
In order to do the homework, you must read the relevant parts of chapter 7 of Winston.
You must also read the relevant parts of a concise (2-pp) tutorial by Bob Berwick, attached to
this homework. Whenever you need to make an implementation-level decision, try to follow
Berwick’s advice. (As a matter of fact, the same advice is available in chapter 7, too.)
Finally, you may want to read the following excellent chapter (freely available to Bilkent IP
addresses) but it is not of immediate relevance to what you’re doing (although it is about
ZOOKEEPER):
Bench-Capon T.J.M., Jones D.M. (1999) PRONTO — Ontology-based Evaluation of
Knowledge Based Systems. In: Vermesan A., Coenen F. (eds) Validation and Verification
of Knowledge Based Systems. Springer, Boston, MA. https://doi.org/10.1007/978-1-
4757-6916-6_7
PROBLEM
The FC (or BC) system that you’ll implement will be specialized in the following strict sense: it’ll
only be able to work with ZOOKEEPER, as specified by Winston (viz. rules Z1 through Z15 but see
the note at the end of this document). In other words, regardless of what strategy (FC or BC) you
pick, your implementation should be limited to ZOOKEEPER and thus is not expected to work
with another set of rules.
For FC, you begin with an initial set of assertions in the WM. The WM will then grow in size. For
BC, you additionally need a hypothesis to test (and you never add anything to the given WM).
With FC, you stop as soon as you identify an animal (e.g., “Ali is an alligator”). With BC, you stop
when you (dis)prove the hypothesis (which is always an assertion such as “Sue is a snake”).
A submission consists of:
• Your program listing. (Explain in block comments which strategy you’ve implemented
and how. Details are important here.)
• (1 pt) Output of your program with the first FC (respectively, the first BC) example given
in chapter 7. (Just see figures 7.2 and 7.3 in the aforementioned chapter.)
• (6 pts) Outputs of your program for two examples (3 pts each) created by you. For FC,
an example simply consists of the lists of assertions in the WM and your program’s
output for this WM. For BC, you need to add a hypothesis, too. Your examples should be
reasonably nontrivial (at least as complicated as Winston’s examples). They should also
be sufficiently different from each other (and the examples given by Winston).
• (3 pts) I’ll email you a ‘surprise’ example the night before the due date of the homework
(i.e., the night of Tue April 13th). You’ll then solve it and include the output in your
submission. (Thus, do not submit your homework early!)
• (3 pts) Quality of your software.
As usual, your program should have a proper single-stepping facility so that its execution (firing
the rules as in figure 7.2, in case of FC; using the rules as in figure 7.3, in case of BC) should be
sufficiently transparent and understandable to your TAs. It is crucial to be able to display the
current snapshot of the WM and the rules of ZOOKEEPER (two windows!) when necessary.
Note: Make sure that you retype Z1 through Z15 correctly before you start using them in your
program. Beware that there is a typo in rule Z10: “strips” should read “stripes”. Avoiding typos
is important because in this homework you’ll be doing string pattern matching all the time.
Caveat: If you choose to implement BC, you’ll receive a bonus of 2 pts, provided that you collect
at least 11 pts (out of 13) from this homework.