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

On Mon, Aug 24, 2009 at 12:42 AM, OvermindDL1 <overminddl1@gmail.com> wrote:

I might be able to whip up an example if you want, but what it would do is populate a tree of type resolvers (this would actually allow for unlimited type resolution, not just two) with plenty of use of type_traits is_virtual_child and so forth all stuffed into templated structs that resolve the lookups. At compile time the tree is created, at call-time into the multimethod it creates a lookup in the tree that is specialized on the types passed into the multimethod caller, and at runtime the specialized caller resolves through the tree to compare the compile-time types at runtime, and if equal or if proper children, then it is equal and calls the necessary method, it will not fail since the base-most test could be tested at compile time as well and if it is not a child of that then it would fail at compile-time, but resolve to a specific function at runtime. I have been creating a lot of things like this recently for binding function between scripting languages and C++, makes things so easy once you figure out how to create it. I love Boost.Fusion. :)

It does sound fun, but I'm afraid I still don't understand how it changes the work required of the implementation to find the best method. I'm not sure if "call-time" is during compile-time or run-time. It sounds like the first, since you mention a "specialized caller". If so, that won't work because the static types of the parameters may not be the dynamic types. If the second, I don't see the advantage. Testing for proper children won't work in general, because a related type may not be a child. Besides, we don't need to check for that, because the method only accepts specific types. It is possible that a method implementation doesn't exist for that combination, but that can only be determined at run-time.

Just for note, if you do read the PDF, he describes a method that makes multi-methods have less cost then two virtual functions, and in many cases it has equal cost to one virtual function program-wide, so basically, much faster then your implementation, but his looks like it might require a compiler back-end change.

I was aware of the proposal for the addition of openmethods to C++. However, it's not even under consideration yet. I don't want to wait 20 years for multimethods to become a language feature. Furthermore if concepts are any example, when the time comes the multimethod proposal will do better if a library has already popularized them. Nick