Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!samsung!munnari.oz.au!goanna!ok
From: ok@goanna.oz.au (Richard O'keefe)
Newsgroups: comp.lang.prolog
Subject: Re: What does/should your Prolog make of this ?
Keywords: cut assert fail backtracking
Message-ID: <2953@goanna.oz.au>
Date: 7 Mar 90 10:24:50 GMT
References: <1990Mar1.210219.5687@Neon.Stanford.EDU> <1557@maestro.htsa.aha.nl>
Organization: Comp Sci, RMIT, Melbourne, Australia
Lines: 120

In article <1557@maestro.htsa.aha.nl>, jand@maestro.htsa.aha.nl (Jan Derriks) writes:
> In the book 'AI Through Prolog', Neil Rowe uses something like this:

> (1)   doo :- agenda(X), assertz(agenda(next)), write(X), fail.

> My question: Is there ANY Prolog interpreter that does what
>              I (and apparently N. Rowe too) expect ?
> BTW, the workaround is of course to always have two 'dummy' facts in
>      the database for cases like this. (or is there a better way ?)

No, that workaround does *NOT* work in general.  It won't work in
Quintus or SICStus Prolog, for example.  The question is,

	if a predicate is changed by assert, retract, abolish, &c
	while there is a call active for that predicate,
	what should happen?
	retract/1 and clause/2 count as calls to the predicate.

In DEC-10 Prolog and C Prolog, the answer was the "immediate update" model,
where *every* change to a dynamic predicate must immediately be visible to
all active calls to that predicate.  This makes sense, and Rowe's example
does work under that model.

The trouble with that model is that getting it _right_ means that you
must ALWAYS leave a choice point behind when you call a dynamic predicate
even when you get to the last clause, because another clause *might* be
added while it is running.  DEC-10 Prolog and C Prolog do in fact leave
such choice-points behind.

A lot of Prolog implementors haven't bothered to do anything specific
in this case, thinking that it is unlikely.  Some Prologs will crash if
you retract a clause and then an active call tries to backtrack into it.

Sometime in 1983 or 1984 I proposed what I called the "transaction",
or "logical" model.  In that model, calling a predicate behaves as if
it made a private copy of the relevant clauses which were present at
the instant of the call, and changes to the data base don't affect that
private copy.  Now, that model was invented to solve some other problems,
but Quintus adopted it because it made sense of indexed dynamic predicates:
at long last compiled and interpreted predicates needed cuts in precisely
the same places.  Rowe's hack won't work at all under this model, no
matter how many clauses there are in the agenda to start with:  it will
exhaust the initial clauses and then stop.

A point to appreciate is that because of the Prolog systems which don't
bother to implement any particular model, portable code never could use
this backtrack-into-the-agenda code anyway.  Here's a portable way of
doing it:

	:- dynamic
		agenda/1.

	/*  start(Task) tries to accomplish Task.  It succeeds if
	    process_item(Item) ever succeeds.  It fails if
	    next_agenda_item(_) runs out of agenda items instead.
	*/
	start(Task) :-
		initialise_agenda(Task),
		next_agenda_item(Item),
		process_item(Item),
		!.

	initialise_agenda(Task) :-
		retractall(agenda(_)),
		assert(agenda(Task)).

	agenda_is_empty :-
		\+ Item^agenda(Item).


	/*  next_agenda_item/1 is a hybrid between retract and repeat;
	    think of it as a version of retract/1 where the search
	    for another matching clause starts again from the beginning
	    of the predicate instead of continuing from where the last
	    search left off (as retract does).
	*/
	next_agenda_item(Item) :-
		retract(agenda(I)),
		!,
		(   Item = I
		;   next_agenda_item(Item)
		).

	/* process_item(Item) works on the current agenda item.
	   It may add new items to the front of the agenda with
	   asserta/1 or to the back of the agenda with assertz/1.
	   It may even remove items from the agenda.
	   It should succeed when the over-all task has been
	   accomplished; otherwise it should fail.

	   If you would like to use a different approach where
	   the loop is to stop *successfully* when the agenda
	   runs out, you can just do
		process_item(X) :- ......, agenda_is_empty.
	*/

This approach generalises nicely to a multi-level agenda.  Suppose we
want an agenda with three priority levels.  Then we use

	:- dynamic
		agenda/2.

	initialise_agenda(Task) :-
		retractall(agenda(_,_)),
		assert(agenda(1,Task)).

	agenda_is_empty :-
		\+ Level^Item^agenda(Level, Item).

	next_agenda_item(Item) :-
		(   retract(agenda(1,I))
		;   retract(agenda(2,I))
		;   retract(agenda(3,I))
		),
		!,
		(   Item = I
		;   next_agenda_item(Item)
		).

It should be clear how to generalise this to N levels.