Next: , Previous: FailLoops, Up: Top   [Contents]


6 Cuts and indexing

The Prolog cut operator is not part of the Mercury language.

Mercury allows if-then-elses to be written not just as ‘C -> T ; E’, but also as ‘if C then T else E’. In Mercury, an if-then-else prunes away either the ‘else’ goal (if the condition succeeded) or the ‘then’ goal (if the condition failed), but if there are multiple solutions to the condition, they will all be found on backtracking, and the ‘then’ goal will be executed for each of those solutions. By contrast, an if-then-else in Prolog prunes away all solutions of the condition except the first.

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.


Next: , Previous: FailLoops, Up: Top   [Contents]