in praise of tabling

Some time ago, in this newsgroup, Bart Demoen tried to interest me in
tabling. He told me of a web page about it. I read this page, totally
failed to understand it, and replied rather dismissively.

Today I had another look at tabling. I downloaded and installed XSB
Prolog (which is free and supports tabling) onto my Windows system. I
consulted in my favourite predicate:

shapes( X, _, 0 ) :- X<0, !.
shapes( 0, _, 1 ) :- !.
shapes( 1, _, 1 ) :- !.
shapes( _, 1, 1 ) :- !.
shapes( Cards, Suits, Result ) :-
FewerCards is Cards - Suits,
shapes( FewerCards, Suits, A ),
FewerSuits is Suits - 1,
shapes( Cards, FewerSuits, B ),
Result is A + B.

This calculates the number of "shapes" of card hand with C cards chosen
from S suits. For example, in bridge a hand has 13 cards from 4 suits,
resulting in 39 shapes such as (4,4,3,2) and (7,4,2,0). A call to
shapes( 13, 4, X ).
gives the result
X = 39

I gave XSB Prolog the query
shapes( 100, 80, X ).
and after 246.625 seconds, it answered 190567205.

Then I read the XSB documentation about tabling, failed to understand
most of it, but came across the directive
:- auto_table.
This directive lets it apply tabling the way it thinks will be helpful.
So I added it to my program, and re-ran the same query. This time it
gave the same answer, after only 0.0150 seconds.

So for this particular application, tabling produced a speed-up factor
of 16,000. This is really impressive.

I therefore strongly recommend tabling to anyone whose Prolog
application is suitable and time-critical. I wish I could find a
simple, Clocksin & Mellish-level, tutorial on how tabling works and how
to use it. I believe the availability of such a tutorial would help to
convince people of the benefits of tabling.

Nick
--
Nick Wedd nick@xxxxxxxxxxxxx
.

Relevant Pages

  • Re: in praise of tabling
    ... > I therefore strongly recommend tabling to anyone whose Prolog ... FewerCards is Cards - Suits, ... FewerSuits is Suits - 1, ...
    (comp.lang.prolog)
  • Re: in praise of tabling
    ... Today I had another look at tabling. ... shapes(Cards, Suits, Result):- ... FewerCards is Cards - Suits, ...
    (comp.lang.prolog)
  • Re: in praise of tabling
    ... This is another good example which illustrates the importance of tabling. ... Many people think tabling can be done on top of Prolog (as in the program ... > FewerCards is Cards - Suits, ...
    (comp.lang.prolog)