Path: utzoo!mnetor!uunet!husc6!sri-unix!quintus!ok
From: ok@quintus.UUCP (Richard A. O'Keefe)
Newsgroups: comp.lang.prolog
Subject: Re: back_retract
Message-ID: <777@cresswell.quintus.UUCP>
Date: 15 Mar 88 11:25:43 GMT
References: <1194@kulcs.kulcs.uucp>
Organization: Quintus Computer Systems, Mountain View, CA
Lines: 107

In article <1194@kulcs.kulcs.uucp>, bimbart@kulcs.uucp (Bart Demoen) writes:
> See what you can do in BIMprolog:
[ I have reformatted this so that I can read it:  if you want to see how
  Bart Demoen wrote it, read his message.
]
> back_retract((HeadUsed:- BodyUsed)) :-
> 	clause(HeadUsed, BodyUsed, Index),		% FIND the clause
> 	functor(HeadUsed, Symbol, Arity),
> 	functor(HeadCopy, Symbol, Arity),
> 	clause(HeadCopy, BodyCopy, Index),		% COPY the clause
> 	(   retract((HeadUsed :- BodyUsed), Index)	% DELETE the clause
> 	;   assert((HeadCopy :- BodyCopy), Index),	% REPLACE the clause
> 	    fail					% resume failing
> 	).

Porting problem:  DEC-10 Prolog has assert(+Clause, -Ref) and
clause(+Head, ?Body, -Ref) where Ref is a sort of pointer, and several
other Prologs do the same.  Even AAIS Prolog tries.  But that's a
minor change, just invent new names for the operations.

This will do what the original poster wants,
ONLY IF there are no other changes to the same predicate.

Consider

	back_retract(<clause>)		-- removes 3rd clause
	asserta(<new clause>)
	fail

This will shuffle the data base, which was not what was wanted.
This kind of excessively unpleasant interaction is precisely why
the DEC-10 Prolog family hasn't got "positional" data base commands.

We could get around this by having an 'assert_before' predicate
which took a clause and a data base reference and put the clause
before the one the reference pointed to (even if the referenced
clause had since been deleted):

* back_retract(Clause) :-
*	prolog_clause(Clause, Head, Body),	% see DECONS.PL in DEC-10 lib
*	clause(Head, Body, Ref),		% FIND the clause
*	instance(Ref, Copy),			% COPY the clause
*	(   erase(Ref)				% DELETE the clause
*	;   assert_before(Ref, Copy),		% REPLACE the clause
*	    fail				% resume failing
*	).

This would be free of shuffling problems, even when other updates to
the predicate in question were being made.

However, both versions of back_retract/1 have a rather more serious
failure mode.

Consider

	back_retract(<clause>),
	...
	!,
	...
	fail

By analogy with variable bindings, you would expect the back-retracted
clause to reappear.  But the cut will have had the effect of pruning
away the "assert".  Was it in 1983 or 1984 that I pointed this problem
out in the Prolog Digest, with reference to an 'assume' operation?

This problem is the reason that Quintus Prolog hasn't got backtrackable
assignment to global variables in the library:  cuts prune away the
restoration code.

> But there should be a better way of doing what you want.

If back_retract is being used to simulate something even vaguely
logical, there has been some very interesting work done at Stony
Brook on extending Prolog with some features of dynamic logic.
Roughly speaking, there are three classes of predicates:

	pure predicates (don't depend on things that change)

	state predicates (depend on things that change, but change nothing)

	transition predicates (express a relation between states)

For example, we might say

	p(X) :-
		<-fred(X)> q(X).

p(X) is true in a world W if there is a world W1 such that
	-(fred(X), W, W1)			-- roughly, retract
and	q(X) is true in W1.

Note that this doesn't change W.
Permanent changes are effected by the top level, where queries have
the meaning "let W be the current world; if there is a world W1 and
a substitution S such that the query arrives in W1 with substitution S,
print S and make W1 the current world."

I'm sorry that I can't remember the name of the person who was working
on this.  He promised me a copy of a paper about it, but it never
arrived, so I can't give you a reference either.  A pity, because this
strikes me as the obviously right way to handle "local" data base
updates, it's even related to an existing logic!

It remains the case that converting an O(N**N) operation to an O(N!)
-- which the original poster cited as motive for having back_retract/1 --
is scarcely worth the trouble.