Home > Archive > Prolog > April 2005 > in praise of tabling
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
in praise of tabling
|
|
| Nick Wedd 2005-04-20, 3:59 pm |
| 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
| |
| rafe@cs.mu.oz.au 2005-04-21, 3:59 am |
| 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...evaluation.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
| |
| Geoffrey Summerhayes 2005-04-21, 8:58 am |
|
"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 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
| |
|
|
> 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.
| |
| Bart Demoen 2005-04-21, 8:57 pm |
| 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
| |
| Jan Wielemaker 2005-04-21, 8:57 pm |
| 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
| |
| rafe@cs.mu.oz.au 2005-04-22, 8:57 am |
|
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
| |
| Geoffrey Summerhayes 2005-04-22, 8:57 am |
|
"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é
| |
| Bart Demoen 2005-04-22, 8:57 pm |
| Geoffrey Summerhayes wrote:
> So, adding auto_table makes you feel secure?
Yes. Does that make you feel like adding auto_table ?
(I hope we can get out of this Elisa mode some day)
Cheers
Bart Demoen
| |
| Bart Demoen 2005-04-22, 8:57 pm |
| Djamé wrote:
> Bart, all you say is probably righ, but you don't need to be rude just
> to make your point.
If you could point out where you think I was rude, I might learn
something - the rudeness you sensed was not intented by me.
> 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 ?
It is easy to check that by mailing to the XSB people or by downloading
XSB and trying it out - after you did that, you could contribute to
c.l.p. by sharing an experience.
> By fair I meant that I would like to see how xsb execute shapes2, that's
> all.
It is not the common meaning of "fair", that's all.
> but executing in normal mode a manually tabbled
> one could be fun...
Sure - and you expect someone else to provide the entertainment. Fair
enough.
> 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....
I do not know of benchmarking of documentation quality (which is
difficult to measure objectively I think) or of integration ease,
but about performance (tabling, builtins, other issues) there is a fair
amount of published literature.
BTW1, in the list of Prologs with tabling, you don't mention ALS-Prolog
(with tabling based on Dynamic Reordering of Alternatives - abbreviated
DRA).
BTW2, you put Yap in the "regular" Prologs, but Yap has tabling.
Cheers
Bart Demoen
| |
|
| Bart Demoen a écrit :
> Djamé wrote:
>
>
>
> If you could point out where you think I was rude, I might learn
> something - the rudeness you sensed was not intented by me.
Come on, you perfectly know what I meant when I said you were rude...
In french I'll said you were "gentiment moqueur" (nicely mocker ?). I'm
sorry, I should have badly used "rude" instead of nicely mocker......
>
>
>
>
> It is easy to check that by mailing to the XSB people or by downloading
> XSB and trying it out - after you did that, you could contribute to
> c.l.p. by sharing an experience.
as opposed to when ?
>
>
>
> It is not the common meaning of "fair", that's all.
>
>
>
> Sure - and you expect someone else to provide the entertainment. Fair
> enough.
not rude. Of course. it's not like I was expecting anything. Isn't this
ng supposed to be a place to talk ? I should have replaced "rude" by
"telling this guy to get the hell out of here"
>
>
>
> I do not know of benchmarking of documentation quality (which is
> difficult to measure objectively I think)
one tip : the capacity to learn how to use a tool reading the less
possible number of pages or the number of running example given to
describe a behaviour..
> or of integration ease,
number of mixed project using this kind of prolog with another language ?
> but about performance (tabling, builtins, other issues) there is a fair
> amount of published literature.
> BTW1, in the list of Prologs with tabling, you don't mention ALS-Prolog
> (with tabling based on Dynamic Reordering of Alternatives - abbreviated
> DRA).
Thanks for that one.
>
> BTW2, you put Yap in the "regular" Prologs, but Yap has tabling.
It's not mentionned on their pages, good to know.
>
>
> Cheers
>
> Bart Demoen
Thanks
Djamé
| |
| lager@ling.gu.se 2005-04-23, 8:56 am |
| Nick Wedd wrote:
> 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.
There is this draft version of a book by David Warren which seems to be
right on target:
http://www.cs.sunysb.edu/~warren/xsbbook/
Very interesting stuff - too bad he never finished it...
- Torbj=F6rn
| |
| Neng-Fa Zhou 2005-04-23, 8:56 pm |
| 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@maproom.co.uk
>
| |
| Geoffrey Summerhayes 2005-04-23, 8:56 pm |
|
"Bart Demoen" <bmd@cs.kuleuven.ac.be> wrote in message news:1114196820.313867@seven.kulnet.kuleuven.ac.be...
> Geoffrey Summerhayes wrote:
>
>
> Yes. Does that make you feel like adding auto_table ?
> (I hope we can get out of this Elisa mode some day)
>
Sure does! Oops, my prolog doesn't have tabling. Let
me just ask my boss if we can switch. He doesn't seem
pleased with the idea of rewriting all the implementation
dependent code for some reason, talked about man-hours
and money. Sometimes I think these business types just
don't care about pretty code, just the profit line.
Well, without tabling, I'm screwed there is nothing else
I can do to speed up the code. Especially after your
argument that refactoring code is bad because it might
introduce bugs.
Bugs are bad.
OTOH, am I to assume from the fact that you didn't
provide a concrete counter-example of the code giving
an incorrect result that, at least in this instance, I
may have blindly stumbled, into a correct transformation?
Naaah, I must be wrong.
I don't have anything against tabling, but just putting
auto_table into code is no guarantee of a speed-up,
anything with side-effects, whether they influence the
results or not, have to turn it off, or the tabling
algorithm is incorrect. You cannot skip the side-effect.
Phew, enough non-Eliza for you?
--
Geoff
| |
| Maori Scarey 2005-04-26, 4:01 am |
| rafe@cs.mu.oz.au a écrit :
> 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.
Yes but I guess the subtle parts of the tabling strategy is to effectively
table calls, not returns, so as to act on recursion loops.
| |
| Bart Demoen 2005-04-26, 4:00 pm |
| Maori Scarey wrote:
> Yes but I guess the subtle parts of the tabling strategy is to
> effectively table calls, not returns, so as to act on recursion loops.
>
No. Or maybe "inclusive no" if that makes sense.
Tabling calls is one thing, necessary, but not sufficient, to do decent
tabling. Tabling just calls can prevent some loops (the ones that
tabling or memoing in general can catch). Tabling "returns" is the hard
part, because one would like to share as much of the return (the answer)
with the call (and other calls) as possible: that's the thing that makes
the data structures for doing tabling "subtle" - as opposed to doing
assert/retract and do-it-yourself-memoing.
Cheers
Bart Demoen
| |
| Bart Demoen 2005-04-26, 8:57 pm |
| djame wrote:
> In french I'll said you were "gentiment moqueur" (nicely mocker ?).
Ok. I'll settle for "gentiment moqueur" - it pays off to haggle :-)
>
>
> as opposed to when ?
I don't understand that question in reply to what I wrote, sorry.
Cheers
Bart Demoen
| |
| Bart Demoen 2005-04-26, 8:57 pm |
| Geoffrey Summerhayes wrote:
> "Bart Demoen" <bmd@cs.kuleuven.ac.be> wrote in message news:1114196820.313867@seven.kulnet.kuleuven.ac.be...
>
>
>
> Sure does! Oops, my prolog doesn't have tabling. Let
> me just ask my boss if we can switch.
My apologies: I didn't understand that by secure, you were hinting
at job-security. Job-security arguments beats all other arguments
all the time of course.
> Well, without tabling, I'm screwed there is nothing else
> I can do to speed up the code.
Sure you can - in the case of the presented example, you could try
to solve the recurrence equation.
> Especially after your
> argument that refactoring code is bad because it might
> introduce bugs.
You misunderstood me: if you are in the desert and your boss is
breathing in your neck, refactoring the way you did is just fine if
that keeps your boss happy.
> Bugs are bad.
Yes. Your point being ?
> OTOH, am I to assume from the fact that you didn't
> provide a concrete counter-example of the code giving
> an incorrect result that, at least in this instance, I
> may have blindly stumbled, into a correct transformation?
The question is not so much whether the (your) final code with assert is
correct in this particular instance, but whether it is clear what are
the properties of the original program that make your code correct.
You might be smart enough to recognise that, but isn't it worth pointing
at these properties ?
> Naaah, I must be wrong.
Don't be so negative about yourself ! Sorry, Elisa mode again :-)
> I don't have anything against tabling, but just putting
> auto_table into code is no guarantee of a speed-up,
> anything with side-effects, whether they influence the
> results or not, have to turn it off, or the tabling
> algorithm is incorrect. You cannot skip the side-effect.
Your transformation is not a guarantee to speed-up (there must be
examples where using assert similarly in similar circumstances
makes complexity worse).
Your transformation doesn't work in the presence of side-effects
either (I know tabling as in XSB doesn't preserve side-effects, but
neither does any other implemented and usable memoing method - Paul
Tarau and I worked shortly on a method that does, but we abandoned it).
So all your arguments against auto-table apply to your method just as
well, and to ANY implemented memoing method.
As a programmer, one needs to know what one is doing.
> Phew, enough non-Eliza for you?
No. More of this !
Cheers
Bart Demoen
|
|
|
|
|