Simple Deductive Retriever

The Simple Deductive Data Retriever (SDDR) 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.

To understand what a deductive retriever does, see the deductive retrieval overview

Setting up the Deductive Retriever

SDDR is one of the local projects in CS325.

(ql:quickload "sddr")

This defines the package sddr where the retriever sites, and sddr-tests where SDDR can be tested. To play with SDDR, do

(in-package :sddr-tests)

Using SDDR

The key function in SDDR is ask.

(ask query rules)

query is a fact. A query can have variables and functional terms. rules is a list of backward-chaining assertions assertions. Each assertion has the form

(<- consequent antecedent1 antecedent2 ...)

The consequent and antecedent are fact forms, They can have variables and functional terms.

ask returns a list of all sentences matching sentence in the knowledge base, including ones inferred by backward-chaining. ask will return a list of instantiations of query 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 a consequent in a backward-chaining rule. This leads SDDR to then recursively query for all the antecedents. Any variables that are bound by the unification are replaced with their bindings. Variables in rules are renamed to avoid confusion with variables of the same name in a query or other rule.

For testing a set of rules with various queries, you can use rap.

(defparameter *rules*
  '(
    (<- (mortal ?x) (human ?x))
    (<- (human socrates))
    (<- (human plato))
    ))

(rap *rules*)

This starts a "read-ask-print" loop using the given list of inference rules. Just enter a query, no quotes, and rap will print the results of calling ask for that query and the given rules.

Type any atom to end the loop.