How does the '!' (cut) operator exactly work in Prolog?

Question

I'm learning Prolog and I'm having some difficulties to understand how this particular operator works. I've been told it's used to stop backtracking during recursivity, but I can't quite picture it. What would be an example in a non-declarative language like Java? Maybe if I find a parallel I'm used to I'll be able to understand it.

Thank you!

Answer 1

The cut (!/0) doesn't "stop backtracking": it simply eliminates a choice point. Consider something like this,

even_or_odd( X , even ) :- 0 =:= X mod 2 .
even_or_odd( _ , odd  ) .

For any odd integer, it has a single solution: odd. But for any even integer, it has two solutions: it will first identify as even, and on backtracking, identify as odd.

An integer's being even or odd is deterministic: 4 is not going to be even on first evaluation, and then magically become odd on reevaluation.

So, we introduce a cut to eliminate the choice point(s)/alternative(s):

identify_even_or_odd( X , even ) :- 0 =:= X mod 2 , ! .
identify_even_or_odd( _ , odd  ) .

Now, having made the determination that X is even, the cut eliminates the choice point, and essentially "prunes" the search tree: backtracking into the cut causes the entire containing predicate to fail (and continue backtracking through the solution tree).