6

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?

false
  • 10,264
  • 13
  • 101
  • 209
Name McChange
  • 2,750
  • 5
  • 27
  • 46
  • 2
    *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.* – false Oct 31 '18 at 19:55
  • 3
    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! – false Oct 31 '18 at 21:12

2 Answers2

5

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?.

mat
  • 40,498
  • 3
  • 51
  • 78
  • 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? – Name McChange Oct 31 '18 at 19:30
  • 3
    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`. – false Oct 31 '18 at 19:49
  • @false 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. – Name McChange Oct 31 '18 at 20:08
  • 2
    @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. – false Oct 31 '18 at 20:24
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

Paulo Moura
  • 18,373
  • 3
  • 23
  • 33