[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