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@maproom.co.uk

Nick Wedd a écrit :
> 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
tabling is only helpfull when you have to do a lot of identical
calculus, natural langage processing is a particulary well suited domain
for tabling (and by extension dynamic programming).
Whenever you fear to be caught into any kind a cycle or whenever you
fear  to traverse more than once the nodes of a graph, tabling is a
solution (if not the only one ?)

have a look to this link
http://atoll.inria.fr/~clerger/work.html#Tabulation
and this one
ftp://ftp.inria.fr/INRIA/Projects/A...LP01-slides.pdf


just to situate, this is the homepage of a logic program compiler
(syntax very close to prolog's one) based on extensive use of tabulation
(DyALog) and whose aim's is to build a large range of parser (from cfg
to TAG and hpsg).
You'll find there some very technical papers on the subject.

Djamé
ps : my email djame DOT seddah AT free DOT fr

Nick Wedd wrote:
> I wish I could find a
> simple, Clocksin & Mellish-level, tutorial on how tabling works and
how
> to use it.

Well, tabling is, to a first order approximation, Prolog-speak for
memoization.  I think the Mercury Reference Manual section on it
says all you need to get the gist in a few paragraphs:
http://www.mercury.cs.mu.oz.au/info...o
n.html

In a nutshell, a tabled predicate is associated with a hash table of
some kind.  Whenever a new result for the predicate is computed, the
result is recorded in the hash table.  When the predicate is invoked
the hash table is first consulted to see if the answer(s) is (are)
already known; if so, they can be returned immediately.  Otherwise,
if there is no entry in the hash table then the predicate proper must
be evaluated to obtain a result.

The decision as to whether a predicate should be tabled or not depends
upon whether the cost of recomputation outweighs the cost of checking
the hash table and the cost of having the hash table in memory.

-- Ralph

"Nick Wedd" <nick@maproom.co.uk> wrote in message news:fLSewreKclZCFAZ+@maproom.demon.co.uk
..
>
> 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.
>

:- dynamic(shapesmemo/3).

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.

shapesmemo( X, _, 0 ) :- X<0.
shapesmemo( 0, _, 1 ).
shapesmemo( 1, _, 1 ).
shapesmemo( _, 1, 1 ).

shapes2( X, Y, Z ) :- shapesmemo( X, Y, Z) , !.
shapes2( Cards, Suits, Result ) :-
FewerCards is Cards - Suits,
shapes2( FewerCards, Suits, A ),
FewerSuits is Suits - 1,
shapes2( Cards, FewerSuits, B ),
Result is A + B,
assert(shapesmemo( Cards, Suits, Result)).

1 ?- time(shapes(100,80,X)).
% 1,387,019,573 inferences, 890.30 CPU in 947.29 seconds (94% CPU, 1557923 L
ips)

X = 190567205

Yes
2 ?- time(shapes2(100,80,X)).
% 40,223 inferences, 0.04 CPU in 0.04 seconds (98% CPU, 1004129 Lips)

X = 190567205

Yes


--
Geoff

> 1 ?- time(shapes(100,80,X)).
> % 1,387,019,573 inferences, 890.30 CPU in 947.29 seconds (94% CPU, 1557923
 Lips)
>
> X = 190567205
>
> Yes
> 2 ?- time(shapes2(100,80,X)).
> % 40,223 inferences, 0.04 CPU in 0.04 seconds (98% CPU, 1004129 Lips)
>
> X = 190567205
>
> Yes
>
>
> --
> Geoff
>

to be fair, somebody should compile shapes2 with xsb (with and without
tabling mode activated). I'd be really curious about its performance. I
thought that swi was faster than xsb in normal prolog mode.

Nick Wedd wrote:
> 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:
[...]
> 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.


It is funny how ALL replies to Nick's message missed important points,
so I will reply to Nick's message and on the side comment on the
replies (and replies to replies).

I am very happy that Nick discovered tabling as something useful.
Tabling should be in any logic programmer's toolbox. Like the torx
screw driver, you can't live withoput it, but tabling is a million
times more useful in everyday life.

Djame says that
> tabling is only helpfull when you have to do a lot of identical calculus
No. You really never have to do identical computations. You can ALWAYS
avoid them.
But the truth is: the natural specification (in terms of a programming
language) of many relations (or function - try fib) results in
repeated identical computations.
And then tabling helps you to avoid doing the identical computations.
So tabling is the tool that makes sure you NEVER have to do identical
computations.

Usually, understanding tabling does not depend on your understanding
hash table: this might be true for understanding tabling in Mercury as
Ralph seemed to imply, but I would be very surprised/disappointed if
the Mercury manual doesn't offer a more high level view of tabling.

Then there is the "do-it-yourself-memoing" by Geoff ... unfortunately
he refrains from making a statement, as if the program and the timing
results should speak for themselves. Maybe we are supposed to
interpret them and comment on them - well, here I go ... a screw
driver is only occasionally useful when removing a nail. When it
works, you feel like you win because you saved on buying tweezers.
But it is a false sense of victory/security: you have a proof that the
transformed program behaves like the original or is it just a
programming trick that was verified empirically ? Do you know when it
can be applied more generally ? Does it perhaps depend on undecidable
properties of the original program ?
I rest my case :-)

And finally, Djame writes:

> to be fair, somebody should compile shapes2 with xsb (with and without
> tabling mode activated). I'd be really curious about its
> performance. I thought that swi was faster than xsb in normal prolog
> mode.

What do you mean by "fair": the XSB solution wins hands down on all
important accounts. You don't change the original specification, add
just one declaration and you get a tremendous speedup while being
guaranteed that the answers are still correct.
And why would one want to use XSB on shapes2 with tabling activated ?
Just to blur the picture ?
XSB with tabling on shapes/3 gains less performance than the
assert-based shapes2 in SWI, but so what: see above for the important
things.

BTW1: XSB is faster than SWI in "normal" Prolog mode. It depends on
the benchmark, but for shapes/3, it is about a factor 3. So please
adjust your believes about relative speed of XSB/SWI.

BTW2: don't say "somebody should compile shapes2 with xsb" if that
"someone" could/should easily be yourself: XSB can be downloaded for
free on many platforms.

> 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.

Indeed, such a tutorial text is needed. Texts I know off go into too
much detail about the implementation, or the execution strategy - which
is fine once you are alreay convinced and want to know the fineprint,
but doesn't help to convince.

The following is not a tutorial, but if you have the guts,
R. S. Bird. Tabulation techniques for recursive programs. ACM Computing
Surveys, 12(4):403--417, Dec. 2002. is worth reading.

Cheers

Bart Demoen

On 2005-04-21, Djamé <djame@jamais-de-la-vie.com> wrote:
> 
>
> to be fair, somebody should compile shapes2 with xsb (with and without
> tabling mode activated). I'd be really curious about its performance. I
> thought that swi was faster than xsb in normal prolog mode.

It uses a lot of arithmetic.  Adding -O might help a lot.  Still though,
SWI-Prolog's strength is in the libraries, scalability for large apps,
development environment, threading, etc.  In the forthcomming years I
hope to be able to tackle performance and tabling :-)

Cheers --- Jan

Bart Demoen wrote:
> Usually, understanding tabling does not depend on your understanding
> hash table: this might be true for understanding tabling in Mercury
as
> Ralph seemed to imply, but I would be very surprised/disappointed if
> the Mercury manual doesn't offer a more high level view of tabling.

The MRM section on tabling says that results from a predicate are
recorded in a table (but says nothing of how the table is implemented)
and goes on to explain the loop-checking and minimal model variants.

My outline using the term "hash table" was just intended to present
a (very) rough idea of how tabling works.

-- Ralph

"Bart Demoen" <bmd@cs.kuleuven.ac.be> wrote in message news:1114110114.749048@seven.kulnet.
kuleuven.ac.be...
>
> Then there is the "do-it-yourself-memoing" by Geoff ... unfortunately
> he refrains from making a statement, as if the program and the timing
> results should speak for themselves. Maybe we are supposed to
> interpret them and comment on them - well, here I go ... a screw
> driver is only occasionally useful when removing a nail. When it
> works, you feel like you win because you saved on buying tweezers.
> But it is a false sense of victory/security: you have a proof that the
> transformed program behaves like the original or is it just a
> programming trick that was verified empirically ? Do you know when it
> can be applied more generally ? Does it perhaps depend on undecidable
> properties of the original program ?
> I rest my case :-)
>

So, adding auto_table makes you feel secure?

--
Geoff

Bart, all you say is probably righ, but you don't need to be rude just
to make your point.
Last time I checked XSB was a pain to install (it was in 2001/2002)
due to the lack of gnuconf toolchain, is it still ?

By fair I meant that I would like to see how xsb execute shapes2, that's
all. I know that tabuling an already tabled program is nonsensical and
so what ? just to see. but executing in normal mode a manually tabbled
one could be fun...


In fact, I would like to see a big benchmarking process  between
all the tabular prolog and the regular ones

xsb- B-Prolog - Dyalog     vs yap/swi/sictus and amzi


something which would enlight us about the performance, the quality of
documentation, the ease to integrate with other langage, quality of
built-in predicate, etc....



Have fun (that's why we enjoy prolog and logic progamming, no ?)

Djamé