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@gmail.com> 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@suddenlink.net> 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@uci.edu> 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