Bounded tabling

Question

Quite recently, I started playing around with tabling in Prolog; some experiments that I did with b-prolog and xsb can be found in this question.

With the tables getting bigger and bigger, I realized that I needed to find some tabling options / parameters that would allow me to limit the amount of memory dedicated to tabling.

So far, I didn't find anything suitable in the manuals of yap, b-prolog and xsb.

Could you please pinpoint me to some useful information?

Halvorsen

B-Prolog shares the virtual machine with Picat, so maybe it supports modes on arguments... – Muss

@CapelliC. I tried the declarations :- table posInt_CollatzSteps/2., :- table posInt_CollatzSteps(+,-). and :- table posInt_CollatzSteps(+,-):10000. but neither had a noticeable impact on memory consumption. – Halvorsen

As to Yap may be you wish to contact [email protected] who is the author of its table extension. – Lucey

Interesting question. What should be the meaning of "bounded" tabling. In a procedural language, with side effects, one would just use a bounded cache with some eviction strategy. For example this is seen many times in Java code. But in Prolog, where you can backtrack, how would this work out if tabling is connected with trailing? – Workingwoman

Answer 1

In the case of YAP, there are some publications that go into detail in the tabling implementation. One of the most relevant ones is likely Mode-Directed Tabling and Applications in the YapTab System:

http://cracs.fc.up.pt/node/4962

I have some of this paper examples adapted in Logtalk (I'm in same research group - CRACS - as the authors):

https://github.com/LogtalkDotOrg/logtalk3/blob/master/examples/tabling/tabling.lgt

(see code starting at line 63).

At the CRACS website (http://cracs.fc.up.pt) you can fine several other papers on tabling.

Shaitan