Path: utzoo!mnetor!uunet!lll-winken!lll-lcc!mordor!sri-spam!sri-unix!quintus!pds
From: pds@quintus.UUCP (Peter Schachte)
Newsgroups: comp.lang.prolog
Subject: Re: Destructive predicates (random musings - part-I).
Message-ID: <716@sandino.quintus.UUCP>
Date: 1 Mar 88 22:38:42 GMT
References: <7289@agate.BERKELEY.EDU>
Organization: Quintus Computer Systems, Mountain View, CA
Lines: 61
Keywords: Destructive predicates, LISP vs PROLOG Philosophy
Summary: The Prolog LIBRARY isn't austere, and doesn't need to be as big anyway

In article <7289@agate.BERKELEY.EDU>, lagache@violet.berkeley.edu (Edouard Lagache) writes:
>     There
>     is a tension here between "the function soup" of LISP, and the
>     comparative austerity of the (standard) PROLOG predicate
>     library.

You mentioned the Prolog library.  There are several Prolog libraries,
containing MANY, many predicates, covering all sorts of things you
might want to do.  But they are (I think properly) not a part of the
language.  If you want them, you can load them in, but you don't have
to have all of them around if you don't need them.  Most Lisps build in
many functions that you don't really need.  (I think) many of them would be
better exported to a standard Lisp library.

Also, note that Prolog doesn't really need as many predicates as Lisp.
For example, in the case of list processing, Lisp needs to have CAR,
CDR, and CONS, while Prolog handles all these through pattern matching.
Lisp has APPEND, LDIFF, MEMBER, and ASSOC (and CommonLisp has ASSOC-IF
and ASSOC-IF-NOT), while Prolog can do all these things with just
append/3.  And by adding in a bidirectional length/2 predicate and
difference lists, Prolog provides most of the list-handling capabilities
that Lisp provides with quite a few built-in functions.  And I could go
on.  Prolog really does gain some useful generality from unification and
nondeterminism.

>     Implementation issues aside (for the moment), each
>     approach has some merits, but PROLOG tends for force the
>     programmer to sacrifice "simple decomposition" for
>     efficiency.

No more than Lisp.  In either language, one often wants to process a
data structure (often a list), and wind up with something else.  And it
is often most convenient to do the processing in small steps,
transforming the first data structure into a second, then a third, and
so forth, until you get what you want.  Often this could be done more
efficiently by doing all the steps at once.  Then, in either language,
one has to ask himself, "how important is efficiency here, and is it
worth writing a lot of my own predicates (functions) to do this more
efficiently?"

Lisp DOES provide destructive operations to make some things more
efficient.  And Lisp has looping constructs to save them from having to
write lots of auxilliary functions.  But Prolog can often get the effect
of side-effects with unbound variables.  And Prolog doesn't loose much
efficiency from having auxilliary predicates, since they can usually be
tail-recursive.

Prolog doesn't loose all that much from not having destructive
operations.  Often this loss can be mitigated by using better data
structures.  Trees instead of lists mean that to change an element you
only have to copy log2(N) elements, rather than N, where N is
proportional to the size of the list or tree.  It would be nice if we
could have compilers that magically turned our nice pure code into
side-effects.  This is VERY hard.

For now, Prolog still has some big wins over Lisp sytems in performance
(faster cons, for example, and cheaper memory management overall) to put
against Lisp's advantage in having destructive operations.
-- 
-Peter Schachte
pds@quintus.uucp
...!sun!quintus!pds