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 ![[*]](../image/cross_ref_motif.gif)
, 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 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.
![[*]](../image/foot_motif.gif)
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 :
(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 appends 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 . 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.