ISO incompatibility in (\+)/1 handling

General
1

Now I am facing this test case:

p(a).
p(b).
q(b).
test(X,Y,Z) :- \+ (X,Y,Z).

GNU Prolog gives me:

/* GNU Prolog 1.5.0 */
?- \+((p(X),!,q(X))).
yes
?- test(p(X),!,q(X)).
yes

SWI-Prolog gives me:

/* SWI Prolog 9.1.17 */
?- \+((p(X),!,q(X))).
true.
?- test(p(X),!,q(X)).
false.

I think GNU Prolog does it right, despite that Trealla Prolog
and ECLiPSe Prolog have the same bug. Other Prolog
systems not yet tested.

1 Like
2

Interesting find, Ciao Prolog shows a warning, with a small
hickup, since the warning is shown twice:

/* Ciao Prolog 1.22.0 */
?- \+((p(X),!,q(X))).
WARNING: ! illegal in \+ or if-parts of ->, if; ignored
WARNING: ! illegal in \+ or if-parts of ->, if; ignored
no

?- test(p(X),!,q(X)).
false.

Otherwise it has the same bug. Meaning the warning is a little
bit useless, since it alllows me to do test/3. I was rather expecting
that a Prolog system that can issue a warning is aware of the

subleties to inline (\+)/1 and can correctly compile it. Further I don’t
think according to ISO core standard a cut is disallowed in the if-part
of ->, as the warning suggests. It only needs a little more effort

to handle since the if-part of → opens a new cut scope.

1 Like
3

I first thought GNU-Prolog is right. That is, it the correct interpretation is that a cut inside \+/1 or the If if If->Then;Else is scoped to the \+/1 goal or If. The ISO doc on \+/1 is not so clear as it doesn’t mention the cut and gives two examples where the cut has no effect, but these examples do not distinguish the cut having no effect from the cut being scoped to the goal.

The problem is illustrated by listing test/3. This interpretation indeed turns the cut into a non-op as it is scoped by call/1.

?- listing(test/3).
test(X, Y, Z) :-
    \+ ( call(X),
         call(Y),
         call(Z)
       ).

If we write test/3 like below, the result is true.

test(X,Y,Z) :- \+ call((X,Y,Z)).

Now, we have a bit of a problem. If-then-else, and similar constructs are described in section 7.8 (control structures) of the ISO document, \+/1 in section 8.15 (built-in predicates → logic and control). The latter probably implies that the argument if \+/1 must be considered at runtime. SWI-Prolog (and apparently most others) compile \+/1 as (Goal->fail;true) and in this interpretation we get to the listing of test/3.

I think this was long time ago discussed before. I don’t recall the result. I guess the strict ISO interpretation would be to only allow compiling \+/1 if there are no variables at goal position for which scoping the cut affects the overall result and compile it as \+ call(Goal) otherwise.

Now the question is whether this was intended by the ISO committee or this was an oversight. As is, I’m inclined to document this rather than “fixing”. The ISO interpretation is much harder to implement and slows down execution.

4

Currently experimenting with this guard, might be more
complicated for modules. Where does this guard come from?
Derived from ISO body conversion algorithm:

sys_trans_allowed(V) :- var(V), !, fail.
sys_trans_allowed((A,B)) :- sys_trans_allowed(A), sys_trans_allowed(B).
sys_trans_allowed((A;B)) :- sys_trans_allowed(A), sys_trans_allowed(B).
sys_trans_allowed((A->B)) :- sys_trans_allowed(A), sys_trans_allowed(B).
sys_trans_allowed(A) :- callable(A).

The idea of sys_trans_allowed/1 is to check whether the given
goal is “troublesome” or not. A similar check that leads Ciao Prolog
to display a warning, only we do not check for the presence of cut (!)/1.

Rather the check is for naked variables that would get the call/1
treatment. Now if sys_trans_allowed(A) holds, you can perform
these transformations:

/* Basically Done in SWI-Prolog */
\+ A          ~~> (A -> fail; true)
/* Not available in SWI-Prolog, unlike other Prolog Systems */
once(A)       ~~> (A -> true; fail)

Transformations from outside to inside. I get these result in
SWI-Prolog, observe that for A = p(X) the predicate sys_trans_allowed/1
holds and obsever that SWI-Prolog does not inline once/1:

test(1, X) :- \+ p(X).
test(2, X) :- once(p(X)).

?- vm_list(test/2).
/*  \+ p(X) */
       3 c_not(2,'L1')
       6 b_var1
       7 i_call(user:p/1)
       9 c_cut(2)
      11 c_fail
L1:   12 i_exit
/* once(X) */
       3 b_functor(p/1)
       5 b_argvar(1)
       7 b_pop
       8 i_depart(system:once/1)
      10 i_exit

The above is fine, now consider a case where sys_trans_allowed/1
does not hold. Use A = (X,Y,Z) again. I get these results, SWI-Prolog
insists to still inline (\+)/2:

test2(1,X,Y,Z) :- \+ (X,Y,Z).
test2(2,X,Y,Z) :- once((X,Y,Z)).

?- vm_list(test2/4).
/*  \+ (X,Y,Z) */
       3 c_not(4,'L1')
       6 b_var1
       7 i_usercall0
       8 b_var2
       9 i_usercall0
      10 b_var(3)
      12 i_usercall0
      13 c_cut(4)
      15 c_fail
L1:   16 i_exi
/* once((X,Y,Z)) */
       3 b_functor((',')/2)
       5 b_argvar(1)
       7 b_rfunctor((',')/2)
       9 b_argvar(2)
      11 b_argvar(3)
      13 b_pop
      14 i_depart(system:once/1)
      16 i_exit

Now observe that once/1 doesn’t show a discrepancy between
inside a clause and inside a query. I get this result, no bug for
once/1 but a bug for (\+)/1:

p(a).
p(b).
q(b).

/* Bug in (\+)/1 */
?- \+ (p(X),!,q(X)).
true.

?- test2(1,p(X),!,q(X)).
false.

/* No Bug in once/1 */
?- once((p(X),!,q(X))).
false.

?- test2(2,p(X),!,q(X)).
false.

The consistent result is because once/1 isn’t inlined. So you could
fix the bug by not always inlining (\+)/1 or then inline it through some
approach that preserves semantics.

5

But there are a dozen other issues. For example this is
also a nice test case:

negation(X) :- X, !, fail.
negation(_).

Now GNU Prolog seems to not give (\+)/1 more properties
than the above definition, negation/1 and (\+)/1 strictly behave the same:

/* GNU Prolog 1.5.0 */
?- fail, negation(1).
no
?- fail, \+ 1.
no

On the other hand SWI-Prolog has some extra “linter” for (\+)/1 although
this is nowhere required by in the ISO core standard:

?- fail, negation(1).
false.

?- fail, \+ 1.
ERROR: Type error: `callable' expected, found `fail,\+1' (a compound)

The error message is a little bit confusing.

6

My vague recollection is that Richard O’Keefe made a long writeup about cuts, call, etc. (and underlying design issues) … it might have been in the old Prolog Digest or it might have been in a submission to ISO (and, IIRC, the ISO committee ignored some of Richard’s recommendations).
If this document or documents exist, it would probably take some effort to find, and might not be relevant anyway.

8

Being inspired by this thread, I checked queries below for sure on call(!), and bare !. Fortunately I feel at ease
to see it works as I expected.

?- X=1; X=2.
X = 1 ;
X = 2.

?- X=1, call(!); X=2.
X = 1 ;
X = 2.

?-  X=1, !; X=2.
X = 1.

?- X=1, (true, !); X=2.
X = 1.
9

There is no such thing. Compiled code cannot represent calls to non-callable terms. That means there are two options: extend the compiler and VM to represent e.g. numbers as goals and make them raise an exception or refuse to compile immediately. I think ISO demands the first, but I chose for the second. Note that ISO is rather inconsistent here as it demands a type error from

?- call((fail,1)).

Compiling once/1 and ignore/1, etc. can be enabled by loading library(apply_macros). Several of these transformations are incorrect in scenarios raised in this topic.

I think there are more interesting problems to be resolved …

11

The library(apply_macros) doesn’t add such a compile time
aka “linter” error. Seems its implemented defensively, not raising
more errors during the compilation? I find:

/* SWI-Prolog 9.1.17 */
?- use_module(library(apply_macros)).
true.

?- fail, call((fail,1)).
false.

?- [user].
test :- fail, call((fail,1)).
^D

?- test.
false.

The library also doesn’t affect (\+)/1, still a compile time aka “linter” error:

?- fail, \+ (fail,1).
ERROR: Type error: `callable' expected, found `fail,\+ (fail,1)' (a compound)
12

My question is whether this was a deliberate choice and if so, what is the rationale for this choice? Given its notation, it looks like a control structure and making it one makes things IMO more consistent.

call/1 is always handled at runtime, even if its argument is sufficiently instantiated. I see no good reason to try and inline it.

13

You have to lookup some meeting notes of ISO committee
about Core Prolog. Thats like doing archeology.

Here is my guess. The idea is that (\+)/1 works like not/1:

/* SWI-Prolog 9.1.17 */
?- listing(not/1).
:- meta_predicate not(0).

system:not(Goal) :-
    \+ call(Goal).

With your not/1 the bug goes away:

p(a).
p(b).
q(b).
test(X,Y,Z) :-not( (X,Y,Z) ).

?- not((p(X),!,q(X))).
true.

?- test(p(X),!,q(X)).
true.

Now the two agree, the test/3 call and the query with not/1.

Edit 01.11.2023
But was expecting that listing(not/1) shows me a more
primitive bootstrapping, like for example:

not(X) :- X, !, fail.
not(_).
14

So what is the bug? (\+)/1 is supposed to be negation-as-failure. You
can read this meaning from the operator, which is a composition of “\” and “+”:

  • “\” and “+”: Basically says not succeed.

The “\” is the same not like the not in bitwise operation. And “+” is basically
a call/1. The bug is very simple, there are call/1 in the wrong place in test/3.

So test/3 is mostlikely executed as follows, at least this is what
SWI-prolog does, since it generates 3 times call/1:

?- \+ (call(p(X)), call(!), call(q(X)))

But call(!) has no more effect.

15

The good old rule was that symbol-based constricts (, ; ->) are control structures that are transparent to the !. At least, that was AFAIK in the Quintus pre-ISO days the rule of thumb. I don’t know what good old Quintus did with ! in (p,!->t;e). Keeping it local to the condition as ISO does surely makes sense. But, \+/1 is also a symbolic operator and defining it to be a shorthand for (Goal->fail;true) makes IMO a lot of sense. That is essentially what SWI-Prolog does, and it appears most Prologs do.

The only reason I can imagine for the current definition is that old systems used not/1 as a normal meta predicate and possibly ISO thought they should not change the semantics of that. Sounds unlikely though as one of the good things of ISO is that it standardized handling the cut in control structures, something that was quite a mess before ISO.

Documenting is the best fix IMO :slight_smile: Added:

In contrast to the ISO standard, but compatible with several other Prolog systems, SWI-Prolog implements \predref{\+}{1} as a \jargon{control structure}. This implies that its argument is compiled as part of the enclosing clause and possible variables in goal positions are translated to call/1. As a result, if such a variable is at runtime bound to a cut (\predref{!}{0}), the cut is scoped to the call/1 call rather than the enclosing \predref{\+}{1}.

18

Its just a choice and I as well as many other implementations made the other choice. Considering it a control structure keeps the compiler simple and it apparently what most Prolog implementers considered to be the most logical thing to do. Either the ISO team or the implementers (or both) did not consider this impact.

I’m done with this topic.

22

My first glimpse from one of above posts:

?- fail, negation(1).
false.

?- fail, \+ 1.
ERROR: Type error: callable' expected, found fail, ‘\+1’ (a compound)

Apart of ISO Standard, I don’t remember exactly (15 years break), there is mathematical difference between operator theory and predicate theory, so probably ERROR message should be like:

ERROR: Theory error: ‘callable’ (‘predicate’) expected, found ‘\+’ (an operator)

Or am I wrong? Because of higher or aside scope theory, which should decide scope problems in the above examples.

PS: I’m sorry for intuitionistic language :slight_smile:

23

PS2. To compilcate things even more, imagine:

?- maplist(\+, [1]).

Per analogy with op/3, which is predicate to operator redefiner (converter), we can imagine reversed constuct pred/2, which would be operator to predicate reverse back redefiner (converter), to establish CONSISTENCY.

25

I understand. You think op/3 does define some converter. But its only
syntactic sugar. It doesn’t do anything. Its a no-op. You can try yourself:

With operator:

?- fail, \+ 1.
ERROR: Type error: `callable' expected, found `fail,\+1' (a compound)

Without operator:

?- fail, '\\+'(1).
ERROR: Type error: `callable' expected, found `fail,\+1' (a compound)

In Prolog op/3 do define some syntax parsing rules, such as X op Y, is
parsed as compound op(X,Y) and so on for infix, prefix and postfix.

But semantic wise op/3 has zero influence, hence you cannot invert it.

27

Syntactic sugar in Prolog, but not equivalent in mathematics afaik.

28

Body conversion is defined in this section 7.6 of the ISO core standard.
Its a compile time device, not related to op/3 since it works on the
so called “abstract term”, what you get after you have read a term.

And only (‘,’)/2, (;)/2 and (->)/2 take part in body conversion.
(\+)/1 doesn’t take part according to the ISO core standard:

Unbenannt

29

Thank you for ISO core fragment. I understand.