Problem with ISO retract/1 test case (Multi Threading)

[j4n bur53]

Because of multi-threading issues I recently
changed the semantic of retract/1 in Jekejeke
Prolog, and also demanded a bug fix for SWI-Prolog.

Namely the semantic of retract/1 is now, that
it returns a match iff the match was just removed.
This is to assure if there is concurrent access
that no duplicates are generated.

Unforntunately the ISO standard seems to allow
duplicates, a test case even describes how these
duplicates might emerge. The test case is on
page 81, examples 8.9.3.4:

:- dynamic insect/1.
insect(ant).
insect(bee).

?- retract(insect(I)), write(I), nl,
retract(insect(bee)), fail; true.

ISO proposed output:

ant
bee

Newest output of SWI-Prolog (nightly build from 30.08.2016):

Welcome to SWI-Prolog (Multi-threaded, 64 bits,
Version 7.3.25-54-g2103258)
Copyright (c) 1990-2016 University of Amsterdam, VU Amsterdam

?- retract(insect(I)), write(I), nl,
retract(insect(bee)), fail; true.
ant
true

Newest output of Jekjeke Prolog (upcoming release 1.1.6):

Jekejeke Prolog 2, Runtime Library 1.1.6
(c) 1985-2016, XLOG Technologies GmbH, Switzerland

?- retract(insect(I)), write(I), retract(insect(bee)), fail; true.
ant
Yes

I will mark this test case as dubious, meaning I don't agree
with the ISO core standard proposal here.

Bye

P.S.: The SWI-Prolog change was caused by:
https://github.com/SWI-Prolog/swipl-devel/issues/162
(Closing it so quickly wasn't my idea)

The new semantics can easily be bootstrapped
as follows (Jekejeke Prolog upcoming release 1.1.6):
http://www.jekejeke.ch/idatab/doclet/blog/en/docs/05_run/02_reference/runtime/dynamic.html?hash=retract/1

Or on GitHub, without HTML predicate anchors and HTML predicate links:
https://github.com/jburse/jekejeke-devel/blob/master/jekrun/headless/jekpro/reference/runtime/dynamic.p#L146
(Thats why I don't really like GitHub, no anchros and links)

[Ulrich Neumerkel]

j4n bur53 <janb...@fastmail.fm> writes:
>Unforntunately the ISO standard seems to allow
>duplicates, a test case even describes how these
>duplicates might emerge. The test case is on
>page 81, examples 8.9.3.4:
>
> :- dynamic insect/1.
> insect(ant).
> insect(bee).
>
> ?- retract(insect(I)), write(I), nl,
> retract(insect(bee)), fail; true.
>
>ISO proposed output:
>
> ant
> bee

(minor remark: you modified the query. It has no "nl", nor "; true"
in 13211-1:1995 8.9.3.4, so the output should be antbee)

The standard explains how this result is obtained, due
to the logical database update (see 7.5.4) the
first goal notes the list of clauses to be retracted
= [insect(ant), insect(bee)]. That is done first.
Therefafter insect(bee) is retracted, but still the
first retract will succeed.

By changing this, there is now a difference in output between:

?- retract(insect(I)), write(I), retract(insect(bee)), fail.

and

?- insect(I), write(I), retract(insect(bee)), fail.

Both should give "antbee". Now, the current version of SWI
gives "ant" and "antbee".

So there is an immediate update for retract, but none for regular
goals. Further it seems there is still the logical database
update for newly added clauses.

>I will mark this test case as dubious, meaning I don't agree
>with the ISO core standard proposal here.

Not clear what "standard proposal" you are referring to. First
you referred to the ISO standard.

[j4n bur53]

What has recenty been implemented in SWI-Prolog and
Jekejeke Prolog is quite non-standard. Here is what
some other Prolog systems stil do:

3) GNU Prolog 1.4.4 (64 bits)
Compiled Apr 23 2013, 16:05:07 with cl

?- retract(insect(I)), write(I), nl,
retract(insect(bee)), fail; true.
ant

bee

yes

4) ECLiPSe Constraint Logic Programming System [kernel]
Version 6.1 #222 (x86_64_nt), Thu Jul 7 16:02 2016

[eclipse 3]: retract(insect(I)), write(I), nl,
retract(insect(bee)), fail; true.
ant
bee

I = I
Yes (0.00s cpu)

5) Ciao 1.15-1781-g328b907: Wed Jun 19 00:06:05 PST 2013

?- retract(insect(I)), write(I), nl,
retract(insect(bee)), fail; true.
ant

bee

yes

6) B-Prolog Version 8.1, All rights reserved,
(C) Afany Software 1994-2014.

?- retract(insect(I)), write(I), nl,
retract(insect(bee)), fail; true.
ant

bee

yes

A possible workaround, to regain ISO compatiblity would be
to change for example the bootstrapping code from:

retract(V) :- var(V),
throw(error(instantiation_error,_)).
retract((H :- B)) :- !,
clause(H, B, R), erase(R).
retract(H) :-
clause(H, true, R), erase(R).

Into the following code:

retract(V) :- var(V),
throw(error(instantiation_error,_)).
retract((H :- B)) :- !,
clause(H, B, R), ignore(erase(R)).
retract(H) :-
clause(H, true, R), ignore(erase(R)).

Whereby ignore/1 is defined as in here:
http://www.swi-prolog.org/pldoc/man?predicate=ignore/1

j4n bur53 schrieb:

[j4n bur53]

Ulrich Neumerkel schrieb:

> ?- retract(insect(I)), write(I), retract(insect(bee)), fail.
>
> and
>
> ?- insect(I), write(I), retract(insect(bee)), fail.
>
> Both should give "antbee".

Yes, according to the standard. But whether this
makes really sense is dubious.

Please note: The problem can be viewed independent
of the logical view of clause/2.

See bootstrapping code, it uses clause/3 which is
also based on the logical view (not explictly
documented):

http://www.swi-prolog.org/pldoc/doc_for?object=clause/3

To be frank, I don't know the exact new internal
implementation of SWI-Prolog. But I guess the bootstrapping
code I presented is also the explanans for SWI-Prolog.
Not sure here. But also not so important.

[j4n bur53]

Ulrich Neumerkel schrieb:

> (minor remark: you modified the query. It has no "nl", nor "; true"
> in 13211-1:1995 8.9.3.4, so the output should be antbee)

BTW: my iso test cases now also mirrored on GitHub
since today. The test case that recently failed is here:
https://github.com/jburse/jekejeke-samples/blob/master/jekdev/compliance/consult/data.p#L142

Enjoy

[Julio Di Egidio]

On Thursday, September 1, 2016 at 2:44:26 PM UTC+2, j4n bur53 wrote:
<snip>

> Unforntunately the ISO standard seems to allow
> duplicates, a test case even describes how these
> duplicates might emerge. The test case is on
> page 81, examples 8.9.3.4:
>
> :- dynamic insect/1.
> insect(ant).
> insect(bee).
>
> ?- retract(insect(I)), write(I), nl,
> retract(insect(bee)), fail; true.
>
> ISO proposed output:
>
> ant
> bee
>
> Newest output of SWI-Prolog (nightly build from 30.08.2016):
>
> Welcome to SWI-Prolog (Multi-threaded, 64 bits,
> Version 7.3.25-54-g2103258)
> Copyright (c) 1990-2016 University of Amsterdam, VU Amsterdam
>
> ?- retract(insect(I)), write(I), nl,
> retract(insect(bee)), fail; true.
> ant
> true

Are you sure? I don't get the same:

====================
Welcome to SWI-Prolog (Multi-threaded, 32 bits, Version 7.3.25)
...

?- [user].

:- dynamic insect/1.
|: insect(ant).
|: insect(bee).

|:
true.

?- retract(insect(I)), write(I), nl,
| retract(insect(bee)), fail; true.
ant

bee
true.
====================

Well, I could even understand the point of ISO (though the whole
thing of logical updates makes very little sense to me, but that
might be me) *if* rectractall/1 as well as the assert family did
the same... which does not seem to be the case (but I do not have
the standard to check what is the expected behaviour):

====================
?- [user].

:- dynamic insect/1.
|: insect(ant).
|: insect(bee).

|:
true.

?- retractall(insect(_)), fail.
false.

?- listing(insect).
:- dynamic insect/1.


true.
====================

====================
?- assertz(t__),fail.
false.

?- listing(t__).
:- dynamic t__/0.

t__.

true.
====================

Julio

[Julio Di Egidio]

Forget my remark, as after doing that anyway we get:

?- listing(insect).
:- dynamic insect/1.


true.

I concur it makes very little to no sense. I'll add it
to the reasons why a standard for a logical language should
be rewritten from scratch.

Julio

[j4n bur53]

Julio Di Egidio schrieb:

>> Newest output of SWI-Prolog (nightly build from 30.08.2016):
>>
>> Welcome to SWI-Prolog (Multi-threaded, 64 bits,
>> Version 7.3.25-54-g2103258)
>> Copyright (c) 1990-2016 University of Amsterdam, VU Amsterdam

> Are you sure? I don't get the same:
>
> ====================
> Welcome to SWI-Prolog (Multi-threaded, 32 bits, Version 7.3.25)
> ...

Watch the versions, I was using nightly build from
30.08.2016, with a recent patch concerning erase/1
and retract/1 from Jan W.

Its very difficult to judge whether the ISO core
proposed semantics makes sense. There seems to be
other semantics around in the old time.

For example I find in an Aurora paper, for ??
MProlog and/or SICStus ??, the following interresting
code snipped:

lock(Mutex) :-
repeat,
retract(locked(Mutex)).

Putting aside the issues that the above is a busy
wait, it wont work with the ISO semamtics. Two
threads would be allowed to return positives,

One thread would return a true positive, and
another thread woukld return a false positive.

Thats why Jan W. is hesitant to follow my
current rollback request for retract/1. I don't
know at the moment, how to have the cake and
eat it two. How to do the following:

- sequentiall single thread is allowed to
receive false positive (as per ISO example)
- in multi-threaded access no false positives
at least for example for the first result

Also what would be interesting would be some
tests with multi-threads and other Prolog systems.
I am only testing SWI-Prolog so far.

Bye

(*)
Contributions To Or-Parallel Logic Programming
http://www.cs.bme.hu/~szeredi/docs/SzerediPhd.pdf
(See section 6 about dynamic predicates)

(**)
New issue for retract/1 rollback:
https://github.com/SWI-Prolog/swipl-devel/issues/163

[j4n bur53]

j4n bur53 schrieb:

> Watch the versions, I was using nightly build from
> 30.08.2016, with a recent patch concerning erase/1
> and retract/1 from Jan W.

Nightly builds (oops daily builds now), have their
own download page, only for Windows:

http://www.swi-prolog.org/download/daily/bin/

[Julio Di Egidio]

On Friday, September 2, 2016 at 10:18:33 AM UTC+2, j4n bur53 wrote:
<snip>

> How to do the following:
>
> - sequentiall single thread is allowed to
> receive false positive (as per ISO example)
> - in multi-threaded access no false positives
> at least for example for the first result

I am not sure working around the standard makes sense at all, if it's
even possible in this case. Anyway, to me the idea of logical updates
is not senseless, just as long as there is also an option for immediate
updates available, because we cannot (reasonably) get immediate updates
otherwise. That said, logical updates should be local to the top level
call, which amounts to thread-local if I am not missing anything, and
all the assert/retract predicates should be either non-backtracking or
fully backtracking, not something in between (while immediate update
predicates should all be non-backtracking).

Julio

[Julio Di Egidio]

At the bottom of this file is some code that makes extensive use
of assert/retract (to generate successive levels of a prime wheel):
<https://github.com/jp-diegidio/Nan.Numerics.Prime-Prolog/blob/prime_whl/Code/nan_numerics_prime_whl.pl>

It works on SWI 7.3.25, but I suppose I have just been lucky...

Julio

[j4n bur53]

Julio Di Egidio schrieb:

> At the bottom of this file is some code that makes extensive use
> of assert/retract (to generate successive levels of a prime wheel):
> <https://github.com/jp-diegidio/Nan.Numerics.Prime-Prolog/blob/prime_whl/Code/nan_numerics_prime_whl.pl>
>
> It works on SWI 7.3.25, but I suppose I have just been lucky...

Could be an interesting cannary in the coal mine.

Someting else, did you try to find primes in parallel?

The following can be easily parallelized:

for (int i=0; i<M; i++)
if (isPrime(i))
System.out.println(i);

Just let N threads takle some subregions of [0..M)
for example thread 1 could do 0, 0+N, 0+2N, etc..
and thread 2 could do 1, 1+N, 1+2N, etc..

But what if there is some shared sieve inbetween?
Not so easy, since I guess when threads reorder the
results, everything goes wrong.

Bye

[Julio Di Egidio]

On Friday, September 2, 2016 at 11:01:09 AM UTC+2, j4n bur53 wrote:
> Julio Di Egidio schrieb:
> > At the bottom of this file is some code that makes extensive use
> > of assert/retract (to generate successive levels of a prime wheel):
> > <https://github.com/jp-diegidio/Nan.Numerics.Prime-Prolog/blob/prime_whl/Code/nan_numerics_prime_whl.pl>
> >
> > It works on SWI 7.3.25, but I suppose I have just been lucky...
>
> Could be an interesting cannary in the coal mine.
>
> Someting else, did you try to find primes in parallel?

With the premise that mine is still a "simple" library,
I'd leave that to the user, but I could indeed use some
parallelism for factoring. But you raise a good point:
I do have memoization, but due to logical updates and
how these are not shared between threads until after
the fact, for the moment I have just ended up making
memoization thread-local... But I might review this
in the future: at least SWI provides an Edinburg-style
recorded database, which provides immediate updates,
so with that and some locking... (although, in my
specific case, some benchmarking suggests that
extensive memoization is not even that useful, so I
might just end up having some fixed table generated at
runtime, if not even just hard-coded in some file).
Anyway, that's the point: I'd think only immediate (and
non-backtracking) updates make sense for multi-threading.

Julio

[Julio Di Egidio]

On Friday, September 2, 2016 at 11:23:04 AM UTC+2, Julio Di Egidio wrote:

> Anyway, that's the point: I'd think only immediate (and
> non-backtracking) updates make sense for multi-threading.

No, I take that back, logical updates with concurrency may indeed be useful:
these can e.g. save us from locking on predicates that just read the shared
state. I suppose the bottom line would be that every combination of the
logical vs. immediate and the backtracking vs. non-backtrack updates might
make sense, just the standard I still think makes little sense: it backtracks
on those assert/retract but the changes get anyway applied to the database when
the call is done?

Julio