The Deductive Data Retriever is a simple logic system that supports basic 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.
For study purposes, you may prefer to look at the Simplified Deductive Data Retriever. It's a subset with simpler code that passes the same test cases, but is less efficient, and doesn't support tracing or forward chaining.
Setting up the Deductive Retriever
The functions you need are
defined in ddr.lisp
and exported from the package DDR
. This is loaded by the CS325 system.
The key functions for the Deductive Retriever are:
(tell form)
: stores form in the knowledge base(ask sentence)
: returns a list of all sentences matching sentence in the knowledge base, including ones inferred by backward-chaining(replace-variables form binding-list)
: replaces the variables in form with the values those variables have in binding-list(clear-rule-base)
: removes all forms in the knowledge base
A form can be:
- an atomic sentence
(predicate term1 term2 ...)
, e.g.,(horse seabiscuit)
- A backward-chaining rule
(<- q p1 p2 ...)
, e.g.,(<- (horse ?x) (parent ?y ?x) (horse ?y))
- A forward-chaining rule of the form
(-> p q1 q2 ...)
or(-> (and p1 p2 ...) q1 q2 ...)
, e.g.,(-> (married ?x ?y) (married ?y ?x))
Terms in an atomic sentence can be:
- constants, e.g.,
seabiscuit
- variables, e.g.,
?x
- functional terms of the form
(function term2 ...)
, e.g.,(father-of ?x)
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
- The sentence is added to the knowledge base.
- If the sentence matches p in
the forward-chaining
rule
(-> p q1 q2 ...)
, then q1, q2, ... are also added, usingtell
, with the appropriate variable substitutions - if the sentence matches p1 in
the forward-chaining
rule
(-> (and p1 p2 ...) q1 q2 ...)
, and the remaining pi can be retrieved, using ask, then q1, q2, ... are also added, usingtell
, with the appropriate variable substitutions
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. 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.
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
- query unifies with an atomic sentence in the knowledge base
- query unifies with a q in a backward-chaining rule
(<- q p1 p2 ...)
and all the pi can be recursively retrieved, using ask.
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)) |
(ask '(horse ?x) '?x) | returns (flicka 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.
(not sentence)
implements "negation as failure."(ask '(not sentence))
will fail, i.e., returnnil
, if(ask 'sentence)
succeeds, otherwise it will return the list of((not sentence))
, which represents success.(bind variable lisp-expression)
will bind variable to the result of evaluating lisp-expression. Logic variables can appear in lisp-expression as long as they have been bound to some constant by the time the expression is evaluated.
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 ddr-tests.lisp. Post your discoveries and puzzlements on the Q&A site.
Also, there's more information about the Retriever on the CS325 deductive retriever page.