Committed Choice
Pat Chkoreff
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
Chris Moss
>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.
Michel Billaud
>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 : bil...@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 Naish
>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
Fernando Pereira
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
per...@ai.sri.com
Paul Broome
repeat(Body,Until) :-
repeat,
Body,
Until,
!.
Then we can accomplish the same thing with
...
repeat(<continue condition>, <exit condition>).
-Paul
In article <82...@russell.STANFORD.EDU> per...@russell.UUCP (Fernando Pereira) writes:
:In Edinburgh-family Prolog systems, the scope of a cut is the whole
Paul Broome
bro...@brl.arpa
Chris Moss
>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.
Richard Okeefe
: : repeat,
: : { Body }
: : ( <exit condition> -> !
: : ; <continue condition> -> fail
: : ).
: 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.)
Chris Moss
>: : 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
Inst.f.Prakt.Info 1802
>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 (ulr...@vip.UUCP UUCP: ...!mcvax!tuvie!vip!ulrich)
<<please don't type "r", but mail to the adress above>>
Micha Meier
>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
Jamie Andrews
>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.
j...@lfcs.ed.ac.uk
Inst.f.Prakt.Info 1802
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),...
Pat Chkoreff
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