Abbott%AEROSPACE@sri-unix.UUCP (11/04/83)
From: Abbott at AEROSPACE (Russ Abbott)
I'd like to suggest a notion that many readers of this Digest
may consider heresy, namely that Prolog is not the ultimate
programming language. And I'd like to open a discussion on
the following subject (if I'm not stoned for making the
suggestion): How can an algorithmic capability be included
cleanly in Prolog ?
As prolog (pardon) let me say that I've been very impressed
with the way that Prolog *is* able to accommodate certain
programming paradigms:
- concurrency (in certain senses), types (in certain
senses),
- object-oriented-ness (in certain senses), etc. I see
Prolog as in the process of developing a programming
style that suits its capabilities. I'm excited and
pleased with the process. I expect that this process
will probably go on for several years while Prolog
either annexes or rejects various modern programming
notions.
My problem is more fundamental. Prolog is not an algorithmic
language: that is supposed to be one its strengths. Yet in
programming computers it seems that one cannot avoid algorithms
--in the sense of step-by-step sequences of actions that one
wants to have occur. Even Prolog programs include algorithms.
I challenge any Prolog programmer to claim that he has never
written an algoritm in Prolog. Currently one writes algorithms
in Prolog by making use of the algorithm by which Prolog itself
attempts to satisfy goals. By riding on the coat tails of that
algorithms one can compute anything computable. But doing so
often obscures what one wants rather than clarifies it.
Algorithms appear most often in those Prolog program that include
Prolog predicates with side effects, I.e., the "impurities" in
Prolog, such as read, write, assert, etc. I claim that we will
never get rid of these impurities. It seems to me that, like
it or not:
(1) any program that is to be of much use in the world has
to have I/O, and
(2) any program that is not simply a function (and very few
programs of any real use are) has to have a way of changing
its behavior on the basis of past inputs. That is,
programs must have a "database" capability of some sort,
and that means assert or the equivalent.
Another argument for adding an algorithmic capability may be
built on the nature of Prolog as a "passive" language. In
"pure" Prolog one cannot define a "process," I.e., something
that continues to operate in time. At its heart Prolog lets
one create a static body of information that may be queried.
It does not provide means to define an ongoing process that
continues in operation indefinitely, doing whatever it is
supposed to do. Yet many programs do have that form.
The Prolog interpreter itself is of this form. Once started,
it's an ongoing process that is always interacting with the
user at the terminal. It makes no (predicate-logical) sense
to write the top level of the Prolog interpreter as a Prolog
predicate. Even if one could make the following work as an
interactive program (E.g., by making Input and Output special
variable names, for example), I'm not happy with:
interpret([Input | Inputs], [Output | Outputs]) :-
process(Input, Output),
interpret(Inputs, Outputs).
Since asserts performed for one input may affect how later inputs
are processed, this forces asserts in the middle of interpret to
affect the same call to interpret--since there is only one call
to interpret. More generally, it imples (incorrectly) that all
the inputs exist at once. It ignores the element of time completely.
Why should one have to live with this fiction ?
Nor am I happy with the other approach:
interpret :-
read(Term),
process(Term),
interpret.
or
interpret :-
repeat,
read(Term),
process(Term), % process has a cut at the end.
fail.
These are both the "coat tail" approach, using Prolog's underlying
satisfaction algorithm for a purpose for which it wasn't "intended."
In addition the first version stacks wasted return pointers for no
good reason. (I know that tail recursion can be optimized away, but
that isn't the point.) The second is even worse conceptually; it has
little if anything to do with Prolog as a logic language. Both of
these also suffer from the problem mentioned above--asserts within
a call to interpret affect later processing of the same call (since
there is only one call to interpret).
The problem may be summarized: predicate calculus is a language of
static facts; algorithms express sequences of operations in time.
Prolog implements predicate calculus; most useful programs operate
in time.
So given all that what am I asking ? I'm suggesting that Prolog
needs to be wedded cleanly to some way to express algorithms--rather
than to continue to use the coat tail approach to writing algorithms
in Prolog. I'd like to open a discussion on how best to do that.
I think that a side benefit of such a successful wedding will be
that most, if not all, of the "impurities" in current Prolog can
be moved to the algorithm side--where they will not be impurities.
The extended Prolog will thus be both cleaner and more useful.
I am now heading for my bomb shelter to await replies.
-- Russ Abbott