jonasn@ttds.UUCP (Jonas Nygren) (07/29/88)
Maybe it's presumptuous of a novice Prolog programmer like myself to come with suggestions on how to improve the language but somehow you have to find out if your'e dead wrong or if your ideas have any substance. Here we go. When trying to write procedural code for a simple curvplotting routine I often encountered problems with backtracking over system-calls. The remedy for this was code like: a :- !, b, !, c, !, d, !, e, !. to avoid backtracking of goals a,b,c,d,e but this looks rather awkward. If you instead could write something like: a :- !!, b, c, d, e. with the same effect it wouldn't look to bad, I call it the double-cut. Naturally the double-cut could be placed later in the goal chain, e g: a :- b, c, !!, d, e. to achieve the equivalence of: a :- b, c, !, d, !, e, !. What do you think of the double-cut: 1 is it any good? 2 are there any Prolog-variants with similar functionality? 3 would it provide means for the Prolog-implementor to do more optimization than without it? 4 is there a better way to achieve the same result? /jonas
ok@quintus.uucp (Richard A. O'Keefe) (07/30/88)
In article <1162@ttds.UUCP> jonasn@ttds.UUCP (Jonas Nygren) writes: >When trying to write procedural code for a simple curvplotting routine >I often encountered problems with backtracking over system-calls. The >remedy for this was code like: > a :- !, b, !, c, !, d, !, e, !. >to avoid backtracking of goals a,b,c,d,e but this looks rather awkward. Forgive me, but I cannot imagine this cropping up. Why do you WANT to prevent backtracking over system-calls? You can backtrack over read/1, write/1, var/1, assert/1 &c all you like, it doesn't hurt. As a general rule, code with side-effects should be determinate, so backtracking over it will do nothing at all. (retract/1 is an exception, but I doubt that anyone would commend as an example to follow.) Please let's see a real example of where you think you need to do this.
gooley@s.cs.uiuc.edu (08/01/88)
Some debuggers on some systems (C-Prolog is one, I think) show apparent retries of deterministic system calls. Might this be misleading people into thinking that cuts are needed to prevent such retries in actual execution? Mark. Gooley, gooley@s.cs.uiuc.edu
ok@quintus.uucp (Richard A. O'Keefe) (08/02/88)
In article <208500002@s.cs.uiuc.edu> gooley@s.cs.uiuc.edu writes: >Some debuggers on some systems (C-Prolog is one, I think) show apparent >retries of deterministic system calls. Might this be misleading people >into thinking that cuts are needed to prevent such retries in actual >execution? "Four-port" debuggers are _supposed_ to show "redo"s of built-in predicates. As you can easily determine by writing e.g. my_abolish(F, N) :- ( write(call), nl, fail ; true ; write(fail), nl, fail ), abolish(F, N), ( write(exit), nl, fail ; true ; write(redo), nl, fail ). and doing | ?- my_abolish(foo, 10), foo = 10. the "redo"s are _happening_, so naturally they get shown! (I get four lines of output: "call", "exit", "redo", "fail".) In Edinburgh-style debuggers, it is important to distinguish between REDO which is what happens of itself when something downstream fails, and RETRY which is what happens when you give a r)etry command, and involves re-executing a goal from the start. ReTRYing a command will indeed cause it to happen again, e.g. | ?- write(retry), fail. % in trace mode (3) 0 Call (built_in): write(retry) ? retry (3) 0 Exit (built_in): write(retry) ? r %-----------------------------------------------------^ explicit reTRY [Debugger: retry goal] (3) 0 Call (built_in): write(retry) ? %----------------^^^^ restarted this goal from the beginning retry (3) 0 Exit (built_in): write(retry) ? (3) 0 Redo (built_in): write(retry) ? %----------------^^^^ reDO caused by downstream failure (3) 0 Fail (built_in): write(retry) ? %----------------^^^^ immediately fails without having done anything more no Cuts not only aren't needed to prevent retries, they can't prevent them. But a debugger should not retry a goal unless you explicitly tell it to. Would it be clearer if the "redo" port were renamed to "Next" (short for "please give me your next solution"? (C Prolog actually calls this port "Back", I think, because the debugger isn't _quite_ a four-port one.)
micha@ecrcvax.UUCP (Micha Meier) (08/08/88)
In article <227@quintus.UUCP> ok@quintus.UUCP (Richard A. O'Keefe) writes: >"Four-port" debuggers are _supposed_ to show "redo"s of built-in predicates. >... >Would it be clearer if the "redo" port were renamed to "Next" (short for >"please give me your next solution"? (C Prolog actually calls this >port "Back", I think, because the debugger isn't _quite_ a four-port one.) I think it would be interesting if people would report about their experiences with real four-port debuggers - is it really necessary to show REDO of deterministic calls? I always get lost when the system backtracks a lot, usually the important information disappears from the screen. Normally, I know which call is the most recent one that has a choice point and it is tiring to get redo's I'm not interested in. I suggest that the REDO ports correspond only to calls with a choice-point left, deterministic calls would only have two ports, CALL and EXIT. By showing only the call with an active choice-point it is clear that all the calls inbetween have failed and they cannot be resatisified. The only objection I can see is that one might not know where exactly is the REDO port that eventually exits, when all the parent calls are not shown. The solution is simple, however - just look at the ancestors of the given call (using the debugger option). This actually means that if there is potentially a lot of data to be shown, it is shown only on demand, not by default. Such a scheme is simpler both for the user and for the implementor (especially for tracing compiled code). (Btw, are there Prologs around which can trace compiled code? We'd like to share some experiences on this topic.) --Micha
jonasn@ttds.UUCP (Jonas Nygren) (08/08/88)
In a previous article I suggested a new language primitive for Prolog,
the double-cut with the following semantics:
a :- b, c, !!, d, e.
to achieve the equivalence of:
a :- b, c, !, d, !, e, !.
Below are most of the comments, in short, I recieved, followed by a
final comment from me where I try to state my case.
-------------
2 are there any Prolog-variants with similar functionality?
From: "Brad Miller" <miller@ACORN.CS.ROCHESTER.EDU>
>From the RHET user manual (tr 238, university of rochester)
\hornfnitem{And*}{$<$Form$>$*}{New\\Current Status: Untested} A macro form
for \HC{AND [CUT] Form1 [CUT] Form2 \ldots [CUT] FormN}. That is, any
backtracking\index{backtracking}\ needed at all inside of the AND* causes it
to fail.
------------------
From: Peter Reintjes <pbr@mcnc.org>
............ It is almost never
necessary -- no that is too mild -- it is never *necessary*
< -- to have more than one cut per clause -- >,
and you are right that it looks messy.
Richard O'Keefe has written a very good little paper on
the correct use of cuts. ..........
-----------
>From: ok@quintus.uucp (Richard A. O'Keefe)
Forgive me, but I cannot imagine this cropping up. Why do you WANT to
prevent backtracking over system-calls? You can backtrack over read/1,
write/1, var/1, assert/1 &c all you like, it doesn't hurt. As a general
rule, code with side-effects should be determinate, so backtracking over
it will do nothing at all. (retract/1 is an exception, but I doubt that
anyone would commend as an example to follow.)
Please let's see a real example of where you think you need to do this.
>> SEE example below!
----
>From: gooley@s.cs.uiuc.edu
Some debuggers on some systems (C-Prolog is one, I think) show apparent
retries of deterministic system calls. Might this be misleading people
into thinking that cuts are needed to prevent such retries in actual
execution?
---------
>From: lang@zeta.PRC.Unisys.COM (Francois-Michel Lang)
This could also be a "problem" for when debuggers show apparent
retries of deterministic user-defined predicates.
<-- examples -->
In the second example, it looks like the cut has saved some work,
whereas it really hasn't.
---------
My comments to the response :
Well somebody else have had the same thought (rochester above) before me and
I still have to wait for an original idea. The reason behind the double-cut
suggestion wasn't performance and it wasn't induced by trace or debug output.
Rather it was triggered by the code I had to construct in order to make my
program work correct.
Instead of inventing my own example I choose to base it on an example most of
you have seen, the reconsult example in Clocksin & Mellish. I have done some
smaller modifictions to the code. After this follows the same example
but with the use of the double-cut.
myreconsult(File) :-
retractall(done(_)),
assert(done(1)),
seeing(Old),
see(File),
repeat,
read(Term),
try(Term),
seen,
see(Old),
!.
try(X) :- is_eof, !.
try((?- ...Goals)) :- !, do_call(Goals), fail.
try(Clause) :-
head(Clause,Head),
record_done(Head),
assertz(Clause),
fail.
do_call([]) :- !.
do_call([G|Goals]) :- call(G), do_call(Goals), !.
record_done(Head) :- done(Head), !.
record_done(Head) :-
functor(Head,Func,Arity),
functor(Proc,Func,Arity),
asserta(done(Proc)),
retractall(Proc),
!.
head((A:-B), A) :- !.
head(A,A).
The cuts in 'do_call','record_done' and 'head' are due to the fail in 'try'
which means that the complexity of 'try' (2nd & 3rd clause) has propagated to
their subgoals. Using the doubel-cut as proposed would allow us to limit
the complexity to the clause where it arises:
dc_try(X) :- is_eof, !!. % Just for symmetry
dc_try((?- Goals)) :- !!, dc_do_call(Goals), fail.
dc_try(Clause) :- !!,
dc_head(Clause,Head),
dc_record_done(Head),
assertz(Clause),
fail.
dc_do_call([]).
dc_do_call([G|Goals]) :- call(G), dc_do_call(Goals).
dc_record_done(Head) :- done(Head).
dc_record_done(Head) :-
functor(Head,Func,Arity),
functor(Proc,Func,Arity),
asserta(done(Proc)),
retractall(Proc).
dc_head((A :- ...B), A).
dc_head(A,A).
In this code no cuts are needed in 'dc_do_call', 'dc_record_done' or
'dc_head' and the fail-complexity is totally contained in 'dc_try'.
Mr O'Keefe it's not a question of necessity but of beauty and functionality.
In the last example the number of cuts has actually diminished with use of
the double-cut and the code is 'cleaner' and easier to understand, I believe.
I don't know if I have been able to show how the double-cut could benefit
Prolog but I will not carry my 'campaign' further, this is my last entry on
the double-cut.
Jonas Nygrenok@quintus.uucp (Richard A. O'Keefe) (08/10/88)
In article <609@ecrcvax.UUCP> micha@ecrcvax.UUCP (Micha Meier) writes: >In article <227@quintus.UUCP> ok@quintus.UUCP (Richard A. O'Keefe) writes: >>"Four-port" debuggers are _supposed_ to show "redo"s of built-in predicates. >>... >>Would it be clearer if the "redo" port were renamed to "Next" (short for >>"please give me your next solution"? (C Prolog actually calls this >>port "Back", I think, because the debugger isn't _quite_ a four-port one.) > > I think it would be interesting if people would report about their > experiences with real four-port debuggers - is it really necessary > to show REDO of deterministic calls? Well, Quintus' debugger is a real four-port debugger, if ever there was one. There is an 'x' command (as there was in DEC-10 Prolog) to take you to the next "real" choice-point. I for one am profoundly grateful for the REDO port, not just for the symmetry, but because it gives me a stopping place where I can issue a r)etry command. I would LOATHE having re-execute large chunks of the tree to get back to a particular goal just because someone cleverly decided that because it was determinate I should never be able to get back to it again. What I'm getting at is this: suppose I have a predicate p(~~) :- q(~~), r(~~). and in a particular case q(~~) succeeds, but delivers the wrong answer, so that r(~~) fails. We see something like this: CALL p(~~) c % creep CALL q(~~) s % skip EXIT q(~~) c % creep CALL r(~~) s % skip FAIL r(~~) c % oh dear, creep back to previous goal REDO q(~~) r % retry q ~a message saying that the debugger is going to retry~ CALL q(~~) s % now creep into q Since I take pains to make my code determinate whenever that is appropriate, if the REDO port did not appear on q, I would have lost a large chunk of my tree and would have to spend several painful minutes reconstructing it. r)etry is one of the most powerful features of four-port debuggers. Let's not cripple it, please! > (Btw, are there Prologs around which can trace compiled code? > We'd like to share some experiences on this topic.) How do you mean "trace"? Quintus Prolog can put spypoints on compiled code. If you put a spypoint on each of your predicates, it is pretty much the same as tracing interpreted code. The ALS Prolog debugger operates on compiled code (because there isn't anything else in ALS Prolog). The LOGIX system will trace compiled FCP (if I've understood this correctly, it does so by applying source-to-source transformations). I don't think any of these three systems will let you look at the stack of code that wasn't expecting to be looked at, is that what you had in mind?
ok@quintus.uucp (Richard A. O'Keefe) (08/10/88)
In article <1164@ttds.UUCP> jonasn@ttds.UUCP (Jonas Nygren) provides an example which explains why he wanted double-cut. In this message, I go through that example and show why it does not need the double-cut. >Instead of inventing my own example I choose to base it on an example most of >you have seen, the reconsult example in Clocksin & Mellish. I have done some >smaller modifictions to the code. .. > >myreconsult(File) :- > retractall(done(_)), > assert(done(1)), %<-- This seems to be a mistake > seeing(Old), > see(File), > repeat, > read(Term), > try(Term), > seen, > see(Old), > !. The "assert(done(1))" is not present in Clocksin & Mellish, and doesn't seem to accomplish anything. (Since done(Skel) is used to record that a predicate has been loaded, it can be argued that assert(done(1)) is in some sense ill-typed. If there is some Prolog system which is so very badly broken that it _needs_ a dummy clause, assert(done(fail)) might be slightly better taste. Best of all, don't use broken tools.) Apart from that, the code is verbatim from Clocksin & Mellish. They have the cut in the wrong place. You should always put the cut of a repeat loop as early as possible. reconsult(File)) :- retractall(done(_)), seeing(Old), see(File), repeat, read(Term), try(Term), !, seen, see(Old). >try(X) :- is_eof, !. >try((?- ...Goals)) :- !, do_call(Goals), fail. >try(Clause) :- > head(Clause,Head), > record_done(Head), > assertz(Clause), > fail. >do_call([]) :- !. >do_call([G|Goals]) :- call(G), do_call(Goals), !. OUCH! What IS this? The code in Clocksin & Mellish was try((?-Goals)) :- !, call(Goals), !, fail. (Which isn't quite what Prolog is supposed to do, but we'll get to that.) Assuming that there is a Prolog system which reads the query ?- p(X), q(X) as ?-(...([p(X),q(X)])), which is a strange thing for it to do, we shouldn't need the cuts in do_call, but should write ... try((?- ... Goals)) :- !, call_list(Goals), !, fail. ... call_list([]). call_list([Goal|Goals]) :- call(Goal), call_list(Goals). Note that by putting the cut where it belonged (which is where C&M put it), we have ended up with a much more useful predicate: call_list/1 is more generally useful than do_call/1. >record_done(Head) :- done(Head), !. >record_done(Head) :- > functor(Head,Func,Arity), > functor(Proc,Func,Arity), > asserta(done(Proc)), > retractall(Proc), > !. Note that the cut at the end of the second clause here is utterly and completely useless: the clause is determinate anyway! >head((A:-B), A) :- !. >head(A,A). >The cuts in 'do_call','record_done' and 'head' are due to the fail in 'try' The cut in head/2 has nothing whatsoever to do with the fail in try/1. That cut is needed because head/2 is a disguised if->then;else : head((Head :- Body), Head). head(Unit, Unit) :- Unit ~= (_ :- _). There are two cuts in record_done/1. As we just saw, one of them is totally pointless. The other one is again implementing if->then;else: record_done(Head) :- done(Head). record_done(Head) :- \+ done(Head), same_functor(Head, Skel), retractall(Skel), assert(done(Skel)). Efficiency is not a concern here, so we might as well leave it in if-then-else form. We saw that the two cuts in do_call/2 were in the wrong place (actually, the first of them accomplishes nothing) and should be replaced by a single cut in try/3. >which means that the complexity of 'try' (2nd & 3rd clause) has propagated to >their subgoals. Using the double-cut as proposed would allow us to limit >the complexity to the clause where it arises: We've seen that this conclusion is false. [Pause to check through various Prolog manuals.] The ... and list appear to come from AAIS Prolog. **UGH**! Page 139 of the AAIS manual says that read/1 returns the atom 'end_of_file' at the end of a file, so we have that much Edinburgh compatibility. Strictly speaking, the definition in Clocksin & Mellish is incorrect: if a query in a file fails, a Prolog system is supposed to print a warning message. So we can write reconsult/1 thus: reconsult(File)) :- retractall(done(_)), seeing(Old), see(File), repeat, % repeat and cut form an inseparable read(Term), % pair of brackets, *never* have a process(Term), % repeat-loop without its cut. !, seen, see(Old). process(end_of_file) :- !. % This is a guard/commit cut process((?- ... Goals)) :- !, % This is a guard/commit cut ( call_list(Goals) -> true % Execute the goals, but if they fail ; write(user_output, 'Command failed: '), writeq(user_output, (?- ... Goals)), nl(user_output) ), fail. process(Clause) :- clause_parts(Clause, Head, Body), maybe_retractall(Head), assertz(Clause), fail. call_list([]). call_list([Goal|Goals]) :- call(Goal), call_list(Goals). clause_parts((Head :- Body), Head, Body). clause_parts(Unit, Unit, true) :- Unit \= (_ :- _). maybe_retractall(Head) :- done(Head). maybe_retractall(Head) :- \+ done(Head), functor(Head, F, N), functor(Skel, F, N), same_functor(Head, Skel), retractall(Skel), assert(done(Skel)). Summary: one repeat-fail-! loop (avoidable by using recursion) one guard/commit cuts (due to the defaulty input representation, avoidable in the general case by elementary data structure design) one if->then;else due to reconsult's idiosyncratic rules about queries in files one if-then-else due to the defaulty representation of clauses one if-then-else required to implement the rule "don't clear out a predicate if you have already seen it". Not *ONE* of these cuts is required "to prevent backtracking over builtins", and in *NONE* of these cases is the double-cut required or even useful. >In this code no cuts are needed in 'dc_do_call', 'dc_record_done' or >'dc_head' and the fail-complexity is totally contained in 'dc_try'. >Mr O'Keefe it's not a question of necessity but of beauty and functionality. >In the last example the number of cuts has actually diminished with use of >the double-cut and the code is 'cleaner' and easier to understand, I believe. This is wrong. dc_head is simply incorrect as it stands. According to the code as Nygren wrote it, the head of (p :- q) is (_ :- _). Oh, it _also_ says that the head is p, but it _will_ deliver the wrong answer if given a chance. Similarly, dc_record_done is quite happy to clear out a predicate a second time (and add done(...) a second time to the data base), if it is given the chance. These operations can no longer be read on their own: to understand how dc_head or dc_record is supposed to work, you have to check EVERY place in the program that calls them, to make sure that there is a cut following (or even obscurer, preceding in the guise of a double-cut). I think that the code as I wrote it is much clearer. In particular, you do not have to examine the callers of clause_parts/3 to see that it is determinate. To paraphrase the Bible, parents should not be cut for the sins of their children, but each clause should be cut (if at all) for its own sins.