[mercury-users] How did Mercury do away with the cut?
Fergus Henderson
fjh at cs.mu.OZ.AU
Fri Jul 6 01:26:31 AEST 2001
On 05-Jul-2001, Terrence Monroe Brannon <tmbranno at oracle.com> wrote:
>
> I always found the cut to be a confusing part of Prolog. I was
> wondering how Mercury managed to eliminate the necessity for this
> predicate.
Partly by doing what cut is used for automatically, and partly by
replacing uses of cut with alternative, much more well-behaved, constructs.
Mercury's automated replacements for cut include clause indexing,
automatic pruning, and determinism checking/inference. Alternative
constructs that can be used instead of cut include if-then-else,
committed choice nondeterminism, and `promise_only_solution'.
1. Indexing.
The Mercury compiler does type, mode and determinism analysis of
Mercury programs. Using the information provided by these analyses,
the Mercury compiler is able to perform very good "indexing" of
procedures with multiple clauses. Lacking mode information, Prolog
compilers generally only index on the top-level functor of the first
argument, whereas the Mercury compiler will do indexing on any
argument, or any set of arguments, and can also index on sub-terms of
arguments.
2. Automatic pruning.
If a goal has no output arguments, then it can only succeed or fail,
and there's no point having it succeed twice. In such situations,
the Mercury compiler will automatically prune away any solutions
after the first.
3. If-then-else.
In Prolog, cut is often (mis-)used as a way of writing if-then-else.
Prolog has an if-then-else construct which can be used instead,
but some Prolog programmers prefer to use cut, for reasons that
I have difficulty understanding and definitely don't agree with.
In Mercury, you have to use if-then-else in this situation,
so in a sense, Mercury enforces good style.
Note that Mercury's if-then-else is also much better behaved than
Prolog's. Prolog's if-then-else always commits to the first solution
of the condition, which gives it many of the same problems as cut.
Mercury's if-then-else is quite capable of returning multiple
solutions for the condition, on backtracking, if the condition
happens to be non-deterministic.
4. Committed choice nondeterminism.
Committed choice nondeterminism can be used when you only need
one solution to a goal. If a goal is called in a context which
only requires one solution, e.g. from `main', or from a goal
with no output arguments (see 2 above), that goal can have
determinism `cc_nondet' or `cc_multi'. Disjunctions inside
goals with committed choice determinism are treated specially.
In such cases, the compiler will automatically commit to a
disjunct (pruning away any other disjuncts in the disjunction)
as soon as none of the remaining goals in the disjunct can fail.
Information about which goals can fail is obtained during
determinism analysis.
Note that goals with multiple clauses are treated as disjunctions.
5. `promise_only_solution'.
In some cases, a goal may have at most one solution, but will
look to the compiler as though it may have more than one
solution; if there's more than one computation path which might
suceed, the compiler's determinism inference can't tell when
the answers obtained via those different computation paths are
guaranteed not to differ. In such cases, you can use
`promise_only_solution' to tell the compiler that for any given
values of the input arguments, all solutions returned by the
procedure will be equal. This allows you to introduce
committed choice nondeterminism, which leads to automatic
pruning (see 4 above).
> In eliminating it, is it still possible to make programs semantically
> equivalent to Prolog in about the same amount of code?
The short answer is yes.
--
Fergus Henderson <fjh at cs.mu.oz.au> | "I have always known that the pursuit
The University of Melbourne | of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh> | -- the last words of T. S. Garp.
--------------------------------------------------------------------------
mercury-users mailing list
post: mercury-users at cs.mu.oz.au
administrative address: owner-mercury-users at cs.mu.oz.au
unsubscribe: Address: mercury-users-request at cs.mu.oz.au Message: unsubscribe
subscribe: Address: mercury-users-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------
More information about the users
mailing list