patch@hpldola.HP.COM (Pat Chkoreff) (03/10/89)
It seems to me that the if-then-else construct in Prolog completely eliminates the need for the cut, and is a far superior mechanism for enforcing committed choice. Am I right? Books on Prolog tend to emphasize the nuances of using the cut, but rarely discuss if-then-else. Is this due to historical reasons? - Patrick Chkoreff
cdsm@doc.ic.ac.uk (Chris Moss) (03/14/89)
In article <11500012@hpldola.HP.COM> patch@hpldola.HP.COM (Pat Chkoreff) writes: >It seems to me that the if-then-else construct in Prolog completely >eliminates the need for the cut, and is a far superior mechanism for >enforcing committed choice. Am I right? There are 2 reasons for choice of control structures in Prolog: efficiency and clarity. Certainly from a theoretical point of view (the "power" of the system) if then-else is adequate, but there are lots of reasons why it's given problems. See for instance the appendix in Ehud Shapiro's book "Algorithmic Program debugging" which uses conditionals far more than his later book "Art of Prolog". (He had an argument with David Warren and lost!). (Art of Prolog has very few cuts too). Richard O'Keefe put a powerful counterargument in his "Treatment of Cuts in Prolog Source-Level tools" paper in IEE Symposium on LP, 1985. But even he advocates cuts in some places on stylistic and efficiency grounds. >Books on Prolog tend to emphasize the nuances of using the cut, but >rarely discuss if-then-else. Is this due to historical reasons? Well for one thing there are different variations even of if-then-else! For example, does an if-then without an else fail or succeed. It appears that the Europeans on the standardization committee think it should succeed: in "Edinburgh" systems it fails. If we were to start Prolog again, I'd back Gert Smolka's proposals in "Making Control and Data Flow in Logic Programs Explicit" in the 1984 ACM Functional Programming Conference. But of course we aren't going to! Chris Moss.
billaud@geocub.greco-prog.fr (Michel Billaud) (03/16/89)
In article <11500012@hpldola.HP.COM> patch@hpldola.HP.COM (Pat Chkoreff) writes: >It seems to me that the if-then-else construct in Prolog completely >eliminates the need for the cut, and is a far superior mechanism for >enforcing committed choice. Am I right? If you restrict yourself to 'flat clauses' with no ";" in their body part : Theorem 1 Any 'flat' procedure with cut can be translated into an equivalent procedure using if-then-else instead. But if you remove the restriction, some Prolog "program schemes" with cut just *cannot* be translated into equivalent schemes with if-then-else. For example : p(X) :- g(X),( (f(X),!,fail) ; true) . Think of g as a 'generator' which produces values for X. f is a 'filter' which accepts or rejects these values. The whole thing p produces the 'stream' of the first answers of g which are rejected by f . Theorem 2: You *cannot* express such a combination of g and f without cut. Proofs Formal proofs need a formal framework (sorry for hackers .. :-) ) see Prolog Control Structures, a Formalization and its Applications, by Michel Billaud, in Programming for Future Generations Systems (?) eds Prof Fuchi & Nivat. Elsevier (Proceedings of the France-Japan Symposium on Artificial Intelligence and Computer Science Tokyo 87) [] But Prolog authors never read my papers :-) ! Michel Billaud #include 'self/advertisement' -- Michel BILLAUD : billaud@geocub.greco-prog.fr Departement d'Informatique : ...!decvax!mcvax!inria!geocub!billaud IUT "A", Universite Bordeaux I : 33405 Talence (FRANCE) : phone: 56.84.57.92 // 56.84.60.79
lee@munnari.oz (Lee Naish) (03/20/89)
In article <733@gould.doc.ic.ac.uk> cdsm@doc.ic.ac.uk (Chris Moss) writes: >There are 2 reasons for choice of control structures in Prolog: >efficiency and clarity. Certainly from a theoretical point of view >(the "power" of the system) if then-else is adequate, but there are >lots of reasons why it's given problems. See for instance the appendix >in Ehud Shapiro's book "Algorithmic Program debugging" which uses >conditionals far more than his later book "Art of Prolog". (He had an >argument with David Warren and lost!). As I understand it, the reason why the argument was lost was that *in DEC-10 Prolog* '->' is not compiled and is therefore much slower. I don't know of any other Prolog system where this is the case. In fact, -> is significantly more efficient than ! in some systems for some simple conditions. For example: ( A < B -> ... ; ...) does not create a choice point in Quintus or NU-Prolog. The equivalent code using cut does (this may not be the case forever). >Well for one thing there are different variations even of if-then-else! (and cut, as Chris has pointed out in the past) >For example, does an if-then without an else fail or succeed. It appears >that the Europeans on the standardization committee think it should >succeed: in "Edinburgh" systems it fails. I am embarassed to say that the Melbourne group only discovered this last year. In MU-Prolog and (still) in NU-Prolog (fail -> xyz) succeeds (I hope this will be changed to the standard behaviour some day). I suggest that people using {MN}U-Prolog avoid using -> without the else part. While I think its not such a good idea to change the "standard" behaviour at this stage, I think the whole construct must have been designed after a good many pints of 70 shilling on Grassmarket: 1) -> in logic means implication, or if-then, so the syntax is suggestive of logic. However, in logic false->xyz is true! 2) Making -> fail when the condition fails make -> without ; virtually useless. a->b is the same as once(a),b which is much more clear. The only common use is (a->b;c->d;otherwise->e), which behaves the same way with either semantics for ->. Also if -> succeeded when the condition failed "otherwise->" could be dropped, making the code simpler and more efficient. 3) With the non-standard semantics -> is very useful for checking error conditions and other exceptions: (var(X) -> error("Nonvar expected")),... 4) Why use ; for else? It overloads ; and makes its definition (which could be nice, simple and logical) into a non-logical mess (remember that a->b;c is ((a->b);c)). 5) What is cut meant to do inside a condition? This is a great way to break Prolog systems and when -> was defined the use or scope of ! inside contitions should have been restricted (the problem is that the -> creates a choice point, ! removes it, then -> tries to cut back to it). Lee Naish
pereira@russell.STANFORD.EDU (Fernando Pereira) (03/21/89)
In Edinburgh-family Prolog systems, the scope of a cut is the whole clause in which it appears, even it the cut is inside a conditional. This is a very useful control behavior, messy to simulate with cuts that stay inside the scope of conditionals. For example, the following is a common way of terminating a repeat/fail loop: ... repeat, ... ( <exit condition> -> ! ; <continue condition> -> fail ). I will agree with anybody that this is not a pristine example of declarative programming, but such things *are* needed in the imperfect logic-programming languages we have today. I also appreciate that we could move the cut to after the conditional with the same result, but there are more complicated situations, which I don't have the time now to discuss, in which that alternative is not available. Fernando Pereira AI Center SRI International pereira@ai.sri.com
broome@adm.BRL.MIL (Paul Broome ) (03/24/89)
Here's one alternative I've seen that's only slightly cleaner: Define
repeat(Body,Until) :-
repeat,
Body,
Until,
!.
Then we can accomplish the same thing with
...
repeat(<continue condition>, <exit condition>).
-Paul
In article <8209@russell.STANFORD.EDU> pereira@russell.UUCP (Fernando Pereira) writes:
:In Edinburgh-family Prolog systems, the scope of a cut is the whole
:clause in which it appears, even it the cut is inside a conditional.
:This is a very useful control behavior, messy to simulate with cuts
:that stay inside the scope of conditionals. For example, the following
:is a common way of terminating a repeat/fail loop:
:
: ...
: repeat,
: ...
: ( <exit condition> -> !
: ; <continue condition> -> fail ).
:
:I will agree with anybody that this is not a pristine example of
:declarative programming, but such things *are* needed in the imperfect
:logic-programming languages we have today. I also appreciate that we
:could move the cut to after the conditional with the same result, but
:there are more complicated situations, which I don't have the time now
:to discuss, in which that alternative is not available.
:
:Fernando Pereira
:AI Center
:SRI International
:pereira@ai.sri.com
Paul Broome
broome@brl.arpacdsm@doc.ic.ac.uk (Chris Moss) (03/24/89)
In article <1305@murtoa.cs.mu.oz.au> lee@munmurra.UUCP (Lee Naish) writes: >As I understand it, the reason why the argument was lost was that *in >DEC-10 Prolog* '->' is not compiled and is therefore much slower. I >don't know of any other Prolog system where this is the case. Yes, this was one reason, but the other was to do with style. You CAN make the program ugly by overuse of conditionals, destroying the essential simplicity of the Horn Clause form; evidence: excessive use of =. >2) Making -> fail when the condition fails make -> without ; virtually > useless. a->b is the same as once(a),b which is much more clear. The But certain widely distributed Prologs (Q..) don't include once, at least as a compiled option. Your alternative thus includes a metacall. I suspect the reason they don't is precisely because -> without ; is exactly equivalent as you point out. You pays your money... >5) What is cut meant to do inside a condition? This is a great way to > break Prolog systems and when -> was defined the use or scope of ! > inside contitions should have been restricted (the problem is that the > -> creates a choice point, ! removes it, then -> tries to cut back to > it). Interesting. _That's_ why Richard didn't include -> in his metainterpreter! In fact Quintus flags it as a compile-time error. We came accross that a couple of days ago comparing a metacircular interpreter I was using and Richard's (which incidentally has at least one bug in it). Chris.
ok@aucsv.UUCP (Richard Okeefe) (03/30/89)
: In article <8209@russell.STANFORD.EDU> pereira@russell.UUCP (Fernando Pereira) writes: : : repeat, : : { Body } : : ( <exit condition> -> ! : : ; <continue condition> -> fail : : ). In article <18798@adm.BRL.MIL>, broome@adm.BRL.MIL (Paul Broome ) writes: : Here's one alternative I've seen that's only slightly cleaner: Define : repeat(Body, Until) :- : repeat, : Body, : Until, : !. : Then we can accomplish the same thing with : ... : repeat(<continue condition>, <exit condition>). They don't do the same thing. When we're talking about cuts and repeats, we're in Imperative land. Consider then that the first version calls the body then the exit condition and then the continuation condition. While the second version is missing the body and calls the continuation condition before the exit condition. (Actually, the second version has mixed the body and continuation condition up.)
cdsm@doc.ic.ac.uk (Chris Moss) (04/04/89)
In article <8209@russell.STANFORD.EDU> pereira@russell.UUCP (Fernando Pereira) writes: >: : repeat, >: : { Body } >: : ( <exit condition> -> ! >: : ; <continue condition> -> fail >: : ). What I'd like to know is: is there EVER any good reason for using a repeat loop, with current Prolog technology? Repeat loops are basically of value for side effect programs such as file readers, compilers etc. They don't do any global binding of variables so they can be represented by parameterless procedures (or procedures that take only input bindings). Thus they do not produce garbage on the stack if the top level is a tail recursive procedure. Is there any way such a program can run out of memory? To make the situation more concrete, here is a toy program which simply reads a file and throws it away. But it does attempt to use permanent variables and introduce choice points, although these are then thrown away. It does NOT produce any garbage. re(File) :- see(File), tailrec, seen. tailrec :- r, !, tailrec. tailrec :- write(ok). r :- c(X),!, X\== -1. % -1 is end of file r. c(X) :- get0(X). c(X) :- fail. Can anyone produce a similar program that DOES make any one of the standard stacks overflow? Chris Moss
brock@tuvie (Inst.f.Prakt.Info 1802) (04/06/89)
In article <751@gould.doc.ic.ac.uk> cdsm@doc.ic.ac.uk (Chris Moss) writes: [...] >so they can be represented by parameterless procedures (or procedures that >take only input bindings). Thus they do not produce garbage on the stack ^^^^^^^^^^^^^^^^^^^^^^ >if the top level is a tail recursive procedure. >Is there any way such a program can run out of memory? It just depends what You mean by garbage. Try the following little program which implements the equivalent of LISP's "blam"-lists: blam(0,[]). blam(N,[L|L]) :- N > 0, M is N - 1, blam(M,L). ..., blam(32,L), assert(little_fact(L)),... Even if this would be successfully executed - is there any Prolog which can do this? Quite shure not (Might be - that some LISP-based implementation take this, but this is only a very vage speculation) However You'll also have problems when just trying to copy such a blam list. Now this was the worst case which might occur: You had a term represented by N lists which implements a term consisting of 2^N - 1 lists. In practical programs You`ll probably get only some growth nearer to k*N when You use shared variables heaviliy. Most probably when transforming graphs. So my question is just. Do You or anyone else have applications using shared variables <which are later on bound to some structures> ? :-) Ulrich Neumerkel (ulrich@vip.UUCP UUCP: ...!mcvax!tuvie!vip!ulrich) <<please don't type "r", but mail to the adress above>>
micha@ecrcvax.UUCP (Micha Meier) (04/06/89)
In article <751@gould.doc.ic.ac.uk> cdsm@doc.ic.ac.uk (Chris Moss) writes: >What I'd like to know is: is there EVER any good reason for using a >repeat loop, with current Prolog technology? > >Repeat loops are basically of value for side effect programs such as >file readers, compilers etc. They don't do any global binding of variables >so they can be represented by parameterless procedures (or procedures that >take only input bindings). Thus they do not produce garbage on the stack >if the top level is a tail recursive procedure. Chris, why do you think repeat loops are of value only for file readers, compilers etc.? When such programs do not produce garbage on the global stack then of course the repeat loops are *not* of value for them, you can use tail recursion instead, which is faster. The repeat loops are useful for programs which do create garbage on the global stack because the garbage can be disposed of without the garbage collector. It is certainly not necessary to use repeat loops if your Prolog system has a garbage collector, but failure is a very simple and efficient way of a partial garbage collection. It is also possible to write a preprocessor that adds to your tail-recursive program control primitives that make the garbage collection faster (garbage cut of Jonas Barklund), but the failure loops will still remain as a valid alternative, I think. --Micha
jha@lfcs.ed.ac.uk (Jamie Andrews) (04/07/89)
In article <674@tuvie> ulrich@vip.UUCP (Ulrich Neumerkel) writes: >blam(0,[]). >blam(N,[L|L]) :- N > 0, M is N - 1, blam(M,L). > >..., blam(32,L), assert(little_fact(L)),... I think most Prolog implementations would do this sensibly, representing this as 32 cons cells with both pointers pointing to the next element on the list, and the last cell pointing to the null list. There seems to be no reason for copying at all -- [L|L] creates one cons cell. Or am I missing something? --Jamie. jha@lfcs.ed.ac.uk
brock@tuvie (Inst.f.Prakt.Info 1802) (04/09/89)
In article <1717@etive.ed.ac.uk> jha@lfcs.ed.ac.uk (Jamie Andrews) writes: >In article <674@tuvie> ulrich@vip.UUCP (Ulrich Neumerkel) writes: >>blam(0,[]). >>blam(N,[L|L]) :- N > 0, M is N - 1, blam(M,L). >>..., blam(32,L), assert(little_fact(L)),... > I think most Prolog implementations would do this sensibly, >representing this as 32 cons cells with both pointers pointing >to the next element on the list, and the last cell pointing to >the null list. There seems to be no reason for copying at all >-- [L|L] creates one cons cell. Or am I missing something? This is true for blam/2 but it is not evident for assert/1. Chris Moss question was about possible overheads of loops which use assert/1 to save the state of computation. When assert/1-ing this highly shared structure most systems will copy it into the database, flatting it. You can estimate the effects of copying such structures with: same([],[]). same([HX|LX],[HY|LY]) :- same(HX,HY), same(LX,LY). ..., blam(N,L), same(L,K), something(K),... Ulrich Neumerkel (ulrich@vip.UUCP UUCP: ...!mcvax!tuvie!vip!ulrich)
patch@hpldola.HP.COM (Pat Chkoreff) (04/12/89)
Thanks for all the informative responses. I `lose'.
o If-then-else has some connotations which are logically bogus.
Cut doesn't pretend: it's metalogical and proud of it.
o The `filter' example:
p(X) :- g(X),( (f(X),!,fail) ; true) .
shows how the cut can be superior when you really need to get
zany.
o If-then-else is not appreciably more readable than cut: after
all, in both cases you're going to have a string of antecedent-
consequent pairs.
So I'll keep cuts in their place: down low in the system, and as scarce
as feasible. I like omnidirectional predicates when I can have them.
- Patrick Chkoreff