Re: Best multimethods/multiple dispatch implementations?

On Sep 24, 8:00 am, George Neuner <gneun...@comcast.net> wrote:
> On Mon, 22 Sep 2008 04:17:41 -0700 (PDT), Christoffer Lernv
>> I'm thinking about something like "toString()" in Java.
>
>> Assuming it is implemented as a generic function, wouldn't it need to
>> a rather imposing if-then list since there must be hundreds of
>> versions of this function in the java libs alone?
>
>> Why is this not a problem?
>
> It could be a problem, but only if the class hierarchy is deep. That
> is not the case in most real code ... even in enormous class
> frameworks, studies have shown that the real world class hierarchies
> are rarely more than about 10 levels deep.
>
> In Java, all the standard classes derive from Object in just a few
> steps. Developer added hierarchies contribute little even if they
> derive starting from existing standard classes.


Does this have anything to do with hierarchy depth? Perhaps I am
misunderstanding something.


I am assuming that to create an OO system using generic functions,
Object#toString() is implemented as the generic function


String toString(Object o) { ... }


When a subclass X to Object implements an overriding function, we add
a new function definition


String toString(X o) { ... }


So if we have 10 direct subclasses to Object overriding toString, we
have 100 extra definitions of toString()


So


String toString(Object o) { ... }
String toString(X1 o) { ... }
String toString(X2 o) { ... }
...
String toString(X10 o) { ... }


If I now have the object o that can have any type and I call
o.toString(), then this will transform into the generic function call
toString(o);


This call is then in practice:


String toString(Object o)
{
if (o.class == Object) { <original implementation of toString()> }
else if (o.class == X1) { <X1 implementation of toString()> }
else if (o.class == X2) { <X2 implementation of toString()> }
...
else if (o.class == X10) { <X10 implementation of toString()> }
else throw new UnsupportedOperationException();
}


I suppose this could be optimized a bit by creating a tree instead.


String toString(Object o)
{
if (o.class == Object) { <original implementation of toString()> }
else if (o.class < X5)
{
if (o.class < X3)
{
if (o.class == X1) { <X1 implementation of toString()> }
else { <X2 implementation of toString()> }
}
else
{
if (o.class == X3) { <X3 implementation of toString()> }
else { <X4 implementation of toString()> }
}
else
{ ... }
}
else
{
if (o.class < X8) { ... }
else { ... }
}
}


So wouldn't this be independent on hierarchy depth but instead
dependent on the number of different versions of the method?


> The basic idea is right ... you create a dispatch table and somehow
> index it based on the run time argument types. The problem in Java
> (and in Lisp, see below) is that the tables have to be constructed at
> run time.


But doesn't discrimination trees mean corresponding difficulties when
compiling the language, since a precompiled generic function will need
to be recompiled when extended, right?


> In either case - table or discrimination tree - the set of type ids
> and function overloads is known at compile time so all the tests are
> effectively against integer constants. But in Lisp, a direct function
> call is quite a bit faster than an indirect call via the function
> symbol,


The big win I see about discrimination trees would be that it is
possible to merge the results of these trees to reduce them
significantly.


The second is that one would be able to inline shorter functions at
compile time - which is impossible to do with function pointers.


With a VM of course, you could do inlining during runtime.


> FWIW, I have been told off-line that some of the heavyweight Lisps do
> now use table dispatch ... but those particular Lisps all have CLOS
> functionality built into them rather than as a separate library so
> they can implement the functionality however they please.


Table dispatch for performance reasons or are there other reasons?




/Christoffer

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