Control Flow in PROLOG
CUT and FAIL
In Prolog, the cut-and-fail operators are used to control the search for solutions and to prevent backtracking. Here are some examples of how cut and fail are performed in Prolog:
- Cut operator:
The cut operator, denoted by the exclamation mark (!), is used to prune the search tree and prevent backtracking. It cuts off all the alternative solutions that may exist for the current goal. Here's an example:
findMax([X],X).
findMax([H|T], Max) :- findMax(T, MaxT), H =< MaxT, !, Max = MaxT.
findMax([H|T], Max) :- findMax(T, MaxT), H > MaxT, Max = H.
In this example, findMax
is a program that finds the maximum value in a list of integers. The first rule defines the base case where the list has only one element. The second and third rules define the recursive case. In the second rule, the cut operator is used to prevent backtracking and prune the search tree. This is done when the current element H
is less than or equal to the maximum value found so far MaxT
. By cutting off the search at this point, Prolog will not consider any other elements in the list that are less than or equal to MaxT
. The third rule is used when the current element H
is greater than the maximum value found so far MaxT
.
For example, consider the following program
likes(john, mary).
likes(john, jane).
likes(jane, john).
friend(X,Y) :- likes(X,Y), likes(Y,X).
In this program, friend/2 is a predicate that determines if two people are friends based on whether they both like each other. However, this program will generate redundant solutions because likes/2 is symmetric. To eliminate redundant solutions, we can use the cut operator as follows:
likes(john, mary).
likes(john, jane).
likes(jane, john).
friend(X,Y) :- likes(X,Y), likes(Y,X), !.
In this version of friend/2, the cut operator ensures that there is only one solution for each pair of friends.
- Fail operator:
The fail operator, denoted by the keyword fail
, is used to signal that a goal has failed and that Prolog should backtrack and try another solution. Here's an example:
parent(pam, bob).
parent(tom, bob).
parent(tom, liz).
sibling(X,Y) :- parent(Z,X), parent(Z,Y), X = Y, !.
sibling(X,Y) :- fail.
In this example, sibling
is a program that determines whether two individuals are siblings or not. The first two rules define the parent-child relationship between individuals. The third rule defines the sibling relationship between individuals. It uses the cut operator to prevent backtracking and prune the search tree when a sibling pair is found. If Prolog reaches the end of the third rule without finding a sibling pair, it uses the fail operator to signal failure and backtrack to try another solution.
For example, consider the following program:
likes(john, mary).
likes(john, jane).
likes(jane, john).
dislikes(X,Y) :- likes(X,Z), likes(Y,Z), !, fail.
dislikes(X,Y).
In this program, dislikes/2 is a predicate that determines if two people dislike each other based on the fact that they do not share a common friend. The cut operator is used to prevent backtracking after finding a common friend. The fail operator is used to indicate that there are no other possible solutions once a common friend is found.
Overall, CUT and FAIL are powerful control constructs that allow for more precise control over the execution of Prolog programs. However, they should be used with care, as improper use can lead to incorrect or inefficient programs.
These are just a couple of examples of how cut-and-fail operators are used in Prolog to control the search for solutions and prevent backtracking.