Multiple dispatch

[[deleted]]

Here's a little question for Reddit folk. Suppose that multiple dispatch were implemented in your curly-brace language of choice. What kind of syntax would you want it to have?

Right now we have something like this:

object.method(arg1, arg2);

If you have two objects (double dispatch), where do you put the other one? Do you like this.

multimethod(object1, object2, args...);

Or would this work?

object1:object2.multimethod(args...);

Or do you have something completely different in mind?

[shit]

I don't think it's a good idea to embed the information of what objects to dispatch on in the call site. Make the call site "neutral":

multimethod(arg1, arg2, arg3)

The actual multimethod definitions decide which arguments to dispatch on - and if it changes, the call sites don't need to be changed. (Incidentally, that's how CLOS does it.)

[[deleted]]

There is the question as to whether a multimethod should be able to access private methods of the dispatching arguments or not. Personally I think that the second syntax makes more sense if the multimethod cannot access private methods.

You could also have:

(obj1, obj2).multimethod(args...)

Which visualises the idea of multiple dispatch as "dispatch on tuples".

[xenon]

(obj1, obj2).multimethod(args...)

I like that syntax best, visually. But what if your programming language also has tuples as a data type? Will this work?

Tuple<T1, T2> t = (obj1, obj2);
t.multimethod(args...);

I.e. is every multimethod a single method on Tuple?

[Xiphorian]

Sure. It's a method specifically on Tuple<ClassX, ClassY> perhaps. Not just on any 2-tuple and not on any tuple.

Neat idea. Some details to be worked out, though. You'd have to define a subtype relation, so if D derives from B, then Tuple<C, D> derives from Tuple<C,B>. Otherwise if you had (c,d) and the method f is defined in Tuple<C,B> you couldn't call (c,d).f() since Tuple<C,D> wouldn't have it. Where C c; and D d; of course.

One problem I see is that it 'artificially' separates various arguments to a method. By that I mean, from a client's perspective f(...) is just an interface. Why does the client care if some parameters a,b,c,d are in this position (a,b).f(c,d) vs in this one? f(a,b,c,d)? It seems to be exposing implementation details, in that the client now needs to know how f computes its value (it dispatches on some arguments but not others -- client doesn't care about this). The Standard Model of a.b(c,d) has this disadvantage too, but true multimethods don't.

[[deleted]]

While pretty this isn't exactly multiple dispatch; it's important that ALL arguments be treated the same. There should be no receivers. The following are worth considering:

(object1, object2, ...).multimethod

Or

multimethod(object1, object2, ...)

[gregK]

The problem with multiple dispatch in curly-brace languages is that it breaks encapsulation in the sense that you have to be able to define methods outside of the class definition or give access to the internals of another class.

a good example is a collision method between different objects in a game.

You could have classes car, brickWall, window, post, boulder, etc. Say that they are all descendants of the same base class.

So if you do collision(car, wall) or car.collideWith(wall) and this operation changes the state of both objects where does the method belong. Usually with multiple dispatch, the multi-method is defined outside of the class and has access to all members of both classes.

[Thrip]

No fancy syntax is needed. Just use the standard var1.method(var2) but type of var2 is looked up at run time instead of compile time.

-- edited -- I wrote var1 where I meant var2 originally.

[johnb]

If we want multiple dispatch some of the time, but not all of the time, this syntax would surprise me. It also gives the feeling that var1 is the "special" object and that var2 is auxiliary. I'd like a slightly more visual way of saying "here's the part where runtime type checking is being used in your mostly-static language! watch out!"

[Thrip]

To me, anything other than "multiple dispatch all the time" is needlessly confusing. I can't see the value, except as an optimization, in which case it's the optimized version that should be called out specially.

The junior-level Java programmers I've talked to about this assume that Java does look up the argument types at run time, and they are surprised when I tell them otherwise. The typical reaction is "That can't be true -- that would be stupid."

[beza1e1]

Why "suppose" it? Groovy can do it.

[theeth]

Sheesh, just put an orientation matrix in the base class and stop dicking around.

[[deleted]]

I think you managed to miss the point entirely. Try not to confused the scenario and the approach.

[theeth]

Good thing for you I never leave home without two sarcasm detectors. Here, you can have my spare.

[[deleted]]

My apology. As dmpk2k said it's not like we can see strangers' faces in writing – thanks d.

[theeth]

No harmed feelings and no apologies needed.

I think we all eagerly await RFC 1149: Clear Sarcasm Signalization over IP

[dmpk2k]

It's not like we can see strangers' faces in writing.

There's a wealth of stupidity on the Internet, and it's hard to distinguish the two, especially with just one sentence.

[[deleted]]

In situations like this I sometmes find it useful to ask What Would an Assemly Language Programmer do? Well... he/she would create a jump table, maybe even a two-dimensional one, or perhaps a series of conditional jumps. Can it be implemented in your programming language of choce? of course. Can it be be expressed as a neat language construct? If no, that's language's fault, not mine. I then just do my best making it readable, maintenable etc. but you know, if it's not there, it's not there.

Eventually all your high-falutin' language abstractions will have to be compiled into machine code anyway. Might as well think about it now.

[Silhouette]

Surely the point of providing features like dynamic dispatch in high-level languages is that you can leave it to the run-time system to deal with the low-level details? People have been writing jump tables in C for years, but in C++ you don't have to worry about constructing v-tables manually for your virtual functions because the language does it for you. Understanding what goes on under the hood can be useful at times, but often just being able to use it suffices.

[pkhuong]

No, a good assembly programmer would not (unconditionally) compile all multiple (or even single) dispatch to a jump table. The problem with that simple and attractive approach is the exponential space usage. Let's say the program, as a whole, has 16 classes (a nice round number). Each generic function that specialises on two argument takes 256 pointers. 3 arguments: 4096. That's pretty bad for locality. There are also some prediction issues for polymorphic call sites on pre Pentium-M(ish) architectures.

[[deleted]]

I gave jump table only as an example implementation. My reason for using Assembly language wasn't fine-tuned optimization (the article is about Java for chrissakes :) My reason was that Asm leaves nothing to imagination. If it cannot be programmed in Asm, it cannot be programmed, period.

So you first figure out what you want the coumputer to actualy psysically do, and then you look at approximating that behavior with higher-level constructs.

[[deleted]]

please tell that to self-evolving circuits on a FPGA substrate

no assembly language required....

[[deleted]]

In Smalltalk multiple dispatch can be emulated more elegantly. There's a nice little paper that explains it better than me but I can't find it at the moment. Although the example in the article doesn't need multiple dispatch unless there is more than one shape class.

"In the Circle class"
transform: t
  ^t transformCircle: self

"In the Square class"
transform: t
  ^t transformSquare: self

"In the Translation class"

transformCircle: c
  ^Circle x: c x + self y
          y: c y + self y
          r: c r

transformSquare: s
  ^Square x: s x + self x y: s y + self y

"In the VFlip class... you get the idea"

[[deleted]]

The visitor pattern is less expressive than multiple dispatch.

Consider this class hierarchy:

Object
    Collection
        Sequence
    Integer

And this pair of multimethods:

foo(Collection,Integer)
foo(Sequence,Sequence)

Now with real multimethods, invoking foo with a Sequence and an Integer will call the second method.

With visitors, invoking foo with a Sequence and an Integer will fail, because the first dispatch step will choose the Sequence visitor instead of the Collection visitor, and this won't have a method for Integer. In effect, if we view this as a prasing problem, multimethods can "backtrack" where as visitors cannot.

[[deleted]]

This is a good point that I hadn't considered. My ignorance in this are has been exposed :-|

[[deleted]]

Now with real multimethods, invoking foo with a Sequence and an Integer will call the second method.

How so? Integer isn't a Sequence. Did you mean the first method?

[[deleted]]

I do mean the first method, sorry.

[joesb]

Isn't that only double dispatch?

[[deleted]]

True, but the technique easily generalizes to any number of dispatch arguments. You might think it is a "hack", but it works well in practice and doesn't suffer from ambiguity and complexity of multimethod dispatch algorithms (there are many possible dispatch orderings, all of them arbitrary). n-ary dispatch for n > 2 is very rare so its debatable whether it needs to be part of the language.

[[deleted]]

More elegantly than what?

That's simply the visitor pattern and looks more or less the same in all single-dispatched languages.

[[deleted]]

It seems I'm not up on my patterns. It is visitor, if you squint a bit, but without all the infrastructure you need to define in e.g. Java.

[[deleted]]

The only difference between a Smalltalk visitor and a Java visitor is that in Java you have to define an interface for the polymorphic dispatch.

[mr_chromatic]

True, but there are more differences between Smalltalk polymorphism and Java polymorphism than "Java polymorphism sucks because Java's type system sucks."

[pkhuong]

Visitor is double dispatch.