4.4.1 Deductive Information Retrieval - SICP Comparison Edition

Logic programming excels in providing interfaces to data bases for information retrieval. The query language we shall implement in this chapter is designed to be used in this way.

In order to illustrate what the query system does, we will show how it can be used to manage the data base of personnel records for Gargle, a thriving high-technology company in the Boston area. The language provides pattern-directed access to personnel information and can also take advantage of general rules in order to make logical deductions.

A sample data base

The personnel data base for Gargle contains assertions about company personnel. Here is the information about Ben Bitdiddle, the resident computer wizard:

address(list("Bitdiddle", "Ben"),
        list("Slumerville", list("Ridge", "Road"), 10))
job(list("Bitdiddle", "Ben"), list("computer", "wizard"))
salary(list("Bitdiddle", "Ben"), 122000)

Assertions look just like function applications in JavaScript, but they actually represent information in the data base. The first symbols—here address, job and salary—describe the kind of information contained in the respective assertion, and the arguments are lists or primitive values such as strings and numbers. The first symbols do not need to be declared, as do constants or variables in JavaScript; their scope is global.

As resident wizard, Ben is in charge of the company's computer division, and he supervises two programmers and one technician. Here is the information about them:

address(list("Hacker", "Alyssa", "P"), 
        list("Cambridge", list("Mass", "Ave"), 78))
job(list("Hacker", "Alyssa", "P"), list("computer", "programmer"))
salary(list("Hacker", "Alyssa", "P"), 81000)
supervisor(list("Hacker", "Alyssa", "P"), list("Bitdiddle", "Ben"))

address(list("Fect", "Cy", "D"), 
        list("Cambridge", list("Ames", "Street"), 3))
job(list("Fect", "Cy", "D"), list("computer", "programmer"))
salary(list("Fect", "Cy", "D"), 70000)
supervisor(list("Fect", "Cy", "D"), list("Bitdiddle", "Ben"))

address(list("Tweakit", "Lem", "E"), 
        list("Boston", list("Bay", "State", "Road"), 22))
job(list("Tweakit", "Lem", "E"), list("computer", "technician"))
salary(list("Tweakit", "Lem", "E"), 51000)
supervisor(list("Tweakit", "Lem", "E"), list("Bitdiddle", "Ben"))

There is also a programmer trainee, who is supervised by Alyssa:

address(list("Reasoner", "Louis"), 
        list("Slumerville", list("Pine", "Tree", "Road"), 80))
job(list("Reasoner", "Louis"), 
         list("computer", "programmer", "trainee"))
salary(list("Reasoner", "Louis"), 62000)
supervisor(list("Reasoner", "Louis"), list("Hacker", "Alyssa", "P"))

All these people are in the computer division, as indicated by the word "computer" as the first item in their job descriptions.

Ben is a high-level employee. His supervisor is the company's big wheel himself:

supervisor(list("Bitdiddle", "Ben"), list("Warbucks", "Oliver"))

address(list("Warbucks", "Oliver"), 
        list("Swellesley", list("Top", "Heap", "Road")))
job(list("Warbucks", "Oliver"), list("administration", "big", "wheel"))
salary(list("Warbucks", "Oliver"), 314159)

Besides the computer division supervised by Ben, the company has an accounting division, consisting of a chief accountant and his assistant:

address(list("Scrooge", "Eben"),
        list("Weston", list("Shady", "Lane"), 10))
job(list("Scrooge", "Eben"), list("accounting", "chief", "accountant"))
salary(list("Scrooge", "Eben"), 141421)
supervisor(list("Scrooge", "Eben"), list("Warbucks", "Oliver"))

address(list("Cratchit", "Robert"), 
        list("Allston", list("N", "Harvard", "Street"), 16))
job(list("Cratchit", "Robert"), list("accounting", "scrivener"))
salary(list("Cratchit", "Robert"), 26100)
supervisor(list("Cratchit", "Robert"), list("Scrooge", "Eben"))

There is also an administrative assistant for the big wheel:

address(list("Aull", "DeWitt"), 
        list("Slumerville", list("Onion", "Square"), 5))
job(list("Aull", "DeWitt"), list("administration", "assistant"))
salary(list("Aull", "DeWitt"), 42195)
supervisor(list("Aull", "DeWitt"), list("Warbucks", "Oliver"))

The data base also contains assertions about which kinds of jobs can be done by people holding other kinds of jobs. For instance, a computer wizard can do the jobs of both a computer programmer and a computer technician:

can_do_job(list("computer", "wizard"), 
           list("computer", "programmer"))
can_do_job(list("computer", "wizard"), 
           list("computer", "technician"))

A computer programmer could fill in for a trainee:

can_do_job(list("computer", "programmer"),
           list("computer", "programmer", "trainee"))

Also, as is well known,

can_do_job(list("administration", "assistant"),
           list("administration", "big", "wheel"))

Simple queries

The query language allows users to retrieve information from the data base by posing queries in response to the system's prompt. For example, to find all computer programmers one can say

Query input:

job($x, list("computer", "programmer"))

The system will respond with the following items:

Query results:
job(list("Hacker", "Alyssa", "P"), list("computer", "programmer"))
job(list("Fect", "Cy", "D"), list("computer", "programmer"))

The input query specifies that we are looking for entries in the data base that match a certain pattern. In this example, the pattern specifies job as the kind of information that we are looking for. The first item can be anything, and the second is the literal list list("computer", "programmer"). The anything that can be the first item in the matching assertion is specified by a pattern variable, $x. As pattern variables, we use JavaScript names that start with a dollar sign. We will see below why it is useful to specify names for pattern variables rather than just putting a single symbol such as $ into patterns to represent anything. The system responds to a simple query by showing all entries in the data base that match the specified pattern.

A pattern can have more than one variable. For example, the query

address($x, $y)

will list all the employees' addresses.

A pattern can have no variables, in which case the query simply determines whether that pattern is an entry in the data base. If so, there will be one match; if not, there will be no matches.

The same pattern variable can appear more than once in a query, specifying that the same anything must appear in each position. This is why variables have names. For example,

supervisor($x, $x)

finds all people who supervise themselves (though there are no such assertions in our sample data base).

The query

job($x, list("computer", $type))

matches all job entries whose second item is a two-element list whose first item is "computer":

job(list("Bitdiddle", "Ben"), list("computer", "wizard"))
job(list("Hacker", "Alyssa", "P"), list("computer", "programmer"))
job(list("Fect", "Cy", "D"), list("computer", "programmer"))
job(list("Tweakit", "Lem", "E"), list("computer", "technician"))

This same pattern does not match

job(list("Reasoner", "Louis"),
    list("computer", "programmer", "trainee"))

because the second item in the assertion is a list of three elements, and the pattern's second item specifies that there should be two elements. If we wanted to change the pattern so that the second item could be any list beginning with "computer", we could specify

job($x, pair("computer", $type))

For example,

pair("computer", $type)

matches the data

list("computer", "programmer", "trainee")

with $type as list("programmer", "trainee"). It also matches the data

list("computer", "programmer")

with $type as list("programmer"), and matches the data

list("computer")

with $type as the empty list, null.

We can describe the query language's processing of simple queries as follows:

The system finds all assignments to variables in the query pattern that satisfy the pattern—that is, all sets of values for the variables such that if the pattern variables are instantiated with (replaced by) the values, the result is in the data base.
The system responds to the query by listing all instantiations of the query pattern with the variable assignments that satisfy it.

Note that if the pattern has no variables, the query reduces to a determination of whether that pattern is in the data base. If so, the empty assignment, which assigns no values to variables, satisfies that pattern for that data base.

Exercise 4.53 Give simple queries that retrieve the following information from the data base:

all people supervised by Ben Bitdiddle;
the names and jobs of all people in the accounting division;
the names and addresses of all people who live in Slumerville.

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Compound queries

Simple queries form the primitive operations of the query language. In order to form compound operations, the query language provides means of combination. One thing that makes the query language a logic programming language is that the means of combination mirror the means of combination used in forming logical expressions: and, or, and not.

We can use and as follows to find the addresses of all the computer programmers:

and(job($person, list("computer", "programmer")),
    address($person, $where))

The resulting output is

and(job(list("Hacker", "Alyssa", "P"), list("computer", "programmer")),
    address(list("Hacker", "Alyssa", "P"), 
            list("Cambridge", list("Mass", "Ave"), 78)))

and(job(list("Fect", "Cy", "D"), list("computer", "programmer")),
    address(list("Fect", "Cy", "D"), 
            list("Cambridge", list("Ames", "Street"), 3)))

In general, and($query$$_{1}$, $query$$_{2}$, $\ldots$, $query$$_{n})$ is satisfied by all sets of values for the pattern variables that simultaneously satisfy $query$$_{1}, \ldots,$ $query$$_{n}$.

As for simple queries, the system processes a compound query by finding all assignments to the pattern variables that satisfy the query, then displaying instantiations of the query with those values.

Another means of constructing compound queries is through or. For example,

or(supervisor($x, list("Bitdiddle", "Ben")),
   supervisor($x, list("Hacker", "Alyssa", "P")))

will find all employees supervised by Ben Bitdiddle or Alyssa P. Hacker:

or(supervisor(list("Hacker", "Alyssa", "P"), 
              list("Bitdiddle", "Ben")),
   supervisor(list("Hacker", "Alyssa", "P"),
              list("Hacker", "Alyssa", "P")))

or(supervisor(list("Fect", "Cy", "D"), 
              list("Bitdiddle", "Ben")),
   supervisor(list("Fect", "Cy", "D"), 
              list("Hacker", "Alyssa", "P")))
   
or(supervisor(list("Tweakit", "Lem", "E"), 
              list("Bitdiddle", "Ben")),
   supervisor(list("Tweakit", "Lem", "E"), 
              list("Hacker", "Alyssa", "P")))

or(supervisor(list("Reasoner", "Louis"),
              list("Bitdiddle", "Ben")),
   supervisor(list("Reasoner", "Louis"), 
              list("Hacker", "Alyssa", "P")))

In general, or($query$$_{1}$, $query$$_{2}$, $\ldots$, $query$$_{n}$) is satisfied by all sets of values for the pattern variables that satisfy at least one of $query$$_{1} \ldots$ $query$$_{n}$.

Compound queries can also be formed with not. For example,

and(supervisor($x, list("Bitdiddle", "Ben")),
    not(job($x, list("computer", "programmer"))))

finds all people supervised by Ben Bitdiddle who are not computer programmers. In general, not($query$$_{1}$) is satisfied by all assignments to the pattern variables that do not satisfy $query$$_{1}$.[1]

The final combining form starts with javascript_predicate and contains a JavaScript predicate. In general, javascript_predicate($predicate$) will be satisfied by assignments to the pattern variables in the $predicate$ for which the instantiated $predicate$ is true. For example, to find all people whose salary is greater than $50,000 we could write[2]

and(salary($person, $amount), javascript_predicate($amount > 50000))

Exercise 4.54 Formulate compound queries that retrieve the following information:

the names of all people who are supervised by Ben Bitdiddle, together with their addresses;
all people whose salary is less than Ben Bitdiddle's, together with their salary and Ben Bitdiddle's salary;
all people who are supervised by someone who is not in the computer division, together with the supervisor's name and job.

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Rules

In addition to primitive queries and compound queries, the query language provides means for abstracting queries. These are given by rules. The rule

rule(lives_near($person_1, $person_2),
     and(address($person_1, pair($town, $rest_1)),
         address($person_2, pair($town, $rest_2)),
         not(same($person_1, $person_2))))

specifies that two people live near each other if they live in the same town. The final not clause prevents the rule from saying that all people live near themselves. The same relation is defined by a very simple rule:[3]

rule(same($x, $x))

The following rule declares that a person is a wheel in an organization if he supervises someone who is in turn a supervisor:

rule(wheel($person),
     and(supervisor($middle_manager, $person),
         supervisor($x, $middle_manager)))

The general form of a rule is rule($conclusion$, $body$) where $conclusion$ is a pattern and $body$ is any query.[4] We can think of a rule as representing a large (even infinite) set of assertions, namely all instantiations of the rule conclusion with variable assignments that satisfy the rule body. When we described simple queries (patterns), we said that an assignment to variables satisfies a pattern if the instantiated pattern is in the data base. But the pattern needn't be explicitly in the data base as an assertion. It can be an implicit assertion implied by a rule. For example, the query

lives_near($x, list("Bitdiddle", "Ben"))

results in

lives_near(list("Reasoner", "Louis"), list("Bitdiddle", "Ben"))
lives_near(list("Aull", "DeWitt"), list("Bitdiddle", "Ben"))

To find all computer programmers who live near Ben Bitdiddle, we can ask

and(job($x, list("computer", "programmer")),
    lives_near($x, list("Bitdiddle", "Ben")))

As in the case of compound functions, rules can be used as parts of other rules (as we saw with the lives_near rule above) or even be defined recursively. For instance, the rule

rule(outranked_by($staff_person, $boss),
     or(supervisor($staff_person, $boss),
        and(supervisor($staff_person, $middle_manager),
            outranked_by($middle_manager, $boss))))

says that a staff person is outranked by a boss in the organization if the boss is the person's supervisor or (recursively) if the person's supervisor is outranked by the boss.

Exercise 4.55 Define a rule that says that person 1 can replace person 2 if either person 1 does the same job as person 2 or someone who does person 1's job can also do person 2's job, and if person 1 and person 2 are not the same person. Using your rule, give queries that find the following:

all people who can replace Cy D. Fect;
all people who can replace someone who is being paid more than they are, together with the two salaries.

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Exercise 4.56 Define a rule that says that a person is a big shot in a division if the person works in the division but does not have a supervisor who works in the division.

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Exercise 4.57 Ben Bitdiddle has missed one meeting too many. Fearing that his habit of forgetting meetings could cost him his job, Ben decides to do something about it. He adds all the weekly meetings of the firm to the Gargle data base by asserting the following:

meeting("accounting", list("Monday", "9am"))
meeting("administration", list("Monday", "10am"))
meeting("computer", list("Wednesday", "3pm"))
meeting("administration", list("Friday", "1pm"))

Each of the above assertions is for a meeting of an entire division. Ben also adds an entry for the company-wide meeting that spans all the divisions. All of the company's employees attend this meeting.

meeting("whole-company", list("Wednesday", "4pm"))

On Friday morning, Ben wants to query the data base for all the meetings that occur that day. What query should he use?
Alyssa P. Hacker is unimpressed. She thinks it would be much more useful to be able to ask for her meetings by specifying her name. So she designs a rule that says that a person's meetings include all "whole-company" meetings plus all meetings of that person's division. Fill in the body of Alyssa's rule. rule(meeting_time($\texttt{\$}$person, $\texttt{\$}$day_and_time), $rule$-$body$)
Alyssa arrives at work on Wednesday morning and wonders what meetings she has to attend that day. Having defined the above rule, what query should she make to find this out?

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Exercise 4.58 By giving the query

lives_near($person, list("Hacker", "Alyssa", "P"))

Alyssa P. Hacker is able to find people who live near her, with whom she can ride to work. On the other hand, when she tries to find all pairs of people who live near each other by querying

lives_near($person_1, $person_2)

she notices that each pair of people who live near each other is listed twice; for example,

lives_near(list("Hacker", "Alyssa", "P"), list("Fect", "Cy", "D"))
lives_near(list("Fect", "Cy", "D"), list("Hacker", "Alyssa", "P"))

Why does this happen? Is there a way to find a list of people who live near each other, in which each pair appears only once? Explain.

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Logic as programs

We can regard a rule as a kind of logical implication: If an assignment of values to pattern variables satisfies the body, then it satisfies the conclusion. Consequently, we can regard the query language as having the ability to perform logical deductions based upon the rules. As an example, consider the append operation described at the beginning of section 4.4. As we said, append can be characterized by the following two rules:

For any list y, the empty list and y append to form y.
For any u, v, y, and z, pair(u, v) and y append to form pair(u, z) if v and y append to form z.

To express this in our query language, we define two rules for a relation

append_to_form(x, y, z)

which we can interpret to mean x and y append to form z:

rule(append_to_form(null, $y, $y))

rule(append_to_form(pair($u, $v), $y, pair($u, $z)),
     append_to_form($v, $y, $z))

The first rule has no body, which means that the conclusion holds for any value of $y. Note how the second rule makes use of pair to name the head and tail of a list.

Given these two rules, we can formulate queries that compute the append of two lists:

Query input:

append_to_form(list("a", "b"), list("c", "d"), $z)

Query results:
append_to_form(list("a", "b"), list("c", "d"), list("a", "b", "c", "d"))

What is more striking, we can use the same rules to ask the question Which list, when appended to list("a", "b"), yields list("a", "b", "c", "d")? This is done as follows:

Query input:

append_to_form(list("a", "b"), $y, list("a", "b", "c", "d"))

Query results:
append_to_form(list("a", "b"), list("c", "d"), list("a", "b", "c", "d"))

We can ask for all pairs of lists that append to form list("a", "b", "c", "d"):

Query input:

append_to_form($x, $y, list("a", "b", "c", "d"))

Query results:
append_to_form(null, list("a", "b", "c", "d"), list("a", "b", "c", "d"))
append_to_form(list("a"), list("b", "c", "d"), list("a", "b", "c", "d"))
append_to_form(list("a", "b"), list("c", "d"), list("a", "b", "c", "d"))
append_to_form(list("a", "b", "c"), list("d"), list("a", "b", "c", "d"))
append_to_form(list("a", "b", "c", "d"), null, list("a", "b", "c", "d"))

The query system may seem to exhibit quite a bit of intelligence in using the rules to deduce the answers to the queries above. Actually, as we will see in the next section, the system is following a well-determined algorithm in unraveling the rules. Unfortunately, although the system works impressively in the append case, the general methods may break down in more complex cases, as we will see in section 4.4.3.

Exercise 4.59 The following rules implement a next_to_in relation that finds adjacent elements of a list:

rule(next_to_in($x, $y, pair($x, pair($y, $u))))

rule(next_to_in($x, $y, pair($v, $z)),
     next_to_in($x, $y, $z))

What will the response be to the following queries?

next_to_in($x, $y, list(1, list(2, 3), 4))

next_to_in($x, 1, list(2, 1, 3, 1))

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Exercise 4.60 Define rules to implement the last_pair operation of exercise 2.17, which returns a list containing the last element of a nonempty list. Check your rules on the following queries:

last_pair(list(3), $x)
last_pair(list(1, 2, 3), $x)
last_pair(list(2, $x), list(3))

Do your rules work correctly on queries such as last_pair($x, list(3))?

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Exercise 4.61 The following data base (see Genesis 4) traces the genealogy of the descendants of Ada back to Adam, by way of Cain:

son("Adam", "Cain")
son("Cain", "Enoch")
son("Enoch", "Irad")
son("Irad", "Mehujael")
son("Mehujael", "Methushael")
son("Methushael", "Lamech")
wife("Lamech", "Ada")
son("Ada", "Jabal")
son("Ada", "Jubal")

Formulate rules such as If S is the son of F, and F is the son of G, then S is the grandson of G and If W is the wife of M, and S is the son of W, then S is the son of M (which was supposedly more true in biblical times than today) that will enable the query system to find the grandson of Cain; the sons of Lamech; the grandsons of Methushael. (See exercise 4.67 for some rules to deduce more complicated relationships.)

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.