## Code Note

The simplest deductive retriever code I've been able to write is in sddr.lisp. It does unification and backward chaining and can handle all the key examples. There is an ASDF module that should be in your Quicklisp local projects folder.

ddr.lisp
is an improved version of this retriever. It's automatically
loaded into the `CS325-user`

package. It
is faster and
supports simple assertions and
forward chaining rules.
The general concepts are described in this document,
and functions for using it are described
here.

## Introduction

Deductive retrieval is a generalization of simple data
retrieval. Though the extensions appear relatively small, the result
is in fact a full-fledged alternative to the declarative approach seen
in C++, Java, PHP, ..., and the functional approach seen in
Lisp, Scheme, Haskell,.... This alternative is called
**declarative** programming

A data retriever has a database of assertions, e.g.,
`(married john mary)`

, `(in chicago illinois)`

, and
so on. The main operations are

- storing assertions in the database
- retrieving all assertions that match a
*query pattern*

The retriever looks through the database and returns all the assertions that match the input query pattern. Assertions are usually indexed and organized for fast retrieval, but the semantics is as if all assertions are matched against the query.

**A deductive retriever** adds the following operations:

- storing rules in the database
- using those rules to infer answers to queries, in addition to the assertions explicitly stored

Deductive retrieval has these major processes:

- unification -- generalized pattern matching
- backward chaining -- linking rules together to form a conclusion
- backtracking -- trying all possibilities until one or all answers are found

## Pattern Matching

A pattern can be any form, e.g., `(in tiger savannah)`

,
but usually a pattern will have variables, e.g., ```
(in ?x
savannah)
```

. A form without variables is sometimes called a
*constant* form.

A form matches a pattern all corresponding elements of the form and pattern can be matched. Constant elements match each other if they are equal. Variable elements can match anything, but if multiple occurrences of the same variable must match the same thing.

The result of a match is a *list* of binding lists. A
binding list is a list of `(`

pairs, recording each pattern variable and the corresponding form
element.*variable value*)

For example, the result of matching `(in ?x savannah)`

with `(in tiger savannah)`

is `(((?x tiger)))`

.

With simple patterns, the result of a match will be either
`NIL`

or a list of one binding list. It is possible to
extend patterns in such a way that multiple bindings can occur,
i.e., there is more than one way the pattern can match the
form.

In particular, matching `(in tiger savannah)`

with
`(in tiger savannah)`

will produce `(nil)`

, while
matching `(in tiger savannah)`

with ```
(in tiger
swamp)
```

will produce `nil`

.

### Unification

Unification introduces one additional feature to normal
pattern matching. It allows a pattern to match a pattern. This
raises a number of complexities. For example, a variable can bind
to another variable, or even to itself. Fortunately, these issues
have been worked out long ago, and the code for implementing
unification, while subtle and subject to pitfalls, is not all
that complicated. It can be found in the `unify.lisp`

file.

Patterns matching against patterns is important for backward chaining.

## Assertions and rules

The knowledge base for our deductive retriever contains:

- simple assertions, e.g.,
`(in tiger savannah)`

- backward chaining rules, e.g.,
`(<- (near ?x grass) (in ?x savannah))`

- forward chaining rules, e.g.,
`(-> (predator-of ?x ?y) (prey-of ?y ?x))`

Assertions and rules are stored using ```
(tell
```

, e.g.,*form*)

> (tell '(at tiger savannah)) > (tell '(<- (near ?x grass) (at ?x savannah))) > (tell '(-> (predator-of ?x ?y) (prey-of ?y ?x)))

## Logical terms

The arguments of predicates, such as `near`

or `at`

,
are called terms. Terms in logic can be

- Simple constants, e.g.,
`tiger`

- Variables, e.g.,
`?x`

- Functional terms, e.g.,
`(father-of john)`

Functional terms may look like assertions but they most definitely are not.
An assertion is like a sentence, e.g., `(at tiger savannah)`

is "The tiger is in the savannah." An assertion can be true or false.

A functional term is like a noun phrase, e.g., `(father-of john)`

is "the father of John." A functional term refers to something, but is neither
true nor false. It's like the difference between "the dog" and "that is a dog."
The former is a reference, the latter is an assertion.

Functional terms in logic are not like functions in Lisp. They are not
executable. They don't return values. They are simply ways to construct
a representation of something, e.g., `(date 2015 10 13)`

for
"the date October 13, 2015."

Functional terms turn out to give deductive retrieval super powers.

## Answering Queries

A query is asked by typing `(ask `

.
The query can be any form.*query*)

If the query is a constant form, then we're effectively asking a yes or no question. For example, to ask "Is the tiger near grass?" we type:

> (ask '(at tiger savannah)) ((AT TIGER SAVANNAH))

The result is a list of answers to the query found in the KB. There's just one answer to this query.

### Backward Chaining

Now consider a query very similar to the previous one:

> (ask '(near tiger grass) ((NEAR TIGER GRASS))

The query is still a "yes/no" questions, and the answer still
says "yes" but ```
(near tiger
grass)
```

was not explicitly stored in the knowledge base. It
was inferred using the backward chaining rule "something is near
grass if it is in a savannah."

In this case, only one rule was needed to derive the answer. In general, though, many rules may be chained together.

For example, let's add a rule that says that if you're near something, you can bite it:

> (tell '(<- (can-bite ?x ?y) (near ?x ?y)))

Now let's ask if the tiger can bite grass:

> (ask '(can-bite tiger grass)) ((CAN-BITE TIGER GRASS))

The answer is obviously yes, but it required two rules and an assertion to prove it. The retriever found a rule that said the tiger could bite grass if it was near grass. It then found a rule that said a tiger would be near grass if it was in a savannah. Finally, it found the assertion that the tiger was indeed in a savannah.

The two rules and the assertion form a chain, or proof, of the assertion that the tiger can bite grass. The retriever will find all the chains that it can. Chains always terminate in assertions.

## Representing Knowledge in Rules

There are many ways to represent a rule in English as deductive retrieval rules. Just as with the frame system, you have to develop a coherent ontology, i.e., a set of predicates and objects.

For example, consider the rule "something can satisfy its hunger with something if it's near something it eats." There are many parts to be represented in this rule:

- "can"
- "satisfy"
- "near"
- "hunger"
- "is food it eats"

There's no single right answer to these questions, though some answers are better than others, depending how sophisticated you need the retriever to be, how efficient it should, how easy you want it to be for others to add rules, and so on.

We've already chosen a representation for "near," namely
`(near `

. "Can" is a complex concept that
still puzzles philosophers. "Hunger" is an interesting property,
because it keeps coming back. "Satisfying hunger" is not an
all-or-none result, but a matter of degree, ranging from "hungry
but surviving" to "stuffed to the gills."*x y*)

However, for our purposes, we don't care about any of these
issues. We just want to know whether something will starve or
not. Therefore, we'll merge all these concepts into one
predicate. `(can-satisfy-hunger-with `

that
represents the claim that *x y*)*x* could satisfy the problem of
hunger by eating *y*.

For "food it eats" we'll use the predicate ```
(eats
```

to say that *x y*)

is a food that
*y*

eats.*x*

Our rule then becomes something like this:

(<- (can-satisfy-hunger-with ?x ?y) (eats ?x ?y) (near ?x ?y))

The difference between the above and

(<- (can-satisfy-hunger ?x) (near ?x ?y) (eats ?x ?y))

is purely one of possible efficiency. The predicate that generally has fewer answers should be tested first. In the extreme case, a predicate that is often false should be tested as early as possible in a rule, to avoid needless testing of other parts of the rule. The same answers would be returned by either form of the rule.

Since we already have a `predator-of`

predicate,
let's link that to `eats`

:

> (tell '(<- (eats ?y ?x) (predator-of ?x ?y)))

The important point is that every one of these choices for
predicates, include the `near`

predicate, could have been
made differently. The odds are great that the rules that result
from the choices used here will not work well for a system
reasoning about spatial relationships, detailed animal behavior,
and so on.

### Deductive Retrieval versus Logic

Deductive retrieval is based on logical principles, but a deductive retriever is different from a theorem prover in a number of significant ways.

First, simple deductive retrievers are very limited in the logic that they can represent and deduce:

- Rules are limited to the form
`(<-`

.*predication pattern pattern*...)- You can't directly represent disjunctive assertions, such as "Either Mary or John will come to the party."

- All assertions are universally quantified. That is,
the assertion
`(p ?x)`

says "for all x, p(x) is true," or in logic notation, "∀x p(x)." The assertion`(<- (q ?x) (p ?x))`

says "for all x, p(x) implies q(x)," or in logic notation "∀x p(x) ⇒ q(x)."- You can't assert something like "There exists a smallest prime."

- All queries are existentially quantified. That is,
the query
`(p ?x)`

asks "does there exist an x such that p(x) is true?," or, in logic, "∃x p(x)." The retriever returns all such values.- You can't ask something like "Are all birds mammals?"

- You can't make assertions or queries with variables for
predicates. These systems implement first-order logic only.
- You can't assert something like "All predicates about mammals take two arguments.

Deductive systems can be extended to overcome many of these limitations, and others, but this has to be done carefully. The limitations to what's called Horn clause logic allow for very simple and fast deductive retrieval. Adding more power can lead to slower processing, or to queries that can't be answered.

Deductive retrieval also uses techniques not available in logic. Prolog, for example, applies rules in the order in which they were defined, so that different proofs are possible, depending on the order in which rules are specified. Prolog also has a "cut" operation that allows a rule to eliminate other proof paths from the search process. Our retriever has a mechanism for allowing arbitrary Lisp code to be executed during retrieval.

## Negation in the deductive retriever

One of the most common places where deductive retrieval
behaves differently than logic is when `(NOT `

is implemented as "true if and only if *p*)*p* can not
be proved." While this works as expected in many cases,
consider these rules for
a blocks world robot arm.

(<- (can-move ?x) (block ?x) (clear ?x)) (<- (clear ?x) (not (on ?y ?x))) (block a) (block b) (block c) (on b a)

The first rule says "you can move a block if it is clear." The second rule says that something is clear if nothing is on it. The remaining assertions describe a scene with blocks A, B, and C, where block B is stacked on block A.

Here's what the deductive retriever returns for the following queries.

Query | Results |
---|---|

(clear a) | NIL |

(clear b) | ((CLEAR B)) |

(clear c) | ((CLEAR C)) |

(can-move a) | NIL |

(can-move b) | ((CAN-MOVE B)) |

(can-move c) | ((CAN-MOVE C)) |

(can-move ?x) | ((CAN-MOVE B) (CAN-MOVE C)) |

(clear ?x) | NIL |

Everything is just what you expect until the last row. Even though the retriever can respond correctly to "what blocks can I move?" it can't respond correctly to "what blocks are clear?" Why the difference?

The query `(clear ?x)`

leads to the query
`(not (on ?y ?x))`

.
`(on ?y ?x)`

returns `((ON B A))`

,
so `(not (on ?y ?x))`

query fails.

In contrast, the query `(can-move ?x)`

leads
to the query `(block ?x)`

, which has three answers, A, B,
and C. This leads to the queries
`(not (on ?y A))`

, `(not (on ?y B))`

,
and `(not (on ?y C))`

. The queries
`(on ?y B)`

,
and `(on ?y C)`

fail, so the corresponding `not`

queries succeed and hence the `can-move`

succeeds for those cases.

We can fix this specific problem by changing the second rule to

(<- (clear ?x) (block ?x) (not (on ?y ?x)))

We will need a version of this rule for every kind of shape we want to use.

The failure to prove `(clear ?x)`

with the original
version of the rule is not
a bug in the code, but a fundamental limitation in what Horn clause
logic can represent.
The query `(clear ?x)`

logically asks "∃x clear(x)"
which, in the original form of the rule, asks "∃x ¬∃y on(y, x)."
Now we're in trouble. In logic, "∃x ¬∃y on(y, x)"
is equivalent to "∃x ∀y ¬on(y, x)," i.e.,
"is there an x such that for all possible y, on(y, x) is not true?"
But Horn clause logic doesn't support universal queries,
only existential ones.

## Implementing deductive retrieval

### Backtracking

Assume we've loaded the
assertions in `*tiger-kb*`

in
ddr-tests.lisp.

> (load "ddr-tests.lisp") ... > (in-package :ddr-tests) ... > (init-kb *tiger-kb*) ...

Now, let's ask how our tiger can satisfy its hunger:

> (ask '(can-satisfy-hunger-with tiger ?x))

The retriever will find that it has to choose something
the tiger eats. To do that, it has to choose something a tiger is a
predator of. Suppose it picks `zebra`

. Now, the
retriever will ask `(near tiger zebra)`

. This query will
fail, because there is no zebra in the same place as the tiger.

The fact that this query has failed doesn't mean that the
tiger can't eat something. It means that the retriever has to
"back up" and look for another answer to ```
(predator-of tiger
...)
```

. The other possible answer is `antelope`

.
This leads to the query `(near tiger antelope)`

which eventually succeeds.

The backing up process, undoing one possible match when it
doesn't pan out, is called *backtracking*. It's one of the
classic *weak* methods of AI, so called because it always
works, even when the system is knowledge poor, but it may not
work very efficiently. Basically, backtracking means writing your
code to try all possibilities, because your code isn't smart
enough to know the right thing to do.

### Arithmetic in logic

Implementing a backward chaining deductive retriever takes surprisingly little code, if we don't worry about efficiency. sddr.lisp is 80 lines of actual code. Only about half of that is for backward chaining. The rest is for unification.

Even more surprising is that such a small system is capable not only of retrieving implied logical facts, such as "Socrates is mortal", but of actually constructing new results.

The secret is functional terms. Consider the following two rules, from sddr-tests.lisp.

(defparameter *peano-kb* '( (<- (add 0 ?x ?x)) (<- (add (succ ?x) ?y (succ ?z)) (add ?x ?y ?z)) ))

The first rule is an unconditional assertion that the `(add `

is always true if *x y z*)*x* is 0, and *y* and *z* are the same.

The second rule is more easily understood in the forward direction:
if `(a `

is true, then
*x y z*)`(a (succ `

is also true.
*x*) *y* (succ *z*)

What these are are rules for addition, where 0 is 0, and
`(succc `

means "the successor number of *x*)*x*", i.e., x + 1.
So the first rule says "0 + x = x", and the second rule says
"if x + y = z, then (x + 1) + y = (z + 1)".

All of which seems true, but pointless. What can we do with this? A lot, it turns out.

We can verify addition, e.g., that 2 + 3 = 5.

(ask '(add (s (s (s 0)) (s (s (s 0))) (s (s (s (s (s (s 0)))))))) *peano-kb*)

This will succeed for valid sums and fail for others. But we can also ask the retriever,
*with no additional machinery*, to calculate the sum for us.

(ask '(add (s (s (s 0)) (s (s (s 0))) ?sum)) *peano-kb*)

This will return one answer, where `?sum`

is 5, written with successor terms.

We can actually use this to solve any simple addition, e.g., "x + 4 = 5".

(ask '(add ?x (s (s (s 0))) (s (s (s (s (s (s 0)))))))) *peano-kb*)

We can even ask for all solutions to "x + y = 5".

(ask '(add ?x ?y (s (s (s (s (s (s 0)))))))) *peano-kb*)

To understand how this works, it helps to hand-execute a simple query, such as "1 + 1 = x",
to see how just unification and backward chaining will eventually
bind `?x`

to `(succ (succ 0))`

.

### Append and cons in logic

Clearly, we would not want to really implement arithmetic in logic. But almost exactly the same kind of rules can be used to implement concepts in Lisp, and that is a reasonable thing to do.

(defparameter *append-kb* '( (<- (append nil ?x ?x)) (<- (append (cons ?x ?l1) ?l2 (cons ?x ?l3)) (append ?l1 ?l2 ?l3)) ))

The predicate `(append x y z)`

says "x appended to y is z". The
functional term `(cons x y)`

represents a CONS pair (not the CONS function!).
For example, the functional term `(cons 1 (cons 2 nil))`

represents
the list (1 2). We use the constant `nil`

for the empty list, for our convenience.
To the deductive retriever, it's just another symbol. We could use `empty`

or
`nothing`

,
or whatever we want.

The first rule says "nil appended to any list is the same list". This is like saying zero plus a number is the number.

The second rule, read forward, says "if l1 appended to l2 is l3, then the list (cons x l1) appended to l2 is the list (cons x l3)". As with addition, the rules seem to be true, but what can we do with them?

Well, we can append. Here we ask what we get if we append (1 2) with (3 4).

(ask '(append (cons 1 (cons 2 nil)) (cons 3 (cons 4 nil)) ?lst) *append-kb*)

This will return `(cons 1 (cons 2 (cons 3 (cons 4 nil))))`

for `?lst`

.

But we can also ask for solutions to problems such as "what appended to (1 2) would give (1 2 3 4)".

(ask '(append (cons 1 (cons 2 nil)) ?lst (cons 1 (cons 2 (cons 3 (cons 4 nil))))) *append-kb*)

We can even ask for all the ways to split the list (1 2 3 4).

(ask '(append ?head ?tail (cons 1 (cons 2 (cons 3 (cons 4 nil))))) *append-kb*)

Unlike arithmetic, this is gives our logic engine a very general tool for handling data.
First, it can construct lists. Second, we can write backchaining rules that
"loop over a list" by defining rules so that `(member `

is true if *x lst*)*x* is an element of a list *lst* represented with CONS functional terms.
This is in fact what Prolog does.

Now that we have a way to construct and map over lists, we can do things like planning using deduction.

### Extensions

Many predicates are very difficult or inefficient to do with
logical rules. For example, `(< `

should
return true if *x y*)`x`

is less than `y`

, but try
defining this with pure logic. It can be done, but you have to
axomiatize arithmetic first.

On the other hand, our retriever is running on top of Lisp,
and it's trivial to tell if `x`

is less than `y`

in
Lisp. So, why not allow our retriever to call Lisp functions?

We do this in our retriever by defining *retrieval
methods*. A retrieval method for a predicate `P`

is
basically a function to call when the retriever sees anything of
the form `(P ...)`

. Retrieval methods are defined
using

(define-retrieval-methodname(var)body)

is the name of the predicate for which the method is being
defined, e.g., *name*`<`

.

will be bound
to the pattern beginning with that predicate, that the retriever
has come across.*var*

The retrieval method has to be prepared for variables in its
arguments. For example, if `(< ?x ?y)`

appears in a
rule, then `?x`

and `?y`

will be replaced by their
bindings, if any, but any unbound variable will still be in the
pattern passed to the retrieval method.

In the case of `<`

, we'll assume that it's OK to
simply fail if there are any unbound, or otherwise non-numeric,
arguments.

(define-retrieval-method < (pat) (destructuring-bind (x y) (pattern-args pat) (and (numberp x) (numberp y) (< x y) (make-empty-bindings)))

A retrieval method should always return a list of bindings
lists, or `NIL`

, so that the predicate will act like every
other predicate in the system.