Tabling meets negation!

I’ve pushed a series of commits in the context of bringing SWI-Prolog tabling closer to XSB. This part deals with negation and implements tnot/1. This implements delaying negative goals that allows us to solve problems like this (from the XSB test suite):

:- table a/0, b/0, c/0, d/0.

a :- b, tnot(c).

b :- a.
b :- d.
b.

c :- tnot(d).

d :- b, fail.

The code passes the XSB negation test suite, but should still be considered experimental. Please give it a try.

All this was relatively easy to do thanks to regular discussions with Theresa Swift, David Warren and Fabrizio Riguzzi, initiated by Kyndi.

1 Like

Hi Jan, thanks for the announcement, I look forward to playing with this.

One question that comes to my mind is can we have the option of getting the same behavior but without having to use a different predicate (tnot) for negation? Since in SWI Prolog tabled predicates are declared with the table directive then the interpreter can know in advance that when a tabled predicate has a \+ clause then that clause should be treated as tnot. The benefit of this is that tabling (or un-tabling) of the predicate would only rely on adding (or removing) the table directive, and would not require rewriting the predicate definitions to swap \+ with tnot (or vice versa).

(Unless I am misunderstanding something about tnot of course.) Thanks!

That makes a lot of sense. Note that \+ works fine in tabled code (since recently) as long as there are no loops through the negation due to the implementation of dynamic and minimal connected components. If there are loops through the negation, non-tabled execution will not terminate anyway.

I will probably implement such a rewrite as a goal_expansion/2 rule in due time.

Also note that current implementation only deals with programs that can be solved by stratification, either statically (by the programmer) or dynamically (by the tabling engine). Future versions should deal with more complicated situations.

1 Like

Hi Jan,

Could I ask you to show a domain example where tnot/1 is useful … i can’t get my head around the synthetic example and how tnot/1 helps.

Also, what is the semantic reading of tnot/1 – beyond being a deferred negation (in terms of resolution).

thanks,

Dan

I guess it is quite simple: it gets Prolog a little closer to logic. Tnot/1 at the moment solves negation properly only if the problem can be (dynamically) stratified, i.e., by delaying negations the whole thing becomes trivial. If that is not the case, you get a wrong answer. Future versions will avoid that. Eventually it is the aim that SWI’s tabling becomes semantically equivalent to XSB.

Hi Jan and everyone,

In trying to understand how tabling can help with Prolog I found Programming in Tabled Prolog (very) DRAFT by David S. Warren. While reading this is interesting and helpful on its own, would it be safe to consider what is written in there of value for the tabling being added to SWI-Prolog? Also as that is a draft, is there a better source of information to understand the additions of tabling you are bringing to SWI-Prolog?

Thanks,
Eric

There are a lot of technical papers about the SLG-WAM as the XSB engine is called. At this moment my guide is “An Abstract Machine for Tabled Execution of Fixed-Order Strati ed Logic Programs” by
KONSTANTINOS SAGONAS and TERRANCE SWIFT and "An Abstract Machine for E cient Computation of Non-Ground Well-Founded Models by the same authors and David S. Warren. Most valuable are the discussions with them though.

I’m not very familiar with the literature on when and how you apply tabling. Possibly someone else can jump in. In my understanding it brings many of the good things from DataLog to Prolog as it effectively realises goal directed bottom up evaluation. This brings you the nice termination and avoidance of repeated computation properties from DataLog, while you you still have the full power of Prolog around.

1 Like

I recall the hub-authority problem as illustrated for SQL in: https://lagunita.stanford.edu/assets/courseware/v1/91073db257ca06a33322ffdeef367ddc/c4x/DB/Recursion/asset/OtherRecursion.pdf

An LP formulation would be:

hub(A) :-
  hubStart(_B,A).
hub(A) :-
  group_by((link(A,B), not auth(A), auth(B)),
           [A],
           (C=count,C>=3)).

auth(A) :-
  authStart(_B,A).
auth(A) :-
  group_by((link(B,A), not hub(A), hub(B)),
           [A],
           (C=count,C>=3)).

Though this follows the syntax of a deductive database, I think that the mutual recursion through negation is exemplified in this problem and might be a target for tnot.

Hi Jan,

Thank you for including the name of the paper. I’ve been searching for something that describes the Tabling approach taken. This is a good reference.

Is there a tracking issue for Tabling in SWI-Prolog? I’ve spent maybe an hour or so now clicking through various posts and issues, but I can’t seem to find the nexus of conversation around the tabling dev effort. I’m not complaining at all, I’m just wondering if other people might have the same question.

All my best,
Damon

Discussion is between Theresa Swift, David Warren, Fabrizio Riguzzi and me. It is hosted and sponsored by Kyndi. Output can be found at

  • The Git repo
  • The docs
  • An working report (LaTeX) that should eventually provide a guide for understanding the source and result in a publication. The aim of the publication will be to describe tabling at a more abstract level than the SLG WAM used by XSB and provide a complete overview to complement the individual papers on enhancing tabling published by the XSB team.

The hope is of course that this will be picked up in the SWI-Prolog community and make Prolog a great tool for a whole new class of problems. Tabling roughly brings the following (of course, only creativity limits what you can do with it :slight_smile: )

  • Rule based reasoning that is subject to non-terminating recursion using SLD resolution. Think for example about OWL and SWRL reasoning (see e.g., Thea)
  • Rule based reasoning with negation in a knowledge base that may be inconsistent (contradicting rules through negation). Well Founded Semantics is the provided semantics here.
  • Datalog style applications based on incremental tabling where derived tables are automatically updated after the world, represented by dynamic facts or rules, changes. This combines the goodies of Datalog and Prolog in one system.
  • Share computation results between queries and threads (caching).

Still open issues are

  • Complete sharing tables between threads.
  • Reliability, notably in the event of errors.
  • Establish a final API. Currently the a lot of the advanced API is in the XSB emulation layer. Some of this is too low level. We hope to achieve a more minimal an comprehensive API.
  • Performance.
2 Likes

You tell us about the carrot now I feel like the horse. I do thank Jan and others for making the carrot (tabling).

image

While I am aware of tabling in Prolog, and probably need it in a few places, even with my current project, I don’t have enough experience with it such that I see it as a natural solution to a problem.

Maybe if someone were to write a nice article on this using a classic problem it would benefit others.(I would but my plate is overflowing).

If the article contained lots of pictures for the concepts it would be appreciated; I say this because it is what I have had to resort to many times when concepts are not clear in the wording but a single picture makes it very apparent.

I am aware of the docs

1 Like

In my current project of creating a PostScript interpreter, they use concepts that are described using common computer science terminology such as object, stack, dictionary, reference, pointer, type, attribute, virtual memory, early binding, late binding, etc, but the way PostScript implements many of these is just different enough from OO concepts and functional concepts that each one has to be analyzed in detail to understand the true semantics.

I suspect that tabling would fit the needs for one of these (Local VM), but the knowledge gap is something I am currently filling in from the PostScript side. In implementing the semantics for some of these concepts it is becoming a real eye opener for the commonality of how the basics of CPU indexing instructions can be used as an underpinning for many of them. Also knowing about De Bruijn index helps

1 Like

Yes, caches might also benefit from using Prolog incremental tabling. Worth checking out for a latter revision after I get the basics working.

Hi EricGT (and all),

I’ve found the docs in the XSB project to be most helpful in understanding why it’s needed and how it’s being implemented (mostly). Unzip that tarball and there’s two PDFs under docs. For a jump start on tabling, I recommend starting on page 86 of manual1.

Hope this helps,
Damon

2 Likes