Given the definitions and rules of Section 3, the implementation of accessory functions does not pose many interesting technical challenges. We simply move the existing algorithms for building dispatch tables from compile-time to link-time, retaining the general principles used for virtual functions in C++: each object contains a pointer to a table of all functions that may be dynamically dispatched based on its type, and the compiler statically produce code that will locate a given function with a (constant time) table lookup (for single inheritance, we simply use a fixed offset into the table).
The restrictions in Section 3.2 can be checked trivially as function declarations are processed at compile-time. To compile a (possibly dynamically dispatched) function call, we start by applying the C++ rules for overloaded function selection [17, Section 7.4] to the set of functions that are in scope and have the correct name and number of parameters, with the restriction that type casting of values cannot be used to create a match with a virtual parameter. If there is not a unique match, a compile-time error is produced. If there is a unique best match, we generate either a regular function call (if the best match has no virtual parameter) or a dynamic function dispatch.
If the best match had a virtual parameter, the dynamic dispatch is very much like a C++ virtual function call. We know that the virtual argument will contain a pointer to a table of dynamically dispatched functions, and generate a load of a function pointer from this table, and a branch to this address. The presence of accessory functions means that we no longer know the size or layout of this table when compiling a single file, but we handle this by treating the offset into the table as an undefined reference that will be filled in later by the linker.
Note that we need a separate entry in the dispatch table for each virtual parameter position, function name, and arity. A group of three-parameter functions may be dispatched differently from some two-parameter functions of the same name; different three-parameter functions may have different virtual parameters (as long as they are not in the same scope).
We rely on the compiler to give the linker a complete description of the DAG describing the class inheritance structure, and a list of all functions (complete with parameter types and information about which parameters are virtual). We topologically sort the inheritance DAG and we apply the algorithm used to build C++ virtual function tables, using a new offset for each set of statically distinct functions. Since the offsets are determined at this stage, we can resolve the undefined references produced at compile time.
This implementation places an increased load on the linker, and thus may increase link times. However, this is a fundamental consequence of the fact that declarations of accessory functions for a given class may be spread across several files (unlike the class' virtual functions), not a weakness of our implementation. The distribution of accessory functions over different files prevents detection by the compiler of certain errors that could be detected by traditional C++ compilers, such as the instantiation of a class with a pure virtual accessory function (one file may instantiate an object of a class for which pure virtual accessory functions are created in another file).
It may be possible to reduce the link-time overhead somewhat by replacing our implementation with a version of Millstein and Chambers' techniques for modular multimethod dispatch [15], restricted to the case of single dispatch. We have not investigated this possibility, since some degree of link-time overhead is unavoidable, and our main goal is to present a simple implementation that demonstrates that we can retain the constant-time nature of the dynamic dispatch used in C++.