Re: Best multimethods/multiple dispatch implementations?

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

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