Click to edit Master text styles
Second level
Third level
Fourth level
Fifth level
I’d like to begin by expressing my gratitude the program committee for this opportunity to present this work here in Scotland, in my native United Kingdom. You might not immediately guess, given my spot-on Chicago accent, that I am indeed a native of the United Kingdom of Great Britain and Northern Ireland, the latter part thereof, to be specific. I left, together with my mother, another native of Northern Ireland, and my father, a native of Chicago, Illinois, when I was about three months old. I’ve lived in Illinois ever since. My fathers folk’s left the UK during the nineteenth century having heard (correctly) that potatoes were more abundant in the United States than in Ireland at the time. Ethnically, we’re all purebred Irish(men).
It may seem peculiar / somewhat indulgent / that I’m bothering to mention this, but, patience, my reason for doing so will become evident as my talk progresses.
(It has been 21 years since I’ve set foot on Great Britain, alas).
I’ve had the privilege of working with two native speakers of the language on this paper. The gentlemen whose visages grace the edges of this slide (and who would appear to have the same barber) are my co-authors, Ralph Johnson, and James Noble. Ralph, a native of the Panama Canal Zone, is now perhaps best  known for work on Design Patterns and Refactoring. His longstanding, staunch Smalltalk advocacy, and long-time interest in frameworks, reflection and metalevel architectures are all on display here.
James Noble, alas, is at home, about as far away as a person can get from here w/o getting wet right now. I wouldn’t be here without James’s contributions to this enterprise. His command of the language, and of the literature, have been simply indispensable.
Both send their regrets, and regards.
We’re allotted 30 minutes for these presentations, less with time for questions, meaning that we are allotted about the same amount time as an American television situation comedy, including commercials.
There was a time during my misspent youth when I’d take this time to try to methodically demonstrate to the twelve people in the room who already had the background to really appreciate it just how diabolically / ingeniously clever this work is. But given the nature, and the history of this work, I’m not going to do that now.
Instead, I’m going to divide the talk into five sections. First, we’ll examine what multimethods are, what they are not, and what they are good for. Then we’ll look at what they look like. Next, we’ll look at what it means to implement the bulk of one of the most interesting and refined metaobject architectures on top of the other one. We’ll then explore our multimethod implementations, and their relative performance. Finally, we’ll try to place this work in the context of some of the broader currents flowing through the research community, and try to gauge the enduring significance (if any) of all of this.
Academics are veritable novelty vampires. They crave that which is new, and research contributions must usual pander to these appetites. This work is rather unusual in that it is the culmination of line of research much of which was already complete seven or eight years ago. From the fact that we are here at all, one is tempted to conclude that this work must have aged well; that the program committee must have seen something of enduring value here.
I gather Scotsmen are fond of washing down Caledonian cuisine like haggis with something they call Single Malt Scotch, which, I’m told it tastes something like paint thinner poured over a tire fire. I gather it tastes even worse when it is fresh, and that it is somewhat more palatable after it has festered in an oak barrel for several years. We presented a sneak preview of some of this work, back when it was fresher, at ECOOP ’98. We hope you’ll find that time has made it more palatable.
Maybe this should be delivered and not displayed: Ponder…
Hmm. Or perhaps displayed and not delivered.
“One day an Englishman, a Scotsman, and an Irishman walked into a pub together. They each called for a dram of whiskey. Just as they were about to enjoy their libations, three flies landed in each of their drinks, and became stuck inside the glasses. The Englishman pushed his shot away in disgust. The Scotsman fished the fly out of his glass, and continued drinking it, as if nothing had happened. The Irishman, too, picked the fly out of his drink, held it out over the glass, and started yelling, ‘SPIT IT OUT, SPIT IT OUT YOU BASTARD!!!!’…”
Here’s something like what I think I used here:
So I’m going to begin by showing you some Java code I put together, based on a programming dilemma drawn from a compelling real-world situation, inspired by the perhaps apocryphal tale above, and thereby expose some of Java’s (perhaps somewhat subtle) limitations. I feel it is important in general to illustrate programming language design issues like the ones we’ll be discussing here. using realistic, real-world examples.
This example, while it may strike some as somewhat frivolous, will illustrate that opportunities to use multidispatch are not limited to mixed mode arithmetic or visitor pattern applications, but are all around us, potentially ubiquitous in fact, and pare resent anywhere where additional contextual information might be employed to refine a computational choice/decision…
We discovered, during the process of workshopping this paper at UIUC, that a half-generation of object-oriented programmers have grown up knowing only Java. Not only are they largely ignorant unaware of / oblivious to / of Smalltalk, let alone CLOS, but they are confused as well to the distinction between dynamic multidispatch and static overloading. So I’ve taken the liberty of concocting a simple, real-world example in order to illustrate this distinction, and thereby dispel some of this confusion.
Consider this Simple Scotsman. He’s a subclass of Carouser, and implements but a single operation, “imbibe”, which takes a Libation as an argument. In order for our model to exhibit the degree of real-world fidelity this problem demand, we’ll need find a way to ensure our Scotsman’s behavior is distinguished by the kind of Libation he imbibes.
Here’s our first attempt: When our Caledonian Carouser savors his dram of Scotch, he adds it / augments the contents of his stomach, nudges / cranks his blood alcohol level up a wee notch, and utters something incomprehensible that evidently nonetheless indicates profound satisfaction…
However, when Angus samples the Irish, he adds it to the contents of his stomach. It would seem it has no discernable effect on his BAL. He mutters something in visible disgust.
Consider, by contrast, this Hibernian.
His reaction to Scotch is to empty the contents of his stomach. In deference to the audience’s sensibilities, the detailed implementation for this method is not shown.
His soothed and satisfied response to his native spirits is of course like that of a babe to mother’s milk, save for the effect on his BAL.
Here’s a simple but naïve test of this code. We create an Irishman, “paddy”, and a Scotsman, “angus”, and press them into service imbibing each of the ancestral Libations at issue here.
Now, you can run this program (and rest assured, I did, one should never display code in a presentation what ain’t been run), and it produces the expected output.
There is, of course, a problem with the previous example. It may even strike some as quite subtle, the first time they think about it. Let’s try invoking our “imbibe” operation in a context where the type of the operands cannot be statically determined.
In fact, this code not only will not run, it won’t even compile. This is because while the first operand to imbibe, the receiver, the Carouser, is dispatched using runtime polymorphism, the second, the Libation, is resolved using static overloading, which is a horse of an entirely different color.
The implementations we’ve seen are really nothing but “name mangled” single-dispatch invocations under the hood.
The only thing that operator overloading has in common with real object-oriented programming is the double-Os…
We can get the previous example to compile by adding this method. This doesn’t enable us to realize our desired result though. It results instead in this useless method being called every time a Carouser imbibes a Libation.
Now, on could argue that this at least gave us a foothold. If we change the implementation of “imbibe” in Carouser to explicitly test and dispatch according to its second argument, using the a type case, we can achieve the desired effect.
But writing type cases sort of defeats the purpose…
Type cases are regarded as… <change slide…>
…what Kent Beck so vividly refers to as a “Code Smell”.
Kent Beck is one of the more remarkable figures the OO community has produced. I met him about twenty years ago when he managed to help get me an under-the-table copy of the Apple Smalltalk interpreter and image for the Apple Lisa. His seminal contributions are too numerous to mention… …but as intellectual paternity goes… …where do we begin?
His brainchildren are numerous: father of the patterns movement, Smalltalk evangelist, with Ward, one of the original pair of pair programmers, the Vince Lombardi of Extreme Programming… However, it is sad that real genius exhibits itself in the gaps, at the borders, between disciplines. It is for this reason that I think that Kent will be best remembered as the Founder of the field of Computational Scatology.
The notion of “code smell” is vivid, compelling, immediate… …ingenious. Beck veritably channels Marcel Proust.
…and, my friends, type cases are redolent of code rot…
So, the customary solution in singly dispatched object oriented languages to this problem is to employ an idiom known as “double dispatch(ing)”.
Multiple dispatch was first described in a classic OOPSLA ’86 paper by Smalltalk master-coder Dan Ingalls. Kurt Hebel and Ralph Johnson produced a nice, readable treatment of Double Dispatch about 12 years ago.
The code above illustrate how it works.
When an Irishman imbibes a Dram, he can’t be sure exactly what’s in it, but he knows for sure its been drunk by an Irishman.
He dutifully informs the Libation of this fact.
By virtue of this  second method invocation, true polymorphism is brought into play a second time.
And, sure and begora, the Irishman may not have been sure what he drank, but a Dram of IrishWhisky knows just what to do when its inside an Irishman.
Of course, using double dispatch requires that you implement these ricochet / pinball bumper routines. In general, the number which must be implemented is potentially, but seldom actually, quite large. We’ll see just how large later in this presentation.
Wouldn’t it be nice if we could specify that more than one of the arguments to a method can participate fully, at runtime, in the dispatch process?
Here’s how this might look in Java. Or might have looked in Java.
I gather that with Java 1.5, the language’s keepers came up with an altogether different role for angle bracketed type designators.
Someone evidently decided that what Java really needed, to relieve the onerous, evidently unbearable burden of writing an explicit downcast for Iterator assignments, was a full blown parametric polymorphic type system, that, when compiled down to byte code, mysteriously vanishes without a trace.
Java now has not one but two useless type systems as seamlessly integrated as, well, Great Britain and Northern Ireland / HP and Compaq / Bosnia-Herzegovina…
Someone should be tried for crimes against Computer Science for inflicting this odious abomination on the body politic. In the hands of the untutored, it promises to undermine / stand in the way  of everything about Java that had made it possible to engage in the faux-dynamic style of programming that helped to make many design patterns practical / popular…
If you want to add multidispatch, multimethods, generic functions what have you to a language, you need a way to specify, when declaring a method, for any parameter, not just the first or the receiver, that this method should execute only when the corresponding argument is of the sort specified for this method. In CLOS, these designators are called specializers.
One way to introduce specializers and multimethods into your language is to extend the syntax of the language somehow. This slide illustrates how three languages that allow multimethods, CLOS, Dylan and Cecil, did so.
(More could be said about generic functions, multimethods, specializers, etc. here, were time to have permitted this.)
This illustrates the syntax we used. Our class specializers are enclosed in angle brackets. The VisualWorks Smalltalk compiler had a dormant, postfix, bracketed type recognition facility already built into it. We simply had to turn it on, and override a few methods to wire in our multimethod facilities. Any “easter egg” in the compiler, I think they call it…
Asymmetric multimethods are preferentially attached or owned by their primary receiver classes. Symmetric multimethods are owned by none, or all, depending on how you want to look at it.
As with the faux-Java example show, our is arguably an “asymmetric” design. Our goal was to present a symmetric syntax, as CLOS had done, while maintaining (at least for the time being) asymmetric implementations.
(I’d like to have made it symmetric, but more compiler hacking would need to be done to carry this off.)
Presentation matters too…
Indeed, “tooling” takes more time that implementation, as the Eclipse folks can tell you as well.
Manipulating first class program objects directly is arguable a more modern way of programming than augment a quaint, 20th Century, 95 character ASCII representation of a program. Our implementation relies on syntactic solutions for specializers, but employed something of a hybrid approach for CLOS “qualifiers” and Method Combination designation. (By hybrid, I mean we assembled them programmatically, but hadn’t completed adding browser support, which brings me back to my point about “tooling”)….
Here’ s how Visitor usually looks in Smalltalk. Indeed, Visitor has become something of a double-dispatch poster child…
With Multidispatch available, the node side “pinball bumpers” routines all disappear, leaving only the “meat” that does the actual work…
Both the Wrappers to the Rescue paper and this one contain more detail descriptions of how this works, and I urge those of you who are interested to peruse these at your leisure…
I can’t begin to tell you how impressed I was, when I was first learning Smalltalk, to discover that programs were themselves built out of objects, and that you could change and extend these too, just like an other. It’s a big part of why I’m still here, and standing before you today.
(Give a brief rundown of what these do at runtime)…
There is really very little that you can’t get at in Smalltalk. We identified the things you can’t override back in ’89: sending a message, receiving a message, returning from a context, and reading and writing instance variables.
A short time after I learned Smalltalk, I came across another effort to build a language out of objects, the Common Lisp Object System.
Here are the CLOS like objects we built atop of Smalltalk to implement our multimethods.
(Explain these, one by one…)
In fact, we went well beyond simple multmethods. The collection of metabojects we built is a surprisingly complete / comprehensive implementation of the CLOS MOP. The major missing elements are multiple inheritance, and around methods.
Choreographer is a better name for MethodCombination that is Method Combination. A number of the names are rather droll. Is this in part to blame for this works relative, and undeserved, obscurity?
The two mops coexist fairly harmoniously, especially in contrast with Java’s dueling type systems.
There is a potential synergy between these two mops that I regret to say remains undemonstrated to this day. Between the two of ‘em, they’ve nearly got the space covered. But that’s a talk for another day.
Wave hands, frantically.
Same here.
One of the method combination objects generalizes the notion of double dispatch to an arbitary # of arguments. Using yet another Easter egg in the VW3.x compiler, we use the dotted method selector syntax show above to distinguish our generated pinball-cushion methods from user-written code.
Our N-way multidispatch facility is arguable / certainly a more generative approach than our MOP objects. Of course, you need a compiler around at runtime to build ‘em.
(Now) Any IDIOT can (plainly) see that this formula is (trivial, and) self-explanatory.
<pretend to change slide>
Okay now wait a minute.
I’ve always wondered what it feels like to be a “theory guy” and get away with glib remarks like that one.
Now let me be precise for one in my life…
The formula above gives the cardinality of the set of generated redispatching methods (bar D bar) given a generic function with a set of specialized parameters S1 through SN, the cardinality of each of which is indicated by bar S sub j bar.
I was encouraged to typeset this by our distinguished / illustrious program chair (Andrew Black), and frankly am quite delighted / thrilled with the result. However, the formulation at the bottom may strike some as more accessible though. It may seem to sum that the number of generated methods might, in general, be quite large. In practice, both the number of specialized, polymorphic parameters, and the number of alternatives (one might call them alleles) will be relatively modest. Note that you can minimize the number of generated methods by redispatching to them out of order, and bouncing off the parameters whose sets of specializers have the smallest cardinalities first.
I’m often / frequently asked, where did that factor of two in the last term on the bottom come from. That is present because the final designation methods can be made easier to read if you introduce on more dispatch to a presentation method in which the parameters are listed in the original order, thereby perhaps not exposing the “pinball bumper” methods to the user at all. This final ricochet can be elided for efficiency too.
I thought about this for a long time, and it does in fact unfailing describe the number of methods we generate. I’ve never seen this published anywhere else (though that doesn’t mean it hasn’t been published elsewere.) I’ll gladly pay the some of ONE GUINEA (cash-money) to the man or woman who can demonstrate that this formula not correct.
Here in lies a tale. Fortunately, I have it memorized.
We are raising a generation of object people who’ve know only Java. They no nothing of Smalltalk, the MOP, or multimethods. This is a tragedy. It is one that should have been avoided, and it is one that must be redressed.
Spelunking around the Smalltalk image is the finest apprenticeship in object-oriented design and programming a boy / a person / a body could possibly have / ask for. If they had World Heritage sites in cyberspace, the PARC images, the land of Ingalls, and Kay, and Goldbeg, and Kahler, and Liebs, and … <oversight> ought be one…
The CLOS MOP is one of the most remarkable object oriented designs I’ve ever seen. The Art of the MOP is a landmark that has nearly been lost.
The sheer potential of building languages out of objects is being forgotten, even as it reemerges that the next level. It cannot be swept under the rug. Eclipse is a pile of black box components built of reflective glue, but everywhere, designers of all kinds are rediscovering this power…
Oscar Wilde, is, of course, one Ireland's most gifted minters of colorful epigrams...
Wilde, when, visiting America for the first time, was asked upon arriving at the New York Customs House if he had anything to declare, and is said to have replied: I have nothing to declare except my genius .
-–Oscar Fingal O’Flahertie Wills Wilde (1854-1900) (Wow, when he was my age, he’d been dead for nearly five years.)
I’ve always thought this would be nifty / ideal / epigram for a talk on dynamic types. Hence, here goes nothing.
Of Type Systems and customs posts. Goal posts…
It seems rather bizarre that one still has to make the case that dynamic types are as “strong” as static types, but one does. I’d claim they are, in fact stronger.
Close-form, close world type theorists seem like soccer (er, this is Europe so “football”) coaches who seek to show that their game plan is so foolproof that it can be conclusively shown that no shot on goal is possible, conceivable, and hence no goalie is even necessary. In fact, they seek to assert that the game need not even be played, since victory is certain, and any rational adversary would capitulate, forfeit in the fact of such claims, of such an irrefutable demonstration.  With a dynamic type system, we just keep the goalie. Which approach makes YOU feel safer?
Earlier this year, I finally came across one of the greatest “classic” papers I’d never read: “End-to-End Arguments in System Design” by Saltzer, Reed, and Clark. The end-to-end argument was developed in the realm of internet protocol design. Succinctly put (and this format allows for no alternative) it argues that facilities, such as error checking, which one might be tempted to place at the lower levels of a system or network, might actually be redundant, and therefore useless as the lower levels, when they must be included in the upper levels of the system as well. We argue that this argument applies as well to programming language design as it does to networking. For instance, facilities that some languages provide for security, protection, synchronization, namespace management, or type checking must often be re-implemented in applications programs in a variety of different ways, many at odds with the manner in which these facilities were provided in these underlying languages. Such duplication raises the question of why these now redundant facilities need be present in these programming languages at all. This argument suggests a simpler, more dynamic approach to programming language design, based on an end-to-end analysis of the kinds of facilities users really use, may be better suited to the demands of our clustered, networked, threaded multi-core 21st world.
Real applications live, and breath, function, and yes fail, in a world well beyond our “formal” logistics train. Real computer science is an empirical, even behavior science, and not the feeble parody of seventeenth century closed-form mathematics some in CS make it out to be.
There are patterns of programming language design. Objects for lists of states, or zip codes, these are the types our clients demand. Will the legacy of the reflection movement be that we get out of their way, and finally give people the tools to build these as first-class runtime entities?
I want to tell you one last story about and Irishman, a Scotsman, and an Englishman, (well, Kiwi), who submitted an ECOOP / multimethod Paper.
We were right up against the page limit with this paper, and hence didn’t have any room for acknowledgements, so if you’ll indulge more for one more moment, I’d like to offer some now. (I mean, right up, one more line and we’d have had to shell out a hundred quid from our own pockets to get the last reference in. I’m one of … Dave Ungar’s biggest fans, but a hundred quid?).
This paper has almost literally been pulled out of the dumpster twice. Ralph and I are grateful to James Noble for climbing aboard and resurrecting this work. We are all grateful to Don Roberts, and, in particular, to John Brant, for providing us with their insidiously / scathingly ingenious Method Wrapper contraption, without which much of the rest of this work would not have been demonstrable.
I gather that the PC pretty much rescued this paper from their own dumpster as well. Despite that, more likely because of that fact, we received the most detailed, most constructive criticism I’ve ever gotten for a conference submission. Andrew Black wrote ten pages alone. Richard Gabriel, Stephan Ducasse, and Christophe Dony, and others who chose to remain anonymous provide a wealth of useful advice.
We’re grateful as well to the UIUC Software Architecture Group, who devoted a patterns conference-style writer’s workshop to this work, and were a font of sagacity as well, as is there custom.
In the event I’m not way over my time slot already, I’d be delighted to take any questions you might have…