6 Cuts and indexing

The Prolog cut operator is not part of the Mercury language. Most Prolog code that uses cuts should probably be translated into Mercury using if-then-elses.

In both Prolog and Mercury, the behavior of an if-then-else ‘C -> T ; E’ depends on whether the condition ‘C’ has any solutions. If it does, then they both execute the then-part ‘T’; if it does not, then they both execute the else-part ‘E’. However, Prolog and Mercury differ in what they do if the condition has more than one solution.

In most versions of Prolog, if the condition of an if-then-else has more than one solution, the if-then-else throws away all its solutions after the first. The way this is usually implemented is that after the condition generates its first solution, and before execution continues to the then-part goal with the bindings in that first solution, the Prolog implementation cuts away all the choice points in the condition. This prevents backtracking into the condition, which thus cannot generate any of its other solutions.

Mercury does not prune away later solutions in conditions. If the condition has more than one solution, Mercury will execute the then-part goal on every one of them in turn, using the usual rules of backtracking.

Mercury allows if-then-elses to be written not just as ‘C -> T ; E’, but also as ‘if C then T else E’. These two syntaxes have identical semantics.

Prolog programs that use cuts and a ‘catch-all’ clause should be transformed to use if-then-else in Mercury.

For example

p(this, ...) :- !,
    ...
p(that, ...) :- !,
    ...
p(Thing, ...) :-
    ...

should be rewritten as

p(Thing, ...) :-
    ( Thing = this ->
        ...
    ; Thing = that ->
        ...
    ;
        ...
    ).

The Mercury compiler does much better indexing than most Prolog compilers. Actually, the compiler indexes on all input variables to a disjunction (separate clauses of a predicate are merged into a single clause with a disjunction inside the compiler). As a consequence, the Mercury compiler indexes on all arguments. It also does deep indexing. That is, a predicate such as the following will be indexed.

p([f(g(h)) | Rest]) :- ...
p([f(g(i)) | Rest]) :- ...

Since indexing is done on disjunctions rather than clauses, it is often unnecessary to introduce auxiliary predicates in Mercury, whereas in Prolog it is often important to do so for efficiency.

If you have a predicate that needs to test all the functors of a type, it is better to use a disjunction instead of a chain of conditionals, for two reasons. First, if you add a new functor to a type, the compiler will still accept the now incomplete conditionals, whereas if you use a disjunction you will get a determinism error that pinpoints which part of the code needs changing. Second, in some situations the code generator can implement an indexed disjunction (which we call a switch) using binary search, a jump table or a hash table, which can be faster than a chain of if-then-elses.