Re: Multi-method

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)
>>and
>> 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
executed.


      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
> http://citeseer.nj.nec.com/millstein99modular.html) 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.


Regards,
Joachim

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