Efficient Multimethods in a Single Dispatch Language

	Brian Foote
	Ralph Johnson
	Dept. of Computer Science
	University of Illinois at Urbana-Champaign
	201 N. Goodwin, Urbana, IL 61801, USA
	foote@cs.uiuc.edu johnson@cs.uiuc.edu
	James Noble
	School of Mathematical and Computing Sciences
	Victoria University of Wellington
	P.O. Box 600, Wellington, New Zealand
	kjx@mcs.vuw.ac.nz

Landmarks

	Motivation for Multimethods
	Syntax Matters
	A Tale of Two MOPs
	Two Implementations
	Enduring Significance

Let’s Get Serious

One day an Englishman, a Scotsman, and an Irishman walked into a pub together. They each called for a dram of whiskey. As they were about to enjoy their libations, three flies landed, one 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!!!!"

Motivation: A Simple Scotsman

	public class Scotsman extends Carouser
	{
	public void imbibe(ScotchWhiskey libation)
	{
	stomach.add(libation);
	bloodAlchoholLevel += 0.01;
	System.out.println("A wee dram...");
	}
	public void imbibe(IrishWhiskey libation)
	{
	stomach.add(libation);
	bloodAlchoholLevel += 0.00;
	System.out.println("Belfast Bog water...");
	}

A Simple Irishman

	public class Irishman extends Carouser
	{
	public void imbibe (ScotchWhiskey libation)
	{
	emptyStomach();
	System.out.
	println("Caledonian Swill...");
	}
	public void imbibe (IrishWhiskey libation)
	{
	stomach.add(libation);
	bloodAlchoholLevel += 0.01;
	System.out.println("Sure and begora...");
	}

A Simple, but Naïve Test

	public void testOverloads()
	{
	Irishman paddy = new Irishman();
	Scotsman angus = new Scotsman();
	System.out.
	println("--> testOverloads()...");
	paddy.imbibe(new IrishWhiskey());
	paddy.imbibe(new ScotchWhiskey());
	angus.imbibe(new IrishWhiskey());
	angus.imbibe(new ScotchWhiskey());
	}

A Simple, Unsuccessful Variation

	public void testBreakOverloads()
	{
	Irishman paddy = new Irishman();
	Scotsman angus = new Scotsman();
	Carouser carouser = paddy;
	System.out.println("--> testBreakOverloads()...");
	Dram dram = new IrishWhiskey();
	// You can't really do this properly...
	carouser.imbibe(dram);
	carouser = angus;
	carouser.imbibe(new IrishWhiskey());
	}

A Useless Overload

	public void imbibe(Dram libation)
	{
	System.out.
	println("Saints preserve us...");
	}

 A Type Case

	public void imbibe(Dram libation)
	{
	if (libation instanceof ScotchWhiskey)
	{
	emptyStomach();
	System.out.println("Caledonian Swill...");
	}
	else if (libation instanceof IrishWhiskey)
	{
	stomach.add(libation);
	bloodAlchoholLevel += 0.01;
	System.out.println("Sure and begora...");
	}
	else
	System.out.println("Mother of God...");
	}

The Olfactory Method

	Kent Beck: May be Best Remembered as the Man Who brought Scatology and Software Engineering together…
	If it stinks, change it!
	--Grandma Beck
	Code Smells are (not so) subtle indications a piece of code is in need of attention… …and is a likely candidate for refactoring…

Double Dispatch

	public class Irishman extends Carouser
	{
	public void imbibe(Dram libation)
	{
	libation.whenImbibedByIrishman(this);
	}

Dynamic Multidispatch?

	public class Scotsman extends Carouser
	{
	public void imbibe(<ScotchWhiskey> libation)
	{
	stomach.add(libation);
	bloodAlchoholLevel += 0.01;
	System.out.println("A wee dram...");
	}
	public void imbibe(<IrishWhiskey> libation)
	{
	stomach.add(libation);
	bloodAlchoholLevel += 0.00;
	System.out.println("Belfast Bog water...");
	}

Syntax Matters

	CLOS:
	(defmethod speak ((who animal))  (format t "I'm an animal: ~A~%" who))

Multimethods in Smalltalk

	ScreenDisplay>>draw: aGraphicalObject <Line>  ”draw a line on a screen”
	ScreenDisplay>>draw: aGraphicalObject <Arc>  ”draw an arc on a screen”

Browsing Multimethods

Visitor: Before

	ParseNode>>acceptVistor: aVisitor
	^self subclassResponsibility
	VariableNode>>acceptVistor: aVisitor
	^aVisitor visitWithVariableNode: self
	ConstantNode>>acceptVistor: aVisitor
	^aVisitor visitWithConstantNode: self
	OptimizingVisitor>>visitWithConstantNode: aNode
	^aNode value optimized
	OptimizingVisitor>>visitWithVariableNode: aNode
	^aNode lookupIn: self symbolTable

Visitor: After

	OptimizingVisitor>>visitWithNode: aNode <ConstantNode> ^self value optimized
	OptimizingVisitor>>   visitWithNode: aNode <VariableNode> ^aNode lookupIn: self symbolTable

A Language Built of Objects

	Object
	Behavior
	ClassDescription
	Class
	Metaclass
	Method
	MethodDictionary
	CompiledMethod
	ByteArray
	Context
	MethodContext
	BlockContext
	Message
	Process
	ProcessScheduler
	Semaphore
	SharedQueue
	Compiler
	SystemDictionary

Objects We Built

	MultiMethod
	Specializer
	ClassSpecializer
	EqualSpeciealizer
	GenericMessage
	MethodCombination
	DiscriminatingMethod
	Qualifiers (#Before #After, etc.)
	SubStandardMethodCombination
	SimpleMethodCombination
	BetaMethodCombination
	DispatchingMethodCombination

Slide 20

Slide 21

N-Way Multidispatch

Generated Redispatching Methods

	|D| = |S1|   + |S2| × |S1|   + |S3| × |S2| × |S1| …   + |Sn| × ... × |S2| × |S1| × 2

Performance

Lessons

	The Beauty of Smalltalk
	The Elegance of the CLOS MOP
	Building Languages of Objects
	The Power of Multimethods

I Have Nothing to Declare

	End to End Argument
	Impact of Dynamic Types and Languages
	The Arrogance of Closed Worlds
	Reflection as a School of Architecture

Acknowledgements

	Ralph Johnson
	James Noble
	John Brant
	Don Roberts
	Richard P. Gabriel
	Andrew Black
	Stéphane Ducasse
	Christophe Dony
	Anonymous ECOOP Reviewers
	UIUC Software Architecture Group