Dispatch on what? (Was: seeking ideas for short lecture on type classes)

[John Hörnkvist]

On Tuesday, February 4, 2003, at 03:46 PM, Jerzy Karczmarczuk wrote:

> I would say that - unless I am dead wrong, the OO languages such as 
> Smalltalk
> do not dispatch on dynamic types of a value. The receiver is known, so 
> its vir.
> f. table (belonging to the receiver's class) is known as well, the 
> dispatching
> is based on the *message identifiers* independently of subsidiary 
> arguments.

Yes, normally only the receiver and "message identifier" matters. In 
languages like Java, where the type of the other arguments is 
considered, this is handled statically.

For languages like Smalltalk, Objective-C, etc, all that you know at 
compile time is that the receiver is an object. You don't know what 
kind of object. Thus you cannot use a static dispatch style or vtables 
as you would in a language like C++. Even when the type is bounded, 
vtables are not enough because of "categories" and "method packages" 
that add methods to classes at run time.

Dispatch is done on the "target" (receiver) and "selector" (message 
identifier).

So if you consider an expression like:
	target_expr doSomething:arg_expr
then you should break that up into
	v = target_expr
	f = lookup_method(v, "doSomething:")
	f(v, "doSomething:", argexpr).

You dispatch on the dynamic type of the target (it's class) and on the 
dynamic state of its method tables. Note that you cannot assume that 
the receiver has a method that matches the selector!

Dynamic method lookup is a fairly complicated and expensive process, 
and it's a barrier to many optimizations. This can be mitigated by 
program analysis and specialization or similar techniques; dynamic 
dispatch and the surrounding problems are getting fairly well 
researched.

Languages with dynamic dispatch:
* Brad J Cox, Object oriented programming: an evolutionary approach, 
Addison-Wesley Longman Publishing Co., Inc., 1986
* Apple Computer, Inc., The Objective-C Programming Language, 2002.
   http://developer.apple.com/techpubs/macosx/Cocoa/ObjectiveC/index.html
* Pieter J. Schoenmaker, Supporting the Evolution of Software, Ph.D. 
thesis, Eindhoven University of Technology, July 1, 1999.

Some research:
* Zoran Budimlic, Ken Kennedy, and Jeff Piper, The cost of being 
object-oriented: A preliminary study, Scientific Computing 7(2), 1999
* David Detlefs and Ole Agesen, Inlining of Virtual Methods, Proc. of 
13th ECOOP
* A Diwan. Understanding and improving the performance of modern 
programming
     languages. Ph.D. thesis, University of Massachusetts at Amherst. 
1997
* Peeter Laud, Analysis for Object Inlining in Java; 
http://citeseer.nj.nec.com/laud01analysis.html
* Ole Agesen and Jens Palsberg and Michael I. Schwartzbach, Type 
Inference of {SELF}: Analysis of Objects with Dynamic and Multiple 
Inheritance, Lecture Notes in Computer Science, 
http://citeseer.nj.nec.com/agesen93type.html

> Only after that - perhaps - some "reversions", message propagation 
> depending on
> the arg(s) value(s), etc. may take place, but all this is irrelevant...

Well,  "self" and the "selector" is usually an argument to the method, 
but otherwise I agree.

Regards,
John Hornkvist