Prolog Cuts
Skip to end of metadata
Go to start of metadata
Unknown macro: {style}

cite

Unknown macro: {font-family}
Unknown macro: {table}
Unknown macro: {tr}
Unknown macro: {td}
Program
1. term2(value2).
2. term2(value3).
3. term3(value2, value4).
4. term3(value2, value5).
5. term3(value3, value6).
6. term3(value3, value7).
7. term3(value8, value8).
8. term(Value):-term2(Value).
9. term(Value):-term2(Var),term3(Var,Value).
10. term(Value):-term3(Value,Value).
Unknown macro: {td}
Unknown macro: {tr}

As mentioned previously, Prolog executes queries by attempting to unify terms with rules. When a rule turns out to be false, it backtracks and tries a new rule for the term.

As an abstract example, consider the set of rules listed on the left. On the query term(Value), it first returns value2, and by requesting more options it runs through all other possible values. We visualize this as a search tree. The query is at the top, and each level is the result of unifying a term with some rule. A node has as many children as there are rules with the same name. In this example, all branches lead to a solution, though in general some, or even all, may end in failure. Execution progresses by taking the leftmost branch. If a branch leads to failure, the interpreter backtracks to the last node with an alternative replacement.

Cuts are indicated with the operator !. These are used to prune off parts of the search tree. For instance, if we change line 8 to read term(Value):-!,term2(Value)., then branches (a) and (b) are eliminated – the only solutions found are value2 and value3. If we instead put the cut after finding a value from term2 by writing term(Value):-term2(Value),!., then (a) and (b) are pruned, and so is (c). This difference shows that a cut "freezes" the values to its left, but will backtrack to its right.

Cuts only affect the tree up to the node above where they occur. If we instead change line 3 to be term3(value2, value4):-!., then the interpreter prunes any alternative resolutions of term3 on this branch (just the one labeled (d)), but the rest of the tree remains intact.

When would you want to prune the tree? Generally it is just used to increase efficiency by preventing the interpreter from testing additional rules when it has found the only possibly correct one. In particular, if multiple rules correspond to mutually exclusive different test cases, then placing a cut after the test will prevent unnecessary inspection of the other rules.

For example, consider the program for executing a binary search. There are three contains rules, and by the second term you have determined that the other options will fail. Adding cuts in these locations would prevent unnecessary searching if the remainder of the clauses fails. The resulting code is provided below.

contains(List, Value):- even_division(_, [Value|_], List).

contains(List, Value):- even_division(_, [Center|SecondHalf], List),
Center=<Value, !, SecondHalf \= [],
contains(SecondHalf, Value).

contains(List, Value):- even_division(FirstHalf, [Center|_], List),
Center>=Value, !,FirstHalf\=[],
contains(FirstHalf, Value). 

When the original code searched for a value larger than the greatest element, it would try the first statement, fail, try the second, and succeed until the end. Once it failed, it then backtracked and tested to see if the third statement could ever be used. This means that fora list of n elements, it must call even_division n/2 times more than necessary. Adding the cuts prevents this behavior.

It is good to consider whether or not you would want to add a cut to the end of the first line. If you did so, then the program would only ever find a single instance of the value in the list. If the purpose is only to check for containment, then this is sufficient. If the program were modified to also return the index, then you would likely want to allow for the possibility that the List may contain repeats. As it is, only some repeats are found since the third rule is not used when Center==Value due to the cut in the second statement.

Labels
  • No labels