MultiMethods in C++: Finding a complete solution

• Download sample files - 23.8 Kb

Preamble

This paper provides a way to solve famous "multimethods problem". The main merits of the proposed solution are:

• no use of type casts of any kind (dynamic, static, reinterpret, const or C-style)
• no use of RTTI;
• no use of preprocessor;
• strong type safety;
• separate compilation;
• constant time of multimethod execution;
• no dynamic memory allocation (via new or malloc) during multimethod call;
• no use of nonstandard libraries;
• only standard C++ features is used.

The Problem

Let's consider following example.

Suppose we have a simple hierarchy of geometrical shapes and want to write a function answering the question: "do two (or more) shapes intersect". Shapes hierarchy may look as follows.

Function, that checks for shapes intersections, must work with IShape references, i.e. in polymorphic manner. For example:

void foo( IShape_& _shape0, IShape_& _shape1 ) {
  bool f = CheckIntersection( _shape0, _shape1 );
}
...
Rect_ rect( Point_( 1, 1), Point_( 2, 2) );
Triangle_ tri( Point_( 0, 0), Point_( 2, 0), Point_( 0, 2) );
foo( rect, tri );

It corresponds to object-oriented view of virtual methods execution, where we don't care about concrete types of objects, because appropriate method is called automatically, via virtual method invocation mechanism [1].

Indeed, it's easy to write specialized intersection functions (for intersecting rectangle against triangle, for example). However, when CheckIntersection is called, there is no information about concrete types of its arguments. And there is no compiler support to do this job.

Run-time type determination

Nevertheless, there is a regular way to determine concrete object type at run-time using well-known Visitor pattern [2]. This method is also called dual dispatching. Each visitable object should implement method Visit that accepts reference to special object - dispatcher. Dispatcher should have a set of Dispatch methods that accepts references to concrete types of visitable objects. Simple example of Visitor pattern usage is shown below.

struct Triangle_;
struct Rect_;

struct IDispatcher_ {
  virtual void Dispatch( Triangle_& _shape ) = 0;
  virtual void Dispatch( Rect_& _shape ) = 0;
};

struct IShape_ {
  virtual void Visit( IDispatcher_& _dsp ) = 0;
};

struct Triangle_ : public IShape_ {
  virtual void Visit( IDispatcher_& _dsp ) {
    _dsp.Dispatch( *this );
  }
};

struct Rect_ : public IShape_ {
  virtual void Visit( IDispatcher_& _dsp ) {
    _dsp.Dispatch( *this );
  }
};

struct Dispatcher_ : public IDispatcher_ {
  virtual void Dispatch( Triangle_& _shape ) {
    cout << "This is a triangle." << endl;
  }
  virtual void Dispatch( Rect_& _shape ) {
    cout << "This is a rect." << endl;
  }
};

void PrintType( IShape_& _shape ) {
  Dispatcher_ dsp;
  _shape.Visit( dsp );
}

int main()
{
  Rect_ rect;
  Triangle_ triangle;
  PrintType( rect );
  PrintType( triangle );
  return 0;
}

This programs prints:

This is a rect.
This is a triangle.

This method has a constant overhead: two virtual method calls plus object construction on stack.

Visitable shapes

We will use the Visitor pattern to implement multimethods. All particular shapes should be visitable objects, i. e. all of them should implement Visit method. We can write the following code:

//IShape.h

//forward declaration of shapes dispatcher
class IShapesDsp_;

struct IShape_ {
  typedef IShapesDsp_ IDispatcher;
  virtual void Visit( IDispatcher& _dispatcher ) = 0;
};

//Rect.h
#include "IShape.h"
#include "Point.h"

class Rect_
  : public IShape_
{
public:
  Rect_( Point_ const& _top_left, Point_ const& _bottom_right );

  Point_ const& GetTopLeft();
  Point_ const& GetBottomRight();

  virtual void Visit( IDispatcher& _dispatcher );
private:

  Point_ top_left;
  Point_ bottom_right;
};
//etc

Note that when we declare Visit methods we don't need to have a full definition of IShapesDsp, forward declaration is ok. In other words, declaration of shapes depends only on IShapesDsp name.

Dispatcher interface generation

We will generate dispatcher interface from typelist of used shapes. Typelists are discussed in [3]. Very lightweight type-list implementation will be used for simplicity.

Using partial template specialization mechanism [4], dispatcher interface will be generated using following code:

//IDispatchPart.h

template< typename TItem >
struct IDispatchPart_ {
  virtual void Dispatch( TItem& _item ) = 0;
};

//IDispatch.h

template< typename TItems >
struct IDispatcher_
  : public IDispatchPart_< typename TItems::item >
  , public IDispatcher_< typename TItems::next > {};

//Deferred dispatcher interface stub.
template<>
struct IDispatcher_< ListEnd_ > {};

//IShapesDsp.h

class Rect_;
class Square_;
class Triangle_;
class RightTriangle_;

typedef TypeList_< Rect_,
        TypeList_< Square_,
        TypeList_< Triangle_,
        TypeList_< RightTriangle_
                    > > > > Shapes_;  

class IShapesDsp_ : public IDispatcher_< Shapes_ > {};

The following hierarchy will be generated:

Note that the declaration of IShapesDsp doesn't depend on shapes declarations, it depends only on their names.

Shapes implementation

Although shapes don't depend on IShapesDsp declaration, their implementations do. Now, when IShapesDsp is declared, we can implement shapes' Visit methods.

//VisitImpl.h
#include "IShapesDsp.h"

template< typename TShape, typename IDispatcher >
void VisitImpl( TShape& _self, IDispatcher& _dispatcher )
{
    IDispatchPart_< TShape >& part = _dispatcher;
    part.Dispatch( _self );
}

//Rect.cpp
#include "Rect.h"
#include "VisitImpl.h"

void Rect_::Visit( IDispatcher& _dispatcher ) {
  VisitImpl( *this, _dispatcher );
}

//Triangle.cpp
void Triangle_::Visit( IDispatcher& _dispatcher ) {
  VisitImpl( *this, _dispatcher );
}

//etc

Dispatcher generation

Now we have the dispatcher interface and the set of nodes, which can be visited by this interface implementations. These implementations will be generated from type-list using the following code:

template < typename TItems,     //typelist
           typename IDsp,       //dispatcher interface
           typename TMixedImpl  //mixed-in dispatcher implementation
         >
class Dispatcher_
  : public Dispatcher_< typename TItems::next, IDsp, TMixedImpl >
{
  typedef Dispatcher_< typename TItems::next, IDsp, TMixedImpl > TBase;
  typedef typename TItems::item TItem;

  virtual void Dispatch( TItem& _item ) {
    Implement( _item ); // this method should be provided by TMixedImpl
  }
};

//Deferred dispatcher implementation stub.
template < typename IDsp,
           typename TMixedImpl
         >
class Dispatcher_<ListEnd_, IDsp, TMixedImpl >
  : public IDsp
  , public TMixedImpl {};

This Dispatcher overrides all pure virtual Dispatch methods that were declared in IDsp.Implementations of these methods are redirected to a mixin class, passed as TMixedImpl parameter.

MultiMethods gateway

Now, when we know how to generate dispatchers, we can write our CheckIntersection function. It is a non-template free function that can be located in a *.cpp file. We will overload CheckIntersection for each arity of multimethod. n-ary multimethod is executed in n steps. Each i-th step begins with dispatcher creation. This dispatcher is used to determine concrete type of i-th multimethod's argument. Information of this type is propagated to the next step and so on. At the last step, where types of all arguments are known, fully specialized implementation is invoked.

Here are the dual and triple versions:

//Intersection.cpp
struct IntersectionsBulk_
{
  template< typename TShape0, typename TShape1 >
  struct DualImpl_ : public DualIntersecter_< TShape0, TShape1 > {};

  template< typename TShape0, typename TShape1, typename TShape2 >
  struct TripleImpl_
   : public TripleIntersecter_< TShape0, TShape1, TShape2 > {};
};

bool CheckIntersection( IShape_& _shape0, IShape_& _shape1 )
{
  Dispatcher_< Shapes_, IShapesDsp_, FirstStep_<2, IntersectionsBulk_> > dsp;
  dsp.UnknownArg( 1, _shape1 );
  _shape0.Visit( dsp );
  return dsp.GetResult();
}

bool CheckIntersection( IShape_& _shape0, IShape_& _shape1, IShape_& _shape2 )
{
  Dispatcher_< Shapes_, IShapesDsp_, FirstStep_<3, IntersectionsBulk_> > dsp;
  dsp.UnknownArg( 1, _shape1 );
  dsp.UnknownArg( 2, _shape2 );
  _shape0.Visit( dsp );
  return dsp.GetResult();
}

Let's look at FirstStep template class declaration:

//CallSteps.h

template< int Arity, typename TImplBulk >
struct FirstStep_ : public FirstStepBase_< Arity > {
protected:
  template< typename TShape0 >
  inline void Implement( TShape0& _arg0 ) {
    Dispatcher_< Shapes_, IShapesDsp_, SecondStep_< TShape0, 
       Arity, TImplBulk > > dsp;
    dsp.Arg0( _arg0 );
    for ( int i = 1; i < Arity; ++i )
      dsp.UnknownArg( i, *unknown[i] );
    unknown[1]->Visit( dsp );
    SetResult( dsp.GetResult() );
  }
};

It has two template parameters:

• arity of executed multimethod;
• intersection checker specializations container.

Also it has one template method - Implement, which will be called from an outer dispatcher. In Implement method the next dispatcher is created. Note, that SecondStep receives type information about first argument and a typed reference to it.

SecondStep template class has two specializations. There is a general version that works like FirstStep and a specialized binary version, which is shown below.

template< typename TShape0, typename TImplBulk >
struct SecondStep_< TShape0, 2, TImplBulk > : public SecondStepBase_< TShape0, 2 > {
protected:
  template< typename TShape1 >
  inline void Implement( TShape1& _arg1 ) {
    typedef typename TImplBulk::DualImpl_< TShape0, TShape1 >::Impl_ TImpl;
    SetResult( TImpl::Implement( *arg0, _arg1 ) );
  }
};

Specialized multimethod implementations

Specialized versions of intersection checkers are called via static methods of XXXIntersecter template class. There is a dedicated class for each arity. These classes should be defined in place where multimethod execution is done (Intersection.cpp in our example).

The DualIntersecter class is for dual multimethods. Firstly, forward declaration of DualIntersecter is provided:

//DualIntersecter.h

template< typename TShape0, typename TShape1 >
struct DualIntersecter_;

After that the specialized versions can be added. For crossing rectangles against triangles we will write:

//Rect2Triangle.h

class Rect_;
class Triangle_;

template<>
struct DualIntersecter_< Rect_, Triangle_ >
{
  typedef DualIntersecter_< Rect_, Triangle_ > Impl_;
  static bool Implement( Rect_& _shape0, Triangle_& _shape1 );
};

//Rect2Triangle.cpp
bool DualIntersecter_< Rect_, Triangle_ >
::Implement( Rect_& _shape0, Triangle_& _shape1 )
{
  std::cout << "Intersecting rectangle against triangle." << std::endl;
  return true;
}

It is obvious that CheckIntersection function is commutative, but compiler doesn't know about it. We must provide a reverse specialization for crossing triangles against rectangles. It can be done very easy:

//DualIntersectionReverse.h

template <typename TShape0, typename TShape1>
struct DualReverse_
{
  typedef DualReverse_< TShape0, TShape1 > Impl_;
  static bool Implement( TShape0& _arg0, TShape1& _arg1 )
  {
    typedef DualIntersecter_< TShape1, TShape0 >::Impl_ TImpl;
    return TImpl::Implement( _arg1, _arg0 );
  }
};

//Rect2Triangle.h

template<>
struct DualIntersecter_< Triangle_, Rect_ >
  : public DualReverse_< Triangle_, Rect_ > {};

Partial intersection specialization

Suppose we don't want to write specialized versions to intersect squares against any another shapes, because it can be done via rectangle facilities. Here we can use partial intersection specialization. Note that we should declare three specializations to avoid ambiguity.

//SquareViaRect.h

#include "Square.h"

template< typename TShape1 >
struct DualIntersecter_< Square_, TShape1 >
  : public DualIntersecter_< Rect_, TShape1 > {};

template<>
struct DualIntersecter_< Square_, Square_ >
  : public DualIntersecter_< Rect_, Rect_ > {};

template< typename TShape0 >
struct DualIntersecter_< TShape0, Square_ >
  : public DualReverse_< TShape0, Square_ > {};

Specialization redirection

Note that each specialization declares Impl typedef. In trivial cases specialization simply re-declares itself. But this typedef allows us to overcome some C++ limitations. Suppose we want to write specialization, that should intersect any two shapes, which are convertible to rectangles. But C++ template specialization lookup algorithm is unable to work with relations between types. That's why we will declare most general DualIntersecter specialization that checks relations between types, provides specialization for crossing rectangular shapes and in other cases redirects to DualIntersecter2. This specialization redirection pattern can be applied sequentially.

//Rect2Rect.h

#include "TypeStuff.h"
#include "Rect.h"
#include "Square.h"
// more rectangular shapes can be included

struct RectsIntersecter_ {
  typedef RectsIntersecter_ Impl_;

  static bool Implement( Rect_& _shape0, Rect_& _shape1 );
};

template< typename TShape0, typename TShape1 >
struct DualIntersecter2_;

template< typename TShape0, typename TShape1 >
struct DualIntersecter_ {
  static bool const both_rectangular =
    IsConvertible_< TShape0, Rect_ >::value &&
    IsConvertible_< TShape1, Rect_ >::value;

  typedef typename
   If_< both_rectangular,
        RectsIntersecter_::Impl_,
        typename DualIntersecter2_< TShape0, TShape1 >::Impl_ >::type
    Impl_; 
};

//Rect2Rect.cpp
bool RectsIntersecter_::Implement( Rect_& _shape0, Rect_& _shape1 ) {
  std::cout << "Intersecting rectangle against rectangle." << std::endl;
  return true;
}

Instead of specialization redirection nested if meta-functions can be used.

Hierarchy furling

Suppose we don't want to write specialized versions to intersect equilateral triangles against any other shapes, because it can be done via triangle ones. Solution is very easy - just don't override Visit method in EquilateralTriangle and don't include this type in shapes type-list.

Integrity

In this approach compiler maintains integrity. It is impossible to forget some specialization, because compiler refuses to accept such programs. For example, it's impossible to comment any of dual specializations #include directives in Intersection.cpp.

However, for debug and development reasons, some specializations subset can be temporarily replaced by a most general specialization of XXXIntersecter. We use this technique for triple intersections.

Overhead

Multimethod execution has constant overhead. This overhead depends only on multimethod arity. When n-ary multimethod is executed:

• 2 * n virtual methods are called;
• n auxiliary objects are constructed on stack;
• n * (n + c) non-virtual get/set methods are called (may be inlined), where c is a small constant.

Dependencies

Let's look on our example dependency diagram:

As you can see, client code depends only on shapes library interface. Client code doesn't include typelists, dispatcher interface and its implementations. That's why there is no compilation time growing. And even if specializations configuration changes, client code will not be recompiled.

Compilation in separate modules

Moreover, some shapes and their intersection checkers' specializations can be moved into separate module (DLL).The essence of the matter is that Visit method can be implemented using dynamic_cast. It can receive a reference to some polymorphic object and cast it to the appropriate IDispatchPart. But this solution isn't discussed here in detail, because it breaks the beautiful type safety concept.

History

This work based on MultiMethods Implementation via Deferred Dispatching. The main advantage against previous solution is a separate compilation possibility.

Acknowledgements

Special thanks to:

• Alexander Evdokimov;
• Michael Litvinov.

References

1. Bjarne Stroustrup. The C++ Programming Language. Addison-Wesley, third edition, August 1997.
2. Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides. Design Patterns - Elements of Reusable Object-Oriented Software. Addison-Wesley, 1995.
3. Andrei Alexandrescu. Modern C++ Design. Addison-Wesley, C++ In-Depth series. 2001.
4. David Vandevoorde and Nicolai M. Josuttis. C++ Templates: The Complete Guide. Addison-Wesley, 2003.