Re: [boost] yet another multimethods library

From: Korcan Hussein (korcan_h_at_[hidden])
Date: 2006-03-03 15:08:31

"David Abrahams" <dave_at_[hidden]> wrote in message 
news:<uslq1y4lo.fsf_at_[hidden]>...

>

> Sounds fascinating; show me more!

>

Heh, okay I still have a little way left to go but the "shell" of it is 
pretty much complete as well as most of the guts of it. Okay I'll try to 
elaborate a bit more about this.

Lets start with what the client gets to play with, well you have a choice of 
two similar but different kinds of front-ends. The first and main one is 
(currently) called generic function (maybe it should change it to something 
like boost::generic::function instead?). This component allows any kind of 
C++ callable entity to be registered for dynamic dispatch, as you could 
probably guess it gets a little help from boost::function in this department 
:). quick example:

// single dispatch

generic_function< void (boost::shared_ptr<foo>, float) > print_foo;

const bool reg[] = {

print_foo.def_method< boost::shared_ptr<bar> >(print_bar),

print_foo.def_method< boost::shared_ptr<fuzz> >(print_fuzz)

};

.....

boost::shared_ptr<foo> foo_ptr(new fuzz);

print_foo(foo_ptr, 0.0f);

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// multiple dispatch ( farfetched example :) )

typedef float (my_sig)(const std::string&, const base1&, float, Base2*, 
std::string,
                                 boost::intrusive_ptr<base3>, base1**, 
Base2*&, wrap<const base3&>);

// const base1&, Base2*, boost::intrusive_ptr<base3> are selected for 
dispatch,
// base1**, Base2*&, wrap<const base3&> are not selected for very good 
reasons!
// "wrap" is a trivial metafunction clients can use to disable the automated 
deduction.

generic_function< my_sig > foobar;

const bool reg[] = {

foobar.def_method< const dev1_1&, dev2_1*, boost::intrusive_ptr<dev3_1> 
 >(func_obj1),

foobar.def_method< const dev1_2&, dev2_2*, boost::intrusive_ptr<dev3_2> 
 >(func_obj2),

foobar.def_method< const dev1_3&, dev2_3*, boost::intrusive_ptr<dev3_3> 
 >(func_obj3)

};

Of-course you are not required to register functions all at once and this is 
completely non-intrusive solution, I'm just doing it here for illustrative 
purposes. As you can see the registration process is a little nasty (open to 
suggestions & debate), unfortunately because of pointer/reference *proxy* 
support CV qualification and raw pointer/reference is required, fortunately 
forgetful clients will be caught at compile-time :). Only sub-types are 
required to be stated and the reason they are required is it's not possible 
to deduce argument types of function objects however I could write an 
overload that can deduce types for free-functions ala 
boost::function_traits.

As of current this is the only place where the order sub-types should come 
in the same order stated to generic_function but generic_function itself 
does not care for order and placement of arguments of polymorphic types, 
again mistakes will be caught out before they have a chance :).

Now I'll briefly describe the other front-end called fast_generic_function 
for a lack of a better name the only difference it has from generic_function 
is it should have less overhead in terms of storage & runtime (but maybe 
slightly longer compile-time) because it deals solely with pointer to 
functions as opposed to boost::function, also "def_method" member function 
for fast_generic_function is used slightly different an example using the 
first example above would be:

const bool reg[] = {

print_foo.def_method< void (boost::shared_ptr<bar>, float), print_bar >(),

print_foo.def_method< void (boost::shared_ptr<fuzz>, float), print_fuzz >()

};

Both generic_function and fast_generic_function use the same backend called 
generic_functionN (this might change latter in into two classes 
generic_base_fun and generic_functionN but this is of no concern to 
clients), they are all parameterized by allocator type and default to use 
std::allocator of-course.

As of current exact method matches are an (amortized) constant time 
operation, as you can pretty much guess a hash map is used that maps a tuple 
of type identifies to either function pointers or boost::function (depending 
on which front-end is used). I'm currently using boost::fusion::vector 
instead of boost::tuples/std::tr1::tuple because it's a bit more flexible to 
work with but I'm going to change it to use boost::tuples::tuple simply for 
the reason that boost::fusion isn't (yet) currently an official part of 
boost. Boost.Functional/Hash is also used.

I'm going to investigate boost::multi_index_container as an alternative so 
there could be a possibility of (amortized) constant time exact matches and 
logarithmic time best matches. That is what I'm going to explore this 
weekend and adding method combinations (before, after around, 
call-next-method etc).

Let me emphasize one thing I'm trying my utmost to keep compile-times and 
code bloat to the minimum as much as possible, taking advantage of lazy 
evaluation (lazy template instantiation) via MPL views where ever possible 
etc, etc.

(Possible) Future directions I would like to see:

support for boost::any, be the end for type-switching code on many anys ^_^,

Move semantics,

Further improve efficiency,

Reduce compile-times further,

Use "Multiple Row Displacement" algorithm,

And the ultimate aim is to have support for Predicate dispatching in C++ if 
it's possible at all (highly doubt it). For those who don't know Predicate 
dispatching is a further generalization of multimethods with some ML pattern 
matching goodness.

P.S. I forgot to mention this *as of current* RTTI support needs to be 
enabled, it's not as bad as it may sound, it is only required in one place 
and that is determining type identities via typeid operator at runtime this 
is the only decent way to make this solution non-intrusive and loosely 
coupled. Besides i've read that invoking the typeid operator is an amortized 
constant time operation however I cannot find any confirmation of this in 
the current C++ standard does anybody for sure?.