retract(pred(X,Y,Z) -- with X,Y,Z bound, creating a choice point

Help!
1

Hello,

I do a retract in my code – and, oddly, that retract causes a choice point.

The idea behind the retract is to aggregate an additional outgoing link of a node in a list – and thereby avoid the need to do a findall/3 search to find those outgoing links.

The to do this, first i retract the current list – which creates the choice point – and then create the new list which includes the new outgoing link.

I am unsure what it means for a retract to have a choice point …

Any comments are much appreciated,

Dan

3

thanks. will do.

I guess i opted to retract because its more selective, but since all variables are bound, retractall amounts to the same.

4

If retract/1 leaves a choice point, that means the predicate you’re retracting has multiple clauses. retract/1 matches its argument against all clauses of the predicate and succeeds once for every matching clause (removing it in the process). For example:

?- assert(foo(a(1))).
true.
?- assert(foo(a(2))).
true.
?- assert(foo(b(1))).
true.
?- retract(foo(a(I))).
I = 1 ;
I = 2.
?- foo(X).
X = b(1).

This can happen even if you pass a ground argument, if the predicate has multiple identical clauses:

?- assert(foo(0)).
true.
?- assert(foo(0)).
true.
?- foo(I).
I = 0 ;
I = 0.
?- retract(foo(0)).
true ;
true.
?- foo(I).
false.

If you want to be sure that all clauses are removed, you should use retractall/1 as suggested. But you should perhaps also check the code that asserts the clauses - your code might be accidentally asserting multiple clauses at once when you’re not expecting it. This would also lead to extra choice points when querying the predicate normally, not just when retracting it with retract/1.

Instead of a dynamic predicate, you could also consider using the global variable predicates b_setval/2 or nb_setval/2. These predicates always overwrite any previous value stored in the given variable, so you can never accidentally end up with multiple values for a single variable, and as a result the corresponding b_getval/2 never leaves choice points.

1 Like
5

Thank you for the explanation and illustration. Very helpful,

And, good point.

I should check why the fully bound predicate generates a choice point – its surely a choice point “smell” …

I am, indeed, reviewing all my test code to identify any choice points that shouldn’t be there.

A while back, I had (foolishly) indicated that all tests are nondet – when they completed with choice points – not really understanding the issue at hand.

Now, i removed all nondet options and am cleaning up my code to ensure no choice points are left over, and i am learning a lot.

Sometimes, code needs to be rewritten and become more efficient.

And, sometimes, i can’t really do anything but add a cut, and its, foe example, because of the basic (normalised) data structures I chose to use – which might need revisiting in the future.

thanks

Dan

6

I now checked, and there is no duplicate, or multiple assertion, of the fact that gets retracted.

What more, the code first retrieve the fact – as a test to see if it exists, and only then retracts it - and the “test” code does not generate a choice point, as if, more than one exists.

So, it seems that something in the retract/1 implementation generates a choice point.

A bit of a mystery …

Btw, it looks like i can’t use findall/ to directly find all asserted same facts, since there is no variable to find. so, what i did was open a second command line window from the debugger, and tried to retrieved the fact which only succeeded once.

Dan

8

Why couldn’t an index be created, in your example …

Because its a list ?

In my case the first argument is an integer, the node id, and the second a list of integers.

The docu on indexing says little about the argument type, although lists are mentioned as special case - if the first argument is an empty list, or not.

Dan

9

Here is no spurious choice point:

?- [user].
|: :- dynamic q/1.
|: q(a).
|: q(b).
|: q(c).
|: 
% user://4 compiled 0.01 sec, 3 clauses
true.

?- retract(q(b)).
true.

Because it can index a,b and c.

In the other example I guess [1,2,3,4,5,6,7,a], [1,2,3,4,5,6,7,b]
and [1,2,3,4,5,6,7,c] doesn’t get indexed, since it exceeds the
indexing limit parameters, like indexing term depth.

What do the SWI-Prolog indexing, multi-argument indexing, just-in-time
indexing and deep indexing manual pages say? I don’t know these
things by heart.

10

I didn’t see any mentioning of lists, and the length of the list, so far, was only 1 – so, its a bit unclear.

But, its also a bit unsettling that indexing would play a role here and be dependent on the length of the list – i.e. a short list gets indexed and after a certain length, not anymore and one gets a choice point.

re: retractall

I guess retractall is less performant than retract, since it typically needs to find all facts and keep the result in a datastructure – although in my case it would always only be one fact.

12

yes, thats what i did … but, then opted for your suggestion to use retractall, since it doesnt create the choice point to begin with.

But, it would be good to have some kind of warning when an index could not be created, and an explanation why …

14

looks like retract with cut is a better choice, after all …

15

The indexing has been discussed several times here and is (IMO) fairly well described in the manual. It is also not set in stone, meaning it may improve as well as suffer slight regression in particular cases when this is needed to get an overall improvement. Bottom line is that you have a guaranteed choice-point free clause selection on the first argument given we can index on atoms, small integers and functors (name/arity of a compound). All the rest merely reduces choice points. Often down to none, but sometimes leaving spurious choice points as a result of hash collisions or exceeded limits.

Note that spurious choicepoints have very little impact on backtracking search (what Prolog is for after all). They merely affect “functional code”, i.e. code that performs many forward inferences without ever backtracking. It you know that table lookups (or retract) should be (semi)det in such code, use a cut (or once/1, …). If there could be duplicates and thus choicepoints could legitimately exist an exceptional spurious one is unlikely to have a lot of impact.

3 Likes
16

Thanks, Jan.

It was not immediately clear to me why a choice point was created – its my bad i didn’t keep the significance of indexing in mind … so i was glad Jan pointed it out to me.

Perhaps some additional information could be emitted when such collisions or exceeded limits occur and indexing doesn’t get created …

Perhaps, a change in my data structure, once i understand the issue at hand, could put the indexing back into the limit …

Dan

18

If I remember right --as a special case-- there is also a guaranteed no choicepoint between [] and [_|_] in the first argument, correct?

Example

just to make it easy for readers of this thread, here are some examples on how to design your clauses:

% Examples using atom, small integer or ftor to discriminate
% without leaving a choice point.

atom_nochp(one, W)               :-  writeln(one(W)).
atom_nochp(two, W)               :-  writeln(two(W)).

smallint_nochp(33, W)            :-  writeln('33'(W)).
smallint_nochp(101, W)           :-  writeln('101'(W)).

ftor_nochp(onearg(A), W)         :-  writeln('onearg/1'(A,W)).
ftor_nochp(another_onearg(A), W) :-  writeln('another_onearg/1'(A,W)).
ftor_nochp(twoargs(A), W)        :-  writeln('twoargs/2'(A,W)).

list_nochp([])                   :-  writeln('empty_list').
list_nochp([_|_])                :-  writeln('non empty_list').

test_nochp :-
	atom_nochp(one,'no choicepoint!'),
	smallint_nochp(33,'no choicepoint!'),
	ftor_nochp(another_onearg(1),'no choicepoint!'),
	list_nochp([1]).


% These leave choice points, as they don't use the first argument
atom_chp(W, one)               :-  writeln(one(W)).
atom_chp(W, two)               :-  writeln(two(W)).

smallint_chp(W, 33)            :-  writeln('33'(W)).
smallint_chp(W, 101)           :-  writeln('101'(W)).

ftor_chp(W, onearg(A))         :-  writeln('onearg/1'(A,W)).
ftor_chp(W, another_onearg(A)) :-  writeln('another_onearg/1'(A,W)).
ftor_chp(W, twoargs(A))        :-  writeln('twoargs/2'(A,W)).

list_chp([_])                  :-  writeln('one_elem_list').
list_chp([_,_|_])              :-  writeln('two_or_more_elem_list').

test_chp :-
	atom_chp('choicepoint!',one),
	once(print_last_choicepoint),
	smallint_chp('choicepoint!',33),
	once(print_last_choicepoint),
	ftor_chp('choicepoint!',another_onearg(1)),
	once(print_last_choicepoint),
	list_chp([1]),
	once(print_last_choicepoint).

Queries:

21 ?- test_nochp.
one(no choicepoint!)
33(no choicepoint!)
another_onearg/1(1,no choicepoint!)
non empty_list
true.

22 ?- test_chp.
one(choicepoint!)
Warning: atom_chp('choicepoint!',one) left a choice point in alternate clause (after success)
Warning:   /tmp/t1.pl:25: clause succeeded
Warning:   /tmp/t1.pl:26: next candidate clause
Warning: Called from
Warning:   [10] test_chp at /tmp/t1.pl:39
33(choicepoint!)
Warning: smallint_chp('choicepoint!',33) left a choice point in alternate clause (after success)
Warning:   /tmp/t1.pl:28: clause succeeded
Warning:   /tmp/t1.pl:29: next candidate clause
Warning: Called from
Warning:   [10] test_chp at /tmp/t1.pl:41
another_onearg/1(1,choicepoint!)
Warning: ftor_chp('choicepoint!',another_onearg(1)) left a choice point in alternate clause (after success)
Warning:   /tmp/t1.pl:32: clause succeeded
Warning:   /tmp/t1.pl:33: next candidate clause
Warning: Called from
Warning:   [10] test_chp at /tmp/t1.pl:43
one_elem_list
Warning: list_chp([1]) left a choice point in alternate clause (after success)
Warning:   /tmp/t1.pl:35: clause succeeded
Warning:   /tmp/t1.pl:36: next candidate clause
Warning: Called from
Warning:   [10] test_chp at /tmp/t1.pl:45
true [...]

You need SWI-Prolog 8.5.4 for print_last_choicepoint/0. Otherwise just delete it from the source, it is just a convenience so you can see the choicepoints.

Bottom line

  • if you want no choicepoints:
    1. Make the \color{red}\text{first argument} of the clauses \color{red}\text{a different atom, small int or functor}
      • for a functor to be different they need to have a different name and/or arity.
    2. As a special case you don’t get a choice point between [] and [_|_] in the first argument.

EDIT: In the example for twoargs functor I forgot to add the other arg , left as an exercise :slight_smile:

19

These are also two different things, one is atomic and the other one a functor. I am too lazy to read now but “name/arity of compound” should cover that.

20

You are right:

4 ?- explain([]).
% [] is a special constant denoting an empty list
true.

5 ?- explain([_|_]).
% [_68396] is is a not-closed list with 1 elements
true.
21

1 elements

Ugh :grinning:

22

It has only spoken machine code since childhood, it is all its parents (they call them INTEL) taught it; be gentle, it’s making quite an effort to speak english to these strangers that don’t speak x86 opcodes! :grin:

23

thank you.

In my case, i have a dynamic fact with a first argument a short integer (with 48 bits) and a second argument an atom. There is a third argument which is "functionality"dependent on the first two. (in the normalization sense) .

Both, the first and the second argument are needed to uniquely identify a prior asserted fact.

Apparently, indexing does not combine the first and second to uniquely retrieve the fact for retract.

To then only use a first argument, i made the first argument a pair, combining the prior first integer with the second symbol, as so:

fact(Int-Sym, Sym, List).

But, also like a choice point was created when retracting the fact as so:

fact(Int-Sym, Sym, Old) →
retract(fact(Int-Sym, Sym, _).
;
Old = [],

So, i guess, i still don’t fully graps indexing.

Perhaps, its related to just in time indexing, i.e. the code hasn’t enough been run, to create a combined index.

Dan

24

If you have a lot of facts, you can control how the indexes are created by an initial set of goals with typical instantiation patterns. If you run the code and then use jiti_list/0, you can create some “warm-up” goals. Here’s an example: https://github.com/kamahen/pykythe/blob/d54fd05096af5eb47efb863f613f12d5d80c6c41/browser/src_browser.pl#L298

1 Like
25

As mentioned above, for functors to be different you need to have a different name and/or different arity. Simply having Int-Sym will have the same name (-) and arity (2) in all the facts.

You need to figure out a way to encode the discriminating first argument as different atoms, ints or functors. One way is contcatenating Int and Sym and making an atom: atom_concat(Int,Sym,MyID). Then you can use MyID as the first argument in fact/3.