Difference \+ & not
Joost Meijer
I've been programming prolog (swi-prolog) and found that there are two
ways to negate a predicate/clause. What's exactly the difference between
\+foo(X). and
not foo(X).
Thanx already!
Joost Meijer
freshmen AI student
Fergus Henderson
>I've been programming prolog (swi-prolog) and found that there are two
>ways to negate a predicate/clause. What's exactly the difference between
>\+foo(X). and
>not foo(X).
On SWI-Prolog, there is no difference.
But there are differences on other Prolog systems.
`\+' is part of the ISO Prolog standard, whereas `not' is not.
`\+' is the usual (potentially unsound) negation-as-failure;
the semantics of `\+' are almost the same as if it were defined by
\+ G :- G, !, fail ; true.
(the only differences arise in the case when `G' contains a cut).
Many Prolog systems use `not' for some kind of "sound" negation
primitive. So the goal `not(G)' may check that the goal `G' is ground
or that execution of `G' does not bind any variables. On Prolog systems
that support coroutining, `not(G)' may block until `G' is ground.
--
Fergus Henderson <f...@cs.mu.oz.au> | "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh> | of excellence is a lethal habit"
PGP: finger f...@128.250.37.3 | -- the last words of T. S. Garp.
Bart Demoen
f...@cs.mu.oz.au (Fergus Henderson) writes:
|> the semantics of `\+' are almost the same as if it were defined by
|>
|> \+ G :- G, !, fail ; true.
|>
|> (the only differences arise in the case when `G' contains a cut).
To my understanding, G is equivalent to call(G) and a cut in G doesn't
leave the scope of call. Then what is the difference ?
Bart Demoen
Fergus Henderson
That is true.
>Then what is the difference ?
For the builtin `\+', the ISO Prolog standard says that a cut inside the
negated _should_ extend beyond the scope of the negation -- it should
cut away any choicepoints in the containing procedure. In other words,
`\+' is transparent to cuts. In contrast, any user-defined predicate is
opaque to cuts. This means that `\+' can't be implement as just an ordinary
user-defined predicate.
For example, if I write
p(X) :- \+ !.
p(X) :- X = 42.
then the query `?- p(X).' should have no solutions, because the cut should
prune away the second clause of p/1, whereas if I write
p(X) :- my_not(!).
p(X) :- X = 42.
my_not(G) :- G, !, fail ; true.
then the query `?- p(X).' should have the solution `X = 42'.
Bart Demoen
f...@cs.mu.oz.au (Fergus Henderson) writes:
|> For the builtin `\+', the ISO Prolog standard says that a cut inside the
|> negated _should_ extend beyond the scope of the negation -- it should
|> cut away any choicepoints in the containing procedure.
Cute - I must have forgotten that. I can't even remember I ever knew :-(
|> For example, if I write
|>
|> p(X) :- \+ !.
|> p(X) :- X = 42.
|>
|> then the query `?- p(X).' should have no solutions, because the cut should
|> prune away the second clause of p/1
SICStus says on the other hand:
{Warning: p(_388):- \+! - illegal clause in lines 1-2}
and its manual says about \+(P): No cuts are allowed in P
Bart Demoen
Mats Carlsson
>
> In article <7ki3ep$4m1$1...@mulga.cs.mu.OZ.AU>,
> f...@cs.mu.oz.au (Fergus Henderson) writes:
>
> |> For the builtin `\+', the ISO Prolog standard says that a cut inside the
> |> negated _should_ extend beyond the scope of the negation -- it should
> |> cut away any choicepoints in the containing procedure.
>
> Cute - I must have forgotten that. I can't even remember I ever knew :-(
Where does it say that? I can't find any such hint in my copy.
On the contrary:
Clause 7.8.8.1, defining the semantics of ';'('->'(If,Then),Else) says:
The If is not transparent to cut [...]
A cut in Then is transparent to Then [...]
A cut in Else is transparent to Else [...]
The standard doesn't say explicitly that \+Goal is defined as:
\+Goal :- Goal -> fail; true.
but that's the customary definition anyway, be it by unfolding or by
an explicit program clause. Hence a cut inside Goal should not extend
beyond the scope of the negation.
One of the (contrived) examples in clause 8.15.1 seems to support that:
?- (X=1; X=2), \+((!, fail)).
Succeeds, unifying X with 1.
On re-execution, succeeds, unifying X with 2.
>
>
> |> For example, if I write
> |>
> |> p(X) :- \+ !.
> |> p(X) :- X = 42.
> |>
> |> then the query `?- p(X).' should have no solutions, because the cut should
> |> prune away the second clause of p/1
>
> SICStus says on the other hand:
>
> {Warning: p(_388):- \+! - illegal clause in lines 1-2}
>
> and its manual says about \+(P): No cuts are allowed in P
SICStus doesn't claim to be ISO compliant.
Quintus and SICStus chose to disallow cuts in the If part of if-then-else
constructs.
Mats Carlsson
Bart Demoen
Mats Carlsson <ma...@scheutz.sics.se> writes:
|> > |> For the builtin `\+', the ISO Prolog standard says that a cut inside the
|> > |> negated _should_ extend beyond the scope of the negation -- it should
|> > |> cut away any choicepoints in the containing procedure.
|> >
|> > Cute - I must have forgotten that. I can't even remember I ever knew :-(
|>
|> Where does it say that? I can't find any such hint in my copy.
Neither could I; so that's why I never knew it :-)
Maybe Fergus is confused by a rule that at some time was used:
if the construct is made up of alphabetic chars, then the
construct doesn't let the ! out of its scope
if the construct is made up of spceial chars, then cut goes through
This rule was used to explain why ! stays inside call/1, findall/3 etc
but goes outside of disjunction (;) if-then-else (-> ;) ...
If you apply the rule to \+, you get what Fergus describes.
But it wasn't adopted by ISO.
> > SICStus says on the other hand:
> >
> > {Warning: p(_388):- \+! - illegal clause in lines 1-2}
> >
> > and its manual says about \+(P): No cuts are allowed in P
>
> SICStus doesn't claim to be ISO compliant.
Fine. But it seems a bit inconsistent that at runtime
wellformed_body(!, L0, Env, Goal, L, _, _, _, _) :- !, Env = +, Goal = !, L = L0.
just fails if Env happens to be - instead of also saying something like
illarg(context(negation,cut), !, 0)
(I mean ?- \+(!). at toplevel just says No)
Related (I mean also in wellformed_body), it is funny that any non callable Goal
is wrapped in call/1; it results in a loop when you type
?- call(4).
at the toplevel. (SICStus 3.7.1 (Linux-2.0.35-i686): Thu Feb 18 12:52:38 CET 1999)
Cheers
Bart Demoen
Mats Carlsson
> In article <ul9bte8...@scheutz.sics.se>,
> Mats Carlsson <ma...@scheutz.sics.se> writes:
>
> >
> > SICStus doesn't claim to be ISO compliant.
>
> Fine. But it seems a bit inconsistent that at runtime
>
> wellformed_body(!, L0, Env, Goal, L, _, _, _, _) :- !, Env = +, Goal = !, L = L0.
>
> just fails if Env happens to be - instead of also saying something like
>
> illarg(context(negation,cut), !, 0)
>
> (I mean ?- \+(!). at toplevel just says No)
>
>
> Related (I mean also in wellformed_body), it is funny that any non callable Goal
> is wrapped in call/1; it results in a loop when you type
>
> ?- call(4).
>
> at the toplevel. (SICStus 3.7.1 (Linux-2.0.35-i686): Thu Feb 18 12:52:38 CET 1999)
That's a known bug (see ftp://ftp.sics.se/archive/sicstus3/BUGS).
Anyway, the upcoming SICStus 3.8 says:
| ?- call(4).
{TYPE ERROR: user:4 - arg 0: expected callable, found 4}
| ?- \+!.
{CONTEXT ERROR: user:(\+!) - cut appeared in if}
| ?- [user].
| p(1) :- \+!.
{CONTEXT ERROR: multifile_assertz((p(1):- \+!)) - cut appeared in if}
| p(2).
| {consulted user in module user, 10 msec 168 bytes}
yes
| ?- listing(p).
p(2).
yes
Mats Carlsson
Fergus Henderson
>Mats Carlsson <ma...@scheutz.sics.se> writes:
>
>|> > |> For the builtin `\+', the ISO Prolog standard says that a cut inside the
>|> > |> negated _should_ extend beyond the scope of the negation -- it should
>|> > |> cut away any choicepoints in the containing procedure.
>|> >
>|> > Cute - I must have forgotten that. I can't even remember I ever knew :-(
>|>
>|> Where does it say that? I can't find any such hint in my copy.
>
>Neither could I; so that's why I never knew it :-)
Sorry, I was mistaken. My apologies.
>Maybe Fergus is confused by a rule that at some time was used:
>
> if the construct is made up of alphabetic chars, then the
> construct doesn't let the ! out of its scope
> if the construct is made up of spceial chars, then cut goes through
...
>If you apply the rule to \+, you get what Fergus describes.
>But it wasn't adopted by ISO.
Yes, that is exactly why I was confused.
I had indeed heard that rule somewhere.
I should have looked in up in the standard, to be sure.
But instead, all I did was to test it with SWI-Prolog, which
unfortunately behaved exactly as I expected. <Sigh>
(I was in fact using a very very old version of SWI-Prolog, one
which predates the ISO Prolog standard, so perhaps this is not
too surprising. I don't know what the latest version of SWI-Prolog does.)
Jens Kilian
> Maybe Fergus is confused by a rule that at some time was used:
>
> if the construct is made up of alphabetic chars, then the
> construct doesn't let the ! out of its scope
> if the construct is made up of spceial chars, then cut goes through
>
>
> If you apply the rule to \+, you get what Fergus describes.
> But it wasn't adopted by ISO.
Indeed. Ruining a mnemonic rule without a good reason :-(
--
mailto:j...@acm.org phone:+49-7031-14-7698 (HP TELNET 778-7698)
http://www.bawue.de/~jjk/ fax:+49-7031-14-7351
PGP: 06 04 1C 35 7B DC 1F 26 As the air to a bird, or the sea to a fish,
0x555DA8B5 BB A2 F0 66 77 75 E1 08 so is contempt to the contemptible. [Blake]
Jan Wielemaker
>>If you apply the rule to \+, you get what Fergus describes.
>>But it wasn't adopted by ISO.
>
>I had indeed heard that rule somewhere.
>
>I should have looked in up in the standard, to be sure.
>But instead, all I did was to test it with SWI-Prolog, which
>unfortunately behaved exactly as I expected. <Sigh>
SWI-Prolog's got `do what I mean' :-)
>(I was in fact using a very very old version of SWI-Prolog, one
>which predates the ISO Prolog standard, so perhaps this is not
>too surprising. I don't know what the latest version of SWI-Prolog does.)
The latest public version says `asserting failure'. This wasn't very
satisfactory, so my internal version makes the ! transparent to \+ and
the conditional part of if-then-else as it used to be. In the end,
SWI-Prolog should be fully compliant to ISO, but this particular problem
is rather low on the list, as I don't think using ! in \+ or
if-then-else is good practice. As I never received a bug-report on the
`asserting failure', I suspect most users agree :-)
Regards --- Jan
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Jan Wielemaker Author of SWI-Prolog and the XPCE GUI library
SWI, University of Amsterdam http://www.swi.psy.uva.nl/projects/SWI-Prolog/
E-mail: j...@swi.psy.uva.nl http://www.swi.psy.uva.nl/projects/xpce/