Node:Terminating a Backtracking Loop, Previous:Placement of Cuts, Up:The Cut

Terminating a Backtracking Loop

Cut is also commonly used in conjunction with the generate-and-test programming paradigm. For example, consider the predicate find_solution/1 defined by

find_solution(X) :-
        candidate_solution(X),
        test_solution(X),
        !.

where candidate_solution/1 generates possible answers on backtracking. The intent is to stop generating candidates as soon as one is found that satisfies test_solution/1. If the cut were omitted, a future failure could cause backtracking into this clause and restart the generation of candidate solutions. A similar example is shown below:

process_file(F) :-
        see(F),
        repeat,
            read(X),
            process_and_fail(X),
        !,
        seen.

process_and_fail(end_of_file) :- !.
process_and_fail(X) :-
        process(X),
        fail.

The cut in process_file/1 is another example of terminating a generate-and-test loop. In general, a cut should always be placed after a repeat/0 so that the backtracking loop is clearly terminated. If the cut were omitted in this case, on later backtracking Prolog might try to read another term after the end of the file had been reached.

The cut in process_and_fail/1 might be considered unnecessary because, assuming the call shown is the only call to it, the cut in process_file/1 ensures that backtracking into process_and_fail/1 can never happen. While this is true, it is also a good safeguard to include a cut in process_and_fail/1 because someone may unwittingly change process_file/1 in the future.