The Deductive Data Retriever is a simple logic system that supports simple backward and forward chaining rules. The code was originally developed by Drew McDermott for the book Artificial Intelligence Programming by Eugene Charniak, Christopher Riesbeck, Drew McDermott and James Meehan. It's been extended and modified slightly for this class.

Setting up the Deductive Retriever

The code for the Deductive Retriever is here:


http://www.cs.northwestern.edu/academics/courses/c48/code/ddr.zip

Extract the files to your CS 348 code area. To load and test the Retriever:

There's just a few tests here, but if they work, you're probably OK.

Using the Deductive Retriever

The key functions for the Deductive Retriever are:

A form can be:

Terms in an atomic sentence can be:

tell and forward-chaining

You use tell to add sentences and rules to the knowledge base. When you tell a rule, it just gets stored in the knowledge base. When you tell a sentence, and the sentence is not already in the knowledge base, then

For example,

(tell '(-> (married ?x ?y) (married ?y ?x)))
adds the forward-chaining rule to the knowledge base
(tell '(married john mary)) adds (married john mary) and (married mary john) to the knowledge base

No endless loop occurs because the forward-chaining stops when the second (tell '(married john mary)) discovers that (married john mary) is already known.

ask and backward-chaining

Most rules you write will be backward-chaining rules. You use forward-chaining mostly for simple rules, like married, that would cause endless loops as backward-chaining rules, or to assert facts with times, e.g., "I was in room 2 at time 3," "I was in room 3 at time 4," ... that would be tedious to infer repeatedly.

You use ask to retrieve information that is stored explicitly or can be inferred by backward-chaining.

(ask query[ form ])

will return a list of instantiations of form for every match to query that is deduced. Both query and form are patterns, with zero or more pattern variables. If form is omitted, it defaults to query. ask generates zero or more binding lists for query. An instantiation of form is created for each binding list.

A binding list is generated when

Here's an example of backward-chaining rules:

(tell '(<- (horse ?x) (parent ?y ?x) (horse ?y))) adds the backward-chaining rule to the knowledge base
(tell '(horse fury)) adds (horse fury) to the knowledge base
(tell '(parent fury flicka)) adds (parent fury flicka) to the knowledge base
(ask '(horse fury)) returns ((horse fury)), because that's in the knowledge base
(ask '(horse flicka)) returns ((horse flicka)), because that can be inferred using backward chaining
(ask '(horse ?x)) returns ((horse flicka) (horse fury))

For debugging, use ask-trace and show-trace.

(ask-trace query [ form ])
(show-trace)

ask-trace will create an internal tree showing what assertions and rules were used. show-trace will pretty-print this tree. The tree will mark which items were used and which didn't match and were skipped. If you get a stack overflow, looking at this tree may help you see where the problem is.

Non-logical Extensions

The Deductive Retriever is extensible. You can define special methods for retrieving and storing forms based on the first element of the form. You should look at the code to see how this is done, but several common extensions have already been implemented for you.

bind is particularly useful when you need to do a numeric calculation. For example, the rule

(tell '(<- (square-root ?n ?r) (bind ?r (sqrt ?n))))

This stores a rule that calculates the root of ?n using the Lisp function sqrt. The form

(ask '(square-root 25 ?x))

matches the rule, binding ?n to 25 and ?r to ?x. The rule then binds ?r, and hence ?x, to the result of evaluating (sqrt 25).

QUESTIONS about the Retriever? Don't ask me. Experiment. Read the code. It's not that long. Look at the example tests in ddrtest.lisp. Post your discoveries and puzzlements on the newsgroup.

Also, there's more information about the Retriever on the CS 325 deductive retriever page. Note: The functions store and retrieve have been renamed to tell and find-blists for this course.


Comments? comment image Send mail to Chris Riesbeck.