jand@maestro.htsa.aha.nl (Jan Derriks) (03/06/90)
In article <1990Mar1.210219.5687@Neon.Stanford.EDU> feldman@Neon.Stanford.EDU (Todd J. Feldman) writes: > >Can someone please help me with a bug in the following Prolog fragment: > Maybe this problem is related to Feldman's: In the book 'AI Through Prolog', Neil Rowe uses something like this: (1) doo :- agenda(X), assertz(agenda(next)), write(X), fail. When this rule starts there is ONE fact 'agenda(start)' in the database, so the first query agenda(X) succeeds with X=start. Now the problem with all of our Prolog interpreters (Prolog-2 from Expert Systems International Ltd, Xprolog, SBprolog) is that they are so 'smart' as to see that with only ONE agenda() fact in the database, there is no need to keep a backtrack-point there, so that fact is interpreted as agenda(start) :- !. And following assertz'ed agenda's are NOT found by backtracking, so the output is just 'start no', while what was intended is: 'startnextnextnextnextnextnext....' (database full) as a result. When you start with TWO agenda facts it works as intended (try calling 'doo' a second time) My question: Is there ANY prolog interpreter that does what I (and apparantly 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 ?) -- Jan Derriks | AHA-TMF (H.T.S. 'Amsterdam'), jand@maestro.htsa.aha.nl | Europaboulevard 23, (or ..hp4nl!htsa!jand) | 1079 PC Amsterdam, phone: +31 20423827 | the Netherlands.
roland@sics.se (Roland Karlsson) (03/06/90)
> (1) doo :- agenda(X), assertz(agenda(next)), write(X), fail. > Now the problem with all of our Prolog interpreters (Prolog-2 from > Expert Systems International Ltd, Xprolog, SBprolog) is that they > are so 'smart' as to see that with only ONE agenda() fact in the > database, there is no need to keep a backtrack-point there, so that > fact is interpreted as > agenda(start) :- !. > And following assertz'ed agenda's are NOT found by backtracking, so > the output is just 'start no', while what was intended is: > 'startnextnextnextnextnextnext....' (database full) as a result. In SICStus Prolog there is a sound implementation of assert after call. In the example above above you will be able to backtrack to all clauses (instances) of agenda/1 known at the time when calling agenda(X). That is, no instances asserted after calling agenda(X) will be known. It dosn't matter if there is 1 or more instances when first calling agenda(X). The output will always be 'start - no' only. -- Roland Karlsson SICS, PO Box 1263, S-164 28 KISTA, SWEDEN Internet: roland@sics.se Tel: +46 8 752 15 40 Ttx: 812 61 54 SICS S Fax: +46 8 751 72 30
ok@goanna.oz.au (Richard O'keefe) (03/07/90)
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.
alf@sics.se (Thomas Sj|land) (03/07/90)
Roland Karlsson wrote:
> In SICStus Prolog there is a sound implementation of assert after call.
^^^^^
Please, do not misuse the terminology like this. This problem has nothing
to do with "soundness" in the logical sense. Use "healthy" or "nice"
or "good" or whatever you like.
----
Another issue that has come up and which could interest this group
relates to bagof(setof)-semantics :
What should be the behaviour of the following queries (in the program 'p(X)') ?
?- freeze(X,write(foo)), bagof(_,(X=1 ; X=2),L).
?- Y=1,
bagof((X,Y),p(X),L).
?- bagof((X,Y),p(X),L),
Y=1.
The behaviour in SICStus seems unintuitive to many. One would perhaps
want to have a less "operational" view on bagof/setof
Is there a need for more versions of findall/bagof/setof ?
Are there efficiently implementable alternatives ?
/Thomas Sjvland,
(look, I can write my name on a SUN with ISO standard 8859 !)
PS.
This is what I get easily into gnu-emacs using C-Q M-<key> !!
1234567890-=\` !@#$%^&*()_+|~
qwertyuyuiop[] QWERTYUIOP{}
asdghjklkl;' ASDFGHJKL:"
zxcvbnm,./ ZXCVBNM<<>?
? Doesn't it look nice ?
Ought we not to think about bigger character sets for Prolog
including Europe and Japan and also FULL (complete, :-)) English
in the syntax ?
DS.
--
Thomas Sjoeland
SICS, PO Box 1263, S-164 28 KISTA, SWEDEN
Tel: +46 8 752 15 42 Ttx: 812 61 54 SICS S Fax: +46 8 751 72 30
Internet: alf@sics.se or {mcvax,munnari,ukc,unido}!enea!sics.se!alfcdsm@sappho.doc.ic.ac.uk (Chris Moss) (03/08/90)
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. > >When this rule starts there is ONE fact 'agenda(start)' in the database, >so the first query agenda(X) succeeds with X=start. ... >And following assertz'ed agenda's are NOT found by backtracking, so This is a standard problem with the semantics of assert and retract in Prolog. The problem is of course that when you enter the clause "agenda" the Prolog system wants to know if it has to set up a backtracking point. Any sensible system won't, a naive interpreter will anyway, but will set the address of the next clause in the backtracking frame. Since this is nil at this point, the effect is the same. It will only be non-nil if it bothers to do an extra dereference at backtracking time. Almost the same thing is happening here: >From: feldman@Neon.Stanford.EDU (Todd J. Feldman) > >Can someone please help me with a bug in the following Prolog fragment: > >process_entries:- > wait(X), > abolish(wait,1), > goal1(.....), > goal2(.....), > goal3(.....), > goal4(.....). > >The intention I had in writing this code was for backtracking to occur >between goals 1 and 4. Finally, goal1 will no longer be able to succeed. But this is one of the easiest ways to crash a fragile Prolog system. Why? The reference to the next "wait" clause has already been stored, when the abolish goes ahead and deletes the clause. Now one of several things can happen. If the "orphaned" next clause happens still to be lying around in store, it will still be executed. If however its space has been reclaimed and in the meanwhile your process has put something else there which is NOT a clausehead, then the system will probably crash. The Edinburgh compiler and its offsprings guarded against this by not recovering space until the end of the program. The better way is make the semantics of assert and retract more logical: that is to copy the "readers and writers" approach to file consistency. Once you've started reading (executing) a predicate, it will stay static and any changes will not be visible. But any subsequent reads (executions) will see the new copy. Not all Prologs do this yet. But Quintus started and the Prolog standard has also incorporated this notion, so hopefully more are following. Does anyone know of others? Mail to me and I'll post. In both cases the problem can be solved by backtracking PAST the goal and then reentering, though some recoding will be needed (e.g. asserta not assertz). I'm not convinced that either program should use assert or retract however. Chris Moss.
ok@goanna.oz.au (Richard O'keefe) (03/08/90)
In article <1990Mar7.104021.28421@sics.se>, alf@sics.se (Thomas Sj|land) writes: > Another issue that has come up and which could interest this group > relates to bagof(setof)-semantics : > What should be the behaviour of the following queries > (in the program 'p(X)') ? I don't understand what "in the program 'p(X)'" means. > ?- freeze(X,write(foo)), bagof(_,(X=1 ; X=2),L). Ignoring the freeze, the call to bagof/3 would create a list L=[U,U] in some versions of Prolog, L=[U,V] in others. When the elements of the result are not ground, setof/3 and bagof/3 have no non-operational meaning. In NU Prolog version 1.4, the result is 2?- prog(L). foofoofooL = [_CYIXR] ; fooL = [_CYIXU] ; fail. which seems reasonable to me. > ?- Y=1, > bagof((X,Y),p(X),L). This should be the same as bagof((X,1), p(X), L), and should presumably act just as it does in non-coroutining Prologs. > ?- bagof((X,Y),p(X),L), > Y=1. I repeat that setof/3 and bagof/3 have no non-operational meaning when the elements of the result would not be ground. It seems to me entirely reasonable for a coroutining implementation of these predicates to compute the set V' = {variables in the Template} \ {variables in the Generator} and do something like setof(T, G, L) => setof(T, (G, await_all_ground(V')), L) bagof(T, G, L) => bagof(T, (G, await_all_ground(V')), L) the wait has to be inside the generator in case the generator binds some constrained variables and the awakened constraints bind some of the variables in V'. > Is there a need for more versions of findall/bagof/setof? Yes. NU Prolog has some of them. For reasons entirely unrelated to coroutining, there are still other versions that would be useful. > PS. > Ought we not to think about bigger character sets for Prolog > including Europe and Japan and also FULL (complete, :-)) English > in the syntax ? The document PS/6 was written in mid-1984 and explicitly recommends that Prolog should accept Kanji, each glpyh being represented by a single integer code. Xerox Quintus Prolog does this. I believe that the approach taken by Xerox Quintus Prolog is the right one. Quintus Prolog handles the full 8859/1 character set, and if Debray didn't make too many changes to the tokeniser I gave him, so does SB Prolog. It is quite straightforward to define Prolog token-level syntax in terms of sets of characters, leaving character set size and coding implementation defined. The main difficulty (which my current specification _just_ manages to cope with) is that some character sets include several replicates of the same characters (for example IBM's DBCS apparently includes two copies of each non-control EBCDIC character) and one might want all the replicates of the digits to function equivalently, without confusing them elsewhere. (Xerox are right: subscript/superscript/width and so on are part of the "looks" of an INSTANCE of a character and should not be part of the code of the IDENTITY of the character. Alas, IBM (RT AIX) and others don't agree.
jand@maestro.htsa.aha.nl (Jan Derriks) (03/08/90)
In article <1681@gould.doc.ic.ac.uk> cdsm@doc.ic.ac.uk (Chris Moss) writes: >In article <1557@maestro.htsa.aha.nl> jand@maestro.htsa.aha.nl (Jan Derriks) >>(1) doo :- agenda(X), assertz(agenda(next)), write(X), fail. > >This is a standard problem with the semantics of assert and retract in Prolog ... [using the 'static|transaction|logical' model] >Not all Prologs do this yet. But Quintus started and the Prolog standard has >also incorporated this notion, so hopefully more are following. Does anyone >know of others? Mail to me and I'll post. As Roland Karlsson writes: SICStus prolog does. >I'm not convinced that either program should use assert or retract however. > Can you tell that to rowe@cs.nps.navy.mil, who wrote 'AI through Prolog' ? His book is full of this kind of stuff !. (He used micro-prolog.) -- Jan Derriks | AHA-TMF (H.T.S. 'Amsterdam'), jand@maestro.htsa.aha.nl | Europaboulevard 23, (or ..hp4nl!htsa!jand) | 1079 PC Amsterdam, phone: +31 20423827 | the Netherlands.