Probably, many C ++ programmers have heard about multimethods and know that to this day there is no acceptable implementation for this language: neither language support nor external libraries. There are code generators, frills through virtual methods, a special case of double dispatching aka the Visitor pattern. But you want to just implement several functions and specify: this set of functions is a multi-method and a full stop.

Meyers and Alexandrescu have long written about multimethods and some approaches to their library implementation. For almost 20 years, these ideas have been discussed in various C ++ literature, but so far they have not been developed to a complete solution that could be conveniently used in real projects ...

I decided to try my luck, dare, to offer my vision of this problem and the way to solve it. It turned out a template library on the headers only.
This is an implementation under the C ++ 03 standard, on pure C ++: without any code generators and additions. The goal is a library with a simple and understandable interface for realizing the ability to overload functions by type (and even by value) at run time (this was a minimum program, eventually many more goodies came out).

For a test drive, you need to download the source , and make a couple #include.
')
I chose the presentation from simple to complex. Therefore, in this article I will talk about the most simple way to use the library and for now I’m not talking about implementation techniques.

What is a multimethod?

It has several synonyms: multiple dispatching, multiple switching by type, function overloading at run time. On this subject there is a lot of information on the Internet and literature, therefore, I will not cross-post the same thing, but I will provide a couple of links:
English and Russian Wikipedia.

Why multimethods in C ++?

This question also will not disclose.
Immediately I will inform you that the goal was an attempt to implement multimethods, and not abstract reasoning with the rationale of whether they are needed in C ++. Some people need, but some do not. If there is an idiom, then the implementation has the right to exist, whether someone likes it or not. Since other languages ​​have such implementations, from the language or library side, is C ++ worse?
By the way, C ++ may someday support multimethods from the language side. Here is Björn Straustrup's offer . Previously, everyone expected them to appear in C ++ 0x, but so far the proposal has not been properly worked out.

From myself I can add. Stroustrup recommends, if possible, to give preference to free functions, instead of internal member methods, if such a function is sufficiently a public class interface. But what if the function should process a polymorphic argument? Every time you have to add a new virtual method that permeates the entire hierarchy (or part of it). This is a feature of tight coupling of data and methods. Multimethods allow to avoid this dependence, allow to expand the functionality without interfering with the class hierarchy. That is, without using internal virtual methods, you can create an external virtual method, and not from one, but from several polymorphic arguments. In general, the application part is quite wide.

A bit of history

I first learned about the multimethod in 2009 in the process of learning C ++ and the design techniques from the book “Gangs of four” “Object-oriented design techniques. Design patterns. ” In the“ Visitor ”section. At that time it seemed to me strange that there is no sane and simple from the point of view of using the multimethod implementation for C ++. I sketched a prototype, and developed it (several times rewriting almost completely) in my spare time as a hobby, as I study and dive into the language. When I grew to read Alexandrescu, I learned that he implemented a multimethod in several ways. But they were very limited, difficult to use, and in some cases do not work at all, this is just an example of metaprogramming to his book . Yes, and the prefix "multi" is useless here: its implementation works only for functions of 2 arguments. I found several other types of implementations, but they needed either a code generator, or writing a manual code and making significant changes in my hierarchy to support dispatching. All this is so difficult that there is no desire to use multimethods in C ++. I managed to find a way to get rid of these difficulties by presenting the interface in a very simple form and an acceptable performance implementation. Looking ahead, one of the easiest ways to create a multimethod (and the library provides a lot of ways, from simple to fine manual tuning with ready-made or own policies of the algorithm's behavior):

mml::make_multimethod(f1, f2,..., fn) 

f1, f2, ..., fn are the names of functions or callable objects that need to be dynamically overloaded (that is, to collect a multimethod from them). There are no additional requirements for the arguments; make_multimethod returns a functional object representing the multimethod (dynamically overloaded function), configured by default parameters. This is a low threshold for a library user to enter; it does not require additional knowledge.
As a result, a library was formed, probably, even a decent one, I called it trite: MML - MultiMethod Library . It's time for her to see the light, most likely, it will be useful to someone. Considering that during these almost 3 years the situation with multi methods in C ++ has not moved anywhere (IMHO, maybe I just don’t know something).

Formulation of the problem

What a multimethod should do is understandable. But how should he do it, and, importantly, what will it look like? I will build on the main purpose - overload at run time . And what is overloading in object oriented style? In general, what does function overloading look like at compile time in C ++? Let's analyze.
Without going into all the subtleties of the rules for overloading (including inheritance, using-declarations, Konig search, etc.), consider a simple example:

 void f(int){} void f(double){} void f(char, void*){} 

It shows that the name of the function f is overloaded 3 times by the types of arguments and their number. Despite the fact that functions overload appeared in C ++ as an advantage of OOP (there is no overload in C), its form does not smell of object orientation. These 3 functions are implicitly related: by coincidence of names, moreover, the term “overloaded function” as a whole is not applicable to this example. Try, for example, to save the entire set to a variable or transfer it to a certain function and somewhere later make a call with overload:

 auto of = f; //      f 

A language has no means of combining a set of overloaded functions into a single object. This form of overload refuses to encapsulate.
Consider an object-oriented alternative:

 struct f { void operator()(int) const {} void operator()(double) const {} void operator()(char, void*) const {} }; auto of = f(); //  , of  ,       

You might think that all functions are now better designed as a functor (functional object). There is a common sense in this if it is justified, for example, to obtain the benefits of embedding in the transfer of predicates to standard algorithms, etc., but not for all problems. Unreasonable writing of a functor instead of the usual good old function will be inconvenient, time consuming, and also for some problems an unacceptable solution.

So, in an object-oriented style, an overloaded function is a functor (a functional object) with an overloaded operator (). The MML library has a ready-made useful template that wraps many individual callable entities (these are functors, lambdas, and pointers to ordinary functions) and represents an overloaded operator () for each of them. This is the object overloaded_function <F1, ... Fn> and the function make_overloaded_function (f1, ..., fn), which creates an object by displaying the parameters of its template through the types of its arguments.

overloaded_function is an entity representing an overloaded function at compile time that can be called using operator (). From the same considerations you need to proceed when designing a multimethod interface. Those. it should be some callable entity, look externally also like an overloaded functor, but perform an overload at run time depending on the actual dynamic type of parameters that is unknown at compile time. The multimethod should be an object-value, contain all the necessary data within itself, i.e. support the concept of assignable. Such an interface and behavior will allow a multimethod to look like a regular callable entity and interact with STL, boost, as well as with many STL like-libraries and custom code without special adaptation.

Total we get the following problem statement: develop a callable entity, which will include a set of statically (at compile time) overloaded functions, provide a callable interface, while dispatching incoming calls to the desired target static function from the set at run time.

Proposed Solution

It was possible to obtain a set of classes, strategies, classes of characteristics, facades, adapters, and so on. Utilities for the most general solution of the problem besides the multimethod itself. But, since The article is introductory, I’ll talk about the simplest variant of using multimethod, the so-called low threshold. To do this, I prepared a multimethod facade and a function to create it based on the set of target callable entities make_multimethod . The core of the library is the template dispatcher class, which I will discuss in the following articles as it goes deeper, it is maximally generalized and not limited to the implementation of a multimethod, multimethod is a facade to simplify the use of a dispatcher.

Perhaps enough of reasoning, it is better to use examples with comments to understand how everything is really simple.

For example, we need a simple hierarchy. I will use the classic example: a game in which we will collide spaceships, asteroids and space stations:


For convenience, a function that returns an array of polymorphic pointers to game objects:


A set of target statically overloaded functions:

 const char* collide_go_go(game_object*, game_object*) { return "Unsupported colliding!"; } const char* collide_sh_sh(space_ship*, space_ship*) { return "Space ship collides with space ship"; } const char* collide_sh_as(space_ship*, asteroid*) { return "Space ship collides with asteroid"; } const char* collide_as_sh(asteroid*, space_ship*) { return "Asteroid collides with space ship"; } const char* collide_as_as(asteroid*, asteroid*) { return "Asteroid collides with asteroid"; } 

What are they overloaded, you ask, they have different names. Yes, different, for the convenience of taking the address. If someone strongly needs, you can give the same name, just have to resolve the ambiguity when you take the address of functions.

The first important point. Create a multimethod (you need to connect the header <mml / generation / make_multimethod.hpp>):

 #include <mml/generation/make_multimethod.hpp> auto collide = make_multimethod( collide_go_go , collide_sh_sh , collide_sh_as , collide_as_sh , collide_as_as ); 

Done! collide - there is a multimethod. You can do without auto, immediately transfer the result to a template function, assign boost :: function <const char * (game_object *, game_object *)> collide = ... or explicitly specify the type of multimethod <...>. Explicitly specifying the type is quite difficult, it is best to use automatic breeding. By encapsulating in (boost | std | std :: tr1) :: function, you lose some of the functionality and performance in some specific cases (below is an explanatory example), but, in general, in most cases the behavior will be the same.

The second important point. We use multimethod. Push all game objects in pairs:

 auto& objs = get_obj_pointers(); for (size_t i = 0; i < objs.size(); ++i) for (size_t j = 0; j < objs.size(); ++j) cout << '\t' << collide(objs[i], objs[j]) << endl; 

The output in the console shows who actually encountered. As you can see, the hierarchy does not require any special support for dispatching. In multimethod, by default, dynamic_cast is used to find out the actual dynamic type of an object. Therefore, you need to compile the code with RTTI enabled.
To assess the effectiveness, I give pseudocode, which when compiled will give the same machine code as the call collide (objs [i], objs [j]):


As you can see, the overhead during runtime is represented at best by 2 dynamic_cast, at worst - by 4.

The library works with pointers to polymorphic objects: both with embedded, and with smart and even user-defined. To work with links, I wrote the facade ref_multimethod (implemented in <mml / generation / make_ref_multimethod.hpp>):

Utility function for the convenience of creating an array of links to polymorphic objects:


Target functions that accept links:


In order not to repeat the same cycle of pushing objects, I wrapped it in a template function:

 template <typename F, typename Objs> void collide_tester(F collide, Objs& objs) { for (size_t i = 0; i < 2; ++i) for (size_t j = 0; j < 2; ++j) cout << '\t' << collide(objs[i], objs[j]) << endl; } 

Create and use reference multimethod:

 #include <mml/generation/make_ref_multimethod.hpp> collide_tester( make_ref_multimethod( collide_ref_go_go , collide_ref_sh_sh , collide_ref_sh_as , collide_ref_as_sh , collide_ref_as_as ) , get_objs_refs() ); 

The runtime equivalent in pseudocode will be the same as in the previous pointer example.

I have already said that functional objects compare favorably with pointers to a built-in function in that they are easy to embed. Moreover, the majority of such objects have no data members, therefore they allow not to store them at all in the memory of the container using the clever technology “Empty Base Optimization”, which is used in the depths of the library. Here is an example of multimethod interaction with a functor:

 struct collider_sh_as { const char* operator()(space_ship*, asteroid*) const { return "Space ship collides with asteroid"; } }; collide_tester( make_multimethod( collide_go_go , collide_sh_sh , collider_sh_as() , collide_as_sh , collide_as_as ) , get_obj_pointers() ); 

As you can see, using functors is as simple as inline functions. But at the same time, the size of the multimethod will be less than the width of one pointer, and any compiler will be able to easily embed the body collider_sh_as :: operator () into the place of the call.

The types of parameters and the return value of the call-operator library define through BOOST_TYPEOF (& collider_sh_as :: operator ()). Do not be discouraged if your compiler does not support BOOST_TYPEOF, or you do not want to register custom types to support BOOST_TYPEOF, or do not want to know what it is. You can explicitly specify the types of parameters, for this there are several convenient ways. The library implements the following protocol for determining the types of parameters and the return value of the functor (F):

1. Attempts to get a functional type from a functor type via F :: signature. You must define it as follows:
   
   

    struct collider_sh_as { typedef const char* signature(space_ship*, asteroid*); ... } 

   
   
2. If the previous typedef is missing, it tries to find the types inside the functor through F :: result_type, F :: arg1_type, F :: arg2_type, ..., F :: arg n _type:
   
   

    struct collider_sh_as { typedef const char* result_type; typedef space_ship* arg1_type; typedef asteroid* arg2_type; ... } 

   
   Thus, boost :: function is automatically supported, which exports such typedefs.
   
   
3. If they are missing, it tries to find types through F :: result_type, F :: argument_type (for a unary function), F :: first_argument_type, F :: second_argument_type (for a binary function).
   
   

    struct collider_sh_as { typedef const char* result_type; typedef space_ship* first_argument_type; typedef asteroid* second_argument_type; ... } 

   
   or, which is much more convenient:
   
   

    struct collider_sh_as : std::binary_function<space_ship*, asteroid*, result_type> { ... } 

   
   Thus, std :: unary_function, std :: binary_function is automatically supported.
   
   
4. If the previous 3 steps failed, then BOOST_TYPEOF is used. Any functor with one non-template operator () is supported. Thus, std :: function and C ++ 11 lambda are supported. Some compilers will have to register custom types. I still do not understand how BOOST_TYPEOF works, I have not registered user types, but it perfectly displays the types of parameters on MSVC 7.1 and higher.

In the previous examples, the multimethod was built from functions of the same arity. This is not a library limitation.
In general, the library supports arity from 0 to MML_MAX_ARITY. MML_MAX_ARITY defaults to 5. The default value can be changed. To do this, before connecting the header you need to define a macro:

#define MML_MAX_ARITY n
n is the maximum arity.

Add for example nullar, unary and ternary functions:

 //   , ,     const char* collide_void() { return "Nothing collides?!"; } //     ,   const char* collide_go(game_object*) { return "Unsupported colliding!"; } const char* collide_sh(space_ship*) { return "Space ship collides with what?!"; } const char* collide_as(asteroid*) { return "Asteroid collides with what?!"; } const char* collide_go_go_go(game_object*, game_object*, game_object*) { return "Unsupported colliding!"; } const char* collide_sh_as_as(space_ship*, asteroid*, asteroid*) { return "Space ship collides with two asteroids"; } const char* collide_sh_as_st(space_ship*, asteroid*, space_station*) { return "Space ship collides with asteroid and space_station"; } 

We need a new tester that will collide a different number of objects:

 template <typename F, typename Objs> void collide_tester_var_arg(F collide, Objs& objs) { //   cout << '\t' << collide() << endl; // 1  cout << '\t' << collide(objs[0]) << endl; cout << '\t' << collide(objs[1]) << endl; // 2  cout << '\t' << collide(objs[0], objs[0]) << endl; cout << '\t' << collide(objs[0], objs[1]) << endl; // 3  cout << '\t' << collide(objs[0], objs[1], objs[1]) << endl; cout << '\t' << collide(objs[0], objs[1], objs[2]) << endl; } 

Create and use multimethod:

 collide_tester_var_arg( make_multimethod( collide_go_go , collide_sh_sh , collide_sh_as , collide_void , collide_go , collide_sh , collide_as , collide_go_go_go , collide_sh_as_as , collide_sh_as_st ) , get_obj_pointers() ); 

Thus, the multimethod behaves like a statically overloaded function by the number of arguments.
The rantaim equivalent in pseudocode here will be more interesting, it strongly depends on the number of arguments:


You can mix polymorphic types and value types. Value types will simply be passed as is.
We introduce a couple of additional objective functions that can take the 3rd parameter of the int type:

 const char* collide_go_go_int(game_object*, game_object*, int) { return "Unsupported colliding with extra int parameter!"; } const char* collide_sh_as_int(space_ship*, asteroid*, int) { return "Space ship collides with asteroid with extra int parameter"; } 

Tester for clarity will pass to the multimethod:
2 polymorphic types;
3 polymorphic types;
2 polymorphic with one non-polymorphic type:

 template <typename F, typename Objs> void collide_tester_non_polymorphic_arg(F collide, Objs& objs) { cout << '\t' << collide(objs[0], objs[1]) << endl; cout << '\t' << collide(objs[0], objs[1], objs[2]) << endl; cout << '\t' << collide(objs[0], objs[1], 1) << endl; } 

We create a multimethod based on previous and new objective functions and use:

 collide_tester_non_polymorphic_arg( make_multimethod( collide_go_go , collide_sh_sh , collide_sh_as , collide_as_sh , collide_as_as , collide_go_go_go , collide_sh_as_st , collide_sh_as_as , collide_go_go_int , collide_sh_as_int ) , get_obj_pointers() ); 

I gave the rantaim equivalent for the first and second calls, consider the third:


As you can see non-polymorphic arguments do not lead to additional overhead.

Overloading by const and volatile qualifiers is also supported:

 const char* collide_go_cvgo(game_object*, const volatile game_object*) { return "Unsupported colliding!"; } const char* collide_sh_cas(space_ship*, const asteroid*) { return "Space ship collides with const asteroid"; } const char* collide_sh_vas(space_ship*, volatile asteroid*) { return "Space ship collides with volatile asteroid"; } const char* collide_sh_cvas(space_ship*, const volatile asteroid*) { return "Space ship collides with const volatile asteroid"; } template <typename F, typename Objs> void collide_tester_cv(F collide, Objs& objs) { game_object* object = objs[1]; const game_object* c_object = objs[1]; const volatile game_object* cv_object = objs[1]; cout << '\t' << collide(objs[0], object) << endl; cout << '\t' << collide(objs[0], c_object) << endl; cout << '\t' << collide(objs[0], cv_object) << endl; } collide_tester_cv( make_multimethod( collide_sh_as , collide_go_cvgo , collide_sh_cas , collide_sh_vas , collide_sh_cvas ) , get_obj_pointers() ); } 

An important feature of the multimethod is the ability to optimize scheduling, if the exact type of polymorphic argument is already known at the compilation stage. In other words, the search for a real type of argument begins with the node of the hierarchy, which is the actual type of the argument passed. It would be easier to explain ... Here is a better example:

 template <typename F, typename Objs> void collide_tester_compile_time_optim(F collide, Objs& objs) { space_ship ship; asteroid ast; cout << '\t' << collide(objs[0], &ast) << endl; cout << '\t' << collide(&ship, &ast) << endl; } collide_tester_compile_time_optim( make_multimethod( collide_go_go , collide_sh_sh , collide_sh_as , collide_as_sh , collide_as_as ) , get_obj_pointers() ); 

Now carefully consider the runtime equivalent:

 // collide(objs[0], &ast) inline const char* collide(game_object* obj1, asteroid* as2) { if (space_ship* sh1 = dynamic_cast<space_ship*>(obj1)) return collide_sh_as(sh1, as2); else if (asteroid* as1 = dynamic_cast<asteroid*>(obj1)) return collide_as_as(as1, as2); else return collide_go_go(obj1, as2); } //    : // min 1 cast // max 2 casts // collide(&ship, &ast) inline const char* collide(space_ship* sh1, asteroid* as2) { return collide_sh_as(sh1, as2); } //   ! 

The first call is dispatched only by the first argument, the second argument is passed as is, because its type is known exactly at compile time.
The second call generally just forwards, the types of both arguments are known at compile time.
That is why, in order to support such optimization, the multimethod should, if possible, be stored and transmitted in a pure form, and not be hidden behind boost :: function / * std :: function * /. A call with upcasting - collide ((game_object *) & ship, (game_object *) & ast) - will deprive the library of the possibility of optimization.

The multimethod supports not only bare pointers, but also boost :: shared_ptr, as well as custom pointer types, with the correct specialization of a pair of templates (about them in the following articles). To support boost :: shared_ptr, you need to include the header file <mml / casting / sp_dynamic_caster.hpp>.
Example:

 #include <mml/casting/sp_dynamic_caster.hpp> const char* sp_collide_go_go(game_object*, boost::shared_ptr<game_object>) { return "Unsupported colliding!"; } const char* sp_collide_sh_sh(space_ship*, boost::shared_ptr<space_ship>) { return "Space ship collides with smart_ptr space ship"; } struct sp_collider_sh_as { const char* operator()(space_ship*, boost::shared_ptr<asteroid>) const { return "Space ship collides with smart_ptr asteroid"; } }; template <typename F, typename Objs> void sp_collide_tester(F collide, Objs& objs) { boost::shared_ptr<game_object> obj1(new space_ship); boost::shared_ptr<game_object> obj2(new asteroid); cout << '\t' << collide(objs[0], obj1) << endl; cout << '\t' << collide(objs[0], obj2) << endl; } sp_collide_tester( make_multimethod( sp_collide_go_go , sp_collide_sh_sh , sp_collider_sh_as() ) , get_obj_pointers() ); 

Rantaim equivalent:


Sources of examples are here .

Benefits

Ease of use. Canonicity of expression. You do not need to initialize anything, to describe your hierarchy of classes, you do not need to interfere with the hierarchy. Meta information is not required for normal use. The multimethod will receive all the necessary meta-information from your code itself. At first glance it may seem incredible, but it is.
There is no limit on the number of arguments (maybe even 0).
The main part of the code is compile time, so most of the misuse errors of the multimethod will be detected by the compiler.

disadvantages

High load on the compiler can manifest itself in the case of instantiating a set of multimethods of different types (as in the example for the article). It is different, because the compiler instantiates each pattern with a specific set of parameters only once. The number of single-type multimethods is not important. I suppose that in a real project such diversity will rarely occur. By the way, when using the mechanism of precompiled headings, the compile time of the example almost halves.
When used improperly, vague compiler error messages with sheets of boilerplate code.

Performance

Performance is a weak point in the examples given due to the use of dynamic_cast. But dynamic_cast is not part of the library core. This is the method defined by the default strategy for highlighting the real type of object. In the next article I will show you how to set your own type conversion strategy using the example of “fast_cast”, which breaks dynamic_cast by orders of magnitude in efficiency. On the other hand, even such efficiency will be acceptable for most applications. You are not going to implement streaming video processing, causing a multimethod for each byte?
For application or GUI tasks, this option is very acceptable. After embedding (inlining) for release build there are no other overhead costs in runtime.
It was necessary to suffer with optimization of sample code so as to minimize side effects on runtime. By the way, the performance of the multimethod is comparable to the implementation of the Acyclyc Visitor pattern proposed by Robert Martin. It is also implemented via dynamic_cast.
The multimethod does not use a heap, it stores the state inside, if it exists. Ideally, when using functors rather than function pointers, the state is not stored at all - the object is empty and all calls are easily embedded.

Dependencies

It requires a C ++ compiler that supports standard 03 or higher and BOOST (headers only) version 1.45.0 or higher .

Important!There must be a “boost” and “mml” directory inside the compiler's include-directory. Do not specify the “boost” and “mml” directories themselves as include directories, but the directory containing them .

The library with examples was tested on compilers (currently only under Windows):
GCC 3.4.2;
Visual C ++ 7.1, 8.0, 9.0, 10.0.

UPD: , , . , . , ( 57 ~190 ). , . , , if-else, .

UPD 2: : , C++ . , . , . mejedi .

. , .