To cut or not to cut?
Author Message
To cut or not to cut?

Hi,

I have a question about cuts. Let's say I have this foo/1
predicate, and it's used a lot in my program:

foo( X ) :-
some_conditions( X ) ,
! ,
do_something( X ) .

foo( X ) :-
! ,                            % Should I put a cut here?
do_something_else( X ) ,
do_more_stuff( X ) ,
write( 'Virtual gibberish' ) .

My question is: should I put a cut in the last clause?
Logically, it's useless, since there's no more solutions
anyway. But if this foo/1 predicate is used a lot, would it
save some time/memory? My assumption is that when Prolog
tries this clause, it doesn't know it's the last one. So it
keeps in memory this choicepoint. Upon failure, it will try
to backtrack on foo/1. By adding this cut in the beginning
of the clause, I kind of tell Prolog that there's no more
solutions.

Any help would be appreciated.

Francois Lareau

Thu, 19 Dec 2002 03:00:00 GMT
To cut or not to cut?

Quote:

> Hi,
> I have a question about cuts. Let's say I have this foo/1
> predicate, and it's used a lot in my program:
> foo( X ) :-
>    some_conditions( X ) ,
>    ! ,
>    do_something( X ) .
> foo( X ) :-
>    ! ,                            % Should I put a cut here?
>    do_something_else( X ) ,
>    do_more_stuff( X ) ,
>    write( 'Virtual gibberish' ) .
> My question is: should I put a cut in the last clause?
> Logically, it's useless, since there's no more solutions
> anyway. But if this foo/1 predicate is used a lot, would it
> save some time/memory?

No

Quote:
> My assumption is that when Prolog
> tries this clause, it doesn't know it's the last one.

Your assumption is wrong, I think. Prolog will know it's the last one.

Quote:
> So it
> keeps in memory this choicepoint. Upon failure, it will try
> to backtrack on foo/1. By adding this cut in the beginning
> of the clause, I kind of tell Prolog that there's no more
> solutions.

Gertjan van Noord Alfa-informatica, RUG,  Postbus 716, 9700 AS Groningen
vannoord at let dot rug dot nl            http://www.let.rug.nl/~vannoord/

Thu, 19 Dec 2002 03:00:00 GMT
To cut or not to cut?

Quote:
> Your assumption is wrong, I think. Prolog will know it's the
> last one.

How can it know it's the last one? Do some compilers really
know that? I think when prolog tries a clause, it doesn't
know if there are other clauses to try.

Francois Lareau

Sat, 21 Dec 2002 03:00:00 GMT
To cut or not to cut?

Quote:
> > Your assumption is wrong, I think. Prolog will know it's
> > the
> > last one.

> How can it know it's the last one? Do some compilers really
> know that? I think when prolog tries a clause, it doesn't
> know if there are other clauses to try.

And I would add: when you do a trace, you can see prolog
(well, at least SICStus, LPA, AMZI and Open Prolog) will try
to "redo" the last clause. So it doesn't know it's the last
one.

Francois Lareau

Sat, 21 Dec 2002 03:00:00 GMT
To cut or not to cut?

Quote:

> > > Your assumption is wrong, I think. Prolog will know it's
> > > the
> > > last one.

> > How can it know it's the last one? Do some compilers really
> > know that? I think when prolog tries a clause, it doesn't
> > know if there are other clauses to try.

> And I would add: when you do a trace, you can see prolog
> (well, at least SICStus, LPA, AMZI and Open Prolog) will try
> to "redo" the last clause. So it doesn't know it's the last
> one.

A compiled prolog generally uses either a 'try', 'retry' or a 'trust'
depending this is the first, intermediate or last rule.

In some circonstances, this is not true (I mean this distingo is disabled),
for instance in debug mode, or if the rule is not compiled (assertions),
or maybe if it is 'dynamic', 'multifile', 'discontiguous',...

Maybe are you in such a case ? (you almost certainly are, at least,
in debug mode...)

HTH
--
Pascal

Sat, 21 Dec 2002 03:00:00 GMT
To cut or not to cut?

|> > > Your assumption is wrong, I think. Prolog will know it's
|> > > the
|> > > last one.
|> >
|> >
|> > How can it know it's the last one? Do some compilers really
|> > know that? I think when prolog tries a clause, it doesn't
|> > know if there are other clauses to try.
|>
|>
|> And I would add: when you do a trace, you can see prolog
|> (well, at least SICStus, LPA, AMZI and Open Prolog) will try
|> to "redo" the last clause. So it doesn't know it's the last
|> one.

Lesson number one ...
Do not judge the optimizations a Prolog system usually makes by its behaviour in
debugging mode.

Here is a simple test that can give an indication on whether Prolog
systems "know" they are executing the last clause of a predicate or not:

a :- fail.
a :- a.

?- a.

If the above query runs "forever" in non-debug mode, will you accept
that Prolog knows when it is dealing with a last clause ?

And if you are not convinced, have a look at

\bibitem{WAM-AitKaci}
H.~A\"{\i}t-Kaci.
\newblock {\em Warren's {A}bstract {M}achine: {A} Tutorial Reconstruction}.
\newblock The MIT Press, Cambridge, Massachusetts, 1991.

Cheers

Bart Demoen

Sat, 21 Dec 2002 03:00:00 GMT
To cut or not to cut?

Quote:
> Here is a simple test that can give an indication on whether
> Prolog
> systems "know" they are executing the last clause of a
> predicate or not:

>    a :- fail.
>    a :- a.

>    ?- a.

> If the above query runs "forever" in non-debug mode, will you
> accept
> that Prolog knows when it is dealing with a last clause ?

It does run forever, but how does it prove that the compiler
knows it's the last one?

In the WAM Tutorial Reconstruction
http://www.isg.sfu.ca/~hak/documents/wam.html
pages 121-127, it seems to confirm what I thought: the
compiler does not check if a clause is the last one before
trying it. It adds a choice point and upon failure it will
retry. Maybe there is something I don't understand.

My initial question was: given the following program:

foo :-
some_conditions ,
! .   % (optional)
foo :-
!     % is this cut improving performance?
other_conditions .

Is it better to put a cut in the last clause, though it's
logically useless, to avoid adding a choice point at runtime
when trying this clause? So that upon eventual failure
(let's say, in the rule that called foo/0) there will be no
attempt to backtrack on foo/0? If foo/0 is often called, it
could make a difference.

Maybe I'm just confused. But anyway, thanks for replying.

Francois Lareau

Sun, 22 Dec 2002 03:00:00 GMT
To cut or not to cut?

Quote:

> My initial question was: given the following program:
> foo :-
>    some_conditions ,
>    ! .   % (optional)
> foo :-
>    !     % is this cut improving performance?
>    other_conditions .
> Is it better to put a cut in the last clause, though it's
> logically useless, to avoid adding a choice point at runtime
> when trying this clause? So that upon eventual failure
> (let's say, in the rule that called foo/0) there will be no
> attempt to backtrack on foo/0? If foo/0 is often called, it
> could make a difference.

as many people have already told you, it does not make a difference.

--
Gertjan van Noord Alfa-informatica, RUG,  Postbus 716, 9700 AS Groningen
vannoord at let dot rug dot nl            http://www.let.rug.nl/~vannoord

Sun, 22 Dec 2002 03:00:00 GMT
To cut or not to cut?

|> > Here is a simple test that can give an indication on whether
|> > Prolog
|> > systems "know" they are executing the last clause of a
|> > predicate or not:
|> >
|> >      a :- fail.
|> >      a :- a.
|> >
|> >      ?- a.
|> >
|> > If the above query runs "forever" in non-debug mode, will you
|> > accept
|> > that Prolog knows when it is dealing with a last clause ?
|>
|>
|> It does run forever, but how does it prove that the compiler
|> knows it's the last one?

Knowing statically that it is the last clause and using this knowledge
dynamically, has no dynamic space cost (or a constant one).

Thinking that perhaps it is not the last clause and remembering this
dynamically for every activation of the last clause, has a space cost linear
in the number of activations.

That's not a complete proof of course, because you must also know whether
the system doesn't do choicepoint garbage collection from time to time.

But I am rather confident about the last point: very few Prolog systems
perform choicepoint garbage collection. I know of only one and I bet you
are not using it :-)

|> In the WAM Tutorial Reconstruction
|> http://www.isg.sfu.ca/~hak/documents/wam.html
|> pages 121-127, it seems to confirm what I thought: the
|> compiler does not check if a clause is the last one before
|> trying it.

There is no dynamic checking involved: the WAM code generator generates a
trust instruction (trustmeorelsefail) as first instruction of the last clause
(when that is statically known) and this instruction gets rid of the
choicepoint.

Cheers

Bart

Sun, 22 Dec 2002 03:00:00 GMT
To cut or not to cut?

Quote:

> |> > Here is a simple test that can give an indication on whether
> |> > Prolog
> |> > systems "know" they are executing the last clause of a
> |> > predicate or not:
> |> >
> |> >         a :- fail.
> |> >         a :- a.
> |> >
> |> >         ?- a.
> |> >
> |> > If the above query runs "forever" in non-debug mode, will you
> |> > accept
> |> > that Prolog knows when it is dealing with a last clause ?
> |>
> |>
> |> It does run forever, but how does it prove that the compiler
> |> knows it's the last one?
> Knowing statically that it is the last clause and using this knowledge
> dynamically, has no dynamic space cost (or a constant one).
> Thinking that perhaps it is not the last clause and remembering this
> dynamically for every activation of the last clause, has a space cost linear
> in the number of activations.
> That's not a complete proof of course, because you must also know whether
> the system doesn't do choicepoint garbage collection from time to time.

perhaps you are convinced if you compare the query

?- a.

with the query

?- b.

Using the program:

b :- fail.
b :- b.
b :- fail.

(use e.g. top' to see the rapidly increasing memory size of this latter
example).

Quote:
> But I am rather confident about the last point: very few Prolog systems
> perform choicepoint garbage collection. I know of only one and I bet you
> are not using it :-)
> |> In the WAM Tutorial Reconstruction
> |> http://www.isg.sfu.ca/~hak/documents/wam.html
> |> pages 121-127, it seems to confirm what I thought: the
> |> compiler does not check if a clause is the last one before
> |> trying it.
> There is no dynamic checking involved: the WAM code generator generates a
> trust instruction (trustmeorelsefail) as first instruction of the last clause
> (when that is statically known) and this instruction gets rid of the
> choicepoint.
> Cheers
> Bart

--
Gertjan van Noord Alfa-informatica, RUG,  Postbus 716, 9700 AS Groningen
vannoord at let dot rug dot nl            http://www.let.rug.nl/~vannoord

Sun, 22 Dec 2002 03:00:00 GMT
To cut or not to cut?

Quote:
> perhaps you are convinced if you compare the query

> ?- a.

> with the query

> ?- b.

> Using the program:

> b :- fail.
> b :- b.
> b :- fail.

> (use e.g. top' to see the rapidly increasing memory size of
> this latter
> example).

Ah! This is a good proof...

Quote:
> > There is no dynamic checking involved: the WAM code
> > generator generates a
> > trust instruction (trustmeorelsefail) as first instruction
> > of the last clause
> > (when that is statically known) and this instruction gets
> > rid of the
> > choicepoint.

...and this is a good explanation. And what if the code was
asserted, then? If I was to add dynamically some code, would
it be better to add a cut to the last clause?

Thanks to both of you for these good answers.

Francois Lareau

Mon, 23 Dec 2002 03:00:00 GMT
To cut or not to cut?

|> ...and this is a good explanation. And what if the code was
|> asserted, then? If I was to add dynamically some code, would
|> it be better to add a cut to the last clause?

Why don't you try this with the small predicates that were posted.

Bart Demoen

Mon, 23 Dec 2002 03:00:00 GMT
To cut or not to cut?

Quote:
> |> And what if the code  was
> |> asserted, then? If I was to add dynamically some code,
> |> would
> |> it be better to add a cut to the last clause?
> Why don't you try this with the small predicates that were
> posted.

Tired of answering my stupid questions, eh? So, you might
already know, but for those who could be interested, it's
the same for asserted predicates.

Thanks,
Francois Lareau

Tue, 24 Dec 2002 03:00:00 GMT
To cut or not to cut?

|> Tired of answering my stupid questions, eh?

I just thought I would not deprive you from the pleasure of

Cheers

Bart Demoen

Fri, 27 Dec 2002 03:00:00 GMT

 Page 1 of 1 [ 14 post ]

Relevant Pages