chomicki@aramis.UUCP (04/04/87)
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.edulee@mulga.UUCP (04/06/87)
In article <425@aramis.RUTGERS.EDU> chomicki@aramis.RUTGERS.EDU (Jan Chomicki) writes: >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). One problem with this is that nested calls to xor may not work correctly. The inner call can use the same string and cause it to be put in the dictionary, even though G1 (from the outer call) fails. This would prevent G2 from being called. eg: ?- xor((xor(true, fail), fail), true). % xor is a confusing name here fails when it should succeed (I think). Just to stop a dozen people sending in fixes, I guess I should point out that you can get around this by creating two related strings, both of which must be "new" then making one "old". The computation may create the string in other ways too (though this is unlikely, I guess). was_there_once/1 could get pretty slow on some systems also (maybe slower than finding the first solution to G1). Can anyone confirm that default/2 in Prolog II uses soft cut? Are there any other systems with soft cut implemented? lee