C++Talk.NET

Dylan Nicholson · Guest

I was reading through some of the proposals for adding multimethods to
C++, including implementation details that talked a lot about RTTI
etc. etc., and O(N) call times depending on the number of multimethods
defined.
But surely there is a simple O(1) method that doesn't use RTTI at all,
providing that you can modify the vtable of a class on the fly (which
of course a compiler can do).

So for instance if an initial class definition is:

struct object
{
virtual ~object() { }
};

It contains a vtable with just the one entry.

Suppose the compiler then encounters the following function
declaration:

void interact(virtual object*, virtual object*);

It could then add a further function to the vtable, something like:

virtual __interact(object* obj) { interact(this, obj); }

(Of course for many compilers, it may be possible to point the vtable
entry directly to the standalone 'interact' function).

It then comes across the following:

struct square : object
{
int x;
int y;
int width;
};
struct circle : object
{
int x;
int y;
int radius;
};

void interact(virtual square* sqr, virtual circle* crc);

At this point, it needs to add a new entry to object's vtable like so:

virtual __interact1(circle* crc) { interact(this, crc); }

Then override this in square:

virtual __interact1(circle* crc) { interact(this, crc); }

And override circle's __interact entry:

virtual __interact(object* obj) { obj->__interact1(this); }

It might then encounter:

struct triangle : object
{
/* whatever */
};

void interact(virtual triangle* crc, virtual circle* tri);

This would only require overriding __interact in triangle's vtable:

virtual __interact1(circle* crc) { interact(this, crc); }

Now when an actual call to

interact(obj1, obj2)

is encountered in the code, this is translated as:

obj1->__interact(obj2);

So that if obj1 is a square, it will call

obj2->__interact1(obj1)

Which is obj2 is a circle, will call

void interact(virtual square* sqr, virtual circle* crc);

Likewise, if obj1 is a triangle, it will call

void interact(virtual triangle* tri, virtual circle* crc);

as expected. In any other circumstance, it would call the original
interact(object*, object*) function (which I suppose could be
undefined, thus generate a 'pure virtual function call' exception or
some such).

I haven't thought it much through for more than 2 virtual parameters,
but it would seem to follow a similar (if more complex) pattern.

I take it this isn't under serious consideration for inclusion in the
standard at this point, but is there much interest in it?

Dylan

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Julian Smith · Guest

On 3 Mar 2004 06:49:55 -0500
[email]wizofaus (AT) hotmail (DOT) com[/email] (Dylan Nicholson) wrote:

Ben Hutchings · Guest

Dylan Nicholson wrote:

Dylan Nicholson · Guest

Ben Hutchings <do-not-spam-benh (AT) bwsint (DOT) com> wrote

Dylan Nicholson · Guest

Julian Smith <jules (AT) REMOVETHIS (DOT) op59.net> wrote

Lorenzo Bettini · Guest

Hi

I developed doublecpp:

Doublecpp is a preprocessor for C++ that handles a new linguistic
construct for defining branches of a multi-method. The "right" branch
of such a method will be selected dynamically at run-time according to
the actual type of the object on which the method is invoked and to the
actual type of the first argument: double dispatch.

http://www.lorenzobettini.it/software/doublecpp/index.html

Doublecpp is free software; you are free to use, share and modify it
under the terms of the GNU General Public License (see COPYING).

The double dispatch is performed in *constant* time O(1), since it uses
dynamic binding twice (with a technique similar to the Visitor pattern).

Lorenzo

--
+-----------------------------------------------------+

Ben Hutchings · Guest

Dylan Nicholson wrote: