Scryer-prolog: Logical database updates

[triska]

@infradig spotted a difference between Scryer and Trealla Prolog compared to GNU Prolog:

https://github.com/infradig/trealla/issues/130

Regarding logical database updates, the standard prescribes:

7.5.4 A logical database update

Any change in the database that occurs as the result of
executing a goal (for example, when the activator of a
subgoal is a call of assertz/1 or retract/1) shall affect
only an activation whose execution begins afterwards. The
change shall not affect any activation that is currently
being executed.

Both ways to run the program seem not to contradict this requirement. Are both conforming?

[infradig]

I think swipl and gprolog are unambiguously correct in this. The yap result
surprises me considering how long it's been around, maybe it's a recent
regression.

On Fri, Nov 27, 2020 at 4:30 AM Markus Triska [e-mail]
wrote:

@infradig https://github.com/infradig spotted a difference between
Scryer Prolog and Trealla:

infradig/trealla#130 https://github.com/infradig/trealla/issues/130

Regarding logical database updates, the standard prescribes:

7.5.4 A logical database update

Any change in the database that occurs as the result of
executing a goal (for example, when the activator of a
subgoal is a call of assertz/1 or retract/1) shall affect
only an activation whose execution begins afterwards. The
change shall not affect any activation that is currently
being executed.

Both ways to run the program seem not to contradict this requirement. Are
both conforming?

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/mthom/scryer-prolog/issues/718, or unsubscribe
https://github.com/notifications/unsubscribe-auth/AFNKSETU27ZMDM7YSX5DRPTSR2NFHANCNFSM4UEBRUVQ
.

[triska]

Personally, I think a strong argument can be made that Scryer and Trealla are completely conforming to the standard in this case, because the standard prescribes:

8.9.3 retract/1

8.9.3.1 Description
retract(Clause) is true iff the database contains at
least one dynamic procedure with a clause Clause which
unifies with Head :- Body.

Procedurally, retract(Clause) is executed as follows:

  a) If Clause unifies with ':-'(Head, Body), then
  proceeds to 8.9.3.1 c,

  b) Else unifies Head with Clause and true with
  Body,

  c) Searches sequentially through each dynamic user-
  defined procedure in the database and creates a list L
  of all the terms clause(H, B) such that

    1) the database contains a clause whose head can
    be converted to a term H (7.6.3), and whose body can
    be converted to a term B (7.6.4) and

    2) H unifies with Head, and

    3) B unifies with Body.

  d) If a non-empty list is found, then proceeds to
  8.9.3.1 f,

  e) Else the goal fails.

  f) Chooses the first element of the list L, removes the
  clause corresponding to it from the database, and the
  goal succeeds.

  g) If all the elements of the list L have been chosen,
  then the goal fails,

  h) Else chooses the first element of the list L which
  has not already been chosen, removes the clause, if it
  exists, corresponding to it from the database and the
  goal succeeds.

retract(Clause) is re-executable. On backtracking,
continue at 8.9.3.1 g.

Note the part "if it exists": In the example, when retract/1 backtracks, the (original) second clause has already been removed due to the second retract/1 call.

[infradig]

This seems to explain it clearly, in my view:
https://www.swi-prolog.org/pldoc/man?section=update

4.14.5 Update view

Traditionally, Prolog systems used the immediate update view: new clauses
became visible to predicates backtracking over dynamic predicates
immediately, and retracted clauses became invisible immediately.

Starting with SWI-Prolog 3.3.0 we adhere to the logical update view,
where backtrackable predicates that enter the definition of a predicate
will not see any changes (either caused by assert/1
https://www.swi-prolog.org/pldoc/man?predicate=assert/1 or retract/1
https://www.swi-prolog.org/pldoc/man?predicate=retract/1) to the
predicate. This view is the ISO standard, the most commonly used and the
most‘safe'.83

On Fri, Nov 27, 2020 at 8:23 AM Markus Triska [e-mail]
wrote:

Personally, I think a strong argument can be made that Scryer and Trealla
are completely conforming to the standard in this case, because the
standard prescribes:

8.9.3 retract/1

8.9.3.1 Description
retract(Clause) is true iff the database contains at
least one dynamic procedure with a clause Clause which
unifies with Head :- Body.

Procedurally, retract(Clause) is executed as follows:

a) If Clause unifies with ':-'(Head, Body), then
proceeds to 8.9.3.1 c,

b) Else unifies Head with Clause and true with
Body,

c) Searches sequentially through each dynamic user-
defined procedure in the database and creates a list L
of all the terms clause(H, B) such that

1) the database contains a clause whose head can
be converted to a term H (7.6.3), and whose body can
be converted to a term B (7.6.4) and

2) H unifies with Head, and

3) B unifies with Body.

d) If a non-empty list is found, then proceeds to
8.9.3.1 f,

e) Else the goal fails.

f) Chooses the first element of the list L, removes the
clause corresponding to it from the database, and the
goal succeeds.

g) If all the elements of the list L have been chosen,
then the goal fails,

h) Else chooses the first element of the list L which
has not already been chosen, removes the clause, if it
exists, corresponding to it from the database and the
goal succeeds.

retract(Clause) is re-executable. On backtracking,
continue at 8.9.3.1 g.

Note the part "if it exists": In the example, when retract/1
backtracks, the (original) second clause has already been removed due to
the second retract/1 call.

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/mthom/scryer-prolog/issues/718#issuecomment-734495989,
or unsubscribe
https://github.com/notifications/unsubscribe-auth/AFNKSETMPUVQY2746YGWH73SR3IMFANCNFSM4UEBRUVQ
.

[triska]

Note that this mentions "to the predicate", which I take to mean to that predicate: The logical update view means that a predicate that is currently running is not immediately affected by changes to its own definition.

For example, the logical update view means that, if we have:

:- dynamic(p/1).

p(a) :-
    assertz(p(b)),
    p(b).

Then we get:

?- p(a).
false.

even though p(b) is asserted within the single clause of p/1, and indeed further calls of p(a) do succeed.

The reason that this must be so is that without this property, argument indexing and other optimizations can never be applied, because additional clauses could be added at any time, and we would have to consider these alternative clauses too if the effect were immediate.

The original case under consideration is different from this, because the change in the database affects a predicate that is not presently running. Therefore, any update can be propagated immediately, and as I understand the standard, it also seems that it should be performed immediately.

[infradig]

I see it as an initial matching starts a new view that cannot change
(someone called it the transactional view, like in capital D databases) .
p(b) above starts a new view so must see the asserted value.

In the original case the view is not changed by the retract and so must
remain visible.

I'd be happy if you were right because I wouldn't have to do more work on
it.

On Fri, Nov 27, 2020 at 8:57 AM Markus Triska [e-mail]
wrote:

Note that this mentions "to the predicate", which I take to mean to that
predicate: The logical update view means that a predicate that is
currently running is not immediately affected by changes to its own
definition.

For example, the logical update view means that, if we have:

:- dynamic(p/1).

p(a) :-
assertz(p(b)),
p(b).

Then we get:

?- p(a).
false.

even though p(b) is asserted within the single clause of p/1, and indeed
further calls of p(a) do succeed.

The reason that this must be so is that without this property, argument
indexing and other optimizations can never be applied, because additional
clauses could be added at any time, and we would have to consider these
alternative clauses too if the effect were immediate.

The original case under consideration is different from this, because the
change in the database affects a predicate that is not presently running.
Therefore, any update can be propagated immediately, and as I understand
the standard, it also seems that it should be performed immediately.

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/mthom/scryer-prolog/issues/718#issuecomment-734501644,
or unsubscribe
https://github.com/notifications/unsubscribe-auth/AFNKSERKK5H2NAQ4L6RWOBDSR3ML7ANCNFSM4UEBRUVQ
.

[josd]

At this moment it looks like only scryer-prolog does the above example correctly i.e. given

:- dynamic(p/1).

p(a) :-
    assertz(p(b)),
    p(b).

we get the expected

?- p(a).
false.
?- p(a).
   true.

gprolog gives

| ?- p(a).

yes

and swipl and tpl also give

?- p(a).
true.

[infradig]

I would argue it's the other way around!

On Fri, Nov 27, 2020 at 9:43 AM Jos De Roo [e-mail] wrote:

At this moment it looks like only scryer-prolog does the above example
correctly i.e. given

:- dynamic(p/1).

p(a) :-
assertz(p(b)),
p(b).

we get the expected

?- p(a).
false.
?- p(a).
true.

gprolog gives

| ?- p(a).

yes

and swipl and tpl also give

?- p(a).
true.

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/mthom/scryer-prolog/issues/718#issuecomment-734508698,
or unsubscribe
https://github.com/notifications/unsubscribe-auth/AFNKSEX2RTE7Q7245PR72UTSR3RY5ANCNFSM4UEBRUVQ
.

[josd]

Fair enough ;-)

[triska]

I agree that in the case I posted, p(a) should actually succeed also the first time, because p(b) in fact is "an activation whose execution begins afterwards"!

[michaelby]

Sorry to jump into this coversation out of nowhere. This is correct:

I think swipl and gprolog are unambiguously correct in this. The yap result
surprises me considering how long it's been around, maybe it's a recent
regression.

Yap uses the immediate update view by default. You can get the logical update view by setting it to ISO-conforming mode. At least, that was the case last time I could find the Yap documentation.

There is an example under _8.9.3.4 Examples_ in _ISO/IEC 13211-1:1995_ that shows the correct behaviour. Quoting the relevant parts:

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

retract(insect(I)), write(I),
      retract(insect(bee)), fail.
   'retract(insect(I))' succeeds,
      unifying I with 'ant',
      noting the list of clauses to be retracted
         = [insect(ant), insect(bee)],
      and retracting the clause 'insect(ant)'.
   'write(ant)' succeeds, outputting 'ant'.
   'retract(insect(bee))' succeeds,
      noting the list of clauses to be retracted
         = [insect(bee)],
      and retracting the clause 'insect(bee)'.
   'fail' fails.
   On re-execution, 'retract(insect(bee))' fails.
   On re-execution, 'write(ant)' fails.
   On re-execution, 'retract(insect(I))' succeeds,
      unifying I with 'bee',
      noting the list of clauses to be retracted
         = [insect(bee)],
      [the clause 'insect(bee)' has already
         been retracted.]
   'write(bee)' succeeds, outputting 'bee',
   'retract(insect(bee))' fails.
   On re-execution, 'write(bee)' fails.
   On re-execution, 'retract(insect(I))' fails.
   Fails.

A while ago there was some discussion about this example between Ulrich Neumerkel and Jan Burse on comp.lang.prolog that can be searched for.

I first learned of this counter-intuitive retract/1 behaviour when I saw @false mention it on StackOverflow, for example in this answer.

[pmoura]

A relevant paper on database update semantics:

https://link.springer.com/chapter/10.1007/3-540-54444-5_95

[pmoura]

Yap uses the immediate update view by default. You can get the logical update view by setting it to ISO-conforming mode. At least, that was the case last time I could find the Yap documentation.

:- set_prolog_flag(update_semantics, logical).