Revisiting Multimethod Dispatch

I've been bitten two times by CLOS' multimethods, so badly that I became totally anti-MMD. The problem is that in CLOS, modifications to your class hierarchy can have unpredictable and unintuitive effects as to what method gets called.

The problem is neatly described in the Diesel specification (page 33), by Craig Chambers (now at Google, like his PhD student, Jeff Dean):

Multiple dispatching introduces a ... potential ambiguity even in the absence of multiple inheritance, since two methods with differing argument specializers could both be applicable but neither be uniformly more specific than the other. Consequently, the key distinguishing characteristic of method lookup in a language with multiple inheritance and/or multiple dispatching is how exactly this ambiguity problem is resolved.

Some languages resolve all ambiguities automatically. For example, Flavors [Moon 86] linearizes the class hierarchy, producing a total ordering on classes, derived from each class’ local left-to-right ordering of superclasses, that can be searched without ambiguity just as in the single inheritance case. However, linearization can produce unexpected method lookup results, especially if the program contains errors [Snyder 86]. CommonLoops [Bobrow et al. 86] and CLOS extend this linearization approach to multi-methods, totally ordering multi-methods by prioritizing argument position, with earlier argument positions completely dominating later argument positions. Again, this removes the possibility of run-time ambiguities, at the cost of automatically resolving ambiguities that may be the result of programming errors.

So, the problem with CLOS is that it linearizes classes, and then also makes the function arguments to the left more important than those to the right.

Diesel's solution, which I don't understand fully yet, instead warns programmers of such ambiguities, and requires them to be resolved manually. Which sounds good, and may be a reason to revisit MMD for me.

Multimethods do rock, after all.

Dylan and the Lisp family tree's central branch

Since the early eighties (beginning with Scheme and T), most Lisps began to settle around a common core.

(This also coincides with the point in time when static scoping was finally understood, once and for all, after a painful and embarrassing history.)

With the exception of Scheme, most Lisps don't have multi-shot continuations. They seriously complexify a language, as can be seen in weird implementation techniques like Cheney on the MTA.

It's also hard (or even impossible?) to make a good UNWIND-PROTECT in the face of multi-shot continuations. And UNWIND-PROTECT is surely one of the most important control flow operators.

So what is the common core I'm talking about? You can see it best in Dylan, I think.

First of all, a Lisp that follows this common core design can be efficiently implemented on real hardware. No need to do weird stuff like stack copying or Cheney on the MTA. In fact, Dylan has, with a bit of squinting, the same dynamic (control flow) semantics as C.

Second, the common core is simply nice to program in.

Some features of the common core:

• lexical exits
• unwind protection
• condition system with restarts
• global and lexical bindings
• first-class functions with optional, keyword, and rest parameters
• dynamic (thread-local) variables
• class-based object system
• generic functions
• powerful macros
• multiple return values
• semi-functional stateful programming style

This core can be seen in languages that I consider the central branch of the Lisp family tree:

• Common Lisp
• Dylan
• EuLisp
• ISLISP
• Goo
• PLOT

All of them are great languages, and worth detailed study.

In the future I hope to write about each of the features these languages share in more detail.