Other uses of cut
3.4. Other uses of cut#
Consider the following propositional program:
p:-q,r,s,!,t.
p:-q,r,u.
q.
r.
u.
This inefficiency can be avoided by putting s,! at the beginning of the body of the first clause. However, in full clausal logic the goals preceding s might supply necessary variable bindings, which requires them to be called first. A possible solution would be the introduction of an extra proposition symbol:
p:-q,r,if_s_then_t_else_u.
if_s_then_t_else_u:-s,!,t.
if_s_then_t_else_u:-u.
Just as we did with not, we can rewrite this new proposition symbol to a generally applicable meta-predicate:
if_then_else(S,T,U):-S,!,T.
if_then_else(S,T,U):-U.
Note that we can nest applications of if_then_else, for instance
if_then_else_else(P,Q,R,S,T):-
if_then_else(P,Q,if_then_else(R,S,T)).
Unfolding the definition of if_then_else yields
if_then_else_else(P,Q,R,S,T):-P,!,Q.
if_then_else_else(P,Q,R,S,T):-R,!,S.
if_then_else_else(P,Q,R,S,T):-T.
which clearly shows the meaning of the predicate: ‘if \(P\) then \(Q\) else if \(R\) then \(S\) else \(T\)’. This resembles the CASE-statement of procedural languages, only the above notation is much more clumsy. Most Prolog interpreters provide the notation P->Q;R for if-then-else; the nested variant then becomes P->Q;(R->S;T). The parentheses are not strictly necessary, but in general the outermost if-then-else literal should be enclosed in parentheses. A useful lay-out is shown by the following program:
diagnosis(Patient,Condition):-
temperature(Patient,T),
( T=<37 -> blood_pressure(Patient,Condition)
; T>37,T<38 -> Condition=ok
; otherwise -> diagnose_fever(Patient,Condition)
).
otherwise is always assigned the truth-value true, so the last rule applies if all the others fail.
not and if-then-else show that many uses of cut can be replaced by higher-level constructs, which are easier to understand. However, this is not true for every use of cut. For instance, consider the following program:
play(Board,Player):-
lost(Board,Player).
play(Board,Player):-
find_move(Board,Player,Move),
make_move(Board,Move,NewBoard),
next_player(Player,Next),
play(NewBoard,Next).
This program plays a game by recursively looking for best moves. Suppose one game has been finished; that is, the query ?-play(Start,First) (with appropriate instantiations of the variables) has succeeded. As usual, we can ask Prolog whether there are any alternative solutions. Prolog will start backtracking, looking for alternatives for the most recent move, then for the move before that one, and so on. That is, Prolog has maintained all previous board situations, and every move made can be undone. Although this seems a desirable feature, in reality it is totally unpractical because of the memory requirements: after a few moves you would get a stack overflow. In such cases, we tell Prolog not to reconsider any previous moves, by placing a cut just before the recursive call. This way, we pop the remaining choice points from the stack before entering the next recursion. In fact, this technique results in a use of memory similar to that of iterative loops in procedural languages.
Note that this only works if the recursive call is the last call in the body. In general, it is advisable to write your recursive predicates like play above: the non-recursive clause before the recursive one, and the recursive call at the end of the body. A recursive predicate written this way is said to be tail recursive. If in addition the literals before the recursive call are deterministic (yield only one solution), some Prolog interpreters may recognise this and change recursion into iteration. This process is called tail recursion optimisation. As illustrated above, you can force this optimisation by placing a cut before the recursive call.