Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watnot!watmath!clyde!rutgers!aramis!chomicki
From: chomicki@aramis.UUCP
Newsgroups: comp.lang.prolog
Subject: XOR without redundancy and databases
Message-ID: <425@aramis.RUTGERS.EDU>
Date: Fri, 3-Apr-87 21:11:29 EST
Article-I.D.: aramis.425
Posted: Fri Apr  3 21:11:29 1987
Date-Received: Sun, 5-Apr-87 07:46:59 EST
Organization: Rutgers Univ., New Brunswick, N.J.
Lines: 63
Keywords: control, side effects

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 (chomicki@aramis.rutgers.edu)	Phone: (201) 932-3999
Dept.of Computer Science, Rutgers University, New Brunswick, NJ 08903
Usenet: {...harvard,pyramid,seismo,nike}!rutgers!aramis!chomicki
Arpanet: chomicki@aramis.rutgers.edu