Emulating Dynamic Dispatch in C++ based on Template Parameters

Question

This is heavily simplified for the sake of the question. Say I have a hierarchy:

struct Base {
    virtual int precision() const = 0;
};

template<int Precision>
struct Derived : public Base {

    typedef Traits<Precision>::Type Type;

    Derived(Type data) : value(data) {}
    virtual int precision() const { return Precision; }

    Type value;

};

I want a non-template function with the signature:

Base* function(const Base& a, const Base& b);

Where the specific type of the result of the function is the same type as whichever of a and b has the greater Precision; something like the following pseudocode:

Base* function(const Base& a, const Base& b) {

    if (a.precision() > b.precision())

        return new A( ((A&)a).value + A(b.value).value );

    else if (a.precision() < b.precision())

        return new B( B(((A&)a).value).value + ((B&)b).value );

    else

        return new A( ((A&)a).value + ((A&)b).value );

}

Where A and B are the specific types of a and b, respectively. I want function to operate independently of how many instantiations of Derived there are. I'd like to avoid a massive table of typeid() comparisons, though RTTI is fine in answers. Any ideas?

Levesque

I think you should mention that you don't know the complete class type. You just know the Base&. Several answers, including my own, did assume you know the precise type Derived<I>. – Phoenician

Noting from a comment on an answer: An additional requirement is that the function cannot be a template; it must have the given Base*(Base&, Base&) signature. – Cleistogamy

Incorporated the restrictions more clearly into the question. – Levesque

Can you tell us what you need all this for? Maybe there is a simplier or complete compile time solution? – Phoenician

I think to solve this at runtime, you ultimately need to add a virtual function int Base that returns a type of the highest precision, and which is overridden by Derived<I> to return their value. Then you can just do the addition in function. – Phoenician

@Johannes: It's for an interpreter for a language project. The result of an operation on two numbers a and b must yield a result of the same type as whichever of a and b has the greater precision. – Levesque

Answer 1

You can't have function() delegate to templated code directly without selecting between a massive list of all possible types, because templates are expanded at compile-time, and at compile-time function() does not know what derived types it will actually be called with. You need to have compiled instantiations of the templated code for every version of your templated operation function that will be required, which is potentially an infinite set.

Following that logic, the only place that knows all of the templates that might be required is the Derived class itself. Thus, your Derived class should include a member:

Derived<Precision> *operation(Base& arg2) {
  Derived<Precision> *ptr = new Derived<Precision>;
  // ...
  return ptr;
}

Then, you can define function like so, and do the dispatching indirectly:

Base* function(const Base& a, const Base& b) {
  if (a.precision() > b.precision())
    return a.operation(b);
  else 
    return b.operation(a);
}

Note that this is the simplified version; if your operation is not symmetric in its arguments, you'll need to define two versions of the member function -- one with this in place of the first argument, and one with it in place of the second.

Also, this has ignored the fact that you need some way for a.operation to get an appropriate form of b.value without knowing the derived type of b. You'll have to solve that one yourself -- note that it's (by the same logic as earlier) impossible to solve this by templating on the type of b, because you're dispatching at runtime. The solution depends on exactly what types you've got, and whether there is some way for a type of higher precision to pull a value out of an equal-or-lower precision Derived object without knowing the exact type of that object. This may not be possible, in which case you've got the long list of matching on type IDs.

You don't have to do that in a switch statement, though. You can give each Derived type a set of member functions for up-casting to a function of greater precision. For example:

template<int i>
upCast<Derived<i> >() {
  return /* upcasted value of this */
}

Then, your operator member function can operate on b.upcast<typeof(this)>, and will not have to explicitly do the casting to get a value of the type it needs. You may well have to explicitly instantiate some of these functions to get them to be compiled; I haven't done enough work with RTTI to say for sure.

Fundamentally, though, the issue is that if you've got N possible precisions, you've got NN possible combinations, and each of these will in fact need to have separately-compiled code. If you can't use templates in your definition of function, then you have to have compiled versions of all NN of these possibilities, and somehow you have to tell the compiler to generate them all, and somehow you have to pick the right one to dispatch to at runtime. The trick of using a member function takes out one of those factors of N, but the other one remains, and there's no way to make it entirely generic.

Cleistogamy

This is good enough for me. The second factor is removed by the fact that Base defines a facility for converting at runtime to an arbitrary type. – Levesque

Oh, good! I was just editing to suggest that such a facility would be useful for removing the second factor. – Cleistogamy

Answer 2

What you are asking for is called multiple dispatch, aka multimethods. It isn't a feature of the C++ language.

There are workarounds for special cases, but you can't avoid doing some implementation yourself.

One common pattern for multiple dispatch is called "redispatch", aka "recursive deferred dispatching". Basically, one virtual method resolves one parameters type then calls another virtual method, until all parameters are resolved. The function of the outside (if there is one) just calls the first of these virtual methods.

Assuming there are n derived classes, there will be one method to resolve the first parameter, n to resolve the second, n*n to resolve the third and so on - at worst, anyway. That's a fair amount of manual work, and using conditional blocks based on typeid might be easier for initial development, but it's more robust for maintenance to use redispatch.

class Base;
class Derived1;
class Derived2;

class Base
{
  public:
    virtual void Handle (Base* p2);

    virtual void Handle (Derived1* p1);
    virtual void Handle (Derived2* p1);
};

class Derived1 : public Base
{
  public:
    void Handle (Base* p2);

    void Handle (Derived1* p1);
    void Handle (Derived2* p1);
};

void Derived1::Handle (Base* p2)
{
  p2->Handle (this);
}

void Derived1::Handle (Derived1* p1)
{
  //  p1 is Derived1*, this (p2) is Derived1*
}

void Derived1::Handle (Derived2* p1)
{
  //  p1 is Derived2*, this (p2) is Derived1*
}

//  etc

Implementing this using a template for the derived classes would be difficult, and the template metaprogramming to handle it would probably be unreadable, unmaintainable and very fragile. Implementing the dispatch using non-template methods, then using a mixin template (a template class that takes its base class as a template parameter) to extend that with additional features may not be so bad, though.

The visitor design pattern is closely related to (basically implemented using) redispatch IIRC.

The other approach is to use a language designed to handle the problem, and there are a few options which work well with C++. One is to use treecc - a domain-specific language for handling AST nodes and multiple-dispatch operations which, like lex and yacc, generates "source code" as output.

All it does to handle the dispatch decisions is generate switch statements based on an AST node ID - which can just as easily be a dynamically-typed value class ID, IYSWIM. However, these are switch statements that you don't have to write or maintain, which is a key difference. The biggest issue I have is that AST nodes have their destructor handling tampered with, meaning that destructors for member data don't get called unless you make a special effort - ie it works best with POD types for fields.

Another option is to use a language preprocessor that supports multimethods. There have been a few of these, partly because Stroustrup did have fairly well developed ideas for supporting multimethods at one point. CMM is one. Doublecpp is another. Yet another is the Frost Project. I believe CMM is closest to what Stroustrup described, but I haven't checked.

Ultimately, though, multiple dispatch is just a way to make a run-time decision, and there are many ways to handle the same decision. Specialist DSLs bring a fair amount of hassle, so you generally only do it if you need a lot of multiple dispatch. Redispatch and the visitor pattern are robust WRT maintenance, but at the expense of some complexity and clutter. Simple conditional statements may be a better choice for simple cases, though beware that detecting the possibility of an unhandled case at compile-time is then difficult if not impossible.

As is often the case, there is no one right way to do it, at least in C++.

Recorder

Answer 3

First, you want to make your precision member a static const int value, not a function, so that you can operate on it at compile time. In Derived, it would be:

static const int precision = Precision;

Then, you need some helper structs to determine the most-precise Base/Derived class. First, you need a generic helper-helper struct to pick one of two types depending on a boolean:

template<typename T1, typename T2, bool use_first>
struct pickType {
  typedef T2 type;
};

template<typename T1, typename T2>
struct pickType<T1, T2, true> {
  typedef T1 type;
};

Then, pickType<T1, T2, use_first>::type will resolve to T1 if use_first is true, and otherwise to T2. So, then we use this to pick the most precise type:

template<typename T1, typename T2>
struct mostPrecise{
  typedef pickType<T1, T2, (T1::precision > T2::precision)>::type type;
};

Now, mostPrecise<T1, T2>::type will give you whichever of the two types has a greater precision value. So, you can define your function as:

template<typename T1, typename T2>
mostPrecise<T1, T2>::type function(const T1& a, const T2& b) {
  // ...
}

And there you have it.

Cleistogamy

This is very interesting and useful to another project of mine, but I specifically need the decision to be made at runtime. – Levesque

Thanks. I'll leave this one up for historical value rather than deleting it, then, but see my other answer for comments on doing this at runtime. – Cleistogamy