In my last post I wrote that Scheme lets you extend the base language in powerful ways. In this post I’ll give you a concrete example of such an extension: TinyClos.
TinyClos is a minimal implementation in Scheme of Common Lisp’s object system CLOS. CLOS is different in many ways from the object systems of C++ and Java that most of us are familiar with. Two big differences are multiple dispatch and open classes.
Before I explain what multiple dispatch is I must explain what dispatch refers to. When you make a function call in any language, the compiler or language runtime must figure out which function the call refers to. This is called binding the function to an implementation. In some languages binding always occurs at compile time, in others always at runtime, and in still others sometimes at runtime and sometimes at compile time.
Some languages, such as C++, allow you to declare many functions with the same name as long as they have different parameter lists. Not only the name of the function but also the number of arguments and their types are used when binding. This is called overloading in C++ terminology. However, overloading is a compile-time mechanism, and as such only looks at the static types of the arguments. If you want to bind the call based on the run-time type of an object you have to make the function virtual.
However, virtual functions in C++ (and most other mainstream languages) only take the run-time type of the first parameter into account–the “this” pointer. This is called single dispatch, because it dispatches the call based on a single argument. As you can probably guess by now, multiple dispatch is when the run-time types of multiple arguments is used for binding. In other words, multiple dispatch is like overloading but with run-time types.
This is immensely useful in some situations, because you can decide what to do based on combinations of types, without having to sprinkle your code with instance-of tests or resorting to ugly work-arounds like the visitor pattern. For instance, to express that anti-aircraft units can attack air units but not tanks or other units types, I just specify a method can-fire-at? for the type combination (AirDefenseUnit, AirUnit) and another one for (AirDefenseUnit, Unit). The method with the most specific matching argument list will be selected, at run time.
Here’s another simple example in the syntax Bjarne Stroustrup wants for C++ (not included in the coming update of the standard):
bool canShareHex(virtual Unit u1, virtual Unit u2) {
return true;
}
bool canShareHex(virtual GroundUnit u1, virtual GroundUnit u2) {
return false;
}
bool canShareHex(virtual AirUnit u1, virtual AirUnit u2) {
return false;
}
bool canShareHex(virtual SeaUnit u1, virtual SeaUnit u2) {
return false;
}
In other words, GroundUnits can share hex with all units but other GroundUnits. This example also demonstrates the other feature I wanted to write about: open class extensions. As you can see above, the methods were not part of a class but added separately. This too is very useful, because you can’t always anticipate what people may want to do with your classes, and sometimes it’s impractical to cram everything into one class.
For example, let’s say you are writing a compiler and define classes for different kinds of expressions, like addition and multiplication and so on, reflecting the tree structure of arithmetic expressions. Since the set of operations (optimizations) you may want to perform on the tree is open ended, you wouldn’t want to make them all methods of the tree classes. It would be much cleaner to define each optimization separately, while still dispatching on the actual run-time type(s) of the tree nodes.
With Scheme, I could just download TinyClos and start using these features. They can be compiled efficiently too, though I’m not sure they are in Chicken. Knowing that it can be solved should the need arise is reassuring, though.
Further reading:
- An efficient implementation of open multimethods for C++: www.research.att.com/~bs/multimethods.pdf
- Multijava, a version of Java extended with multiple dispatch: ftp://ftp.cs.iastate.edu/pub/techreports/TR04-01/TR.pdf
