Re: in praise of tabling
- From: "Neng-Fa Zhou" <nzhou@xxxxxxx>
- Date: Sat, 23 Apr 2005 18:26:32 GMT
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
posted by Geoffrey Summerhayes), but it is extremely hard to get reasonable
performance and even harder to guarantee the completeness. The execution
mechanism of tabling in general is quite complicated (as stated in the
Mercury page) but not linear tabling. As demonstrated by our
implementation in B-Prolog, it is efficient as well.
Cheers,
Neng-Fa
> 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
>
.
- References:
- in praise of tabling
- From: Nick Wedd
- in praise of tabling
- Prev by Date: Wolf, Goat, Cabbage problem again
- Next by Date: Re: in praise of tabling
- Previous by thread: Re: in praise of tabling
- Next by thread: Interpreter/Compiler texts
- Index(es):
Relevant Pages
|
|
