How can I simulate a soft cut in Prolog?

Question

How can I simulate a soft cut I *-> T; E in ISO Prolog? I has side effects, so I can not call it multiple times.

Except for the last requirement, I think the following definition works:

if_(I, T, E) :-
    not(not(I)) ->
    call((I, T));
    call((not(I), E)).

(I'm actually using XSB prolog; a solution for XSB would be useful for me too.)

Answer 1

Yes, we can implement this in ISO Prolog and even in XSB, but not very efficiently. To make this efficient, you would need some "selective cut". Further, XSB does not implement ISO conforming integers so the overflow must be handled separately.

:- dynamic(if_counter/1).

if_counter(0).

:- dynamic(no_if_answer/1).
if(If_0, Then_0, Else_0) :-
   once(if_counter(Id)),
   Idx is Id+1,
   (  Idx > Id -> true
   ;  throw(error(representation_error(max_integer),
               'XSB misses ISO conforming integers'))
   ),
   retractall(if_counter(_)),
   asserta(if_counter(Idx)),
   asserta(no_if_answer(Id)),
   (  If_0,
      retractall(no_if_answer(Id)),
      Then_0
   ;  retract(no_if_answer(Id)) ->
      Else_0
   ).

The major source of inefficiency is that for a determinate condition If_0, there is still a choice point left. It is thinkable next to unthinkable that an implementation could conclude that retract(no_if_answer(Id)) will always fail, once retractall(no_if_answer(Id)) has been executed, but I doubt that implementers will invest in such optimizations. EDIT: The reason why this seems highly improbable is that an implementation would have to guarantee that the numbers asserted always go up.

Note that soft cut produces incompleteness in the same way the cut does. Consider:

| ?- if(X = a, T = equal, T = not_equal).

X = a
T = equal;

no

This clearly misses an answer! To see why, take X = b:

| ?- X = b, if(X = a, T = equal, T = not_equal).

X = b
T = not_equal;

no
| ?- if(X = a, T = equal, T = not_equal), X = b.

no % bad!!

Conjunction should be commutative (modulo non-termination, errors, side-effects).

If you are interested in declaratively sound conditionals that are also very efficient and often faster than their impure counterparts, consider if_/3. See library(reif) for SICStus which gives all correct answers:

| ?- if_(X = a, T = equal, T = not_equal).
X = a,
T = equal ? ;
T = not_equal,
prolog:dif(X,a) ? ;
no

Answer 2

Ok, let's get creative... You essentially need a way to remember (across backtracking) that the If-condition had at least one solution. Dynamic predicates are a no-no for me, but are there any alternatives? Well, ISO-Prolog defines one kind of anonymous object, the stream-term, which could be (ab)used to implement the non-backtrackable flag in this rather elegant way:

if(If, Then, Else) :-
    open(., read, S),
    (
        If,
        close(S, [force(true)]),
        Then
    ;
        catch(close(S), error(existence_error(stream,_),_), fail),   % fail if already closed
        Else
    ).

We close the stream to indicate that If had a solution, and this is then detected by the close-attempt in the else branch. This works perfectly and leak-free in a system like ECLiPSe. However, many systems (including XSB) re-use the identifiers of closed streams (which is not forbidden by ISO), making this solution non-portable.

But wait, streams have a position property, which can be set, and which retains its value across backtracking! Using this trick, the following works on XSB:

if(If, Then, Else) :-
    % open('ReadableAndNonemptyFile', read, S),      % general ISO
    open(atom(a), read, S),                          % XSB (needs no file)
    stream_property(S, position(Zero)),
    get_char(S, _),
    (
        catch(If, Ball, (close(S),throw(Ball))),
        set_stream_position(S, Zero),
        Then

    ; stream_property(S, position(Zero)) ->
        close(S),
        fail
    ;
        close(S),
        Else
    ).

Sadly, the open(atom(...),...) feature is XSB-specific, for strict ISO-Prolog you need a dummy file...