Tabling: "pure Prolog" and the tabling dependency graph

Help!
1

I’m using tabling to improve the performance of a set of predicates that determine what is contained in what given an RDF-like model where you can say things like:

A box has an inside.
A marble is touching the inside of the box.

And then ask questions like:

What is in the box?
A marble!

I’m using incremental tabling because things can move around in this world and I was hoping to get the “auto-invalidation” benefits of incremental tabling.

I’m trying to debug why the tabling is returning different answers than my non tabled version and I’ve got a couple of things I’m unclear on:

  1. This section discusses how “impure programs” may not be tabled correctly (but then describes how SWI Prolog fixes some of that). Does “impure” only mean “using predicates that prune choice points”? Or is using “not” also included in “impure”?
  2. How does the Tabling code find a path from a tabled predicate to the dynamic incremental predicates it depends on? Obviously it can’t find all cases because the connection between them could be arbitrarily complex and impossible to follow for any general purpose algorithm. Is it guaranteed to find everything that isn’t using a metacall for example? I just want to understand what it will find for sure, and then I can make sure my code is only doing those things (or use the approach from here to work around it)
    (…edit…) 3. Does tabling do anything tricky by trying to notice that arguments in the tabled predicate aren’t being used and ignore them? Long story, but I have a “fake” argument in the tabled predicate that represents an “out of band” piece of information that is used by the dynamic predicates it depends on. So it “effectively” would be passed all the way through from the tabled predicate to the dynamic predicates, but it is happening out of band so I put a fake argument there to try to make the tabling engine take it into account.

Thanks!

2

Tabling cannot deal with programs that use side effects during their computation such as assert/retract (etc) to store intermediate results. It can also not deal with predicates that are cut during their evaluation. XSB has a warning if that happens. SWI-Prolog doesn’t at the moment. Now it is not so easy to see when this happens. Tabling works with what is called strongly connected components, a group of predicates that are mutually dependent. SWI-Prolog’s tabling establishes this group dynamically. If the incomplete table calls another tabled predicate, this predicate is added to the SCC, The SCC may thus grow while it is being completed (completion always applies to an SCC). A cut that interferes with this completion may affect the result.

So, using \+/1 still means NAF (Negation as failure), provided the goal evaluated as an argument completes (i.e., does not suspend before the commit happens). Roughly, this means the argument goal should not be involved in recursive calls to the same variant. There is also tnot/1, which does allow for loops through negation. The argument must call a tabled predicate.

The discovery is dynamic. Each time when the evaluation of a tabled predicate calls another tabled predicate or a dynamic predicate we create a dependency. The implies that all (indirect) dependencies on an incremental dynamic predicate must be incrementally tabled. I forgot whether there is a runtime check on this.

I’m afraid I do not understand. There is no magic in tabling :slight_smile: It sounds you may be interested in answer subsumption (aka mode directed tabling).

Two debugging tips:

  • If, given no preloaded tables, the answer differs from the non-tabled version you have to do with unwanted effects of cuts (or → or +/1) or impurity due to site effects.
  • If the answers differ after modifying incremental dynamic predicates you can can run ?- abolish_all_tables. If you get the same results you are in the situation above. Else there is something wrong with the dependencies, which may be due to dependent tabled predicates not being declared for incremental tabling.

Note that you can inspect the tables and dependency graphs. Notably my personal library has some additional tools (tdump, tstat).

3

Ahh, that is good to know. I thought that was something to consider about using \+/1 but couldn’t remember.

Double ahh! My thinking was stuck in static evaluation. Since the dynamic predicates are marked as incremental too, I didn’t consider the fact that you could just watch to see if those get called somehow and truly handle all the crazy dynamic cases too. Nice!

What I meant by that is, if you do something like this:

:- table my_predicate/2 as incremental
my_predicate(X, Y) :-
   retain_value(X),
   atom(Y).

retain_value(_).

or even more obvious:

my_predicate(_, Y) :-
   atom(Y).

Does the system notice that the first argument isn’t used and ignore it from tabling purposes? It sounds like no (and my testing has confirmed that for the first case at least).

This is great, thanks!

4

No.If you wan that, write

:- table my_predicate/1.

my_predicate(Y) :-
    my_predicate(_, Y).