Search code examples
prologprolog-cut

Does Prolog's Cut predicate execute after a true/ yes call?


Say I have the following list of literals and a cut in my query:

?- c(X), d(X), e(X), !.

if X=1 evaluates all the literals to true, does the cut, !, predicate, at the end, get called anyway or can the whole thing backtrack?

From my own experience it seems like it can't backtrack, which implies the cut predicate is called even after true or yes has been found, is that accurate?


Solution

  • Yes; although I'm not sure what you are thinking of when you say

    get called anyway

    even though its name is an exclamation mark instead of a word and it does something outside normal logic, cut is "just another predicate" ("literal") in the sense that it gets called if execution gets to it. If c(X) holds for the current value of X then d(X) is called. If that holds then e(X) is called. If that holds then ! is called.

    Using some low effort proxies for c d e:

        ?- member(X, [1,2,3,4,5]), write(X), X>2, write(X).
    
        ?- member(X, [1,2,3,4,5]), write(X), X>2, write(X), !.
    

    The first line, member chooses a value for X and binds X=1, marks a choicepoint, writes 1, fails at X>2, backtracks to the choicepoint, rebinds X=2, tries again, fails again, backtracks to the choicepoint again, rebinds X=3, now all three succeed; Prolog gives you X = 3 as a solution and the choicepoint is still there so it waits for you to ask for more solutions or cancel. If you prompt for more, it backtracks to the choicepoint, binds X=4, tries again.

    The second line does the same initially, but once it gets to X=3 the cut is called, the choicepoint from member() is removed and Prolog gives you X = 3 and finishes, no prompts. It has found a solution and pruned (cut) the search tree so it has not, and will not, explore for all possible solutions.

    Since a Prolog program can have a lot of choicepoints happening, one "cut" will not remove all of them; exactly which ones are removed by any given ! is in @brebs' link.