4.69 Exercise 4.69

This problem is trickier than it appears. At its most basic level, it’s clear that the answer involves recursively unwrapping lists of the form (great great ... grandson), using each appearance of great to descend another son relationship and verify that the rest of the relationship list holds for the son and the original descendant of the relationship.

The first trick is provided: You have to make sure that the relationship you are modifying with great can actually be modified in the first place. Hence the book’s recommendation of a rule that determines whether a list ends with "grandson".

With all of this in mind, you might expect to be able to write something like this:

(rule ((great . ?rel) ?x ?desc)

(and (son ?x ?y)

(?rel ?y ?desc)

(ends-with-grandson ?rel)))

However, there is a subtle problem with this: if ?rel is a ending with grandson, then we will eventually attempt to verify an expression like ((grandson) Adam Enoch), which will not match. What could be generated and pass the (?rel ?y ?desc) condition is an atomic value from an improper list, such as (great . grandson). If you allow the list to be improper, you could get all of the correct relationships out, but I would prefer to state the rules cleanly.

There is also a subtle danger that the previous example avoids. It seems important to evaluate conditions such as ends-with-grandson after using other rules to generate relationships. In my experience, trying to evaluate these structural rules earlier will result in matches not being produced if you try to generate the relationship itself, e.g. with (?rel Adam ?x).

I’d also like to point out a potential problem that we could exacerbate by trying to fix the rule above. Suppose we wrote a matching rule more like this:

(and (equal ?rel (grandson))

(grandson ?y ?desc))

Something like this could allow you to extract the only element of a list and verify that the relationship holds. But consider what happens if we try to add daughters to our relationship graph. This rule will no longer work, because it only allows you to find grandsons, and not granddaughters. The suggestion to verify that a list ends with grandson can be taken a bit too literally. Instead, we want a rule to determine whether a relationship is modifiable by "great":

(rule (great-modifiable grandson))

You could add another case to allow granddaughter to be great-modifiable as well later on. And if you use this when you define the rule for matching on great- relationships, you don’t need to modify a more complex existing rule in the face of new data.

With all that stated, these are the rules I came up with that match these relationships correctly, and that seem to be correct for arbitrary queries:

(assert! (rule (great-modifiable grandson)))

(assert! (rule (nil ())))

(assert! (rule ((great    ?r . ?rs)  ?x ?desc)

(and (son ?x ?y)

(or (and (?r ?y ?desc)

(great-modifiable ?r)

(nil ?rs))

(and ((?r . ?rs) ?y ?desc)

(not (nil ?rs)))))))

Here are some of the queries that work successfully:

I don’t think I have the cleanest expression of the rule, but I’m reasonably confident that it’s correct. And it avoids repeatedly checking that lists end with grandson (or what have you) at every level of recursion, which seems to me like an inelegance caused by an improperly-expressed rule.