Path: utzoo!mnetor!uunet!lll-winken!lll-tis!mordor!sri-spam!sri-unix!quintus!ok
From: ok@quintus.UUCP (Richard A. O'Keefe)
Newsgroups: comp.lang.prolog
Subject: Re: back_retract
Message-ID: <782@cresswell.quintus.UUCP>
Date: 17 Mar 88 06:57:23 GMT
References: <1194@kulcs.kulcs.uucp> <777@cresswell.quintus.UUCP> <516@ecrcvax.UUCP>
Organization: Quintus Computer Systems, Mountain View, CA
Lines: 59

In article <516@ecrcvax.UUCP>, micha@ecrcvax.UUCP (Micha Meier) writes:
> In article <777@cresswell.quintus.UUCP> ok@quintus.UUCP (Richard A. O'Keefe) writes:
> >	back_retract(<clause>),
> >	...
> >	!,
> >	...
> >	fail
> 	This is only an implementation problem.

The point of my message was that the "obvious" way of doing this in Prolog
doesn't work.  I think it was worth mentioning this because it is one of
those old chestnuts that keeps popping up.  Someone once kindly showed
Quintus how to implement backtrackable global assignment; he'd put a fair
bit of work into it, but the
	( change /* exit */
	; /* redo */ undo_change, fail
	)
pattern was what he had used, so it didn't actually work.

Credit:  of the Prologs I know anything about, LM-Prolog has had undoable
side-effects longest.  I've seen a demo of LM-Prolog "undrawing" a picture,
I think this was at IJCAI-83.  The person who explained the technique of
pushing arbitrary functions onto the trail to me was Preben Folkjaer, then
of InterFace.

Pushing functions on the trail is a neat trick, but it isn't a panacea.
Consider the problem of I/O:  you really don't want to push a function
onto the trail for every character you write.  Chris Moss has a paper,
I don't know where it appeared, on undoable I/O, and when you can actually
produce the output.

> 	Since several people here at ECRC asked me to provide
> 	backtrackable assert and retract, I assume that it can
> 	really be useful.

You should see the things people ask for in comp.lang.c!

>	One possible application is hypothetical
> 	reasoning - with the asserts and retracts you create
> 	alternative worlds, but you certainly want to be able to
> 	return to your universe.

I think Sanjay Manchanda's approach is much cleaner.  Undo the side effect
of an assert or retract?  But <+X> and <-X> haven't GOT any side effects!
For hypothetical reasoning in general, Ken Bowen's approach to meta-level
reasoning is to make the alternative worlds explicit as data values; in a
system like that you can reason about several worlds at once.  If we can
get logical arrays with acceptable efficiency (which would be useful in
any case), it seems that the Manchanda & Bowen approaches need not be
inferior in efficiency to the backtrackable side efffects approach.

What happens if you are using a system with backtrackable side effects
(such as back_retract) and the code aborts (explicit call to abort, or
to some sort of error signalling operation)?  Do the side-effects get
unwound then?  I'm not asking "how do you do it", but "what do you want
it to do?"  What happens if you have an AND-parallel system and one
process executes back_retract, do the other processes notice the change
or not?   If you take the Bowen or Manchanda approach to data base updates,
the answer is obvious:  nothing is changing, you just get additional
worlds.  (The Manchanda approach may be easier for AND-parallel systems.)