Page 1 of 1

fail() predicate behavior

Posted: 1 May 2021 8:19
by dominique f pannier
Hi,
I upgraded a project from VIP 7.5 to VIP 9 then VIP 10.
Some code written for VIP 7.5 leads in the new versions to an infinite loop: the following example illustrates this behavior.

Code: Select all

class facts     style_blue : integer := 13.     token : (unsigned Id, string T, integer Z) nondeterm.   clauses     token(1, "niveau", 3).     token(2, "n°", 10).     token(3, "8", 14).     token(4, "5", 0).   class predicates     p1 : ().     p10 : (string T) determ.     p100 : (unsigned Id, integer S).   clauses % updates the token facts     p1() :-         L = [ Id || token(Id, _, _) ],         Len = list::length(L),         I = fromTo(1, convert(unsigned, Len)),         token(I, T, _),         if p10(T) then             p100(I, style_blue)         end if,         fail().     p1().   % no update condition     p10(T) :-         hasDecimalDigits(T),         !.   % updates the fact     p100(Id, Z) :-         retract(token(Id, T, _)),         !,         assert(token(Id, T, Z)).     p100(_, _).
Under VIP 7.5, the predicate p1() succeeds. Under the higher versions, the predicate is blocked.

VIP 7.5 : when a fact is asserted, the fail() predicate backtracks a second time to the same fact which has been put at the bottom of the stack of the facts by the assert() predicate. At the next step, the fail() predicate backtracks to the fromTo() predicate and increments the value of the variable "I".

VIP 9 -10 : when a fact is asserted and then put to the bottom of the stack, the fail() predicate always backtracks to the same fact and the value of the "I" variable does not change anymore. It is easy to get around to this trouble : the first part of p1() collecting the fact's Id variables to update, the second part updating them.

It is as if, In the first case, the system "knows" that it reached the bottom of the fact's stack, and then can go to the next step. In the second case, it does not.

I'm curious to know why this modification, and what is the right behavior ?

Re: fail() predicate behavior

Posted: 1 May 2021 10:52
by Gukalov
Hi.
I think that no matter VIP 7.5 or VIP 9.
Generally this is not good idea to play with retract(someFact) & assert(someFact)
inside backTrack construction wich is based on iteration of this someFact.

Code: Select all

    p1() :-         L = [ Id || token(Id, _, _) ],         foreach Lj in L do             if token(Lj, T, _) and p10(T) then                 p100(Lj, style_blue)             end if         end foreach.

Re: fail() predicate behavior

Posted: 3 May 2021 12:14
by Thomas Linder Puls
You are absolutely right that there is a change, and the new behavior is (by definition) correct.

And matters will stay like now because it is most "sensible" as I will try to explain here.

Consider this little program:

Code: Select all

class facts     t : (unsigned).   clauses     run() :-         assert(t(0)),         foreach t(X) do             assert(t(X + 1))         end foreach.
We have a single fact t(0) in the fact database, and then we traverse the facts, while we are considering the last fact in the database we are asserting one more fact.

And now the question is, should the fact traversal see this fact or is the traversal finished.

In older versions (prior to Vip9) the traversal was considered finished, and the final result of this program would be that t(0) and t(1) was in the fact database.

In vip9+ the fact traversal is not considered finished, so after having handled t(0) we now see that after t(0) there is another fact t(1). So in vip9+ this program will go into an endless loop asserting more and more facts t(1), t(2), ... (eventually it will break down (or more likely be killed)).

And now the reason why this behavior is more sensible.

Consider this slight change:

Code: Select all

clauses     run() :-         assert(t(0)),         assert(t(0)), % now the fact database contains two facts         foreach t(X) do             assert(t(X + 1))         end foreach.
This program will go into a similar kind of endless loop in all Vip version, because now we assert a fact while examining a non-last fact, and this fact will definitely be found in the traversal.

So in older versions of Vip assert during the handling of the last fact behaved differently than assert during non-last facts.

In the newer version asserts made during traversal will have effect for that traversal, regardless of the assert takes place during a last or non-last fact.

As Gukalov says: this kind of manipulation is in any case a bit "problematic".

A little technicality: p1 is not "blocked", it goes into an endless loop (but apart from the CPU-usage that is of course same-same).

Notice that asserta is completely unproblematic because it always inserts the fact before the one we are considering, and even if we have retracted that fact we move on to the "next").

Re: fail() predicate behavior

Posted: 3 May 2021 14:24
by dominique f pannier
Thanks for your considerations.
And the examples of Thomas, presenting the problem in a light I had not seen, are very instructive. :D

Re: fail() predicate behavior

Posted: 3 May 2021 14:44
by Thomas Linder Puls
I knew exactly what the problem was/is; you just experienced a complex instance of it :-).