Multimethods idioms and library support

[itaj sherman]

Is there any concensus idiom on how to code with multimethods?
How would you go about coding them today?

There's the multi-dispatch idiom: For each override type of the first
parameter. declare a different virtual function to dispatch the second
parameter.
http://en.wikipedia.org/wiki/Multiple_dispatch
But it requires that the definition of every polymorphic class of one
parameter #includes the definition of all polymorphic types of the
following parameter. This makes the code messy, and not scalable due
to circular dependencies between modules.

I had to use them for a some medium size hirarchy and this idiom
became quite a bother. Not to mention that users coult not add their
types becuase this idiom is circular dependant.

I'm more interested in some library that would support this in a more
generic way.
I suppose any such library would need some compiler specific code for
each compiler that it supports, but the API should be the same.

BTW, Stroustrup in "The Design and Evolution of C++ Bjarne Stroustrup"/
13.8 comsiders adding multimethods as a c++ language favorable.
Although less important than many other features. And there are some
proposals for it. However, I don't know there's currently any point in
the future when it's predicted to be added. And a library solutions
seems good

itaj

 

[Victor Bazarov]

Is there any concensus idiom on how to code with multimethods?
How would you go about coding them today?

There's the multi-dispatch idiom: For each override type of the first
parameter. declare a different virtual function to dispatch the second
parameter.
http://en.wikipedia.org/wiki/Multiple_dispatch
But it requires that the definition of every polymorphic class of one
parameter #includes the definition of all polymorphic types of the
following parameter. This makes the code messy, and not scalable due
to circular dependencies between modules.

Not necessarily. If your arguments are references (as they should be),
you only need forward-declarations to declare those member functions.
In the translation unit, of course, you'll need the corresponding
headers included. But that's no mess, that's just a necessity.

[..]

V

 

[itaj sherman]

Not necessarily.  If your arguments are references (as they should be),
you only need forward-declarations to declare those member functions.
In the translation unit, of course, you'll need the corresponding
headers included.  But that's no mess, that's just a necessity.

Agreed.
But another big problem is also that you need many different virtual
functions declarations each belongs to a certain polymorphic class of
the next parameter. In the wikipedia example the names of the
functions contain the class name, or you can add a dummy parameter
using the type. But they must be different virtual functions declared.
This is also what I meant by circular dependency, not just the
#include.

The problem with that is that one cannot use this multimethods idiom
in a core module with intentions for users of the module to inherit
his classes and define their overrides.

itaj

 

[Victor Bazarov]

Agreed.
But another big problem is also that you need many different virtual
functions declarations each belongs to a certain polymorphic class of
the next parameter. In the wikipedia example the names of the
functions contain the class name, or you can add a dummy parameter
using the type. But they must be different virtual functions declared.
This is also what I meant by circular dependency, not just the
#include.

Uh... Yes. If an object of classA has to interact with objects of
classB, classC and classD, all those classes will need virtual functions
to interact with an object of classA. And if they need to interact with
each other, they *need to know* about each other. And if you need to
override those behaviors, you're going to have to provide some way for
those objects to make the distinction between objects with which they
need to interact. If that all is a "well, duh" moment for you, don't
blame the language or the model, change them.

The problem with that is that one cannot use this multimethods idiom
in a core module with intentions for users of the module to inherit
his classes and define their overrides.

Why not? The core module provides a way for objects *defined in it* to
interact. Why can't you expand the core module model and provide more
interaction between yet unknown classes (that you define in your own
modules)? Do you see the idiom breaking down somehow?

What problem are you trying to solve? Let's try together. Show us
where you hit an obstacle, perhaps we can come up with a solution...

V

 

[Stuart Redmann]

Why not?  The core module provides a way for objects *defined in it* to
interact.  Why can't you expand the core module model and provide more
interaction between yet unknown classes (that you define in your own
modules)?  Do you see the idiom breaking down somehow?

One of the problems is that you would have to add overloaded versions
for each of your derived class in the base class interface. This may
not be possible for libraries unless it is a header-only library.

Regards,
Stuart

 

[itaj sherman]

What I was saying about this specific dynamic_cast dispatch idiom, is
that I don't think it's a very good one.
By "mess" I meant extra bookkeeping work on code management, that
would be unnecessary if there was a better library to support
multimethods instead this specific idiom.
I'm trying see if anyone knows such library, or a better idiom.

Why not? The core module provides a way for objects *defined in it* to
interact. Why can't you expand the core module model and provide more
interaction between yet unknown classes (that you define in your own
modules)? Do you see the idiom breaking down somehow?

What problem are you trying to solve? Let's try together. Show us
where you hit an obstacle, perhaps we can come up with a solution...

Very, well.
I won't get into descibing the real module I was working on that
triggered my problem, but I can describe a very short example to
demonstrate it.

For example:
An animal kingdom module defines base classes Carnivour and Prey.
And a multimethod:
void hunt( Carnivour const&, Prey& );
I want to enable users of my module to have their classes inherited
from Carnivour or Prey, and enable them to define override functions
for hunt special for their types.
A certain user then create his classes: Lion, Anaconda and Bear
derived from Carnivour, Giraffe and Gazelle derived from Prey.
He also wants to override the possible hunt implementation.

The following code demonstrates how I wished it could be written
(based on the proposition in "The Design and Evolution of C++ Bjarne
Stroustrup").
I'm looking for a library that will support such multimethods.
Basically replacing the hipothetic language syntax with some library
constrcuts. But enable the same general construction and dependency of
the module and user code.
The dynamic_cast dispatch idiom cannot do that (it's becoming too
lengthy, I'll demonstrate if further post).

//using some hipothetic multimethod syntax

//////my module "animal kingdom"
////animal_kingdom/carnivour.h
class Carnivour
{
};

////animal_kingdom/prey.h
class Prey
{
};

////animal_kingdom/hunt.h
//define a multimethod void hunt( Carnivour const&, Prey& )
#include "carnivour.h"
#include "prey.h"

void hunt( virtual Carnivour const& carnivour, virtual Prey& prey ) =
0;


//////From here on the user code

////lion.h
#include "carnivour.h"
class Lion: public Carnivour
{
};

////the same way files for:
class Anaconda: public Carnivour {};
class Bear: public Carnivour {};
class Giraffe: public Prey {};
class Gazelle: public Prey {};

////hunt_override_1.cpp
#include "lion.h"
#include "Gazelle.h"

void hunt( override Lion&, override Gazelle& )
{
//jumps on it and bite its neck
}

//and same for:
void hunt( override Lion&, override Girrafe& )
{
//bite its ass
}

void hunt( override Anaconda&, override Gazelle& )
{
//inject venom
}

//Anaconda can't kill girrafes so no override for that one

void hunt( override Bear&, override Prey& )
{
//because Bears catch everything in the same way lol.
}

//main.cpp
int main()
{
Carnivour& carnivour = Bear(...);
Prey& prey = Gazelle(...);
void const result( hunt( carnivour, prey ) );
}

itaj

 

[itaj sherman]

What I was saying about this specific dynamic_cast dispatch idiom, is
that I don't think it's a very good one.
By "mess" I meant extra bookkeeping work on code management, that
would be unnecessary if there was a better library to support
multimethods instead this specific idiom.
I'm trying see if anyone knows such library, or a better idiom.

The dynamic_cast dispatch idiom cannot do that (it's becoming too
lengthy, I'll demonstrate if further post).

Well, I was wrong about "cannot do that". It is possible for this
user.
But it requires listing all dynamic_cast options for derived class.
And the user still has to list them all in one place.
On the other hand if someone later wants to add carnivour and prey
classes he must have access to the implementations of other classes.
I'll work on a good example for that.
In any case I think it's much more bookkeeping than could be with some
library support. Especially if it were 3 or more virtual parameters.

However, I am mainly interested in how people usually code such cases,
without any reference to my opinion about this idiom.
So whichever way you use (or would use) in such cases, I'll take it as
your answer to my question (this idiom or anything else).

itaj

 

[Stuart Redmann]

On 22 Feb., itaj sherman wrote:
[snip]

I won't get into descibing the real module I was working on that
triggered my problem, but I can describe a very short example to
demonstrate it.

For example:
An animal kingdom module defines base classes Carnivour and Prey.
And a multimethod:
void hunt( Carnivour const&, Prey& );
I want to enable users of my module to have their classes inherited
from Carnivour or Prey, and enable them to define override functions
for hunt special for their types.
A certain user then create his classes: Lion, Anaconda and Bear
derived from Carnivour, Giraffe and Gazelle derived from Prey.
He also wants to override the possible hunt implementation.

The following code demonstrates how I wished it could be written
(based on the proposition in "The Design and Evolution of C++ Bjarne
Stroustrup").
I'm looking for a library that will support such multimethods.
Basically replacing the hipothetic language syntax with some library
constrcuts. But enable the same general construction and dependency of
the module and user code.

[snip]

The following should scale okay.

#include <iostream>

class CarnivourDispatch;

class Prey
{
public:
virtual void dispatchMe (CarnivourDispatch*) = 0;
};


class Carnivour
{
public:
virtual void hunt (Prey& prey) = 0;
};

class Giraffe;
class Gazelle;

class CarnivourDispatch : public Carnivour
{
public:
virtual void hunt (Prey& prey)
{
prey.dispatchMe (this);
}
virtual void _hunt (Gazelle&) = 0;
virtual void _hunt (Giraffe&) = 0;
};

class Lion: public CarnivourDispatch
{
protected:
virtual void _hunt (Gazelle& Gazelle)
{
std::cout << "Lion jumps on gazelle and bites its neck.";
}
virtual void _hunt (Giraffe&)
{
std::cout << "Lion bites giraffe's ass";
}
};

class Giraffe : public Prey
{
public:
void dispatchMe (CarnivourDispatch* Hunter)
{
Hunter->_hunt (*this);
}
};

class Gazelle : public Prey
{
public:
void dispatchMe (CarnivourDispatch* Hunter)
{
Hunter->_hunt (*this);
}
};

//main.cpp
int main()
{
Carnivour* carnivour = new Lion;
Prey* prey1 = new Gazelle;
Prey* prey2 = new Giraffe;
carnivour->hunt (*prey1);
carnivour->hunt (*prey2);
}

Probably the dispatchMe-methods in Prey derived class should be added
by a template, but I tried to keep it simple.

Regards,
Stuart

 

[itaj sherman]

On 22 Feb., itaj sherman wrote:


The following should scale okay.

[snip code]

You replace a dynamic_cast if-else-if list with a virtual function
Prey::dispatchMe. This save the detailing on 1 parameter. I'm not sure
it would be so helpful for 3 or more virtual parameters.
Also the more internal animal_kingdom module contains Prey which has
to know (forward-dec) the name of CarnivourDispatch which in turn has
to know all polymorphic types under Prey. As it is, it breaks the
encapsulation of the module, becuase user must make it somehow aware
of his different derivations. I think that would be especially more
problematic if there was another user-code adding more derivations,
but that would want to use some of these derivations too.

Probably the dispatchMe-methods in Prey derived class should be added
by a template, but I tried to keep it simple.

Yeah, ultimately everything should work conviniently for override
implementation using some template functions, and also if any of the
base classes (Carnivour or Prey) was actualy a template class.
I don't think we stepped on anything for which that would cause
difference.

I'm sorry what I say here is not 100% formally clear. It's more like a
brainstorm to evaluate idioms for multimethods.

itaj

 

[itaj sherman]

BTW, Stroustrup in "The Design and Evolution of C++ Bjarne Stroustrup"/
13.8 comsiders adding multimethods as a c++ language favorable.
Although less important than many other features. And there are some
proposals for it. However, I don't know there's currently any point in
the future when it's predicted to be added. And a library solutions
seems good

....Stroustrup in "The Design and Evolution of C++ Bjarne Stroustrup"
paragraph 13.8, considers multimethods as a c++ language feature, a
favorable addition. But less important...

itaj

 

[Paul]

Is there any concensus idiom on how to code with multimethods?
How would you go about coding them today?

Have you read this?
http://www2.research.att.com/~bs/multimethods.pdf

HTH
Paul.

 

[Larry Evans]

On 02/22/11 10:32, itaj sherman wrote:
[snip]

I'm sorry what I say here is not 100% formally clear. It's more like a
brainstorm to evaluate idioms for multimethods.

itaj

Hi ita,

If g++ is available, you can use the -std=gnu++0x option to enable
variadic templates and then use the code demonstrated the
test driver here:

http://svn.boost.org/svn/boost/sandbox/variadic_templates
/libs/composite_storage/sandbox/pack
/one_of_multiple_dispatch.test.cpp

to do multimethods. Note that that demo uses 2 different methods.
One uses a disjoint union data type (the one with the one_of_maybe tag)
the other uses virtual methods (which is the one you're interested in).
To select the virtual method version, include:

#define REIFIER_VISITOR

in the driver.

HTH.

-Larry

 

[itaj sherman]

Hi ita,

If g++ is available, you can use the -std=gnu++0x option to enable
variadic templates and then use the code demonstrated the
test driver here:

Sure c++0X is good.

http://svn.boost.org/svn/boost/sandbox/variadic_templates
/libs/composite_storage/sandbox/pack
/one_of_multiple_dispatch.test.cpp

to do multimethods. Note that that demo uses 2 different methods.
One uses a disjoint union data type (the one with the one_of_maybe tag)
the other uses virtual methods (which is the one you're interested in).
To select the virtual method version, include:

#define REIFIER_VISITOR

in the driver.

I look at this file, and I'm not sure where to begin.
Is there any documentation I can read for the code it uses?
I only had the boost release version. I'm downloading this svn tree
now...

Also, this sandbox is like new libraries that aren't yet in boost?
Do you mean that boost will include this multimethod support?

itaj

 

[Larry Evans]

Sure c++0X is good.


I look at this file, and I'm not sure where to begin.
Is there any documentation I can read for the code it uses? Sorry, No.
I only had the boost release version. I'm downloading this svn tree
now...

Also, this sandbox is like new libraries that aren't yet in boost?
Do you mean that boost will include this multimethod support?

Not unless I finally do some documentation and submit it for
review and it's accepted.
However, I'm still working on other things and still have to
figure a way to make the multiple-dispatch code faster.
A timing comparison w.r.t. boost::variant is in the boost vault
as indicated by this post:

http://article.gmane.org/gmane.comp.lib.boost.user/65480

shows it has quadratic performance w.r.t. number of variants.
Although boost::variant also suffers from this, it does
suffer as badly, as indicated by the timing curves shown
in the vault .zip file.

 

[Larry Evans]

On 02/22/11 12:14, Larry Evans wrote:
[snip]

Although boost::variant also suffers from this, it does

^does not
[snip]

 

[itaj sherman]

On 02/22/11 11:44, itaj sherman wrote:

Is it supposed to be possible do checkout the whole svn tree?
It keeps breaking.
Should I better take just part?

Not unless I finally do some documentation and submit it for
review and it's accepted.

For compisite_storage you mean? Or certain part?

However, I'm still working on other things and still have to
figure a way to make the multiple-dispatch code faster.
A timing comparison w.r.t. boost::variant is in the boost vault
as indicated by this post:

http://article.gmane.org/gmane.comp.lib.boost.user/65480

shows it has quadratic performance w.r.t. number of variants.

What exactly is the name of
"variants"? Is it like number of virtual parameters for the function?

Although boost::variant also suffers from this, it does
suffer as badly, as indicated by the timing curves shown
in the vault .zip file.

One measure is the assignment operator.
What does the binary test do?
I know nothing about boost development, what does it measure? Can you
point me to some reading about it?

So one_of_multiple_dispatch is supposed to do what I want?
What exactly is the relation of it with one_of_maybe?

Is it only you working on it? Which parts?

itaj

 

[itaj sherman]

Not unless I finally do some documentation and submit it for
review and it's accepted.
However, I'm still working on other things and still have to
figure a way to make the multiple-dispatch code faster.

This is about "compile faster" right?

itaj

 

[itaj sherman]

Not unless I finally do some documentation and submit it for
review and it's accepted.
However, I'm still working on other things and still have to
figure a way to make the multiple-dispatch code faster.
A timing comparison w.r.t. boost::variant is in the boost vault
as indicated by this post:

That is compilation time, right?

itaj

 

[itaj sherman]

On 02/22/11 10:32, itaj sherman wrote:
[snip]

I'm sorry what I say here is not 100% formally clear. It's more like a
brainstorm to evaluate idioms for multimethods.

itaj

Hi ita,

If g++ is available, you can use the -std=gnu++0x option to enable
variadic templates and then use the code demonstrated the
test driver here:

http://svn.boost.org/svn/boost/sandbox/variadic_templates
/libs/composite_storage/sandbox/pack
/one_of_multiple_dispatch.test.cpp

to do multimethods. Note that that demo uses 2 different methods.
One uses a disjoint union data type (the one with the one_of_maybe tag)
the other uses virtual methods (which is the one you're interested in).
To select the virtual method version, include:

#define REIFIER_VISITOR

in the driver.

So, after I managed to check out the code, it makes more sense.

But, tell me if the following is correct:
using this library on a hirarchy of classes and a certain multimethod.
- I have to collect the declarations of all different overrides in the
same functor class, like functor3 and functor_any do.
- I have to collect all the concrete classes of the hirarchy in one
list, as under hosts_concrete<>

If so, I think this API doesn't solve the main disadvantages I see
with the dynamic_cast idiom.


In my example it would look about:
* except I'm not sure what should be ResultType in there, becuase
hunt() returns void, but what happens if other multimethods return
other types?

struct Carnivours_concrete
: mpl:ackage< Lion, Anaconda, Bear >
{
};


class Carnivour
{
typedef reifier_visit_abstract_seq< ResultType
, typename Carnivours_concrete::type>
visitor_abstract;

virtual ResultType accept( visitor_abstract const&)const=0;
};

class Lion: public Carnivour
{
...

ResultType accept( visitor_abstract const& a_visitor)const
{
return a_visitor.visit(*this);
}
};

class hunt_functor
{


void operator()( Lion const&, Gazelle& )
{
//jumps on it and bite its neck
}

//and same for:
void operator()( Lion const&, Girrafe& )
{
//bite its ass
}

void operator()( Anaconda const&, Gazelle& )
{
//inject venom

}

//Anaconda can't kill girrafes so no override for that one

void operator()( Bear const&, Prey& )
{
//because Bears catch everything in the same way lol.

}


};

itaj

 

[Paul]

void operator()( Anaconda const&, Gazelle& )
{
//inject venom

I do like your wildlife theme but, Anacondas are constrictors.

}

//Anaconda can't kill girrafes so no override for that one

Debateable.


GL with your porject , its beyond me atm.