Re: Best multimethods/multiple dispatch implementations?

On Sep 19, 12:12 pm, George Neuner <gneun...@comcast.net> wrote:
> <le...@dragonascendant.com> wrote:
> >On Sep 16, 1:17 am, George Neuner <gneun...@comcast.net> wrote:
>>> CLOS dispatch is typically implemented as an inline coded minimum
>>> depth discrimination tree - a series of IF-THEN tests on the argument
>>> types - ordered by the partitioning value of the function arguments.
>>> Lisp tries to order the tests so as to most efficiently partition the
>>> virtual search tree at each step.
>
>> The best case scenarios of this ought to be really fast and easy to
>> inline, but what about methods that are frequently overridden?
>> Wouldn't worst case be pretty bad?
>
> The worst case is linear in the number of overloads - that requires
> every overload of the function to have a unique argument type
> signature.


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?


> Tables make sense for single dispatch, but there is a lot of overhead
> associated with using them for multiple dispatch. With MD the naked
> table is very sparse - some arguments may have no discrimination value
> at all and the ones that do will have entries for only a very few of
> the possible data types in the program. So an MD table will
> necessarily be compressed and there must be a mapping from each
> argument's potential type to an index legal for that argument's
> dimension.
> Once you factor in the type->index mapping (which most likely will be
> implemented by conditional chain even if the dispatch source uses a
> tabular construct like switch" or "case"), you've lost most or all of
> the speed advantage of using the table over just using conditional
> chains in the first place.


Won't dispatch be implemented something like this?


public Object dispatch(Objekt... objekts)
{
int index = 0;
for (int i = 0; i < objekts.length; i++)
{
index += m_poleMult[i] *
m_poleTable[i].getPoleForClass(objects[i].getClassId());
}
return m_dispatchArray[index].call(objects);
}


I realize this is a lot longer than a simple if-then, but I was mainly
thinking about commonly overridden functions, such as class creation
or the "toString()" I already brought up.

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