PROLOG-REQUEST@SU-SCORE.ARPA (Chuck Restivo, The Moderator) (09/12/86)
PROLOG Digest Friday, 12 Sep 1986 Volume 4 : Issue 49
Today's Topics:
Query - Proceedings & Control Structures and Parallelism,
Puzzle - Knights and Knaves
----------------------------------------------------------------------
Date: Thu, 11 Sep 86 18:41:52 CDT
From: Will Winsborough <winsboro@crys.wisc.edu>
Subject: Proceedings
Does anyone know how I can get a copy of the proceedings
of last July's International Logic Programming Conference
in London?
Thank you.
-- Will Winsborough
------------------------------
Date: 10 Sep 86 15:14:58 GMT
From: Douglas Baldwin <baldwin@rochester.arpa>
Subject: Question - Control Structures and Parallelism
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.)
Thank you.
-- Doug Baldwin
------------------------------
Date: 10 Sep 86 19:05:55 +1000 (Wed)
From: Lee@mulga.OZ
Subject: Knights and Knaves
I have been away and have missed some of this discussion -
please ignore this if apropriate.
I have a solution to the Knights and Knaves class of
problems in the case when there is no assumption about
perfect knowledge of what people have said. ie, nothing
can be concluded from a knave saying someone said something.
Warning: there may be bugs.
MU-PROLOG Version 3.2
1?- [knaves].
consulting knaves
done
true.
2?- Curly says Larry says Larry is a knave and
Moe says Curly is a knave.
Larry = Larry_177,
Moe = a knight,
Curly = a knave ;
fail.
3?-
End of session
;;; here is the program
?- hide([is(2), or(2), and(2)]). % MU-Prolog hack to hide
% definitions
?- op(750, xfy, says). % allow nice input
?- op(600, fx, a).
?- op(700, xfx, is).
?- op(780, xfy, or).
?- op(760, xfy, and).
a knight is a knight. % the rest is obvious
a knave is a knave.
a knight says A :- A.
a knave says A :- false(A).
A and B :- A, B.
A or B :- A ; B.
false(a knight is a knave).
false(a knave is a knight).
false(A and B) :- false(A) ; false(B).
false(A or B) :- false(A), false(B).
false(A says B). % except this
-- Lee Naish
------------------------------
End of PROLOG Digest
********************