Prolog if-then-else constructs: -> vs *-> vs. if_/3

Question

As noted in another StackOverflow answer that I can't seem to find anymore, this pattern emerges frequently in practical Prolog code:

pred(X) :-
    guard(X),
    ...
pred(X) :-
    \+ guard(X),
    ...

and many people try to condense this to

pred(X) :-
    (guard(X) ->
    ...
    ;
    ...).

However as we all know, the arrow structure destroys choice points and isn't logical.

In Ulrich Neumerkel's and Stefan Kral's Indexing dif/2, a predicate called if_/3 is proposed that is monotonic and logical, however in the paper they mention another construct which caught my eye: *->.

The *-> construct functions exactly like the unsugared guard clause example above, and thus it seems perfect for my uses as I don't want to have a reified condition which is required by if_/3 and I don't care about extra choice points that much. If I'm not mistaken (edit: I am), it offers the same semantics as if_/3 but without the requirement of adding the "reification" to the condition predicate.

However in the SWI documentation for it, it claims that "this construct is rarely used," which seems weird to me. *-> seems to me like it's strictly better than -> when you're trying to do pure logical programming. Is there any reason to avoid this structure, or is there an even better alternative to the entire guard clause / negated guard clause pattern?

Larrabee

If I'm not mistaken, it offers the same semantics as if_/3. You are mistaken. Please refer to 2 The declarative limits of Prolog’s if-then-else, last paragraph: Even the “soft cut”-versions if/3 and (*->)/2 of SICStus and SWI respectively, exhibit the same problems as Prolog’s unsound negation. – Ambulatory

Here is a definition of if/3 (not efficient as it executes the guard twice): if(G_0, Then_0, _) :- G_0, Then_0. if(G_0, _, Else_0) :- \+ G_0, Else_0. You see the \+? It's full of impurity! – Ambulatory

Answer 1

Let's try it out! The pattern you give is:

pred(X) :-
    (    guard(X) ->
         ...
    ;    ...
    ).

I now use (*->)/2 and fill out the "..." as follows:

pred(X) :-
        (   guard(X) *->
            false
        ;   true
        ).

Further, as guard/1, I define the obviously pure predicate:

guard(a).

Now, let's ask pred/1 the most general query: Are there any solutions at all?

?- pred(X).
false.

So, according to the predicate, there is no term X such that pred(X) is true.

But that's wrong, because there is in fact such a term:

?- pred(b).
true.

In fact, pred/1 has infinitely many solutions. In such a situation, is it acceptable that the predicate states there are none at all? Sure thing, because the answer was computed extremely efficiently, is it not so?

We conclude that (*->)/2 shares an important drawback of (->)/2: It may incorrectly commit to one of the branches in cases where a different branch would be applicable if only the variables that occur in the condition were further instantiated. A predicate that depends on the instantiation of its arguments in such a way can never be pure, because it counteracts the monotonic reasoning we expect to be applicable to pure logic programs. In particular, from a logical perspective, since pred(b) holds, we expect that pred(X), which is a generalization of pred(b), must not fail. Once this property breaks, you can no longer apply declarative debugging and other important approaches that let you more easily understand, reason about and manage Prolog programs, and which constitute a major attraction of declarative programming in the first place.

The question you mentioned is probably What uses does if_3/ have?.

Expansive

Okay, I get it now. It seems to me that if we made \+/1 work in the same way as dif/2 (that is, it imposed a constraint that a certain expression will never be proven), we could get proper behavior out of *-> by making it such that if the test clause fails (for example guard(X)), it introduces a constraint \+guard(X) and we could avoid the whole runaround of reification for if_/3 clauses, no? – Larrabee

Please note that to make (\+)/1 work in the same way as dif/2 is tantamount to constructive negation. You find a discussion on this in 7 General reification. At least from the example given, general reification is much more costly compared to the "whole runaround" of if_/3. – Ambulatory

@Ambulatory Awesome, thanks for the tip. It seems like we can accomplish pure behavior by changing the original example to have freeze(X, \+guard(X)), and this looks like it's working the same as the if_/3 form. I'm not sure of the performance implications of this though. – Larrabee

@NameMcChange: Depending on the very precise meaning of guard/1, you may need when(ground(X), \+ guard(X)) or something in between. That's exactly what makes constructive negation so expensive. You need more or less a meta-interpreter that watches guard/1's behaviour. – Ambulatory

Answer 2

The usually named soft-cut control construct is available in several Prolog systems. CxProlog, ECLiPSe, JIProlog, SWI-Prolog, and YAP provide it as both a *->/2 predicate and infix operator. Ciao Prolog, SICStus Prolog, and YAP provide an if/3 predicate with the same semantics.

My main use of this soft-cut control construct is in the implementation of coinduction in Logtalk, where it plays a critical role. Outside of this case, I rarely use it.

The ->/2, on the other hand, it's widely used. The implicit cut in the if part is local to the construct and its usage avoids, as in your example, trying to prove the guard twice, which can be computationally expensive. It may not be pure but, as with the cut, as long as you're fully aware of its pros and cons, it's a useful control construct.

P.S. Logtalk provides unit tests for this control construct for the *->/2 variant at https://github.com/LogtalkDotOrg/logtalk3/tree/master/tests/prolog/control/soft_cut_2_3 and for the if/3 variant at https://github.com/LogtalkDotOrg/logtalk3/tree/master/tests/prolog/control/if_3

Impellent