ISO incompatibility in (\+)/1 handling

j4n_bur53 · October 29, 2023, 7:24pm

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.

j4n_bur53 · October 30, 2023, 12:42am

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.

jan · October 30, 2023, 8:25am

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.

j4n_bur53 · October 30, 2023, 6:09pm

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.

j4n_bur53 · October 30, 2023, 6:47pm

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.

peter.ludemann · October 30, 2023, 6:49pm

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.

j4n_bur53 · October 30, 2023, 7:01pm

Although Trealla Prolog shares the \+ (X,Y,Z) bug, its quite
permissible what fail, \+ 1 concerns. It agrees with GNU Prolog
here, we can even do this clause, its accepted by

both GNU Prolog and Trealla Prolog:

/* GNU Prolog 1.5.0 */
test :- fail, \+ 1.
?- test.
no

SWI-Prolog has the “linter” in place, and barks at it also
during consult, not only in the top-level:

/* SWI-Prolog 1.5.0 */
test :- fail, \+ 1.
ERROR: user://1:8:
ERROR:    Type error: `callable' expected, found `fail,\+1' (a compound)

But the SWI-Prolog “linter” doesn’t know other built-ins like
once/1, forall/2, etc… For example once/1, forall/2 works again
in both SWI-Prolog and GNU Prolog, although an argument is
not a callable, i.e. the number 1:

/* GNU Prolog 1.5.0 */
?- fail, once(1).
no
?- forall(fail, 1).
yes

/* SWI Prolog 9.1.17 */
?- fail, once(1).
false.
?- forall(fail, 1).
true.

kuniaki.mukai · October 31, 2023, 3:00am

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.

jan · October 31, 2023, 7:38am

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 …

j4n_bur53 · October 31, 2023, 9:09am

call/1 doesn’t have a compile time aka “linter” error, you can try yourself:

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

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

Only (\+)/1 has a compile time error in SWI-Prolog, but all other
constructs like call/1, once/1, forall/2, etc… don’t have such an error.
One reason for this compile time error in SWI-Prolog could be that

(\+)/1 is treated as a control construct in SWI-Prolog in some
alley of SWI-Prologs compiler. On par with (;)/2, (,)/2 and (->)/2, its
argument visited during compilation. Whereas the ISO core standard

doesn’t require (\+)/1 to be in this set of operators. But I didn’t check
the C source code of SWI-Prolog to see where this happens. And whether
there are even different modes of compilation, like for dynamic and static

predicates maybe a distinction is made. Don’t know. I only found a
brand new issue in Scryer Prolog recorded here:

\+ sometimes incorrect
https://github.com/mthom/scryer-prolog/issues/2141

This issue states again where (\+)/1 is codified by the ISO
core standard to not be among (;)/2, (,)/2 and (->)/2:

Comment by UWN
(\+)/1 is not a control construct (7.8).

But you pass all these rather easy tests, since the involved predicates
q1, q2 and q3 don’t have parameters:

/* SWI-Prolog 9.1.17 */
?- q1.
true.
?- q2.
true.
?- q3.
true.

Things get an itch more complicated if the predicates have parameters,
which is what my test case tests.

j4n_bur53 · October 31, 2023, 9:25am

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)

jan · November 1, 2023, 11:58am

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.

j4n_bur53 · November 1, 2023, 7:11pm

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(_).

j4n_bur53 · November 2, 2023, 9:47am

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.

jan · November 2, 2023, 2:36pm

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

jan · November 2, 2023, 4:20pm

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.

tbudzen · November 3, 2023, 11:47am

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

tbudzen · November 3, 2023, 11:49am

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.

j4n_bur53 · November 3, 2023, 1:03pm

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.

tbudzen · November 3, 2023, 1:12pm

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

Topic		Replies	Views
A Prolog Unparser Error Discussion	2	305	July 17, 2021
Careful with subtract/3 Help!	34	1423	August 22, 2022
Freeze interferes with multiple solutions Help!	13	502	March 7, 2024
I just finished coding a between/3 with steps: between/4 General discussion	14	967	August 8, 2020
Careful with op/3 General	1	516	April 6, 2022

ISO incompatibility in (\+)/1 handling

Related Topics