Memoisation

[Michael Le Barbier Grünewald]

Dear Group,

I am trying to implement memoisation in C++ for abstract classes such that:

I have an abstract class A with a public `int eval()' method delegating itswork to the private purely virtual, customisable, `int reallyEval()' method.

Now, let's say that I have a few concrete classes B1, .., Bn derived from A..

Is this possible to add memoisation to B1...Bn by introducing a class C andletting B inherit from C instead of A?

If not, what is the best way to add memoisation?

A possibility would be to edit A and add a level of indirection in the `eval' chain by adding a private customisable `memoisedEval' method whose default version would just call `reallyEval' and the version in a class `MemoisedA' would implement actual memoisation.

This is as close as I could get of my goal, but this involves edition of A.Is this avoidable?


Thank you for your insights!
Michael

 

[gwowen]

If not, what is the best way to add memoisation?

I've implemented a very simple memoisation like this: [code not
checked...]

template memoised<class Btype> : public Btype
{
private:
int storedval;
bool stored;

virtual int reallyEval(){
if(!stored) {
storedval = Btype::reallyEval();
stored = true;
}
return storedval;
}
}

 

[Michael Le Barbier Grünewald]

Hye!

If not, what is the best way to add memoisation?

I've implemented a very simple memoisation like this: [code not
checked...]

Thank you for your answer, yet it leadsd me to a few other questions.

1. If we write Btype::reallyEval(), does it mean `the *very* method definedby Btype' or the overriden one? In the first case it means this memoisation scheme can only be used for leaf (final) classes, in the second that it does not work!

2. reallyEval() is typically a private member, so we need to let memoise bea friend of Btype: if memoise can only be used on leaves, this is quite alot of work.

 

[Qi]

Thank you for your answer, yet it leadsd me to a few other
questions.

1. If we write Btype::reallyEval(), does it mean `the
*very* method defined by Btype' or the overriden one?
In the first case it means this memoisation scheme can
only be used for leaf (final) classes, in the second
that it does not work!

Maybe you can dedicate your virtual function to sister
in a multiple inheritance?
http://www.parashift.com/c++-faq-lite/multiple-inheritance.html#faq-25.10

2. reallyEval() is typically a private member, so
we need to let memoise be a friend of Btype: if memoise
can only be used on leaves, this is quite a lot of work.

You can use a global accessor function to
access reallyEval(), and let that function
be Btypes' friend. Then all other classes
use that accessor function.


BTW, please keep your post text line within 79 letters.
Don't use so long line in newsgroups.

 

[Pavel]

Dear Group,

I am trying to implement memoisation in C++ for abstract classes such that:

I have an abstract class A with a public `int eval()' method delegating its work to the private purely virtual, customisable, `int reallyEval()' method.

Now, let's say that I have a few concrete classes B1, .., Bn derived from A.

Is this possible to add memoisation to B1...Bn by introducing a class C and letting B inherit from C instead of A?

Why not?

My understanding is (please correct me if I am wrong) that your B1..Bn classes
have some additional opportunity of memoization in reallyEval() to what's
already done in A::eval() *and* this opportunity is common in at least some of B
(otherwise, you would have done it differently in every Bi::reallyEval() by
delegating to something like Bi::reallyDoEval (non-virtual unless necessary for
other reasons).

So, if you have freedom to change Bi (which I assume you can because you are
considering inheriting them from a different base):

Add class C: public A and implement only one reallyEval() method there that does
that additional memoization and may call some protected pure virtual
doReallyEval() and only implement that doReallyEval, not reallyEval() in B1..Bn.

If not, what is the best way to add memoisation?

A possibility would be to edit A and add a level of indirection in the `eval' chain by adding a private customisable `memoisedEval' method whose default version would just call `reallyEval' and the version in a class `MemoisedA' would implement actual memoisation.

This is as close as I could get of my goal, but this involves edition of A. Is this avoidable?


Thank you for your insights!
Michael

HTH
-Pavel

 

[Michael Le Barbier Grünewald]

Hi Pavel, thank you for your comments.

So, if you have freedom to change Bi (which I assume you can because you are
considering inheriting them from a different base):

Add class C: public A and implement only one reallyEval() method there that does
that additional memoization and may call some protected pure virtual
doReallyEval() and only implement that doReallyEval, not reallyEval() in B1..Bn.

after reading this and the other contributions, I feel it is not
really possible to add memoisation to a class just by changing the
basis class...

What I like in your proposition, is that B1..Bn really gets
tranparently memoised without code editing, but the classes have
to be a bit reworked.

 

[Michael Le Barbier Grünewald]

Hello Qi,

Maybe you can dedicate your virtual function to sister
in a multiple inheritance?
http://www.parashift.com/c++-faq-lite/multiple-inheritance.html#faq-25.10

I do not really understand what you mean here...

I ``discovered'' the `delegate to sister' idiom for a few weeks
and used this in the following manner:

A is an ABS, A': virtual public A implements a concrete A.
P : virtual public A implements algorithms involving A,
and to get a concrete P we just need to let

P': public P, public A'

In this example using `delegate to sister' can be avoided by
letting P access A through a reference and this is probably
the most idiomatic way to go. Just out of curiosity,
in which sort of situations can be `the delegate to sister'
successfully used?

You can use a global accessor function to
access reallyEval(), and let that function
be Btypes' friend. Then all other classes
use that accessor function.

Thank you for the tip, I did not know about it!

 

[Michael Le Barbier Grünewald]

Hello gwowen, thank you for your careful clarifications!

(I am sorry for the long lines, I am used to access Newsgroups
with a sensible client, but here and there must I use Gg groups.
I will try to keep this in mind, though.)