Re: Multi-method

Joachim Durchholz <>
7 Apr 2002 22:44:11 -0400

          From comp.compilers

Related articles
Multi-method (Jean-Marc Bourguet) (2002-03-31)
Re: Multi-method (2002-04-06)
Re: Multi-method (2002-04-06)
Re: Multi-method (Joachim Durchholz) (2002-04-06)
Re: Multi-method (Jean-Marc Bourguet) (2002-04-07)
Re: Multi-method (Jean-Marc Bourguet) (2002-04-07)
Re: Multi-method (Dmitry A.Kazakov) (2002-04-07)
Re: Multi-method (Joachim Durchholz) (2002-04-07)
Re: Multi-method (Richard Rogers) (2002-04-10)
| List of all articles for this month |

From: Joachim Durchholz <>
Newsgroups: comp.compilers
Date: 7 Apr 2002 22:44:11 -0400
Organization: Compilers Central
References: 02-03-190 02-04-029 02-04-049
Keywords: OOP
Posted-Date: 07 Apr 2002 22:44:11 EDT

Jean-Marc Bourguet wrote:
> I fail to see how the dispatch tables can be build incrementally.
> Your mention of a compression scheme make me think you consider that
> there is a point where the whole program is know before it is run.

You can do compression schemes incrementally. It may not give you the
performance that you want. OTOH if adding a new class at run-time is a
relatively rare event, it's feasible. In the worst case, just recreate
the compression.
It's essentially a redundant matrix problem. I know there are heaps of
papers on sparse matrices; some of that should be applicable to
multidimensional vtables.

>>Note that independent compilation and multiple dispatch are at odds
>>conceptually. If you have
>> function foo(Animal, Animal)
>> function foo(Animal, Cow)
>> function foo(Cow, Animal)
>>a call with a run-time type combination giving
>> foo(Cow, Cow)
>>will be ambiguous. If all these code snippets are in different modules,
>>you'll need a link-time check anyway
> Not necessary. Some languages resolve the ambiguity by prefering some
> arguments (if memory serve, Common Lisp will call foo(Cow, Animal) in
> this case).

AFAIK you can even specify your own dispatch strategy.
However, I think such strategies are unsound. They mean that adding a
function may change the execution path taken.
I.e. in the above example, if you test your software with a module
configuration where foo(Cow, Animal) is missing, you'll silently get
foo(Animal, Cow); later, when somebody adds a foo(Cow, Animal) routine,
you'll have to remember to retest all cases where foo(Animal, Cow) was

      One may also constraints the language so that static
> checking is possible (on this subject, a private response gave me an
> interesting reference "Modular Statically Typed Multimethods",
> Millstein and Chambers
> But that's for the
> semantic and static checking and I wonder if my constraints are not
> too tight.

I read that paper a while ago. I found it unsatisfactory but I'd have to
reread it now to say what exactly was missing.

>>(IOW you don't have separate compilation anymore, unless you write
>>your own linker - in which case the linker could in principle do
>>anything that's traditionally associated with the compiler's tasks,
>>such as dataflow analysis to determine which calls could go directly
>>to a routine instead of through a vtable, with subsequent inlining -
>>that's one of the most important optimizations for OO languages, and
>>you can't do it before link time ina multi-dispatch language).
> Even for a single dispatch language you generally need a dataflow
> analysis on the whole program for this kind of optimisation be
> effective.

Right - I'm doubt that Java's load-as-you-go approach is a good idea. It
certainly misses lots of important optimization opportunities.


Post a followup to this message

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