Avoiding the use of cut in Prolog absolute value predicate

Question

I have implemented the following function in prolog with the following code:

abs2(X, Y) :- X < 0, Y is -X.
abs2(X, X) :- X >= 0, !.

How can I implement this function without the use of cut ("!")?

Cement

Answer 1

There's the "hidden" cut in the if-then-else construct of Prolog:

abs2(X,Y) :- X < 0 -> Y is -X ; Y = X.

It is something of a quirk, but Prolog does not backtrack on the subgoal that forms the "premise" of an if-then or if-then-else construct. Here, if X < 0 succeeds the first try, then the choice of "then" clause over "else" clause is committed (hence the description of this behavior as a "hidden" cut).

There is more of a role for a cut in the first clause of the predicate abs2/2 as written in the question. As Nicholas points out, the cut at the end of the second clause doesn't have any effect (there are no choice points left when you get there). But as Kaarel points out, there is a choice point left open if the first clause succeeds.

So what I would have written, allowing the use of a cut, is this:

abs2(X,X) :- X >= 0, !.
abs2(X,Y) :- Y is -X.

Nicholas's comments also suggest ways to "arithmetize" the absolute value (rather than use a logic definition) and avoid "cut" that way.

Chaudoin

What you named "hidden cut" does not behave like a cut: !/0 also prevents alternative clauses from being tried, but the local commit in if-then-else does not. I therefore find this poor terminology. – Scrummage

@mat: I'd be happy to learn of better terminology. I wrote "hidden cut" as a disclosure of sorts in offering my solution avoiding the (apparent) use of cut, so the reader can judge whether my solution is valid or a "cheat". Compare the SWI-Prolog documentation for Control Predicates (Sec. 2.4.7) for an explanation of the localized commit/cut in "if-then-else". swi-prolog.org/pldoc/… – Chaudoin

Answer 2

My prolog is a bit rusty, but why do you even need the cut? If you write the predicate properly, backtracking can't succeed, so the cut is unnecessary:

abs(X, Y) :- number(X) , X <  0 , Y is -X .
abs(X, X) :- number(X) , X >= 0 .

Grendel

Your code still leaves a choice point. This choice leads to failure, but it's nevertheless considered. A cut would avoid that. – Kelsiekelso

If you know that you're dealing with integral values, you can compute ABS with a choice point by twiddling bits: www-graphics.stanford.edu/~seander/bithacks.html#IntegerAbs – Grendel

Another option is this: abs(X,Y) :- Y is sign(X) * X . (assuming that your prolog implementation supports a built-in sign/1 predicate). – Grendel

Another option: abs(X,Y) :- Y is abs(X). – Eskisehir

Answer 3

No need to use prolog-cut!

Simply write:

abs2(X,Y) :- Y is abs(X).

Anuran