Tabling and left-recursive grammars

[Markus Triska]

Hi all,

in my view, one of the greatest benefits of tabling is that - at long last! - it enables us to parse directly with left-recursive grammars.

Like many more recent features of SWI-Prolog, tabling is another great example of a declarative enhancement that has great practical value, and makes countless beginners' questions completely obsolete or at least far less pressing than they have been in the past.

What do I mean by this? Here is an example:

expr(id(a)) --> [a].
expr(A+B)   --> expr(A), [+], expr(B).

This DCG looks natural and straight-forward enough. Unfortunately, it quickly leads to problems without tabling, a phenomenon many of us are painfully familiar with:

?- phrase(expr(E), [a,+,a,+,a]).
%@ E = id(a)+ (id(a)+id(a)) ;
%@ <nontermination>

One solution is found, but the second way to parse this is not.

In contrast, if we enable tabling for expr//1, we get both solutions without changing the grammar at all:

?- phrase(expr(E), [a,+,a,+,a]).
%@ E = id(a)+id(a)+id(a) ;
%@ E = id(a)+ (id(a)+id(a)) ;
%@ false.

Nice, isn't it?

Currently, I have had to resort to a small trick to enable tabling for this DCG: I produced a listing of the DCG, and then added tabling for expr/3.

If possible, please provide a way so that we can simply say:

:- table expr//1.

This feature is a huge relief for me.

Thank you and all the best!
Markus

[Jan Wielemaker]

Hi Markus,

Except for a stupid typo in the wrapper generator, `:- table expr//1.`
already worked. Now it really works. There is a little but though:

```
:- ['../tabling_library/tabling'].
:- ['../tabling_library/table_print'].

:- table expr//1.

expr(id(a)) --> [a].
expr(A+B) --> expr(A), [+], expr(B).

test(E) :-
phrase(expr(E), [a,+,a,+,a]).
```

?- test(E).
E = id(a)+ (id(a)+id(a)) ;
E = id(a)+id(a)+id(a).

So far, so good! ... but

2 ?- print_existing_tables.
EXISTING TABLES
===============
table1: user:expr(_G51,[a,+,a,+,a],[])
table2: user:expr(_G103,[a,+,a,+,a],_G105)
table3: user:expr(_G167,[a,+,a],[])
table4: user:expr(_G201,[a,+,a],_G203)
table5: user:expr(_G277,[a],[])
table6: user:expr(_G314,[a],_G316)

Yes, you get nice logically sound results. Quite often the price you
need to pay in terms of space in this case is large though. This is
probably in general the deception of tabling: it is nice way to reason
with complicated interrelated rules easily. It works great for one-shot
solutions in relatively small domains. It easily gets prohibitively
expensive in terms of memory usage once your domain gets bigger.

It is surely useful for some of the ICLP programming contest problems
though :) Last years problems were no longer solvable in pure Prolog.
This all must work before October :)

Cheers --- Jan

On 05/11/2016 12:59 AM, Markus Triska wrote:
> Hi all,
>
> in my view, one of the greatest benefits of tabling is that - at long

> last! - it enables us to parse /directly/ with left-recursive grammars.

>
> Like many more recent features of SWI-Prolog, tabling is another great
> example of a declarative enhancement that has great practical value, and
> makes countless beginners' questions completely obsolete or at least

> /far/ less pressing than they have been in the past.

> --
> You received this message because you are subscribed to the Google
> Groups "SWI-Prolog" group.
> To unsubscribe from this group and stop receiving emails from it, send
> an email to swi-prolog+...@googlegroups.com
> <mailto:swi-prolog+...@googlegroups.com>.
> Visit this group at https://groups.google.com/group/swi-prolog.
> For more options, visit https://groups.google.com/d/optout.

[Markus Triska]

Hi Jan,

Except for a stupid typo in the wrapper generator, `:- table expr//1.`
already worked. Now it really works.

Awesome! Thank you!

Yes, you get nice logically sound results. Quite often the price you
need to pay in terms of space in this case is large though. This is
probably in general the deception of tabling: it is nice way to reason
with complicated interrelated rules easily. It works great for one-shot
solutions in relatively small domains. It easily gets prohibitively
expensive in terms of memory usage once your domain gets bigger.

I could copy this paragraph verbatim into the CLP(B) documentation after replacing "tabling" with "CLP(B)" ;-)

If it's any consolation, that's all still better than no result at all! It's great that this feature is now available, and I'm sure it will still get a lot better for many use cases.

[Jan Burse]

Hi,

Woa, just browsing the web, find a paper about a grammar (global) constraint:
http://www.a4cp.org/sites/default/files/nina_narodytska_-_reformulation_of_global_constraints.pdf

Bye