Re: [boost] Boost.Multimethod proposal

Subject: Re: [boost] Boost.Multimethod proposal
From: Nicholas Howe (nicholas.howe_at_[hidden])
Date: 2009-08-23 23:45:25

My proposal is based on Scott Meyers' and Andrei Alexandrescu's work.  Their
multimethods support a client-defined mapping from parameter types to method
implementation.  For example, if you have a two-parameter multimethod with a
method implementation for the pair of types A-A, and you intend the pair B-B
to use that implementation, you could register a mapping from B-B to the A-A
implementation.  My proposal extends their multimethods with automatic
mapping from the parameters' dynamic types to the best available method
implementation.  Given B-B, and assuming the A-A method implementation is
the best available, it will use it without requiring the client to register
a mapping from B-B to A-A.  Instead, the client must register a mapping from
B to its parents and A to its parents, and A must be reachable from B.

I believe this automatic mapping is necessary to support scenarios such as
the following.  A library defines a type and a two-parameter multimethod
that accepts that type.  Two client libraries derive types from the type
defined in the first library, but are unaware of each other.  The method
implementation for the base type is acceptable for interactions between the
two derived types.  There is no way for either client to register this
mapping, because the two client libraries are unaware of each other.

To put it in more concrete terms, and hearken back to Scott Meyers' and
Andrei Alexandrescu's examples, a game defines a spaceship, a spacestation
and an asteroid.  The response to collisions between them is determined by a
multimethod.  The game can be extended with plug-ins.  Two plug-in, client
libraries derive new types from spaceship.  The collision response between
the types in the different plug-ins should be the same as for the base
types, but the mapping from the combination of the derived types to the
spaceship-spaceship implementation cannot be determined by either plug-in,
because the plug-ins are not aware of each other, and either might not be
present.

On Sat, Aug 22, 2009 at 7:57 PM, OvermindDL1 <overminddl1_at_[hidden]> wrote:

> Hmm, interesting thought.  What if all user-overloads where put in an
> mpl map, and you registered all overloadable functions in a similar
> way, but for the main function caller you could probably do something
> like variant does for its visitors and recursive down for each of the
> types based on the typeid (or more likely an mpl tag since it will be
> stuffed into an mpl map anyway) using fusion to resolve the type at
> runtime then using fusion::invoke or one of its kin, this would allow
> it to be very efficient and would remove basically all the indirection
> costs.  Could be made even more simple and efficient if the user was
> willing to add a single macro into their class definition.  Hmm...
>

I'm not certain, but it sounds like you might be suggesting resolving the
mapping from dynamic parameter types to available methods at compile-time.
 If so, I explained why I don't like that above.  If not, you'll have to go
into more depth, as I don't follow.  My implementation caches the result of
lookups, so I'm not particularly concerned by the cost of the resolution.

I've looked over their documentation, but I'm not very familiar with variant
and fusion.  I was aware that boost has tuple libraries, but I didn't use
them because I didn't think I was doing anything very complicated and, of
course, it's easier not to learn.  Then there's the excuse that keys have to
cross library boundaries, so I want them to be part of the multimethod
library, rather than a dependency, so they won't change unless they have to.

On Sat, Aug 22, 2009 at 9:58 PM, Larry Evans <cppljevans_at_[hidden]>
 wrote:

> I haven't looked at your code, but the mention of "registered methods"
> in the above quote suggests some sort of time consuming lookup.

How ever they are implemented, multimethods will be more expensive than
virtual functions, just as virtual functions are more expensive than static.
 Likewise, multimethods are more powerful than virtual functions, because
the method implementation is chosen based on the dynamic types of all the
parameters, rather than just one.  They are a tool whose use may or may not
be appropriate for a given application.  I believe the scenario I described
above is one application for which they are appropriate.

I do support single-parameter multimethods, which are interesting because
they give the behaviour of virtual functions with a non-member function.  Of
course, they are much more expensive than a virtual function.

I just uploaded to boost_vault/Patterns a text file:
>
>  PescioNdispatch.txt

I haven't had the time to fully understand the contents of this file, yet.
 It looks similar to a technique I used in the Steps project, which is one
of the examples I uploaded.  However, it appears that the base type in this
example must be aware of the derived types in order for it to function,
which would not support the addition of new types to the hierarchy without
modification of the base type.  The Steps project uses a similar extended
visitor pattern with dynamic_cast, but does not require the base type to be
aware of derived types, and supports the addition of new types without
modification of the base type.  I thought the technique I used in Steps had
an unnatural syntax, was awkward to extend to more than two types, and had
the potential to result in inefficient code because it always searches for
the correct method implementation, instead of caching the result.  Even with
helper templates, the Steps implementation is complex and difficult to use.
 It's possible that's just because everything's poorly named and I'm sure
the templates could be improved.  However, it also requires that client
types support multimethods directly, so a client can't use types that aren't
multimethod aware in a multimethod.  The multimethods I propose don't
require this.  Finally, the implementation in Steps only allows one
multimethod per hierarchy, although this could probably be fixed.  I am
interested in pursuing the Steps project further, but I believe it is less
general than the proposed multimethods.

On Sat, Aug 22, 2009 at 11:01 PM, Jeffrey Bosboom <jbosboom_at_[hidden]> wrote:

> There's a Stroustrup et al paper on the feasibility of adding multimethods
> to C++ here: http://research.att.com/~bs/multimethods.pdf . I'm not sure
> how relevant it is to the current proposal, but it contains information on
> an experimental implementation that was faster than double dispatch.
>

I will read that.  I believe my proposal defines a simple interface for
defining type relationships and registering methods, while leaving plenty of
room for implementation changes.
Nick