PROLOG-REQUEST@SUSHI.STANFORD.EDU.UUCP (04/13/87)
PROLOG Digest Tuesday, 14 Apr 1987 Volume 5 : Issue 26
Today's Topics:
Administration - Listing Service Proposal,
Implementation - XOR & "Delayed Cut"
----------------------------------------------------------------------
Date: Mon 13 Apr 87 10:10:47-PDT
From: Ken Laws <Laws@STRIPE.SRI.COM>
Subject: Listing Service Proposal
While not directly addressing the merits of your suggestion or the
interest of the Prolog Digest readers, I would like to ask whether
there is any compelling reason for the Arpanet discussion lists to
assume the database role you propose. Why is an online system more
useful than the printed journals and vendor literature that are
already available? Why should free database services be offered by a
military network, rather than a commercial network (e.g., CompuServe),
library system, university, or home-hobbyist bboard? And if the
military (or NSF, or other group) really wants this, are they willing
to pay for it?
Similar questions have been coming up on the AIList lately, especially
with regard to the distribution of public-domain software.
Maintaining any system, even an automated one, puts an additional
burden on the moderator and reduces service to the discussion list.
It is reasonable that a commercial service should continue to grow (by
adding more employees), but a volunteer effort will collapse if it
grows to large. This is especially true of discussion lists since it
can be very difficult to find a new moderator if the existing one
moves out or burns out. (A new moderator is faced with doing all that
the previous one did, despite inexperience and possibly incompatible
software systems.)
I am also bothered by the idea of vendors being in charge of the
database contents. There are dangers of some vendors loading it
to their own advantage while others fail to update obsolete messages
(or never enter their products in the first place). If your concern
in creating the database is to help people make rational decisions,
such imbalances are counterproductive. This is one reason for the
Arpanet prohibition against commercial traffic: a publicly supported
network should not give companies with access an advantage over
their competitors.
-- Ken
------------------------------
Date: 4 Apr 87 02:11:29 GMT
From: Jan Chomicki <aramis!chomicki@RUTGERS.EDU>
Subject: XOR without redundancy and databases
Problem: write a Prolog predicate xor(G1,G2) which will generate
through backtracking all and only solutions to G1 if there is
one; otherwise it will generate all and only solutions to G2.
Each solution should be generated exactly once.
In essence, the code should look like:
xor(G1,G2):- G1.
xor(G1,G2):- no_success_in_the_previous_clause, G2.
The problem is how to obtain information about those proof tree
branches that have ultimately failed. Existing bindings and current
refutation bear no trace of them. Prolog interpreter, however, knows
the full computation history. Can we make him talk?
The most obvious answer would be to explicitly use the database
(assert, record etc.) or some other side-effects(file operations).
There is a subtler way which makes use of the concept of the "current
universe of atoms". This universe contains all the atoms known to
the interpreter. They come from three different sources:
- the text of the program.
- the computation so far: input etc.
- the code of the interpreter itself if it is written in Prolog.
The branches of the proof tree may be marked by special atoms
which do not appear anywhere else.
xor(G1,G2) :- pick(String), xor(G1,G2,String).
xor(G1,G2,String):- G1, there_was_once(String).
xor(G1,G2,String):- \+ was_there_once(String), G2.
pick(String) :- new_string(String), \+ was_there_once(String), !.
there_was_once(String):- name(_,String).
was_there_once(String):- current_atom(Atom), name(Atom,String).
new_string([112]).
new_string([112|L]):-new_string(L).
NOTE 1: current_atom/1 which enumerates all the current atoms is
available in Edinburgh and Quintus Prologs.
NOTE 2: We can not directly test for the presence of an atom in the
current universe of atoms. By the very appearance in the goal, the
atom becomes part of this universe! Hence
?- current_atom(abrakadabra).
succeeds even if we substitute the strangest atoms for abrakadabra.
Thus we enumerate the current atoms and compare their string
versions with the original string.
NOTE 3: For every invocation of xor/3 we need a new string which has
not appeared anywhere else as an atom. This string can not be
permanently assigned to a textual appearance of xor. Thus just before
the invocation of xor/3 strings should be generated and tested for
uniqueness (by was_there_once/1) until a brand new atom is found. That
would narrow down the dangerous area to the execution of xor/3 where
we generally know what atoms may appear.
-- Jan Chomicki
------------------------------
Date: 4 Apr 87 02:42:59 GMT
From: Jan Chomicki <aramis!chomicki@RUTGERS.EDU>
Subject: "Delayed cut" without redundancy and databases
The same trick with the current universe of atoms (see my previous
posting) solves the second problem: a complex backtracking schema.
Given a predicate
P :- A, B, C, D.
Is it possible to rewrite P to obtain the following behavior:
If the goal A initially succeeds, then
if B doesn't succeed, backtrack into A. (This is quite normal.)
However, if A initially succeeds, and B does too,
then prevent backtracking into A.
I will consider the following predicate p/2: p(X,Y):-a(X), b(X,Y).
which illustrates all the salient points of the problem except the
presence of C and D. That will be dealt with at the end. The
difficulty here is the position of the cut: we'd like to cut the
computation once the first binding for X (from a/1) and all the Y
corresponding to it are obtained (from b/2), provided there is at
least one such Y. Looking at the text, there is apparently no place
where we can put the cut to ensure the above behavior. But:
p(X,Y):- q(X,Y), Y\=='$$$$$'.
q(X,Y):- pick(String),
a(X),
( b(X,Y), there_was_once(String);
was_there_once(String) -> Y='$$$$$', ! ).
pick(String):-new_string(String), \+ was_there_once(String), !.
there_was_once(String):- name(_,String).
was_there_once(String):- current_atom(Atom), name(Atom,String).
new_string([112]).
new_string([112|L]):-new_string(L).
NOTE 1: The cut is delayed: it appears only after b/2 has succeeded
at least once.
NOTE 2: '$$$$$' is a null value which gives a void success(i.e. without
answer bindings). If C is present (as in the original problem),
we have to propagate this void success through it. This should
do:
q(X,Y,Z):- pick(String),
a(X),
( b(X,Y), there_was_once(String) ;
was_there_once(String) -> Y='$$$$$', ! ),
( Y\=='$$$$$' -> c(Y,Z);
otherwise -> true).
We can not put c/2 in the same Or-branch as b/2, because
backtracking to a/1 depends upon the success/failure of b/2 only.
-- Jan Chomicki
------------------------------
End of PROLOG Digest
********************