5 Failure driven loops

In pure Mercury code, the goal Goal, fail is interchangeable with the goal fail, Goal, and Goal cannot have any side effects. As a consequence of these two facts, it is not possible to write failure driven loops in pure Mercury code. While one could try to use Mercury’s mechanisms for controlled impurity to implement failure driven loops using impure Mercury code, this is not part of the culture of Mercury programming, because failure driven loops are significantly less clear and harder to maintain than other means of iterating through a sequence. Since they are inherently imperative and not declarative, they are also very hard for compilers to optimize.

If the sequence must be generated through backtracking, then a Mercury programmer could just collect all the solutions together using the standard Mercury library predicate solutions, and iterate through the resulting list of solutions using an ordinary tail recursive predicate.

However, most Mercury programmers would prefer to generate a list of solutions directly. This can be easily done by replacing code that generates alternative solutions through backtracking, using predicates like this:

generate_solutions(In1, In2, Soln) :-
    (
        % Generate one value of Soln from In1 and In2.
        generate_one_soln(In1, In2, Soln)
    ;
        % Compute a new value for the second input.
        In2' = ....
        % Generate more values of Soln from In1 and In2'.
        generate_solutions(In1, In2', Soln)
    ).

in which the different solutions are produced by different disjuncts, with predicates in which the different solutions are produced by different conjuncts, like this:

generate_solutions(In1, In2, [Soln | Solns]) :-
    generate_one_soln(In1, In2, Soln),
    In2' = ....
    generate_solutions(In1, In2', Solns).

Unlike predicates following the previous pattern, predicates following this pattern can exploit Mercury’s determinism system to ensure that they have considered all the possible combinations of the values of the input arguments. They are also more efficient, since choice point creation is expensive.

They can be made even more efficient if the consumption of the solutions can be interleaved with their generation. For example, if the solutions are intended to be inputs to a fold (i.e. each solution is intended to update an accumulator), then this interleaving can be done like this:

generate_and_use_solutions(In1, In2, !Acc) :-
    generate_one_soln(In1, In2, Soln),
    use_solution(Soln, !Acc),
    In2' = ....
    generate_and_use_solutions(In1, In2', !Acc).