XSB auto_table

Help!
1

Does SWI-Prolog support XSB’s auto_table ?
(page 67,68)

This is very useful for DCG’s as shown here (from XSB manual p. 427):

11.2.1 Definite Clause Grammars and Tabling

Tabling can be used in conjunction with Definite Clause Grammars to get the effect of a more complete parsing strategy. When Prolog is used to evaluate DCG’s, the resulting parsing algorithm is“recursive descent”. Recursive descent parsing, while efficiently implementable, is known to suffer from several deficiencies: 1) its time canbe exponential in the size of the input, and 2) it may not terminate for certain context-free grammars (in particular, those that are left or doubly recursive). By appropriate use of tabling, both of these limitations can be overcome. With appropriate tabling,the resulting parsing algorithm is a variant of Earley’s algorithm and of chart parsing algorithms.

In the simplest cases, one needs only to add the directive :- auto_table (seeSection3.10.5) to the source file containing a DCG specification. This should generate any necessary table declarations so that infinite loops are avoided (for context-freegrammars). That is, with a :- auto_table declaration, left-recursive grammars can be correctly processed.

2

Not yet. It has been discussed. I wanted to have it to run more of the XSB test suite unmodified, but Theresa (Swift) thinks there are several issues with auto_table and wants to rethink some of this. The next target is incremental tabling, but first there is some work to realize safe destruction of tables, notably tables that are related through undefined answers.

Now that we can dynamically switch tabling on and off, you can write your own analysis code that creates tables at the necessary places :slight_smile:

3

I see. Great progress is being made! Thanks for that work. I hope to see incremental tabling soon!