Inserting a cut in Prolog to make a relation clause bound but bidirectional

Question

Consider the following Prolog program:

transform([], []).
transform([X | Xs],[Y | Ys]):-
    isSpecial(X),
    isSpecial(Y),
    transformSpecial(X,Y),
    transform(Xs,Ys).
transform([X | Xs],[ X | Ys]):-
    transform(Xs,Ys).

isSpecial(foo).
isSpecial(bar).
isSpecial(foobar).

transformSpecial(X,Y):-
    isSpecial(X),
    isSpecial(Y),
    not(X = Y).

There are cases where I will call tranform([foo, 1, 2], X) and cases where I want to call transform(X, [foo, 1, 2]).

In both cases I want X to unify with [bar, 1, 2] and with [foobar, 1, 2], but not with [foo, 1, 2]. That is, I want that once the predicate correctly recognizes that the second clause is applicable it should stick to only backtrack using the second clause.

Where should I insert the cut to achieve this behavior?

false false · Accepted Answer · 2018-05-25T08:52:10

Your program is currently too general. After all, there are three solutions to your query, but only the first are intended. The last one is wrong.

?- transform([foo, 1, 2], Xs).
   Xs = [bar, 1, 2]
;  Xs = [foobar, 1, 2]
;  Xs = [foo, 1, 2].   % wrong

The cut now may reduce the number of solutions. But most of the time this goes very wrong. Your question where you should "insert the cut to achieve this behavior?" has only as answer: there is no place. You need to do much more to achieve this.

Essentially, what you are describing is an element-wise transformation. So maybe we stick with describing one element at a time.

el_transformed(X, Y) :-
    isSpecial(X),
    isSpecial(Y),
    dif(X,Y).
el_transformed(X, X).   % too general!

Use maplist(el_transformed, [foo, 1, 2], Xs) as before...

Note that this version is just as wrong as your original code. But now, it is simple to add the extra condition:

el_transformed(X, Y) :-
   isSpecial(X),
   isSpecial(Y),
   dif(X,Y).
el_transformed(X, X) :-
   dif(X, foo),
   dif(X, bar),
   dif(X, foobar).

There is one big drawback: This version is not very deterministic for certain cases:

?- el_transformed(foobar, bar).
   true
;  false.

If you want to get even more out of it, consider to use library(reif) available both for SICStus and SWI.

el_transformed(X, Y) :-
   if_(( ( X = foo ; X = bar ; X = foobar ),
         ( Y = foo ; Y = bar ; Y = foobar ) ),
       dif(X,Y),
       X = Y).

With this formulation we do not need to repeat ourselves. To check, if the code is fine, let's try the most general query:

?- el_transformed(X, Y).
   X = foo, Y = bar
;  X = foo, Y = foobar
;  X = bar, Y = foo
;  X = bar, Y = foobar
;  X = foobar, Y = foo
;  X = foobar, Y = bar
;  X = Y, dif(Y,foobar), dif(Y,bar), dif(Y,foo).

You are looking at all possible cases that can happen! There are no further cases to consider.

So as a rule of thumb: Whenever you want a predicate that should work "bidirectionally", consider to write it as "omnidirectional" instead!

Maybe you did not like the explicit mentioning of X = foo ; X = bar ; X = foobar, in that case, we would have to dig deeper, by reifying isSpecial/1 to isSpecial_t/2:

isSpecial_t(X, T) :-
   call(
      ( X = foo
      ; X = bar
      ; X = foobar
      ), T).

el_transformed(X, Y) :-
   if_( ( isSpecial_t(X), isSpecial_t(Y) ), dif(X, Y) , X = Y ).

Inserting a cut in Prolog to make a relation clause bound but bidirectional

2 Answers