Reset/shift is not compatible with table/1?

Help!
1

The table/1 directive seems simply not compatible with shift/reset. I wrote codes to confirm this compatibility.

% table version.
% ?- xzdd(sumup(10, A)).
%@ false.

% untable.
% ?- untable(sumup/2), untable(sumup/3).
% ?- xzdd(sumup(10, A)).
%@ A = 55.

:- table sumup/2, sumup/3.

sumup(I, A):- shift(sumup(I, A)).

sumup(0, A, A):-!.
sumup(J, A, B):- K is J - 1,
	C is  B  + J,
	sumup(K, A, C).

:- meta_predicate xzdd(0).
xzdd(M:A):- xzdd(A, 0, M).

:- meta_predicate xzdd(0, ?).
xzdd(M:A, S):- xzdd(A, S, M).

xzdd((A,B), S, M):-!, xzdd(A, S, M), xzdd(B, S, M).
xzdd(M:G, S, _):-!, xzdd(G, S, M).
xzdd(0, _, _):-!.
xzdd(true, _, _):-!.
xzdd(Cont, S, M):- xzdd_reset_continue(M:Cont, S).

:- meta_predicate xzdd_reset_continue(:, ?).
xzdd_reset_continue(Goal, S):- reset(Goal, Ball, Rest),
	(	var(Ball) -> true
	;	call(Ball, S)
	),
	xzdd(Rest, S).
3

My sample codes is real.

5

I know this as a comment of my sample codes. What I would like to know is
whether it is compatible or not, which is necessary for my application. Now I am pessimistic on this.

6

This is indeed quite unlikely to work. In theory tabling could use e.g. shift(table(…)) and if the user also uses something else, one immediate conflict is solved. Tabling however stores and runs the continuations in a completely different context during its completion phase. I don’t see how these can meaningful cooperate.

1 Like
7

I see. So, I give up a “nice” idea of mine to apply table/1 in ZDD. But I have a proposal
for table/1, which I call it projective table in mind. I would like to post it with an example. I made a simple search on table/1, but no relevant information there.

8

I have no clue what a projective table is going to look like, so you’ll have to surprise me :slight_smile:

10

My proposals is:

table f/2 as a projection of g/3, where f(X, Y) is g(X, Y, S) for some S.
That is, f is a projection of g.

Below is an observation taken from my codes in ZDD library. The first codes xcard/3
is to count the number of members of a family of sets. xcard uses term_hash table
via memo/2. memo/2 is very powerful as shown in the log. But it is not somewhat elegant, I feel.

I would like to write ycard/3 for xcard/3 using table/1 in stead of memo/2. It works, but
unfortunately, it is much weaker than memo/2. I guess it is because of the third argument of ycard/3, which is usually large complex structure , but not necessary for tabling, due to the main property of ZDD, which is necessary for only computation purpose; “projective table” is, in a sense, “tabling without computation state.”

I am afraid you are surprised about this so wild proposal, but my intuition have been obtained from experience on ZDD. In short, the projective table is a smart replacement of the memo. Does this make sense ?

xcard/3 
% ?- zdd((X<<pow([a,b]), xcard(X, C))).
% ?- N=2, numlist(1, N, Ns), zdd((X<<pow(Ns), xcard(X, C))).
% ?- N=10000, numlist(1, N, Ns),
%	call_with_time_limit(100, time(zdd((X<<pow(Ns), xcard(X, C))))).
%@ % 880,818 inferences, 0.081 CPU in 0.105 seconds (77% CPU, 10811032 Lips)
%@ N = 10000,
%@ Ns = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
%@ X = 10001,

xcard(X, Y):-shift0(xcard(X, Y)).

%
xcard(I, I, _):- I < 2, !.
xcard(I, C, S):- memo(I-C, S),
	(	nonvar(C) -> true
	;	cofact(I, t(_, L, R), S),
		xcard(R, Cr, S),
		xcard(L, Cl, S),
		C is Cl + Cr
	).
ycard/3 
% ?- zdd((X<<pow([a,b]), ycard(X, C))).
% ?- N=2, numlist(1, N, Ns), zdd((X<<pow(Ns), ycard(X, C))).
% ?- N=100, numlist(1, N, Ns),
%	call_with_time_limit(100, time(zdd((X<<pow(Ns), ycard(X, C))))).
% ?- N=1000, numlist(1, N, Ns),
%	call_with_time_limit(100, time(zdd((X<<pow(Ns), ycard(X, C))))).
%@ % 68,179 inferences, 3.119 CPU in 3.342 seconds (93% CPU, 21858 Lips)
%@ ERROR: '$tbl_variant_table'/6: Not enough resources: private_table_space
%@ ^  Exception: (17) setup_call_catcher_cleanup(system:true, prolog_statistics:catch(test:zdd((test:_20<<pow([...|...]), test:ycard(_20, _22))), _6224,  (report(time{cpu:0.413386, inferences:3538886, wall:1604931141.241928}, 10), throw(_6224))), _223830, prolog_statistics:(_6246=true)) ? creep
%@    Call: (19) _6246=true ? abort
%@ % Execution Aborted

ycard(X, Y):-shift0(ycard(X, Y)).

%
:- table ycard/3.
ycard(I, I, _):- I < 2, !.
ycard(I, C, S):-
	cofact(I, t(_, L, R), S),
	ycard(R, Cr, S),
	ycard(L, Cl, S),
	C is Cl + Cr.
11

Sounds similar. Thanks.

12

So, a non-tabled argument is basically an input argument, but not stored in the tables? This would imply that an nt argument can be inspected by the tabled predicate, but the tabled predicate cannot further instantiate the nt argument?

I guess that is feasible. The drawback is of course that it is easy to write things that are logically incorrect. I wonder whether we should demand the nt argument to be ground?

13

If following condition is guaranteed,

q(X, Y) if and only if p(X, Y, S) for some S.

then S is safely nt argument for tabling q.

Otherwise, it is dangerous. In ZDD applications, such safe and available situations are many, I think, such as the example of xcard/3.

My proposal is not new for you. You are already aware of such request of mine. I feel I am in the palm of hand of Budha. I use the memo/2 frequently, but it is often that it is not sure whether memo should be used or not. In such cases clearly table/1 is better than memo/2 because the table/1 is easily switch on and off, but as for the memo editing codes is not so easy as declaring table/1 or untable/1

15

I’m, not sure this will work. In the end we do not capture the big term in the tables, but we still do capture the term in continuations. The traditional SLG-WAM machinery is not so much affected. Ultimately SWI-Prolog’s continuation based approach performs stack copying and this seems killing for this scenario.

What does work is to use b_setval/2 and b_getval/2 to store the ZDD globally. That way the tabling implementation is completely bypassed.

Note that what table/1 and untable/1 are doing is managing a wrapper using wrap_predicate/4. You can do the same for a more simple memoming implementation. Full tabling mostly addresses the issue of breaking cycles by discovering that a new goal is a variant of an already open call. If you do not need that you can make something much simpler that doesn’t involve reset/shift.

16

Of course, xcard/3 is responsible for keeping nt terms. xcard3 wants safely table/1 to forget the nt terms and treat it as xcard/2. I may not understand correctly your comment. I will read again your comment.

17

Thanks for comment. I like the foreach/2. What is the foreach problem ? Of course, clearly it depends on usage situation due to the possible very big terms, (e.g between(1, 1000000, X) as generator). But still
I like the idea in foreach.

18

I might be wrong but Jan Burse is probably talking about the old vs. the new implementation of foreach/2. See this thread: New hashtable library

From what I understand, foreach/2 almost builds the conjunction of the goals in the second argument; but actually, it would build a conjunction of goals where the variables shared between goals were actually copies (so not the same variable!). This deficiency no longer exists since July 26 this year (see the last message in the thread I shared).

19

Thanks. I have read the discussion, and I see the problem was solved.

EDIT.

P.S. My memo/2 seems faster than table/1 on the naive Fibonacci, but much slower than a smart Fibonacci. So it is somewhat difficult for me to throw the memo/2 to replace with the smarter table/1.

% finonacci with memo.
% ?- time(zdd(use_zdd(fibo_with_memo(10000, F)))).
%@ % 613,519 inferences, 0.060 CPU in 0.066 seconds (92% CPU, 10197613 Lips)

fibo_with_memo(0, 0):- memo(0-0).
fibo_with_memo(1, 1):- memo(1-1).
fibo_with_memo(N, F):- memo(N-F),
	(	nonvar(F) -> true
	;	N0 is N-1,
		N1 is N-2,
		fibo_with_memo(N0, F0),
		fibo_with_memo(N1, F1),
		F is F0 + F1
	).

% fast fibonacci.
% ?- time(fast_fibo(10000, F)).
%@ % 20,000 inferences, 0.018 CPU in 0.032 seconds (58% CPU, 1081256 Lips)

fast_fibo(N, F):- fast_fibo(N, _, _, F).
%
fast_fibo(0, 0, 0, 0):-!.
fast_fibo(1, 0, 0, 1):-!.
fast_fibo(N, X, Y, F):- N0 is N-1,
	fast_fibo(N0, Y, _, X),
	F is X + Y.

% naive fibonacci with table.
% ?- time(naive_fibo(10000, F)).
%@ % 380,032 inferences, 0.094 CPU in 0.119 seconds (79% CPU, 4031229 Lips)

:- table naive_fibo/2.
naive_fibo(0, 0):-!.
naive_fibo(1, 1):-!.
naive_fibo(X, S):- X0 is X-1,
	X1 is X0-1,
	naive_fibo(X0, S0),
	naive_fibo(X1, S1),
	S is S0 + S1.
20

It is tentative conclusion that it would be better for me to keep my memo suits on ZDD despite of not being elegant compared with table/1. Besides the conclusion I am getting more interested little by little into shift/reset. The point is to understanding the third argument of reset/3, which seems a computation state to continue, but so far it’s just a black box for me. I am always slow to understand things.