Re: Best multimethods/multiple dispatch implementations?

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

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