Re: Multi-method

Joachim Durchholz <joachim_d@gmx.de> writes:


> Jean-Marc Bourguet wrote:
> > Is there such a technique allowing to dispatch on the type of several
> > parameters
> > - in time proportionnal to the number of dispatching parameter
> > - in such a way that independant compilation is possible.
>
> Base technique: Do a cascading dispatch, using a vtable for every
> dispatching parameter.
> I.e. for
> foo(x, y)
> you'll have a dispatch table for x, then, for every entry in that table,
> another dispatch table for y.
> This will give a polynomial growth in the number of parameters, but you
> can exploit that programmers try to arrange stuff so that the actual
> number of routines is linear. IOW arrange your table compression scheme
> so that it mimicks the ways programmers organize their multiple dispatch.


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.
That's not really the case for what I was considering: the independant
compilation was there in a context of dynamically loading some modules
(I should perhaps have written this earlier).


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


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


--
Jean-Marc
[Oh, you want to add types at load time. C++ doesn't make that easy.
You might be able to leave space in the vtables and patch in the new
methods, but it's going to be ugly.
-John]

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