baldwin@rochester.ARPA (Douglas Baldwin) (09/10/86)
I'm comparing Prolog to another, somewhat more elaborate,
logic/constraint language called CONSUL, particularly with regard to
potential parallelism (CONSUL is supposed to be a source language for
parallelizing compilers, the question is how much of what CONSUL
provides could be equally well provided by a parallelizing Prolog
compiler).
One of the big differences between CONSUL and Prolog is that
CONSUL has a "forall" form that can be viewed as parallel satisfaction
of a constraint for all elements of a set, i.e., "forall X in S,
<something>" is true iff <something> is true (or can be made true by
suitable bindings) for all elements of S. CONSUL also provides precise
enough control over the scope of a name that one can tell whether names
other than X in <something> can be given independent bindings for each
element of S or whether a single binding has to suffice for all
elements.
It's easy to see how to write iterative clauses in Prolog that
(almost) have the same effect as "forall". In C-Prolog, it looks
something like
forall( ... ) :- setof( X, in_S(X), Xs), body_driver( Xs, ... ).
body_driver( [], ... ).
body_driver( [X|Xs], ... ) :- body( X, ... ), body_driver( Xs, ... ).
body( X, ... ) :- /* Prolog implementation of <something>. */
The dots above indicate the presence of auxiliary arguments that
represent the other variables used in <something>. The problem with
this solution is that by explicitly iterating, the potential
parallelism gets much harder to detect - there will in general be data
dependencies between the auxiliary arguments to body_driver and the
recursive call, and it can be quite difficult to tell whether these
data dependencies are "real", or are spurious ones introduced by the
iterative implementation. (For purists, this has another problem that
the C-Prolog forall will fail if the set S is empty, whereas the CONSUL
one will succeed vacuously, but for now I don't care).
The question is, can anybody come up with a Prolog
implementation of "forall" that DOESN'T iterate explicitly (for
example, that uses clever control of backtracking to enumerate the
elements of S), and which might thus be easier to detect parallelism
in? (To save some wrong starts, the simple
forall(...) :- in_S(X), body(X,...), fail.
doesn't work because if "body" fails for some element of S it will just
backtrack to the next instead of the whole "forall" failing. Simple uses of
cut don't seem to fix this because they make Prolog commit to a single
element of S instead of trying all.)
Suggestions to me; I'll summarize if there seems to be enough
interest. Thanks.
- Doug Baldwin
{decvax|allegra|seismo}!rochester!baldwin