PROLOG-REQUEST@SU-SCORE.ARPA (Chuck Restivo, The Moderator) (10/08/85)
PROLOG Digest Wednesday, 9 Oct 1985 Volume 3 : Issue 42
Today's Topics:
Implementation - Destructive Assignment,
& Connected Components & Cut Tests
----------------------------------------------------------------------
Date: Mon, 30 Sep 85 09:32:42 EDT
From: Paul Hudak <Hudak@YALE.ARPA>
Subject: Prolog vs Lisp and destructive assignment
The analogy that Prolog is to Logic Programming as Lisp is to
Functional Programming is a good one. The analogy would be
even stronger if Prolog had destructive assignment, although
it's easy to argue that Prolog's Assert and Retract are forms
of destructive assignment.
However, as Peter Deutsch points out, despite our need for practical
languages, the "purists" should not give up hope that clever compiler
techniques might make pure logic or functional programming a practical
reality. For example, there now exist fairly powerful inferencing
strategies for converting call-by-need evaluation to call-by-value,
even in the presence of higher-order functions. This makes lazy
evaluation not nearly as expensive as it was once thought. As for
destructive assignment, several strategies have been developed to
infer that a purely functional update is being done to an object with
a *single reference*, so that the update can be done destructively
"behind the scenes." Papers on this topic include an early paper by
Schwartz (1978), one by Mycroft (Edinburgh thesis 1981), and a recent
one by Hudak and Bloss (POPL 85).
In the latter paper we show that if one were to translate (in the
most "obvious" way) an imperative program using destructive assign
-ment on arrays, into a purely functional program without side
effects, then it will always be the case that the updates could be
done destructively behind the scenes. The reason is rather obvious:
in an imperative program, once a change is made to an array there is
no way to access the old version of it, and the most obvious
translation to a functional program tends to preserve this property!
Indeed, this highlights precisely the *power* (rather than
disadvantage) of functional or logic programs in being able to refer
to, or "hang on" to, old objects. It is a feature that can be
simulated in conventional languages only be making explicit copies
of the array in question. (To formalize the notion of translation
we use a version of McCarthy's flowchart-schema-to-recursive-schema
translation.)
Although I haven't done it, I also believe that these results could
be generalized to logic programming.
Well, this is the good news. The bad news is that it is not clear
how one resaons about the space-efficiency of such a program, since
no inferencing strategy can guarantee that *all* copying is avoided.
I don't have an immediate solution to this problem, but am not too
concerned because:
1) In the past we have been able to educate programmers well enough
that they realize that a tail-recursive call is as space-efficient
as a loop. (Indeed, this situation can be viewed as a special
case of updating arrays!) Perhaps a similar degree of education
would help here.
2) It is possible to engineer special constructs that enforce the
single-reference property, while allowing the elegance of a purely
functional solution. Such constructs appear, for example, in
certain data-flow languages.
-- Paul Hudak
------------------------------
Date: Tue, 1 Oct 85 11:13:07 -0200
From: Ehud Shapiro <udi%wisdom.bitnet@WISCVM.ARPA>
Subject: Connected Components
In my paper, A Subset of Concurrent Prolog and its Interpreter
(ICOT TR-003), there is a Concurrent Prolog solution to the
connected components problem (which also happens to be a logic
program solution, if you delete the read-only's). Since the
program and its description are rather short, I enclose them
here.
We associate with each node in the graph a distinct integer
number. The name of a connected component is the smallest
number of any node in the component. The algorithm, for a
graph with vertices V is:
For each node n in V do
Set Xn to n.
Repeat |V| times:
Send Xn to all nodes adjacent to n,
Receive a number from every adjacent node,
Let Xn' be the minimum of Xn and the numbers received.
Set Xn to Xn'.
Set n's connected component number to Xn.
The algorithm is not very efficient. For an n-vertex graph its
computation depth is in the order of n, and its length is in the
order of n@+(2). This means, roughly, that given n processors,
the algorithm runs in linear time. Better parallel algorithms
are known (Shiloach&Vishkin), but this algorithm --- and its
implementation --- are among the simplest.
The program assumes a specialized adjacency list representation
of the graph. With each node N we associate a stream variable
Xn. The graph is represented as a list of n triples (N, Xn, As),
where N is the node number, Xn is its associated stream variable,
and As is a list of the stream variables associated with the
nodes adjacent to N.@: Given this graph, the program computes
a list of pairs (N, C), where C is the name of the connected
component of the node N.
(1) cc(Graph, CList) :-
cc(Graph, Graph, CList).
(2) cc(Graph, [(N, [N|Xn], As)|Gs], [(N, C)|Cs]) :-
node(Graph, N, Xn, As, C),
cc(Graph, Gs, Cs).
(3) cc(_, [], []).
(1) node([_|G], Xn, [Xn1|Xns], As, C) :-
min(Xn, As?, Xn1, As1), node(G, Xn1, Xns, As1, C).
(2) node([], C, [], _, C).
(1) min(Xn, [[B|Bs]|As], Xn1, [Bs|As1]) :-
lt(Xn, B) | min(Xn, As?, Xn1, As1).
(2) min(Xn, [[B|Bs]|As], Xn1, [Bs|As1]) :-
le(B, Xn) | min(B, As?, Xn1, As1).
(3) min(Xn, [], Xn, []).
Clauses (1)-(3) spawn a node process for each node in V; note
that they generates the stream of pairs (N, C) before the
component name C of each node is determined.
Each node process has four arguments. The first is the graph
itself, which it uses to count |V| iterations. Following are
the Xn variable explained above, the list of streams of adjacent
nodes, and the node's final component number. The node process
iterates |V| times, using Clause (1), and on each iteration
performs the operations described above.
The @i(min) process extracts the smallest element among all the
first elements of the adjacent streams and the current node number,
and returns a list of the rest of the streams.
For example, if we invoke the program on the 7-vertex graph in
which 1 is connected to 2 and 3, 2 is connected to 4, 5 is
connected to no one, and 6 is connected to itself and to 7, we
get the following result:
| ?- solve(cc([(1, X1, [X2, X3]), (2, X2, [X1, X4]),
(3, X3, [X1]), (4, X4, [X2]
| (5, X5, []), (6, X6, [X6, X7]), (7, X7, [X6])], Cs)).
|
Cs = [(1, 1), (2, 1), (3, 1), (4, 1), (5, 5), (6, 6), (7, 6)],
X1 = [1, 1, 1, 1, 1, 1, 1, 1],
X2 = [2, 1, 1, 1, 1, 1, 1, 1],
X3 = [3, 1, 1, 1, 1, 1, 1, 1],
X4 = [4, 2, 1, 1, 1, 1, 1, 1],
X5 = [5, 5, 5, 5, 5, 5, 5, 5],
X6 = [6, 6, 6, 6, 6, 6, 6, 6],
X7 = [7, 6, 6, 6, 6, 6, 6, 6]
}
which shows, in addition to the component numbers, also at which
cycle each node discovered its correct component name. We see
that after three cycles every node knew its final component name.
In the paper "Distributed Programming in Concurrent Prolog"
(Weizmann Institute TR CS84-02, by A. Shafrir and myself, a
Concurrent Prolog implementation of a much more complex
distributed algorithm for connected components is described.
-- Ehud Shapiro
------------------------------
Date: Mon, 7 Oct 85 11:51:16 BST
From: mcvax!cdsm@doc.ic.ac.uk
Subject: Results of cut tests
Results of CUT Tests
I've received a large number of replies both via the network and
letters and am very grateful to all those who took the trouble
to send in results. The results as they currently stand are
listed below, and the test is also repeated (I've added a cut to
the first clause of 'do' to allow for those systems which give
all results, e.g. UNSW). As you may see, the second one listed
(all Y except for 'not' test) is numerically most popular but it
does not include any of the compiled systems. Somewhat
surprisingly, the 'Edinburgh Standard' is not a standard.
Implementation Test 1 2 3 4 5 6
DEC-10 (Comp) Y Y Y Y Y Y
Waterloo, MUprolog, Quintus(Int), Y Y Y Y Y N
UNH(1.3), Salford, Criss, Prolog-1,
BIM, York
Quintus (Int) Y Y Y Y Y I
MProlog(1.5) Y Y Y Y N N
Prolog-2 (Int, Comp) Y Y Y N N Y
DEC-10 (Int), C-Prolog, Prolog-X Y Y Y N N N
POPLOG, LM-Prolog Y Y Y I I I
Quintus (Comp) Y Y I N N N
micro, sigma Y N N Y Y N
UNSW Y N N Y N N
ICL Y N N N N N
where Y means did cut, N means did not cut and I means that it
was trapped as an illegal use and failed.
(There are several contradictory results for the Quintus
Compiler, presumably corresponding to different releases.)
If there are any other discriminating cases not covered above I
would be glad to hear of them. I would stress that I do not
consider there to be any "right" answers.
---------------------------------------------------------
/* Tests to distinguish various implementations of cut */
/* Chris Moss, Imperial College, June 1985 */
test1 :- do('Testing that cut is implemented). ', t1).
test2 :- do('Test if cut acts within disjunction', t2).
test3 :- do('Test if it cuts previous choices within disjunction',t3).
test4 :- do('Test if cut acts when passed as metacall', t4).
test5 :- do('Test if & cut acts within metacall', t5 ).
test6 :- do('Test if cut acts through not', t6).
do(Message,Test) :- w(Message), Test, !.
do(Message,Test) :- w('Does act').
w(X) :- write(X), nl.
t :- w('Does not act').
t1 :- (true;w('Did not cut alternatives correctly'),fail),
!, w('Succeeds going forwards'), fail.
t1 :- w('Failed to cut goal').
t2 :- (!;w('Fails to cut disjoint alternatives')), fail.
t2 :- t.
t3 :- t3a(X),(!,fail;w('Fails to cut disjunction')).
t3 :- t.
t3a(!).
t3a(X) :- w('Did not cut alternatives'), fail.
t4 :- t3a(X), X, w('Ok going forwards'),fail.
t4 :- t.
t5 :- t5a(X), X, fail.
t5 :- t.
t5a((true,!)).
t6 :- not(not(!)), fail.
t6 :- t.
------------------------------
Date: Mon, 7 Oct 85 11:50:20 BST
From: mcvax!cdsm@doc.ic.ac.uk
Subject: Assert/Retract tests
Tests for Assert and Retract
Below is a set of tests to look at the effects of assert and
retract along the lines of my earlier tests for cut. I would be
very grateful if anyone with access to a Prolog not listed in
the set of results which I already have could run this and send
me the results (directly) and I will post the list at some
future date in the network. So far I haven't found two
implementations which give the same results! For some
implementations, you may need to add declarations or make other
slight changes to get the desired effects.
------------------------------------------------------------
main :-
test1, test2, test3, test4, test5, test6, test7, test8, test9.
/* Tests to distinguish various implementations of assert */
test1 :- do('1. Test assert on existing predicate',t1).
test2 :- do('2. Test assert on new predicate',t2).
test3 :- do('3. Does it find added 3rd clause on backtracking', t3).
test4 :- do('4. Does it find added next (last) clause on backtracking', t4).
test5 :- do('5. Test retract on single element clause',t5).
test6 :- do('6. Does retract backtrack? ', t6).
test7 :- do('7. Does retract work on invoked clause',t7).
test8 :- do('8. Does retract work on next (last) invoked clause',t8).
test9 :- do('9. Test retracts and asserts on invoked clause', t9).
do(Message,Test) :- w(Message), Test, !.
do(Message,Test) :- w('No Clause found').
w(X) :- write(X), nl.
t :- w('Added clause').
tr :- w('Failed to retract clause').
t1 :- assert((t1a :- t)), t1a.
t1a :- w('Clause 1'),fail.
t2 :- assert((t2a :- t)), t2a.
t3 :- assert((t3:-t)),fail.
t3 :- fail.
t4 :- assert((t4:-t)),fail.
t5 :- retract((t5a :- tr)), t5a.
t5a :- tr.
t6 :- retract((t6a:-X)),fail.
t6 :- t6a.
t6a :- tr.
t6a :- w('Does not backtrack').
t7 :- t7a, fail.
t7 :- fail.
t7 :- tr.
t7a :- retract((t7:-tr)),!.
t8 :- t8a, fail.
t8 :- tr.
t8a :- retract((t8:-tr)),!.
t9 :- retract((t9:-w('Second'))),assert((t9:-t)),fail.
t9 :- w('Second').
-----------------------------------------------------
Results I already have are as follows:
1 2 3 4 5 6 7 8 9
cprolog CA A A N N N N N A
Dec-10, interpreted CA A A A N F N N A
Dec-10 compiled CN N N N N F F F S
micro prolog (CP/M-80) CA A A N E D F N A
muprolog CA A A A N N N N A
poplog CA A N N N N F F S
sigmaprolog (unix) CA A A N E D N F A
sigmaprolog (Dec front) CA A A N N F N F A
where letters stand for the first letter of the message printed
out by the test, and E stands for a "no such predicate" error
message. Note that in the latter case you may have to split up
the "main" procedure into several parts.
This set of tests is certainly not complete. In particular it
doesn't explore the interactions of assert and retract (except
for one test, 9), nor does it look at versions of assert and
retract which have numbered arguments. It's main purpose is
probably to ring the alarm bells about the differences which
have crept in and point to the need for reform. One might note
that retract together with garbage collection and reuse of an
"orphaned" pointer is the easiest way to crash many Prolog
systems. I haven't included such a test as the details appear to
differ for every implementation which is liable.
-- Chris Moss
------------------------------
End of PROLOG Digest
********************