Re: Best multimethods/multiple dispatch implementations?

I'm not an expert on compiler stuff, but I have written an
(unreleased) utility to support multiple dispatch in C++. The
inspiration for it was a utility called treecc.


Based on that experience...


Christoffer Lernv wrote:


> 1. What is state-of-art when it comes to multiple dispatch? From what
> I read so far it sounds that something like Self's PICs could also
> speed up multiple dispatch. Are there any implementations using
> something like that?


Any dispatch decision is, at heart, just a decision. Multiple dispatch
can be implemented many ways. As always, it's a compromise between
different issues.


In my case, my utility is a source-to-source translator which
generates C++ code. It supports multiple dispatch, but only single
inheritance, on a class hierarchy that is defined in the utilities
source (the resulting classes forming part of the generated code).


I considered using table lookups etc, but in the end I used a
decision-tree generator based on a variation on the ID3 theme. That
is, it uses information theory to order a series of questions (what
type is parameter n) in order to decide which variant of the function
to dispatch. The decision tree is minimised using Hopcrofts digraph
minimisation algorithm.


Why? - Well, I had these bits of code laying around, so I used them.


In comparison, treecc uses a series of switch/case statements testing
parameter types strictly left-to-right IIRC.


The benefit of my approach is NOT execution speed, though it can
occasionally avoid checking the type of some parameters. The run-time
benefit is that the final code tends to be a bit smaller.


Why not support multiple inheritance? - It's no problem for the dispatch
handler, but it does mean dealing with the usual multiple inheritance
headaches such as pointer casts that need offsets applied. I couldn't be
bothered, basically.


One last implementation issue - multiple dispatch isn't as tolerant of
separate compilation as single dispatch is. Obviously it depends on how
its done, but I got the feeling that I'd have to build a run-time data
structure at application startup in order to handle multiple dispatch
efficiently if the compiler could not know about all possible variants
of an operation at the same time.


Basically, the 'compiler' needs to know the full class hierarchy and all
the special cases for each operation at once in order to build a
pre-calculated decision handler. For single inheritance this is pretty
easy to avoid, but the normal virtual-table-lookup doesn't work for
multiple dispatch.


This is actually a (minor) problem for my utility. All that overkill
compile-time analysis can take a little while. Not so much for the
ID3-alike stuff itself, but since I have a constraint conditions in
addition to type matching, I end up building a pretty big decision table
that the decision-tree builder has to analyse for each dispatch handler.


OK, thats less than a minute on my deliberately ridiculous test case,
but still pretty bad for a reasonably modern machine running a
command-line code generator.


Actually, thinking about it, there is a virtual-table method that can
handle multiple dispatch and separate compilation. In a sense, it's
already in quite common use, though as a design pattern rather than as a
compiler feature. Dispatch requires a table lookup for each polymorphic
parameter. The design-pattern version uses a polymorphic method for each
polymorphic parameter, so that the multiple dispatch is resolved using a
series of single dispatch calls. Each method calls the next in sequence
(with a different parameter as 'this') until you get to the final
fully-resolved method.


As a design pattern, its annoying and can involve a lot of overhead
source code. As a compiler feature, it'd probably be just as efficient
as my decision-tree method, but without the limitations wrt separate
compilation. Sigh.


> 2. Is it feasible to base an OO-language on multiple dispatch


I don't know anything about CLOS, or even that much about Lisp. However...


Is multiple inheritance compatible with object orientation? - That's
actually a more interesting question than it sounds. In traditional OO,
methods calls are particularly strongly associated with (belong to) one
particular parameter - so much so that we almost forget that it is just
a parameter. When dispatch decisions can be based on any or all
parameters, you start to wonder whether this 'method' concept is really
important at all.


My utility, like treecc, takes the view that "operations" are not
members of classes. They are basically just collections of "variant"
functions that are collected together and wrapped in a dispatch handler
function by the code generator utility.


I mainly use it to avoid the need for the visitor pattern. The
source-code overhead is much less, the run-time efficiency is probably
about the same, and I get strong compile-time consistency checks for all
those scattered special cases, which is basically what all that visitor
pattern source overhead is intended for.


That said, just because the this/self parameter isn't special in the
sense of dispatch any more doesn't mean it can't be special in other OO
senses such as data hiding. And even my utility still uses single
inheritance to build up the data "classes".

Return to the comp.compilers page.
Search the comp.compilers archives again.