From: Jeff Dalton
Subject: Re: Generic function dispatch
Date:
Message-ID: <4828@skye.ed.ac.uk>
In article <···············@raven.cad.mcc.com> ··@raven.cad.mcc.com (Wayne Allen) writes:
>
>I am considering writing a CLOS-like object system for Scheme (in Scheme) and
>would be very interested to hear how generic dispatch could be implemented
>efficiently. I would love to hear about any of your ideas/experiences on
>this subject.
See the paper "Efficient Method Dispatch in PCL" by Gregor Kiczales
and Luis Rodriguez in the Proceedings of the 1990 ACM Conference on
Lisp and Functional Programming.
In general, you will want to
1. Be able to look methods up in hash tables, at least when there
are a fair number of them. If each class has a numeric id, it can
be used for hashing. You'll want the operation that obtains the
id to be a fast one. In Scheme, you'll have to write the hash table
code. In Common Lisp, you could use the built-in tables, but it
may still be better to write your own.
A typical approach is to store methods in some way that is easy to
precess but perhaps slow for lookup and then cache the methods (in a
hash table) for faster lookup when they are first called. This is
especially useful if you will also be computing combined methods,
because you wont' want to redo it each time or (perhaps) to precompute
combinations you may never need.
2. Keep down the cost due to the possibility of multi-methods. Most
methods will probably be specialized on only one or two parameters.
If a generic takes three arguments but only one is ever specialized,
for example, you don't want to do work times 3 if you could arrange to
to work times 1. One approach is to combine the numeric ids of all
the argument classes and then do one hash lookup. You may be able to
have a function that combines only as many as are needed (set up as in
(3) below). Another approach is to think of lookup as a tree search /
finite state machine / sparse array. You hash on the class of the first
argument. This gives you a table, if more arguments are specialized,
or a method. If a method, you're done. Else sontinue with the new
table and the next argument. You have to make sure leaf nodes appear
at the right depth when installing methods in the cache.
3. Perhaps be able to use special-purpose dispatchers for certain
special cases such as when there is only one method or all methods are
accessors for slot values. You can install an initial dispatcher when
the generic funcition is first created and have it figure out whether
a special-purpose dispatcher should replace it when it is first
called. You'll have to be careful to fix things up when new methods
are added (perhaps by going back to the inial dispatcher.)
-- jeff