Structure and Interpretation of Computer Programs (82 page)

In chapter 1 we stressed that computer science deals with imperative
(how to) knowledge, whereas mathematics deals with declarative (what
is) knowledge. Indeed, programming languages require that the
programmer express knowledge in a form that indicates the step-by-step
methods for solving particular problems. On the other hand,
high-level languages provide, as part of the language implementation,
a substantial amount of methodological knowledge that frees
the user from concern with numerous details of how a specified
computation will progress.

Most programming languages, including Lisp, are organized around
computing the values of mathematical functions. Expression-oriented
languages (such as Lisp, Fortran, and Algol) capitalize on the “pun”
that an expression that describes the value of a function may also be
interpreted as a means of computing that value. Because of this, most
programming languages are strongly biased toward unidirectional
computations (computations with well-defined inputs and outputs).
There are, however, radically different programming languages that
relax this bias. We saw one such example in
section 
3.3.5
, where the objects of computation were
arithmetic constraints. In a constraint system the direction and the
order of computation are not so well specified; in carrying out a
computation the system must therefore provide more detailed “how to”
knowledge than would be the case with an ordinary arithmetic
computation. This does not mean, however, that the user is released
altogether from the responsibility of providing imperative knowledge.
There are many constraint networks that implement the same set of
constraints, and the user must choose from the set of mathematically
equivalent networks a suitable network to specify a particular
computation.

The nondeterministic program evaluator of
section 
4.3
also moves away from the
view that programming is about constructing algorithms for computing
unidirectional functions. In a nondeterministic language, expressions
can have more than one value, and, as a result, the computation is
dealing with relations rather than with
single-valued functions. Logic programming extends this idea by
combining a relational vision of programming with a powerful kind of
symbolic pattern matching called
unification
.
⁵⁸

This approach, when it works, can be a very powerful way to write
programs. Part of the power comes from the fact that a single “what
is” fact can be used to solve a number of different problems that
would have different “how to” components. As an example, consider
the
append
operation, which takes two lists as arguments and
combines their elements to form a single list. In a procedural
language such as Lisp, we could define
append
in terms of the
basic list constructor
cons
, as we did in
section 
2.2.1
:

(define (append x y)
  (if (null? x)
      y
      (cons (car x) (append (cdr x) y))))

This procedure can be regarded as a translation into Lisp of the
following two rules, the first of which covers the case where the
first list is empty and the second of which handles the case of a
nonempty list, which is a
cons
of two parts:

• For any list
  y
  , the empty list and
  y
  append
  to form
  y
  .
  
• For any
  u
  ,
  v
  ,
  y
  , and
  z
  ,
  (cons u v)
  and
  y
  append
  to form
  (cons u z)
  if
  v
  and
  y
  append
  to form
  z
  .
  ⁵⁹
  

Using the
append
procedure, we can answer questions such as

Find the
append
of
(a b)
and
(c d)
.

But the same two rules are also sufficient for answering the following
sorts of questions, which the procedure can't answer:

Find a list
y
that
append
s with
(a b)
to produce
(a b c d)
.

Find all
x
and
y
that
append
to form
(a b c
d)
.

In a logic programming language, the programmer writes an
append
“procedure” by stating the two rules about
append
given above.
“How to” knowledge is provided automatically by the interpreter to
allow this single pair of rules to be used to answer all three types
of questions about
append
.
⁶⁰

Contemporary logic programming languages (including the one we
implement here) have substantial deficiencies, in that their general
“how to” methods can lead them into spurious infinite loops or other
undesirable behavior.
Logic programming is an active field of research in computer science.
⁶¹

Earlier in this chapter we explored the technology of implementing
interpreters and described the elements that are essential to an
interpreter for a Lisp-like language (indeed, to an interpreter for
any conventional language). Now we will apply these ideas to discuss
an interpreter for a logic programming language. We call this
language the
query language
, because it is very useful for
retrieving information from data bases by formulating
queries
,
or questions, expressed in the language. Even though the query
language is very different from Lisp, we will find it convenient to
describe the language in terms of the same general framework we have
been using all along: as a collection of primitive elements, together
with means of combination that enable us to combine simple elements to
create more complex elements and means of abstraction that enable us
to regard complex elements as single conceptual units. An interpreter
for a logic programming language is considerably more complex than an
interpreter for a language like Lisp. Nevertheless, we will see
that our query-language interpreter contains many of the same elements
found in the interpreter of section 
4.1
. In particular,
there will be an “eval” part that classifies expressions according
to type and an “apply” part that implements the language's
abstraction mechanism (procedures in the case of Lisp, and
rules
in the case of logic programming). Also, a central role is played in
the implementation by a frame data structure, which determines the
correspondence between symbols and their associated values. One
additional interesting aspect of our query-language implementation is
that we make substantial use of streams, which were introduced in
chapter 3.

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
Microshaft, 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.

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

(address (Bitdiddle Ben) (Slumerville (Ridge Road) 10))
(job (Bitdiddle Ben) (computer wizard))
(salary (Bitdiddle Ben) 60000)

Each assertion is a list (in this case a triple) whose elements can
themselves be lists.

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 (Hacker Alyssa P) (Cambridge (Mass Ave) 78))
(job (Hacker Alyssa P) (computer programmer))
(salary (Hacker Alyssa P) 40000)
(supervisor (Hacker Alyssa P) (Bitdiddle Ben))
(address (Fect Cy D) (Cambridge (Ames Street) 3))
(job (Fect Cy D) (computer programmer))
(salary (Fect Cy D) 35000)
(supervisor (Fect Cy D) (Bitdiddle Ben))
(address (Tweakit Lem E) (Boston (Bay State Road) 22))
(job (Tweakit Lem E) (computer technician))
(salary (Tweakit Lem E) 25000)
(supervisor (Tweakit Lem E) (Bitdiddle Ben))

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

(address (Reasoner Louis) (Slumerville (Pine Tree Road) 80))
(job (Reasoner Louis) (computer programmer trainee))
(salary (Reasoner Louis) 30000)
(supervisor (Reasoner Louis) (Hacker Alyssa P))

All of 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 (Bitdiddle Ben) (Warbucks Oliver))
(address (Warbucks Oliver) (Swellesley (Top Heap Road)))
(job (Warbucks Oliver) (administration big wheel))
(salary (Warbucks Oliver) 150000)

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

(address (Scrooge Eben) (Weston (Shady Lane) 10))
(job (Scrooge Eben) (accounting chief accountant))
(salary (Scrooge Eben) 75000)
(supervisor (Scrooge Eben) (Warbucks Oliver))
(address (Cratchet Robert) (Allston (N Harvard Street) 16))
(job (Cratchet Robert) (accounting scrivener))
(salary (Cratchet Robert) 18000)
(supervisor (Cratchet Robert) (Scrooge Eben))

There is also a secretary for the big wheel:

(address (Aull DeWitt) (Slumerville (Onion Square) 5))
(job (Aull DeWitt) (administration secretary))
(salary (Aull DeWitt) 25000)
(supervisor (Aull DeWitt) (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 (computer wizard) (computer programmer))
(can-do-job (computer wizard) (computer technician))

A computer programmer could fill in for a trainee:

(can-do-job (computer programmer)
            (computer programmer trainee))

Also, as is well known,

(can-do-job (administration secretary)
            (administration big wheel))

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 (computer programmer))

The system will respond with the following items:

;;; Query results:
(job (Hacker Alyssa P) (computer programmer))
(job (Fect Cy D) (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 entries consisting of three items, of which the first is the
literal symbol
job
, the second can be anything, and the third is
the literal list
(computer programmer)
. The “anything” that
can be the second item in the matching list is specified by a
pattern variable
,
?x
. The general form of a pattern variable
is a symbol, taken to be the name of the variable, preceded by a
question mark. We will see below why it is useful to specify names
for pattern variables rather than just putting
?
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 (computer ?type))

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

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

This same pattern does
not
match

(job (Reasoner Louis) (computer programmer trainee))

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

(job ?x (computer . ?type))

For example,

(computer . ?type)

matches the data

(computer programmer trainee)

with
?type
as the list
(programmer trainee)
. It also
matches the data