jeff@aiai.ed.ac.uk (Jeff Dalton) (05/29/91)
In article <WA.91May8142821@raven.cad.mcc.com> wa@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