OKeefe.R.A.%EDXA@sri-unix.UUCP (11/07/83)
From: O'Keefe HPS (on ERCC DEC-10) <OKeefe.R.A. at EDXA>
Logic programs are just as much algorithms as assembly code. So
we should distinguish not between "algorithmic" and "pure", but
between "imperative" and "applicative" uses of Prolog. That aside, I
would like to agree with Russ Abbott. [How's that for a record ?]
There is no need for us to invent an imperative version of Prolog.
Dijkstra has already done it for us. We have only to add a few new
data structures.
There are two good reasons why most Prologs don't accept terms
like P(X...Z). The first is that it is not at all clear what they
mean. 'apply' is defined in the DEC-10 Prolog library as
apply(Pred, Args) :-
atom(Pred), !,
Goal =.. [Pred|Args],
call(Goal).
apply(Pred, Args) :-
Pred =.. List,
append(List, Args, Full),
Goal =.. Full,
call(Goal).
modulo details. The point of this is to give us partial application,
which is how we get the effect of higher-order functions without the
need for any other extensions to the language. [Re dictating to the
user: neither David Warren nor I said to the user "thou shalt not use
higher-order code". His paper pointed out "you've already got the
tools you need, go to it."] So we very often want P to have some of
its arguments already filled in. Since
apply(p, [a,b,c])
apply(p(a), [b,c])
apply(p(a,b), [c])
apply(p(a,b,c), [])
all have exactly the same effect (modulo calls to append), we would like
P1 = p, P1(a,b,c)
P2 = p(a), P2(b,c)
P3 = p(a,b), P3(c)
P4 = p(a,b,c) P4
to have the same effect. Since the terms in the right hand column are
all supposed to be the same goal, we would like them to unify. That's
not too hard to arrange for P1(a,b,c) and P4, but rather harder for
the others. Before anyone points out that p(a,b,c) and
apply(p,[a,b,c]) don't unify either, let me point out that
apply(p,[a,b,c]) makes no pretence of BEING the goal p(a,b,c), but
only claims to CALL it.
Still on logical difficulties, if P(X...Z) is accepted as a term,
one might expect to match it against something in order to bind P.
Again, we already have
P4 = p(a,b,c) working, and it wouldn't be too hard to make
P1(a,b,c) = p(a,b,c)
work. Indeed, you can tell Poplog that you want this to happen. But
P2 and P3 give you trouble. Restricting "predicate variables" to take
on atomic values only just will not do: my experience has been that I
have wanted to pass around a goal with some of its arguments filled in
much more often than I have wanted to pass a goal with none of its
arguments specified. For example, to add N to all the elements in a
list, one might write
... maplist(plus(N), L, Incremented), ...
Poplog permits P$[X,...,Z], and {SU-SCORE}PS:<Prolog>Read.Pl
permits P(X,...,Z) -- against my better judgement -- as notational
variants for apply(P, [X,...,Z]). The Poplog form, where $ is just an
infix 'apply', is a lot cleaner. Of course neither of these makes
much sense except as a goal, and when P is bound to 'p' P$[a,b,c]
claims to be the goal p$[a,b,c] not the goal p(a,b,c).
The second good reason is: how are such terms to be stored ?
Many Prologs use a very space-efficient scheme where f(X1,...,Xn) is
represented by n+1 consecutive pointers. The 1st .. nth pointers are
or point to the arguments, while the 0th pointer points to a "functor
block" representing f/n, so that there is no need to store the arity
with the term. This might be thought to lead to more page references,
but there is an obvious little trick to reduce the impact of that.
The representation used by Poplog is {X1 ... Xn f}, which turns out to
require at least two more words per term. Since most terms are fairly
short, this is a substantial overhead. Poplog represents Prolog lists
as Pop pairs which makes the space cost the same for both methods, but
the price is a time cost on *everything* that looks at terms, even
when they aren't lists. The Poplog system can however handle P4 as
well as P1. Prologs embedded in Lisp commonly represent Prolog terms
as lists. With CDR-coding, that is as efficient as Poplog.
Presumably LM-Prolog does this. If you lack CDR-coding, as
micro-PROLOG does, the result is that handling P(X...Z) as (P X ... Z)
is trivial, indeed it is almost inescapable, but that the space cost
is appalling.
Of course a mixed representation could be used, with most terms
being represented efficiently as <^f/n, X1, ..., Xn>, and P(X1..Xn)
terms being handled as '$$'(P,X1,...,Xn). We could arrange that if
unification of two compound terms failed, it would check for either or
both of the terms being '$$', and if so would flatten them, E.g.
'$$'(p(a,b),c) => p(a,b,c), and try again. We would also arrange to
have machine code definitions for all '$$'/N (whenever a clause is
asserted for F/N, ensure that $$/1 .. $$/N+1 are all defined) with the
effect of
'$$'(Pred, A1, ..., An) :-
call Pred with extra args A1 .. An.
where of course Pred might be another $$ term.
Now I would certainly agree that having a family of predicates
apply(p(X1,..,Xk), Xk+1, ..., Xn) :-
p(X1, ..., Xk, Xk+1, ..., Xn)
efficiently implemented in machine code so that all these wretched
lists weren't created only to be immediately thrown away would be a
good thing. But I cannot see why writing
apply(P, X, Y, Z) or P$[X, Y, Z]
is thought to be an outrageous demand on the programmer, and
P(X, Y, Z)
is thought to be so much more attractive. Whether Prolog **ought** to
make a syntactic distinction between goals and terms is not yet at
issue, the fact is that is *doesn't*, and if we are to adopt a
notation for one use, it ought to make sense in the other.. The
implementation cost of making P2(b,c) = P3(c) work is far too high for
my liking, and the increased complexity in the language in either case
is unacceptable.
Here is a quotation from Hoare, "Hints on Programming Language
Design", which explains my attitude better than I can.
A necessary condition ... is the utmost simplicity in the design
of the language. ... But the main beneficiary of simplicity is the
user of the language. In all spheres of human intellectual and
practical activity, from carpentry to golf, from sculpture to space
travel, the true craftsman is the one who thoroughly understands his
tools. And this applies to programmers too. ...
It therefore seems especially necessary in the design of a new
programming language ... to pursue the goal of simplicity to an
extreme, so that a programmer can readily learn and remember all its
features, can select the best facility for each of his purposes, can
fully understand the effects and consequences of each decision, and
can then concentrate the major part of his intellectual effort to
understanding his problem and his programs rather than his tool.
[This is the paper where he says of Fortran "The standardizers have
maintained the horrors of early implementations, and have resolutely
set their face against the advance of language design technology, and
have thereby saved it from many later horrors." I wonder what he'd
say now of Fortran 8x?! Save Prolog from horrors!]