Double Dispatch Example
Double Dispatch Example[---- A bunch of this should be removed! it is meant to be an example to the DoubleDispatch discussion in other single dispatch languages. The request was made by people who didn't understand the example there. Its not meant to describe how to handle the cartesian product "printer X shapes" problem specifically its meant to illustrate and explore "doubledispatch" as a concept.
[ quoted from the page DoubleDispatch]
We'll assume that the printers all have a common base class (APrinter), and the shapes also have a common base class (AShape).
In the simplest case, as you say, you extend the printer interface with a separate function per shape that it can render. Now, given some code where you have a printer object, and a shape object. But the code only knows the printer object to be of type APrinter (assuming a statically typed language), and the shape object to be of type AShape. How do you, or the compiler, know which printer method to call? That's the crux of the problem. You need to select the method based on the run-time types, not the static types, of two objects.
DoubleDispatch is a pattern for solving this problem in a typical OO language that can dispatch only on one object's type. It requires a bit of extra work by the programmer.
-- DanMuller
]
On DoubleDispatch, someone said: Would someone be willing to create a more verbose example? (hopefully in Java or C++)
Here it is:
Problem:
Assume we are writing a print library. We want the client code of our library to be able to do something like this:
class Client {
/** Prints all figures on each of the printers. */
void printAllEverywhere( Figure[] figures, Printer[] printers ) {
for ( int i = 0; i < figures.length; i++ ) {
Figure figure = figures[ i ];
for ( int j = 0; j < printers.length; j++ ) {
Printer printer = printers[ j ];
figure.printOn( printer );
// must work for any printer or figure !
}
}
}
}
Of course, when we add new printers or figures to our library, we want client code such as the above to immediately work with these new printers and figures, without a change in their code or even a recompile. How can we implement our library to allow this?
Another way to state this is that we need a CartesianProduct of drivers or methods of printer kinds and shape kinds.
Solution:
First, we define two interfaces for our figures and printers:
interface Figure {
void printOn( Printer printer );
}
interface Printer {
void printCircle( Circle circle );
void printRectangle( Rectangle rectangle );
}
Next, we write our two printers:
class InkjetPrinter implements Printer {
public void printCircle( Circle circle ) {
// ... rasterizing logic for inkjet printing of circles here ...
System.out.println( "Inkjet printer prints a cirlce." );
}
public void printRectangle( Rectangle rectangle ) {
// ... rasterizing logic for inkjet printing of rectangles here ...
System.out.println( "Inkjet printer prints a rectangle." );
}
}
class PostscriptPrinter implements Printer {
public void printCircle( Circle circle ) {
// ... postscript preprocessing logic for circles here ...
System.out.println( "PostScript printer prints a cirlce." );
}
public void printRectangle( Rectangle rectangle ) {
// ... postscript preprocessing logic for rectangles here ...
System.out.println( "PostScript printer prints a rectangle." );
}
}
Now, all we have to make sure is that calling the figure.printOn( printer ) method results in the correct printXyz implementation being executed, such as postscriptPrinter.printRectangle( rectangle ).
This can be achieved through a simple indirection in the implementation of printOn in the individual figure classes:
class Circle implements Figure {
public void printOn( Printer printer ) {
printer.printCircle( this ); // <-- the "trick" !
}
}
class Rectangle implements Figure {
public void printOn( Printer printer ) {
printer.printRectangle( this );
}
}
That's it!
To test the above code, just add the following class:
public class Main {
public static void main( String[] args ) {
Figure [] figures = new Figure [] {
new Circle(), new Rectangle() };
Printer [] printers = new Printer [] {
new PostscriptPrinter(), new InkjetPrinter() };
new Client().printAllEverywhere( figures, printers );
}
}
Explanation:
What happens when figure.printOn( printer ) is called at runtime? This depends on the types of the objects referenced by the figure and printer variables at that time. Let's assume that at the moment, figure points to an instance of class Circle, and printer to an InkjetPrinter. So, the implementation of printOn( printer ) being called will be that of the circle instance, defined in the Circle class (first dispatch). This method just contains one line: printer.printCircle( this ), which delegates the work to the printer object. As this object is of the class InkjetPrinter, the printCircle( circle ) method of the InkjetPrinter class will be executed (second dispatch), which is just what we wanted.
The same code recast in CeePlusPlus (jives with both GnuCpp 3.0.3 and Microsoft VisualCeePlusPlus 6.0):
#include <iostream>
using std::cout;
using std::endl;
class Printer;
class Figure {
public:
virtual void printOn(Printer* printer) = 0;
};
class Circle;
class Rectangle;
class Printer {
public:
virtual void printCircle(const Circle* circle) = 0;
virtual void printRectangle(const Rectangle* rectangle) = 0;
};
class Client {
public:
// Prints all figures on each of the printers.
void printAllEverywhere(Figure **figures, Printer **printers) {
Figure **figure;
Printer **printer;
for (figure = figures; *figure; figure++) {
for (printer = printers; *printer; printer++) {
Figure *fig = *figure;
fig->printOn(*printer); // must work for any printer or figure !
}
}
}
};
class InkjetPrinter : public Printer {
public:
void printCircle(const Circle *circle) {
// ... rasterizing logic for inkjet printing of circles here ...
cout << "Inkjet printer prints a circle." << endl;
}
void printRectangle(const Rectangle *rectangle) {
// ... rasterizing logic for inkjet printing of rectangles here ...
cout << "Inkjet printer prints a rectangle." << endl;
}
};
class PostscriptPrinter : public Printer {
public:
void printCircle(const Circle *circle) {
// ... postscript preprocessing logic for circles here ...
cout << "PostScript printer prints a cirlce." << endl;
}
void printRectangle(const Rectangle *rectangle) {
// ... postscript preprocessing logic for rectangles here ...
cout << "PostScript printer prints a rectangle." << endl;
}
};
class Circle : public Figure {
public:
void printOn(Printer* printer) {
printer->printCircle(this); // <-- the "trick" !
}
};
class Rectangle : public Figure {
public:
void printOn(Printer* printer) {
printer->printRectangle(this);
}
};
int
main()
{
Figure *figures[] = { new Circle,new Rectangle,0 };
Printer *printers[] = { new PostscriptPrinter, new InkjetPrinter, 0 };
Client c;
c.printAllEverywhere(figures, printers);
return 0;
}
-- GregBacon
A possible RelationalWeenie solution would look something like this:
Table: printerShapes
--------------------------
printerRef(foreign key to Printers table)
shapeRef(shape name or ID)
implementation (reference or container for algorithm)
The code might resemble:
rs = query("select * from printerShapes where [criteria])
while (getNext(rs)) { // for each row in result
execute(rs['implementation']) // or 'eval'
}
Some might argue that this violates the criteria of non-intrusive addition of new printers or shapes because we have to append to an existing table. However, every solution has to "append" to something. No paradigm lets stuff just float in dark space unlinked or unhitched to everything. Otherwise, we could never reference it. Adding to "object space" is appending to something also. There's often a LaynesLaw risk in using physical vocabulary to describe virtual things.
Using the File System
Another approach that may at least appear less connected would be to name the implementation libraries or scripts with a combination of printer name and shape name:
function runShape(printerName, shapeName) {
filename = stdPath . printerName . '_' . shapeName . '.driver'
status = executeFile(filename)
if (not status.good) {// check status array
errorReport(status.errDescript)
}
}
This is basically using the file-system like a two-key hash array. Running them as a group is tougher than in the table example, I would note.
Files may resemble:
Lexmark1000_circle.driver Lexmark1000_square.driver HP4270jet_circle.driver HP4270jet_square.driver ...etc...The advantage of this approach is that we can add new drivers without having to open or alter any existing driver files. However, the drawback is that we cannot ship new printers or new shapes in a single file for better packaging. The optimum solution depends on the ChangePattern(s) that one expects or observes. If mostly new printers are added and not new shapes, then grouping them by printer (a single printer per file) would be the most convenient. However, if new shapes were added more often than new printers, then making shape files (with all printers in them) would be the way to go. If the pattern is pretty even or chaotic, then either approach, or the finer granularity approach shown above may be the way to go.
However, an installation utility may be more appropriate than allowing the user to insert and/or replace files by themselves. If we go that route, then the database approach can also be used since the "storage mechanism" is not something the user directly faces anyhow. They just receive a file of changes to load in and let a Wizard-like thing guide them through loading. Some may argue that a database is an AbstractionInversion (overkill), but if flexibility with regard to change-pattern is what you really want, then it may be the best approach. (I used to use NimbleDatabase technology extensively, so don't view DB's as inherently bulky.) But if there are only a few hundred rather than thousands, then files are sufficient.
{Code indentation damaged due to TabMunging}
--top
Below is an example in PerlLanguage that uses the Class::Multimethods module by DamianConway. For details, see the following resources:
#! /usr/local/bin/perl
use 5.005;
use warnings;
use strict;
package Figure;
# dummy placeholder
$Figure::VERSION = '1.0';
package Printer;
use Carp;
use Class::Multimethods;
# catchall
multimethod
printFigure => ('Printer', 'Figure') =>
sub {
my $p = ref $_[0];
my $f = ref $_[1];
confess "$0: printFigure: unknown combination: $p, $f";
};
package InkjetPrinter;
use base 'Printer';
use Class::Multimethods;
{ # register in Printer class
package Printer;
multimethod
printFigure => ('InkjetPrinter', 'Circle') =>
sub {
InkjetPrinter::printCircle($_[0], $_[1]);
};
multimethod
printFigure => ('InkjetPrinter', 'Rectangle') =>
sub {
InkjetPrinter::printRectangle($_[0], $_[1]);
};
}
sub new {
my $class = shift;
bless [] => $class;
}
sub printCircle {
# ... rasterizing logic for inkjet printing of circles here ...
print "Inkjet printer prints a circle.\n";
}
sub printRectangle {
# ... rasterizing logic for inkjet printing of rectangles here ...
print "Inkjet printer prints a rectangle.\n";
}
package PostscriptPrinter;
use base 'Printer';
use Class::Multimethods;
{ # register in Printer class
package Printer;
multimethod
printFigure => ('PostscriptPrinter', 'Circle') =>
sub {
PostscriptPrinter::printCircle($_[0], $_[1]);
};
multimethod
printFigure => ('PostscriptPrinter', 'Rectangle') =>
sub {
PostscriptPrinter::printRectangle($_[0], $_[1]);
};
}
sub new {
my $class = shift;
bless [] => $class;
}
sub printCircle {
# ... postscript preprocessing logic for circles here ...
print "PostScript printer prints a cirlce.\n";
}
sub printRectangle {
# ... postscript preprocessing logic for rectangles here ...
print "PostScript printer prints a rectangle.\n";
}
package Circle;
use base 'Figure';
sub new {
my $class = shift;
bless [] => $class;
}
package Rectangle;
use base 'Figure';
sub new {
my $class = shift;
bless [] => $class;
}
## main
package main;
my @figures = (Circle->new,Rectangle->new);
my @printers = (PostscriptPrinter->new, InkjetPrinter->new);
foreach my $f (@figures) {
foreach my $p (@printers) {
# must work for any Printer or Figure!
$p->printFigure($f);
}
}
I'm surprised nobody's offered a solution in a language that supports MultiMethods, as this is exactly what they're for. Here's one in DylanLanguage (the CommonLisp solution would be similar, just with more parentheses):
define class <figure> (<object>) end;
define class <printer> (<object>) end;
define class <circle> (<figure>) end;
define class <rectangle> (<figure>) end;
define class <inkjet-printer> (<printer>) end;
define class <postscript-printer> (<printer>) end;
define generic print (printer :: <printer>, shape :: <figure>);
define method print (printer :: <inkjet-printer>, shape :: <circle>)
format-out("Inkjet printer prints a circle.");
end;
define method print (printer :: <postscript-printer>, shape :: <circle>)
format-out("Postscript printer prints a circle.");
end;
define method print (printer :: <inkjet-printer>, shape :: <rectangle>)
format-out("Inkjet printer prints a rectangle.");
end;
define method print (printer :: <postscript-printer>, shape :: <rectangle>)
format-out("Postscript printer prints a rectangle.");
end;
// Client code...
define method print-all-everywhere (
client :: <client>,
printers :: limited(<collection>, of: <printer>
shapes :: limited(<collection>, of: <figure>)
do(curry(do, print, printers), shapes);
end;
All the functionality of the original, and no code bloat. The language handles all the dispatching. The standard library handles the iteration (do is a function that takes a function and a collection, and applies the function to every element in the collection). If you want to define a new shape or printer, you just subclass <figure> or <printer> and then define the appropriate methods on print. If there's common functionality, you can define an intermediate subclass and factor out the appropriate functionality into methods on that class.
-- JonathanTang
The same solution in the NiceLanguage. It might be more readable to some, since the syntax is close to Java.
abstract class Figure {}
abstract class Printer {}
class Circle extends Figure {}
class Rectangle extends Figure {}
class InkjetPrinter extends Printer {}
class PostscriptPrinter extends Printer {}
void print(Printer printer, Figure shape);
print(InkjetPrinter printer, Circle shape) {
println("Inkjet printer prints a circle.");
}
print(PostscriptPrinter printer, Circle shape) {
println("Postscript printer prints a circle.");
}
print(InkjetPrinter printer, Rectangle shape) {
println("Inkjet printer prints a rectangle.");
}
print(PostscriptPrinter printer, Rectangle shape) {
println("Postscript printer prints a rectangle.");
}
// Client code...
void printAllEverywhere
(Collection<Printer> printers,
Collection<Figure> shapes)
{
printers.foreach(Printer p => shapes.foreach(Figure s => print(p,s)));
}
void main(String[] args)
{
printAllEverywhere
([ new PostscriptPrinter(), new InkjetPrinter() ],
[ new Circle(), new Rectangle() ]);
}
-- DanielBonniot
I don't like the Java and C++ examples at all. If I add a new shape I have to modify every existing printer. I'd rather abstract the way shapes draw themselves to work with any printer (or the way printers draw shapes), then leave all shape knowledge in the shape class hierarchy. Then I can add new printers without touching shapes and new shapes without touching printers. -- EricHodges
That is, in general, very difficult to do. What would be the lowest-common denominator used by printers? Cubic bezier curves? Then you can't draw true circles. Pixels? Then you can't use your framework to output to a plotter. Etc. etc. At some point, you have to have a LinguaFranca that specifies the primitive Printer operations, and those operations will be reified as Figure classes. -- AnonymousDonor
It isn't too hard to do or it wouldn't be done. See PostScript and PCL. -- EricHodges
But those might not recognize the printer's internal primitives. There are different ways to specify ellipses, for example: by two center points, by bounding rectangle, and by circle plus a "flatness" factor and angle. True, there might be groupings such that some printers will fall into one interface group and another will fall into another group. Of course, this is mostly a hypothetical thought experiment anyhow. But in reality there might be some efficiency trade-off between using a standard meta-layer and native primitives. The standard meta-layer may not match up one-to-one with a given printer's primitives. For example, some printers may have built-in dashed line patterns that don't match what the meta-language has. If you want to match, you have to use a bunch of small lines and dots to emulate the dashing of the other brand. -- top
PostScript and PCL don't have to recognize the printer's internal primitives. Each printer recognizes PostScript and/or PCL. -- bottom
Then are PostScript and PCL examples of BridgePattern at work? -- GregBacon
You're not actually saying you've never heard of a printer that works with PostScript, are you? -- francis
I am surprised that nobody mentioned how many real world solves this printer-shape problem, perhaps I am miss the point here? In C/C++ in Windows and OS/2 (likely in other windowing systems too) and in Java, you introduce a third entity, some kind of drawing space (Presentation Space in OS/2, Graphics in Java), that can draw some arbitrary shape "primitives" such as lines, circles, text, etc. All graphics drawing applications can draw to any given drawing space. Any new printer simply implements a method to provide the drawing space. -- OliverChung
This problem is more of a thought experiment than an exercise in production printing drivers. -- AnonymousDonor
The thought experiment reveals a weakness of the double dispatch strategy. It requires a two dimensional matrix of methods. Adding an element to one dimension forces the creation of a method for each element along the other dimension. Compare the cost of change curve with a BridgePattern. -- EricHodges
That makes for an interesting challenge: be able to add methods (or whatever they are called in other paradigms) where the number of dimensions is arbitrary without changing existing code or replacing an existing data structure. My first inclination would be to use the "file name lookup" approach above, but use names like "d1=foo,d2=bar,d3=glob", etc. (However, we would have to use something besides equal signs and commas, for they don't make safe filename characters.) "d1=foo,d2=bar" would not conflict with "d1=foo,d2=bar,d3=glob" because they are different strings. However, adding a file is "changing an existing data structure" if you view the file system as a data structure, which it is. No way out? -- top
No, the challenge isn't to add methods without changing code. Methods are code. The challenge is to add elements to one dimension of the matrix without adding a method for each element in the other dimension. If a new printer shows up you don't have to write a method to draw every shape on that printer. Or vice versa, if a new shape shows up you don't have to write a method to draw that shape on every printer. See BridgePattern for a common solution to this challenge. See the Java virtual machine for a widespread example of its use. -- bottom
I don't think this is possible, unless there's some behavior common to the algorithms that you can factor out. Your BridgePattern solution relies on this toy example having these common data structures or behavior; all shapes can be rendered by PostScript as a "current path" plus the stroke, fill, or clipping operators, and then all printers can convert PostScript drawing primitives into colored regions on the page. But imagine that the problem was defined like this:
(inkjet, circle) => print "Foo" (inkjet, rectangle) => print "Bar" (postscript, circle) => print "Goo" (postscript, rectangle) => print "Gaa"This time, there's no common behavior that you can abstract to use as your "bridge". There're 4 different behaviors needed, to go with the 4 combinations of types. And if you had to add a new shape:
(inkjet, triangle) => print "Glob" (postscript, triangle) => print "Blurp"It's pretty obvious that you would need to define new methods for each combination of types, because the problem now explicitly says that each required behavior is different, with no possibilities for factoring.
Granted, in every real-world system I've worked with, there have been opportunities for factoring and I've been able to use the BridgePattern, but this toy example was intended to illustrate a concept. ;)
My solution to the general case would be to use an n-dimensional array filled with function objects (Runnables in Java). Indexing the array's quite tricky, at least with C/C++/Java family languages. I guess the simplest solution is to assign each class a sequential ordering within the hierarchy, and then add each Runnable to the dispatch table manually. Yes, this means keeping track of the class indexes manually. There's some superclass constructor magic you can pull to avoid this, but the best algorithm I can think of for this requires a hashtable lookup for every object instantiation (could you use static{} blocks to get around this?), and so may be performance-unacceptable.
This is all assuming I'm not allowed to use a language with MultiMethods, of course. Makes you appreciate the trouble implementors of those languages go through for us.
Incidentally, this approach is very similar to the optimum (so far) algorithm for GenericFunction dispatch. That also uses an n-dimensional array, but it's compressed to reflect the inheritance graph (if a class doesn't define a method, it calls the method from its nearest superclass). The language also handles computation of the class indexes automatically, as well as linearizing the class hierarchy (both DylanLanguage and CommonLisp support multiple inheritance). See http://citeseer.nj.nec.com/dujardin96fast.html and http://www.cs.dartmouth.edu/reports/abstracts/TR2001-404/
-- JonathanTang
The fact that it's always been possible for you and me to find a bridge indicates something significant. We're asking different printers to produce the same output. The abstraction of that output (PostScript in this case) provides the bridge. Double dispatch is used when two abstractions intersect. Neither of us have ever wanted entirely different behavior for each intersection. We want similar realizations of the same abstraction in different contexts. -- EricHodges
Anyone else remember DisplayPostscript? Sun spent a bunch of time and money proving that having a nice abstraction layer can turn your successful product into unusable MIP-sucking garbage, and that sometimes you need to go back and write MxN different pieces of code to do high-speed rendering. -- AustinHastings?
DoubleDispatch provides two levels of dispatch in a language context that only supports one, such as JavaLanguage, SmalltalkLanguage, or CeePlusPlus. One level of dispatch is always "easy", in that it can be extended without changing existing code. The second is always "harder", in that the new elements have to added to the existing first-level dispatch code.
In the code example above, adding new kinds of printers is easy - the new printer must provide implementations of printCircle and printRectangle. Adding new shapes is hard - a new printNewShape method has to be added to each existing printer.
This means that guessing which set of classes will change more frequently is an important design decision when using DoubleDispatch. In the VisitorPattern, the implication is that adding Visitors is easy. Adding Visitees is hard.
It's a bit like choosing row-major or column-major order in a 2-D array. It's simply a choice, we have to do the best we can.
The discussion about beziers, postscript and so on, is interesting but distracts from the DoubleDispatchExample. Similarly, if a language has method overloading or multimethods, then DoubleDispatch is still needed, it's just done by the language for you.
If I understand what we mean by "method overloading", then Java at least does take inheritance into account. I think "method overloading" means that several methods with the same name but different argument types are distinguished by the compiler. In Java, a method in a subclass that has the same signature as a method in its superclass is correctly inherited/overridden. I don't remember what CeePlusPlus does in this case.
Java does not take inheritance into account when passing parameters at runtime, only at compile time, this isn't sufficient and is not at all like multimethods. Multimethods take the actual runtime type of the parameter into account when selecting the method to run. This is called MultipleDispatch, and is better than DoubleDispatch.
In practice, what appears to be the way it's done more often now is that an intermediate "meta" format or document is created. Each printer driver then reads this meta format and translates it as needed for its own needs. It is a declarative (data driven) solution rather than a behavioral one. Perhaps this was not the way it was done in the early days because it requires a fairly large work buffer on disk or RAM for the meta document. That space was too expensive on early machines. Thus, the above printer driver example is mostly an academic exercise. (I'm not sure if Postscript counts as a meta-format for printers.) -- top
So we should have stuck with Shapes, one of the OverUsedOopExamples, and done intersection as that one doesn't have an IR that allows Bridging?
Moved game example to DeltaIsolation. See also: InternationalUiExample, ExtrapolatingDeviceDrivers
CategoryComparisons, CategoryExample, CategoryConditionalsAndDispatching
EditText of this page
(last edited March 13, 2011)
or FindPage with title or text search