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.
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.
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?
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.
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
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.
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.
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 )
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.
You tell us about the carrot now I feel like the horse. I do thank Jan and others for making the carrot (tabling).
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.
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
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.
)