Introduction to Prolog cut
Prolog cut is a goal written as in ! which will always succeed but can’t be backtracked. Cut in Prolog can prevent unnecessary backtracking, which includes finding extra solutions and avoiding unnecessary computations in Prolog. This cut in Prolog should be used sparingly, as users insert cuts in an experimental manner into code that does not work as required. If the user does this, and when debugging gets completed, the user should explain the need and effect of each cut used; hence, the Prolog cut has to be commented. Here we shall see what cut is and how it has to be used with few examples.
Here is the syntax required to represent cut,
For e.g., let us consider two elements and find out the max among the two. I Will check below two conditions,
If A > B, then Max := A
If A <= B, then Max:= B
So above two statements are exclusive, which says when one of the conditions is true, the other statement would be automatically false. So in such kinds of cases, we can use cut.
max(A,B,A) := A >= B, !.
max(A,B,B) := A < B.
max_find(A,B,Max) := A >= B, !, Max = A; Max = B.
Before getting into actual examples of cut, along with backtracking. There are few examples which look the same but, with backtracking, will not perform as required.
max(A, B, A);-A>B.
Here we search for clauses from ‘top to bottom manner. Thus, if A is less than or equal to B, the second clause will be applicable.
In the above example, first, two arguments value 4 and 3, and when the above-mentioned rule is tested with 4 and 3, the result follows.
So now, if a user is forced to backtrack, the second clause has to be examined and generate an incorrect answer.
Hence to get the perfect result in cases of unwanted backtracking, we use to cut, represented by !. In the body of the rule, when cut ! is executed for the first time on the goal, it will succeed. As the further evaluation of the above example will always fail, backtracking is cut to avoid this.
Examples of Prolog cut
Given below are the examples of prolong cut:
Prolog cut to find the maximum element among two numbers.
max(A, B, A) :- A>B, !.
max(A, B, B).
:- max(4, 1, R), writeln(R).
Prolog cut for Addition of integers from 1 to given integer.
add(1, 1) :- !.
add(A, B) :- A1 is A-1, add(A1, B1),
B is B1+A.
:- add(10, R), writeln(R).
Prolog cut to find out if an integer is negative, positive, or a zero.
integerType(0, zero) :- !.
integerType(A, negativeInteger) :- A<0, !.
:- integerType(-6, A), writeln(A).
If integer is positive, as, integerType(6, A), writeln(A).
If integer is a zero, as, integerType(0, A), writeln(A).
Prolog cut “!” always succeeds immediately; it has a disadvantage. Once the statement is satisfied, the program will disallow backtracking or backtracking and apply different clauses of the same predicate to satisfy the goal.
- The cut goal will succeed when it is a current goal, and its derivative tree is trimmed of other choices and include a derivative tree where the cut was actually introduced in the sequence of goals.
- ! acts as a marker, beyond which prolog will not go. All choices made to cut are set and treated as though these are only the possible ways.
- If a user gets to move far in the clause, need not backtrack and try another choice to prove the goal, or try another way of satisfying the subgoals that were proved for this goal, as the goal cut “!” satisfies immediately.
- Prolog cut can be used to improve the efficiency of search in prolog by reducing Search Space.
- Prolog cuts can be used to remove unwanted answers.
- Prolog cut can be generally used to tell prolog that it has found the right rule for a particular goal. It tells the prolog system to fail a particular goal immediately without even trying for any alternate solutions.
- It will terminate the generation of alternative solutions.
Cut can be classified to 2 types, i.e., green cut and Red cut.
- Green cut: It will affect the procedural meaning of the program but does not affect the declarative meaning. Therefore, it does not affect the readability of the program and is mainly used to avoid any wasted computations.
- Red cut: It affects the program’s declarative meaning and the procedural meaning of the program. It will affect the program’s readability, is used to avoid any wasted computations, and introduces semantics. If Red cut is not used cautiously, it can affect the output in an arbitrary manner.
Advantages and Disadvantages
- Prolog cut is more efficient; interpreter will not process any unnecessary branches in unification tree.
- Prolog cut will save memory, i.e., interpreter won’t allocate space for tree nodes for those not unified.
- Prolog cuts will create side effects that will change the way of backtracking.
- It makes place markers of some of the goals inaccessible.
With this, we shall conclude the topic ‘Prolog cut’. We have seen the cut, how it is implemented, and the logic behind it. We have also seen its syntax “!” and few examples of backtracking without cut and how backtracking can be avoided with the cut. Finally, we have also seen some of the uses of cut and also listed out a few advantages and disadvantages of cut. Thanks! Happy Learning!!
This is a guide to Prolog cut. Here we discuss the Examples and the uses of Prolog cut and also listed out a few advantages and disadvantages of cut. You may also have a look at the following articles to learn more –