Multiple dispatch is an extension of the concept of virtual functions. With a virtual function, the exact function called depends on the runtime type of the this
object. With multiple dispatch, the exact function called depends on the runtime type of two or more objects. D does not have support for multiple dispatch built into the language, but with some code generation, we can add it ourselves.
Let's consider how we will do it manually. Given two or more class objects and a list of functions, we will need to call the most specific function possible for their dynamic type.
To determine if a class is more specific than another, we look at the inheritance hierarchy. If class A is a parent or an ancestor of class B, class B is more specific than class A. This makes the generic root class, Object
, which has no parents, the least specific of all.
To determine if an object is an instance of a more specific class, we attempt to cast it and test for the null
type.
What if there are two matching functions of equal specificity? You should avoid writing functions like that, but ultimately, the choice is pretty arbitrary. Just pick one.
Now, we'll see how we can automate this process.
Let's execute the following steps to automate dynamic calls with multiple dispatch:
std.traits.CommonType
and std.typetuple.staticMap
to extract the common return value from all overloads.The code is as follows:
class A {} class B : A {} class C : A {} import std.stdio; void test(Object b, Object c) { writeln("Object, Object"); } void test(A b, C c) { writeln("A, C"); } B test(B b, C c) { writeln("B, C"); return b; } void test(B b, B c) { writeln("B, B"); } void test(C b, C c) { writeln("C, C"); } /* The goal is to call the overload of func that best matches the *dynamic types* of the passed argument. */ auto dynamicDispatch(alias func, T...)(T t) { import std.traits; import std.typetuple; // step 1: getting all overloads of the given function alias overloads = TypeTuple!( /* TypeTuple is like our alias helper but it works with multiple arguments and is found in the standard library module std.typetuple */ __traits(getOverloads, // get all overloads… __traits(parent, func), // from the parent of the function… __traits(identifier, func))); // that share a name with it. // step 2: ensure we weren't given null foreach(a; t) assert(a !is null); // step 3: the variable that will hold our match CommonType!(staticMap!(ReturnType, overloads)) delegate() dg; int bestSpecificity = int.min; // and the best match's score overloads: foreach(overload; overloads) { // step 4: loop over each one and find a match ParameterTypeTuple!overload args; static if(T.length == args.length) { int specificity = 0; bool isExactMatch = true; foreach(idx, ref arg; args) { arg = cast(typeof(arg)) t[idx]; if(arg is null) continue overloads; // We check for an exact match – where the typeid we have // is a perfect match for the typeid we need if(isExactMatch && typeid(typeof(arg)) !istypeid(t[idx])) isExactMatch = false; // The specificity is the distance from Object; the number // of base classes. We multiply by the argument length to // help get an average of all arguments. specificity += BaseClassesTuple!(typeof(arg)).length * args.length; } specificity /= args.length; // average specificity // Debugging info, printing out the options we found writeln("specificity of ", typeof(overload).stringof, " = ", specificity); if(specificity > bestSpecificity) { // If it is a better match than we have, it becomes the // new best bestSpecificity = specificity; // the cast ensures we get a consistent type dg = { return cast(ReturnType!dg) overload(args); }; // found an exact match, no point continuing to search if(isExactMatch) break overloads; } } } // if a suitable function was found, call it if(dg) return dg(); // otherwise, throw an exception throw new Exception("no dynamic match found"); } void main() { Object a = new A(); Object b = new B(); dynamicDispatch!test(a, b); }
Play with the new lines in the main
function to see how it works with other combinations too.
We once again visit compile-time reflection over functions to automate a task that requires working with individual function arguments. With the help of std.traits.ParameterTypeTuple
, we can inspect the types of arguments as well as build an argument list to pass to the function.
The cast
operator on class objects when going from a base class or interface to a more derived class attempts a dynamic cast. It uses runtime type information attached to the object itself to see if it is a good match, returning null
if it is not.
The rest of the code implements the algorithm we figured out while getting ready: find the best matching function by looking for arguments that work with the most specificity by looking at the number of base classes. The determination is done at runtime using the compile-time data, which is possible because a new dispatch function will be automatically generated by the compiler for each overload set it is passed with.
The trickiest part of the algorithm's implementation is defining the delegate that holds the current best match. The arguments are left empty because we generated a simple wrapper in the loop previously, which captures the arguments from the outer function in a closure. The return type needs to be consistent, even if the return types of the overloads are not, because the type needs to be known at compile time, and the exact function chosen will not be known until runtime.
To solve this problem, we use CommonType
from std.traits
to extract the best common type from all the possibilities. CommonType
takes a list of types. Since we needed the common return type, we couldn't just pass it the list of overloads. Instead, we had to extract the return type from each overload. Phobos has the magic we need in the std.typetuple
module: staticMap
. staticMap
. Like its runtime partner function, std.algorithm.map
, it takes two arguments: a transformation function and a list of inputs. It applies the transformation to each item in the input list, generating a new output list.
staticMap!(ReturnType, list…)
thus generates a new list of just the return types of the input functions, all at compile time, giving us exactly what we need to determine the common return type for our delegate. Inside the wrapper function, we force the use of the common type with an explicit cast
object completing the implementation.
std.typetuple
module is found at http://dlang.org/phobos/std_typetuple.html3.145.17.140