Re: Best multimethods/multiple dispatch implementations?

> George Neuner <gneun...@comcast.net> wrote:
>> On Thu, 25 Sep 2008 04:33:41 -0700 (PDT), <lerno@dragonascendant.com> wrote:
... discussing a single dispatch scenario ...
>> Does this have anything to do with hierarchy depth? Perhaps I am
>> misunderstanding something.
>>
> I think you do understand, but for some reason you're hung up on
> single dispatch. Discrimination trees efficiently solve *multiple*
> dispatch - single dispatch is an instance of worst case behavior.


Yes I suppose so. This is mostly due to me trying to figure out if
this could be used the language I am thinking of building where I am
using a Java-ish calling syntax for objects, i.e.
myObject.doSomething() but where methods support multiple rather than
single dispatch.


Assuming programming becomes anything like Java then there will indeed
be a bunch of single dispatch methods for querying the object, even if
we disregard accessors.


>> So if we have 10 direct subclasses to Object overriding toString, we
>> have 100 extra definitions of toString()
> No, you get 10 extra definitions.


Editing mistake :), I first wrote it with 100 everywhere, but then
edited it to 10 *almost* everywhere.


>> So wouldn't this be independent on hierarchy depth but instead
>> dependent on the number of different versions of the method?
> Yes it would. I said already that discrimination's worst case is
> linear in the number of overloads. I also said a table or hash is
> better for single dispatch.


Would it make sense to switch between table and tree dispatch
depending on dispatch type?


> That said, even in large frameworks, it's unusual for a method to be
> overridden by every subclass. Doing so, in fact, defeats the purpose
> of using super/sub classification in the first place. Generally a
> large fraction of classes will inherit a large fraction of their
> functionality. So, in general, a dispatch function is likely to need
> tests for only a fraction of the classes of the hierarchy.


But even without taking subclassing into account I can see function
name clashes that will increase search-depth, esp. really simple
function names like "add" "append"


So we get
add(LinkedList l, Object o)
add(Vector l, Object o)
add(Integer i1, Integer i2)
add(Float f1, Floar f2)


and so on, even though this has nothing to do with the actual
subclassing. It's true that these won't explode the same way a
"toString()" or a constructor would.


>>> 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?
>
> No more difficulty than any other dispatch method. If the class
> hierarchy or the set of overloads changes, a table or hash also has to
> be reconstructed and the code that uses it updated and recompiled.


So when we build is something like this:


void myGenericFunction(ObjectA a, ObjectB b) { ... }
void myGenericFunction(ObjectC c, ObjectB b) { ... }


We will create the stub


void myGenericFunction(Object o1, Object o2);


and the specific functions:


void myGenericFunctionAB(ObjectA a, ObjectB b) { ... }
void myGenericFunctionCB(ObjectC c, ObjectB b) { ... }


Using the generic function will call the stub instead of any generic
functions:


...


myGenericFunction(x, y); // calling the stub.


...


When linking the program, the stub is expanded to a real function:


void myGenericFunction(Object o1, Object o2)
{
if (o1 isa ObjectA && o2 isa Object B)
{
myGenericFunctionAB(o1, o2);
}
else if (o1 isa ObjectC && o2 isa Object C)
{
myGenericFunctionCB(o1, o2);
}
// throw some error
}




In some languages I'd have to generate an init method that adds all my
classes:


C c = addClass("Object", definition);
addMethod(c, "someMethod", function1);
addMethod(c, "someOtherMetho", function2);
... and so on ...


Is that what you're referring to?




But what about supporting dynamic loading of classes? It looks like a
table/hash would easily support it, but it would require a runtime
recompilation with a tree, unless that tree is constructed during
runtime - in which case it seems like a table would be many times
faster.


>>> 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?
> I think mostly for performance of their own object GUI frameworks.
> GUI widget frameworks tend to be large and have many overloaded
> methods. Under such circumstances the cumulative branch penalties of
> discrimination overwhelm the prefetch penalties of indirect function
> calls.


That makes sense. So is that a reason for not using generic functions?
- That GUI frameworks would be slow?




/Christoffer

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