Best multimethods/multiple dispatch implementations?

I have been looking a bit at multiple dispatch.

So far I found info about the Cecil/Vortex project (http://
http://www.cs.washington.edu/researc...spatching.html),
a bit about MultiJava (http://multijava.sourceforge.net/pubs.shtml), a
paper about multi-methods for C++ (http://www.research.att.com/~bs/
multimethods.pdf) and something about compressed multi-method
dispatch tables (http://hal.inria.fr/inria-00073721/en/)

I know Dylan and CLOS also has implementations, but I heard CLOS'
might be pretty slow.

So, two questions:

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?

2. Is it feasible to base an OO-language on multiple dispatch (I was
thinking left-to-right to resolve ambiguous calls like CLOS) so that
someObject.someMethod() becomes syntactic sugar for the function
someMethod(someObject). This is how a lot of dynamically typed OO
already are built, but without single dispatch on the remaining
arguments, which allows for some simplifications (and more efficient
dispatch?)


/Christoffer

On Sep 5, 1:20 pm, Christoffer Lernv <le...@dragonascendant.com>
wrote:
> I have been looking a bit at multiple dispatch.
>
> I know Dylan and CLOS also has implementations, but I heard CLOS'
> might be pretty slow.

CLOS dispatch is actually remarkably fast when well implemented. I
have tried replacing, in an inner loop, a generic function call (a
CLOS dispatch) with an ordinary function call, and got a much smaller
speedup than I expected. This was in an implementation (Franz
Allegro) with a well-optimized CLOS, but still I was pleasantly
surprised, particularly considering that the generic function in
question had a couple dozen methods.

I think anyone studying multiple dispatch -- particularly the
semantics, but also the implementation -- needs to look at CLOS very
carefully.

-- Scott

On Fri, 5 Sep 2008 13:20:37 -0700 (PDT), 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?

Theoretically multiple dispatch can be as efficient as indexing a
multidimensional array. The dispatch table of a method is such an array
indexed by the type tags of the arguments (and possibly of the result). To
make these indexes dense, one would likely map each tag to the
corresponding index.

> 2. Is it feasible to base an OO-language on multiple dispatch (I was
> thinking left-to-right to resolve ambiguous calls like CLOS) so that
> someObject.someMethod() becomes syntactic sugar for the function
> someMethod(someObject).

I don't see any ambiguity in multiple dispatch, Talking about feasibility,
single dispatch is clearly infeasible for multi-methods. Also infeasible is
to consider methods as members of a type/object. (The sugar X.Y(Z) |=
Y(X,Z) is OK to me.)

> This is how a lot of dynamically typed OO
> already are built, but without single dispatch on the remaining
> arguments, which allows for some simplifications (and more efficient
> dispatch?)

Are you talking about multiple dispatch viewed as a sequence of single
dispatches? I think this is infeasible, and it does not solve the problem
which multiple dispatch is supposed to do. That is consistency of
operations defined on tuples of possibly different types.

IMO, the implementation shall statically ensure that dispatch never fails
at run time. This is trivial for single dispatch (solved through
inheritance) and quite difficult for multiple one.

--
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

On Sep 6, 10:51 am, "Dmitry A. Kazakov" <mail...@dmitry-kazakov.de>
wrote:
> Theoretically multiple dispatch can be as efficient as indexing a
> multidimensional array. The dispatch table of a method is such an array
> indexed by the type tags of the arguments (and possibly of the result). To
> make these indexes dense, one would likely map each tag to the
> corresponding index.

I looked at one "Eo,cient Compression of Generic Function Dispatch
Tables" by Eric Kidd: http://www.cs.dartmouth.edu/reports/TR2001-404.pdf
which, if I understand, is applicable to any language with C3
linearization of classes since since C3 linearized classes satisfy the
monotonicity requirement.

It looks like it should be very fast, even when using the compression
schemes in Kidd's paper.

In fact I may be overlooking something, but it almost looks like it is
faster than normal Objective-C dispatch.

> > 2. Is it feasible to base an OO-language on multiple dispatch (I was
> > thinking left-to-right to resolve ambiguous calls like CLOS) so that
> > someObject.someMethod() becomes syntactic sugar for the function
> > someMethod(someObject).
>
> I don't see any ambiguity in multiple dispatch, Talking about feasibility,
> single dispatch is clearly infeasible for multi-methods. Also infeasible is
> to consider methods as members of a type/object. (The sugar X.Y(Z) |=
> Y(X,Z) is OK to me.)

I don't quite follow you, what do you mean by X.Y(Z) |= Y(X,Z)?

> > This is how a lot of dynamically typed OO
> > already are built, but without single dispatch on the remaining
> > arguments, which allows for some simplifications (and more efficient
> > dispatch?)
>
> Are you talking about multiple dispatch viewed as a sequence of single
> dispatches?

No, I more meant that dynamically typed single dispatch can be
modelled as a sort of crippled multiple dispatch where the only the
first argument may have a type and each unique function definition
generates an implicit shadow-function handling the "method missing"-
situation.

> IMO, the implementation shall statically ensure that dispatch never fails
> at run time. This is trivial for single dispatch (solved through
> inheritance) and quite difficult for multiple one.

I am sorry but I don't quite follow you. What are you talking about
here?


/Christoffer

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".

On Sep 9, 5:25 pm, Steve Horne <sh006d3...@blueyonder.co.uk> wrote:
> 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.

I'm working on something where multiple dispatch would be the only
type of dispatch available. That's why I want something which is as
fast as possible. I feel it's becoming obvious that I at least need
some kind of type inference for the compiler to get things like
integer operations fast.
Too bad it is inevitable that it is much slower than normal functions
unless you really optimize the heck out of it... :-/

> 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.

Yes it is kind of a headache, but my understanding is that even if one
limits oneself to a java-like single inheritance with interfaces, one
still has to support full multiple inheritance in dispatch (though not
in pointer offsets).

> 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.

I have been thinking a bit about this. Even if it was possible to
precompile parts (this should easily be possible when using CNT-style
dipatch tables), one might still want to optimize precompiled code
once the whole program is assembled.

For instance, using type inference it might be possible to remove
certain methods and classes entirely. That in turn could be fed back
into "precompiled" code to optimize it further.

I was thinking of targetting LLVM and I've been wondering if it would
be possible to compile each chunk to LLVM bc and bundle such a package
with a data description which is fed to the parser. The data
description would both be used to determine the data structures/
objects in the "package" as well as detailing type/method dependencies
for every method to allow partial recompilation. I have no idea how
easy such thing would be though.

But obviously compilation time is a really big issue. At work we have
a c++ team working on a client that takes a few hours to compile from
scratch. I think that's clearly unworkable. Creating any new language
without thought paid to fast incremental compilation would be a good
way to make it useless for big projects.


> 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.

Yes, I think I read about that type of dispatch somewhere but I can't
remember where. It's conceptually easy to understand, but obviously
the dispatch cost would increase linearly with the amount of
arguments. I wonder about the real cost compared to dispatch tables
though.

> 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.

Yes, this is something I've been thinking about as well.

The neat thing with objects is that they can be a useful way to
organize functions related to certain types.

Another thing I find very useful with the "method concept", is the
immediate accesibility of "private" vs. "public" methods, which
immedately draws you towards working with layers of abstraction.

/C

On Fri, 5 Sep 2008 13:20:37 -0700 (PDT), Christoffer Lernv
<lerno@dragonascendant.com> wrote:

>I have been looking a bit at multiple dispatch.
>
>I know Dylan and CLOS also has implementations, but I heard CLOS'
>might be pretty slow.

CLOS dispatch is typically implemented as an inline coded minimum
depth discrimination tree - a series of IF-THEN tests on the argument
types - ordered by the partitioning value of the function arguments.
Lisp tries to order the tests so as to most efficiently partition the
virtual search tree at each step.

CLOS is not slow, but it does have the peculiar behavior that the
dispatch code for a generic function is generated at run time upon the
first call to the function - slowing the first call but not subsequent
ones. This is because Lisp allows functions to be redefined at run
time and so the set of overloads of the generic function might be
modified. Whenever the set of overloads is modified, the dispatch
code is regenerated at the next call. Many benchmarks of CLOS fail to
take this behavior into account.

Dylan uses the same dispatch method as CLOS but allows finalizing the
set of function overloads and generating the dispatch code at compile
time.


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

Certainly.

>(I was thinking left-to-right to resolve ambiguous calls like CLOS)
>so that someObject.someMethod() becomes syntactic sugar for the
>function someMethod(someObject). This is how a lot of dynamically
>typed OO already are built, but without single dispatch on the
>remaining arguments, which allows for some simplifications (and more
>efficient dispatch?)

CLOS evaluates arguments left-to-right, but the argument type dispatch
may be ordered differently.

It is quite feasible to have both object bound methods and separate
generic MD functions in the same language. You could use the same MD
dispatch method for each, but method tables are more efficient for
single dispatch. MD tables can get very large but they are mostly
sparse and so can be compressed effectively. However, compressing the
tables slows lookup at run time. This is ok if few MD dispatches are
expected, but if you anticipate a lot of use, using discrimination
trees like CLOS may be a better bet.

George

On Tue, 09 Sep 2008 16:25:38 +0100, Steve Horne
<sh006d3592@blueyonder.co.uk> wrote:

>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.

I withdraw this - the flaw isn't overhead (in a language that compiles
the pattern, the intermediate calls would be eliminated in favour of
simple vtable-to-vtable lookups). The flaw is that every class needs
to know about every other class from the start, and also needs some
idea of the dispatch decision beyond it's own immediate interest.

The chain of calls is basically a precompiled decision tree, generated
manually be the programmer.

Don't feel so bad now that I've realised that.

From what George said, I suspect what my utility is doing as a code
generator is a slow and overcomplicated variant of what CLOS and Dylan
do on a first-use basis at run-time.

On Sep 16, 1:17 am, George Neuner <gneun...@comcast.net> wrote:
>> I know Dylan and CLOS also has implementations, but I heard CLOS'
>> might be pretty slow.
>
> CLOS dispatch is typically implemented as an inline coded minimum
> depth discrimination tree - a series of IF-THEN tests on the argument
> types - ordered by the partitioning value of the function arguments.
> Lisp tries to order the tests so as to most efficiently partition the
> virtual search tree at each step.

The best case scenarios of this ought to be really fast and easy to
inline, but what about methods that are frequently overridden?
Wouldn't worst case be pretty bad?

> It is quite feasible to have both object bound methods and separate
> generic MD functions in the same language. You could use the same MD
> dispatch method for each, but method tables are more efficient for
> single dispatch. MD tables can get very large but they are mostly
> sparse and so can be compressed effectively. However, compressing the
> tables slows lookup at run time. This is ok if few MD dispatches are
> expected, but if you anticipate a lot of use, using discrimination
> trees like CLOS may be a better bet.

Aren't there some languages with hybrid dispatch using tables or trees
depending on the tree depth? With even rudimentary type inference I
suppose one would be able to cut away a lot of branching.

Do you know of any papers on CLOS dispatch implementations?

/Christoffer

Hi

I implemented doublecpp, which is a translator that
implements double dispatch by using only dynamic binding and static
overloading (it is also cited in the paper of Stroustrup):
http://doublecpp.sourceforge.net/

we also have some papers:

http://rap.dsi.unifi.it/bibliography...=0&category=17
&submit=Go

both implementative ones and foundational ones.

Note that our approach permits discarding all possible ambiguities at
static (compile) time, so the program will never raise an error due to
ambiguities if the compiler type checked the program successfully.

Hope this helps
cheers
Lorenzo

Christoffer Lernv wrote:
> I have been looking a bit at multiple dispatch.
>
> So far I found info about the Cecil/Vortex project (http://
> http://www.cs.washington.edu/researc...spatching.html),
> a bit about MultiJava (http://multijava.sourceforge.net/pubs.shtml), a
> paper about multi-methods for C++ (http://www.research.att.com/~bs/
> multimethods.pdf) and something about compressed multi-method
> dispatch tables (http://hal.inria.fr/inria-00073721/en/)