From: Yutaka Sumi
Subject: Emulate multiple dispatch in a single dispatch language
Date:
Message-ID: <DBHLpw.90A@phe.hitachi-sk.co.jp>
I would like to present the results of my study on
emulation of multiple dispatch in a single dispatch language
as a paper. But I don't know whether it can be a paper level
study or not, and where to send, and what format is requred.
I also like to know related sutudies, papers, and any other
documents.
If you know anything about this, please be kind enough to
let me know it.
Any information would be appreciated.
Thanks in advance.
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Emulations of Multiple Dispatch
in Single Dispatch Object Oriented Languages
in the form of a Design Pattern or a Macro
AND
The meanings of the Existence and Absence
of a Multiple Dispatch scheme in a language
by Yutaka Sumi from Hitachi Soft
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
[ABSTRACT]
This document discusses about emulations of multiple
dispatch in single dispatch languages and implementations
of multiple dispatch schemes in the form of a design pattern,
a macro, or translator for single dispatch languages.
The technique can be used to implement very "light"
multiple dispatch languages (possibility of examples
includes something like a multiple dispatch Perl,
or , a multiple dispatch Emacs Lisp) very easily.
The analysis of various forms of emulations of multiple
dispatch in single dispatch languages depicts the meanings
of the existence and absence of a multiple dispatch scheme
in a language. The meanings varies depending on whether
it's a C++ like single dispatch language with compile-time
type checking or a Smalltalk like interpreter language
in which variables are not required to have their types.
[Introduction]
Let us suppose your company developped and selling a word
processing software. The software has a primitive macro
language to customize it. As time goes by, the customers
create a lot of programs written in the macro language.
Then customers start to complain of the macro language
being too simple to develop complicated softwares.
(The situation is analogous to the history of Emacs and
Emacs Lisp.)
Now you have to improve the macro language drastically
to satisfy the customers' demand.
You decide to make it an Object Oriented Language becase
the design concept of the software is Object Oriented,
and many of the customers are familiar with Object Oriented
programming. (Actually the macro language of Interleaf
(which is a DTP software) is Object Oriented.)
Then you have to decide whether it adopt a single dispatch
scheme or a multiple dispatch scheme.
You may think as follows:
it's easy to implement a single dispatch scheme
and difficult to implement a multiple dispatch scheme.
The multiple dispatch scheme augments
the program size of the macro language processor.
The multiple dispatch requires more memory
more time, in a word, its heavy.
Besides, we can develop softwares without using multiple
dispatch. It might be convenient, but it's not essential.
The necessity of multiple dispatch is quite doubtful.
........
Oh, wait a minute, please.
You have a lot to contemplate before making the final
decision. Firstly, here's a way to implement a "very light"
multiple dispatch scheme "very easily" even though the
applicability is restricted.
Secondly, the lack of a double dispatch scheme is
sometimes very costly.
Thirdly, horribly messy programs would be produced
if you deal with triple or quadruple dispatch structure
in a single dispatch language.
Let's begin with comparison between a single dispatch
language and a multiple dispatch language.
Single dispatch has troubles especially when
a generic function works across two or more hierarchies of
objects and when what should be done by the function call is
decided by the cartesian product of the types of the parameters
rather than only by the first parameter (the object which
receives the message).
For example, suppose here are two inheritance hierarchies
of classes.
==== fig.1 =============================================
G1---G21---G31
Composite-G
G22---G32
G33
V1---V21
V22
V23
Composite-V
=========================================================
G1 is the direct super class of G21,G22 and Composite-G.
G21 is the direct super class of G31.
G22 is the direct super class of G32 and G33.
V1 is the direct super class of V21,V22,V23 and Composite-V.
Instances of the G hierarchy are graphic objects which
are composed into graphic structures.
(A group of graphic objects is a picture. A picture is also
a graphic objects.)
Instances of V hierarchy are visitors which traverses
across a hierarchy of the graphic composition
analysing or modifying the object composition.
Visitors are also composed into a group. A group
of visitor is also a visitor.
Implementation of the visit operation is easy and
natural in a multiple dispatching language.
The coding image would be:
==== fig.2 ==================================================
DefineMethod visit
((visitor IsOfType V1)(graphic IsOfType G1))
{ visitor does default actions to graphic ......}
DefineMethod visit
((visitor IsOfType Composite-V)(graphic IsOfType G1))
{ DO-LOOP child-visitor all-children-of (visitor)
visit (child-visitor, graphic); }
DefineMethod visit
((visitor IsOfType V1)(graphic IsOfType Composite-G))
{ DO-LOOP child-graphic all-children-of (graphic)
visit (visitor, child-graphic);}
DefineMethod visit
((visitor IsOfType V22)(graphic IsOfType G31))
{ visitor modifys graphic......}
:
:
DefineMethod visit
((visitor IsOfType V23)(graphic IsOfType G22))
{ visitor analyses graphic......}
============================================================
******** Note that the following definition:
*==== fig. 3 =============================================
*DefineMethod visit
* ((visitor IsOfType V22)(graphic IsOfType G31))
*{ visitor modifys graphic......}
*========================================================
* is deferent from the C++'s definition:
*=======================================================
* visit (V22 visitor , G31 graphic)
*{ visitor modifys graphic ......}
*=======================================================
*In C++, V22 and G31 are used for type checking by
* the compiler while in the multiple dispatch language
* V22 and G31 are used to decide which method is invoked
* when a function is called *****************
On the other hand, in a single dispatch language, the
corresponding operation would be inefficient, ugly,
and difficult to maintain. The implementation would
include code like:
==== fig. 4 ============================================
DefineMethod visit
((visitor IsOfType V22) graphic)
{ if type of graphic is G31
then do something........
else if type of graphic is G32
then visitor modifys graphic......
:
:
else call-parent-class-method.}
DefineMethod visit
((visitor IsOfType V23) graphic)
{ if type of graphic is G21
then do something........
else if type of graphic is G32
then visitor modifys graphic......
:
:
else call-parent-class-method.}
========================================================
Codes like this can be seen even in a class library as
sophisticated as Unidraw from Stanford University.
But contemporary Object Oriented programmers know
how to implement the operation without resorting to
type tests. It is a design pattern called VISOTOR
(P331 of "Design Patterns" by Erich Gamma).
Adopting the pattern, the code would be like:
==== fig. 5 ===========================================
DefineMethod accept
((graphic IsOfType G1) visitor)
{ visit-G1 ( visitor , graphic ) ; }
DefineMethod accept
((graphic IsOfType G21) visitor)
{ visit-G21 ( visitor , graphic ) ; }
:
:
DefineMethod accept
((graphic IsOfType G32) visitor)
{ visit-G32 ( visitor , graphic ) ; }
DefineMethod visit-G1
((visitor IsOfType V1) graphic)
{visitor does actions to graphic ......}
:
:
DefineMethod visit-G1
((visitor IsOfType V21) graphic)
{visitor does something to graphic ......}
:
:
DefineMethod visit-G21
((visitor IsOfType V1) graphic)
{visitor modifys to graphic ......}
======================================================
The VISITOR pattern version of the implementation (fig.5) is
better than the type checking version (fig.4),
but the multiple dispatch version (fig.2) is still better than
the VISITOR pattern version (fig.5).
The VISITOR pattern version(fig.5) is unnatural
and less readable than the multiple dispatch version (fig.2).
(More serious weekpoints of the VISITOR pattern will be discussed
later in this document.)
However, programmers working on a single dispatch language
adopt the VISITOR pattern everytime multiple dispatching is
necessary because the VISITOR pattern is the best choice
in a single dispatch language.
From another point of view, the VISITOR pattern is an emulation
of multiple dispatching in a single dispatch language.
It expresses multiple dispatching by nesting of single
dispatching. Applying the VISITOR pattern can be viewed as
a routine process of translation from multiple dispatching
into nests of single dispatching which is done by the
programmers.
Now, here is a question. If it's a routine work, why don't the
programmers let the computers do it? To say more
concretely, it may be possible to write a macro which
converts a multiple dispatch method into a few single
dispatch methods. This is what I did in Interleaf Lisp.
Interleaf Lisp is a single dispatch Object Oriented lisp.
I implemented a CLOS-like multiple dispatch scheme
on Interleaf Lisp.
Fortunately for programmers of single dispatch lisp
(including GARNET, Flavors, and Interleaf Lisp),
the lisp macro is powerful enough to implement a
multiple dispatch scheme within a day. You can fling
away the VISITOR pattern onto a garbage dump from
the day after tomorrow and feel comfortable with
a multiple dispatch scheme forever!
However, unfortunately for C++ programmers,
the #define macro is too powerless to implement
the facility. It might be able to be implemented as a
form of a translator which translates a multiple
dispatch C++ into ordinary C++, but it might be
inconvenient by the same reason as why flex++
and bison++ are inconvenient. Generally speaking,
translators don't harmonize well with highly Integrated
development environments. Besides, there are other
reasons why it is more difficult to do this in a
C++ like single dispatch language than in Object
Oriented Lisps.
The implementation of a multiple dispatch scheme by
nesting of single dispatching is also useful for the
situation which is stated at the beginning of this
document because it's "light" and "easy" to implement.
[ Implimentation of a Multiple Dispatch scheme 1 ]
Now, let me explain what the macro or the translator does.
It expands:
==== fig.6 ===============================================
define-m-method visit
((u IsOfType U1)(v IsOfType V1)
(w IsOfType W1)(x IsOfType X1))
{ do something.....}
==========================================================
into the following:
==== fig.7 ===============================================
DefineMethod visit ((u IsOfType U1) v w x)
{ visit_U1_*_?_? ( u , v , w , x ) ;}
DefineMethod visit_U1_*_?_? (u (v IsOfType V1) w x)
{ visit_U1_V1_*_? ( u , v , w , x ) ;}
DefineMethod visit_U1_V1_*_? (u v (w IsOfType W1) x)
{ visit_U1_V1_W1_* ( u , v , w , x ) ;}
DefineMethod visit_U1_V1_W1_* (u v w (x IsOfType X1))
{ do something.....}
==========================================================
The first method is to distinguish the first parameter,
the second one is for the second parameter,
the third one is for the third, the fourth one is for the fourth.
Each method's name has its meaning.
For example, the method name visit_U1_V1_*_? means
that the types of the first and second parameter are
U1 and V1, and the method is identifying the type of the
third parameter, and the type of the fourth parameter has
not been identified yet. According to this naming rule,
the first method's name should be visit_*_?_?_?,
but it doesn't obey this rule for the user interface
because the first method is directly called by the
user program.
In many of single dispatch languages, only the first
parameter can be specialized. I mean, the object
which receives the message. So, the following may
be closer to the real coding image:
==== fig.8 ==============================================
DefineMethod visit ((u IsOfType U1) v w x)
{ visit_U1_*_?_? ( v , u , w , x ) ;}
DefineMethod visit_U1_*_?_? ((v IsOfType V1) u w x)
{ visit_U1_V1_*_? ( w , u , v , x ) ;}
DefineMethod visit_U1_V1_*_? ((w IsOfType W1) u v x)
{ visit_U1_V1_W1_* ( x , u , v , w ) ;}
DefineMethod visit_U1_V1_W1_* ((x IsOfType X1) u v w)
{ do something.....}
=========================================================
The visit method in fig.6 is expanded into 4 methods in
fig.8. This is not because the visit method has 4 parameters
but because it has 4 specialized parameters.
For example a multi-method with 3 specialized parameter
and 2 non-specialized parameters would be expanded
into 3 single-methods. Of course, the specification
that all the parameters are treated as specialized parameter
regardless of whether it is specialized explicitly or not
may be possible, but it is inefficient.
When the number of the specialized parameters is 0,
the define-m-method form is simply replaced by
a ordinal function and when the number of the
specialized parameters is 1, the define-m-method
form is simply replaced by a DefineMethod form.
[ The VISITOR pattern as emulation of Multiple Dispatching ]
The implementation in fig.7 seems to wok well,
but it's incomplete. To make it complete, in-depth analysis
of the VISITOR pattern as emulation of multiple dispatch
is necessary.
Let's think about the classes of the following:
==== fig. 9 ===============================================
Character -- AlphaNumericCharacter -- AlphabeticCharacter
CharVisitor
===========================================================
Character is a superclass of AlphaNumericCharacter.
AlphaNumericCharacter is a superclass of
AlphabeticCharacter.
Character, AlphaNumericCharacter, and AlphabeticCharacter
are concrete classes and will be visited by visitors.
CharVisitor is a visitor class.
CharaVisitor is a concrete class.
You need to implement the visit operation.
The visitor operation don't need to treat characters
differently at the moment. It does the same thing to
all the characters regardless of their types.
But as the system evolves, it may be necessary for
the operation to treat the characters differently according
to their classes in the future.
In a multiple dispatch language, you can just define:
==== fig. 10 ============================================
DefineMethod visit
((visitor IsOfType CharVisitor)
(ch IsOfType Character))
{ visitor does something to ch ...... }
=========================================================
You don't need to have stomachache worrying about
the extensibility of the system for the future.
Because it just happens.
On the other hand, lots of consideration for the future
enhancements is necessary in a single dispatch language.
It's a good chance for you to show off how complicated
problems you can deal with to your boss. Even though your
stomach has a hard time, your admirable brain tastes an
ecstasy of power and achievement being given a chance
of doing something "creative" which would be sheer
unnecessary if it were in a multiple dispatch language.
It seems that the following code in a single dispatch
language has the same semantics as fig.10.
==== fig.11 ============================================
DefineMethod accept
((ch IsOfType Character) visitor)
{ visitCharacter( visitor , ch ) ; }
DefineMethod visitCharacter
((visitor IsOfType CharVisitor) ch)
{ visitor does something to ch ...... }
=======================================================
But, the code in fig.11 lacks extensibility.
For example, suppose a subclass of CharVisitor named
CharVisitor2 is added:
==== fig.12 ============================================
Character -- AlphaNumericCharacter -- AlphabeticCharacter
CharVisitor -- CharVisitor2
========================================================
And the operation visit does a different action from the
default action when it is called with AlphaNumericCharacter
and CharVisitor2 as its parameters.
In a multiple dispatch language, you just need to add
the following:
==== fig.13 ============================================
DefineMethod visit
((visitor IsOfType CharVisitor2)
(ch IsOfType AlphaNumericCharacter))
{ visitor does something special to ch ...... }
==========================================================
And that's all.
In a single dispatch language, it seems that you can just
do something analogous to fig.13. The code is:
==== fig.14 =============================================
DefineMethod accept
((ch IsOfType AlphaNumericCharacter) visitor)
{ visitAlphaNumericCharacter( visitor , ch ) ; }
DefineMethod visitAlphaNumericCharacter
((visitor IsOfType CharVisitor2) ch)
{ visitor does something to ch ...... }
=========================================================
In a Smalltalk like single dispatch language with no
compile-time type-checking, mere addition of the
code fig.14 leads to a run-time system down.
If you remove the code fig.14, the fatal bug is also
removed. Why?
Think about calling the operation visit with CharVisitor
and AlphabeticCharacter as its parameters.
In the multiple dispatch language, the visit method in
fig.10 will be called. Because it's the applicable method
of the two. There's no problem.
In the single dispatch language, when the operation
accept is called with AlphabeticCharacter and CharVisitor,
the accept method in fig.14 will be called. Because it's
the more specific one of the two. Then the accept method
calls visitAlphaNumericCharacter on CharVisitor.
But CharVisitor has no method named
visitAlphaNumericCharacter, and he system falls down.
Let me introduce two of the remedies of the fatal bug.
Both of them are to add more code.
One is to add the following code:
==== fig.15 ==========================================
DefineMethod visitAlphaNumericCharacter
((visitor IsOfType CharVisitor) ch)
{ visitCharacter ( visitor , ch ) ; }
======================================================
The other is to add the following:
==== fig.16 ==========================================
DefineMethod accept
((ch IsOfType AlphabeticCharacter) visitor)
{ visitAlphabeticCharacter( visitor , ch ) ; }
DefineMethod visitAlphabeticCharacter
((visitor IsOfType CharVisitor) ch)
{ visitCharacter ( visitor , ch ) ; }
======================================================
Let's think about the case of a C++ like single dispatch
language with compile-time type-checking.
The C++ version of the code in fig.14 would be:
==== fig.17 ==========================================
void AlphaNumericCharacter::accept
(CharVisitor& visitor)
{ visitor.visitAlphaNumericCharacter(*this); }
void CharVisitor2::visitAlphaNumericCharacter
(AlphaNumericCharacter& ch)
{ visitor does something to ch ...... }
======================================================
A compile error is signaled when the code is compiled.
Because CharVisitor doesn't have a method named
visitAlphaNumericCharacter. Actually this compile error
is quite reasonable. The type-checking scheme of
C++ seems to be doing an excellent job when
you forget the original intention and the ideal goal
which could easily be achieved in a multiple dispatch
language.
A careless programmer who just swallowed the
sentence "The VISITOR pattern uses a technique called
double-dispatch" in the book "Design Patterns" without
ruminating it might remove the compile error by putting
a downward cast:
==== fig.18 ===========================================
void AlphaNumericCharacter::accept
(CharVisitor& visitor)
{ ((CharVisitor2) visitor).visitAlphaNumericCharacter(*this); }
void CharVisitor2::visitAlphaNumericCharacter
(AlphaNumericCharacter& ch)
{ visitor does something to ch ...... }
=======================================================
This causes the same result as fig.14. A system down.
The right solution is the same as the case of a Smalltalk
like single dispatch language. It's to add the code fig.15
or fig.16.
However, in a C++ like single dispatch language,
this means modification of the superclass's interface.
This is very unwelcomed. Because it often leads to
a recompilation of a hefty chunk of code.
As seen above, a single dispatch language has neither
carings nor consideration toward programmers when
they deal with inherently multiple dispatch structure.
The programmers have to train and adjust themselves
to this harsh and malicious environment of a single dispatch
language to survive it never knowing gentle lands of
multiple dispatch languages in calm greenery,
or, envying the people who live there.
The training menu may include the followings.
(1) In the case of fig.9, you have to
*1* prepare the accept method for every subclass
of the class Character and the class Character
and
*2* define the methods on the class CharVisitor
which are called by each accept method
regardless of the necessity at the moment.
The code would be:
==== fig.19 =======================
DefineMethod accept
((ch IsOfType Character) visitor)
{ visitCharacter( visitor , ch ) ; }
DefineMethod visitCharacter
((visitor IsOfType CharVisitor) ch)
{ visitor does something to ch ...... }
DefineMethod accept
((ch IsOfType AlphaNumericCharacter) visitor)
{ visitAlphaNumericCharacter( visitor , ch ) ; }
DefineMethod visitAlphaNumericCharacter
((visitor IsOfType CharVisitor) ch)
{ visitCharacter( visitor , ch ) ; }
DefineMethod accept
((ch IsOfType AlphabeticCharacter) visitor)
{ visitAlphabeticCharacter( visitor , ch ) ; }
DefineMethod visitAlphabeticCharacter
((visitor IsOfType CharVisitor) ch)
{ visitCharacter( visitor , ch ) ; }
============================
This is effective when you expand the system by
adding a new subclass of CharVisitor or adding a
method without touching the class structure
as long as you don't modify the Character class
hierarchy. Especially in a C++ like single dispatch
language, it often prevents the system from large
scale recompilation.
(2) You should discipline yourself to define the accept
method and the method on the CharVisitor class which is
called from the accept method everytime you add a new
class to the Character class hierarchy regardless of the
current necessity. This prevents bugs which might emerge
in the future enhancement.
(3) Use run-time type checking or implement the facility
of the visitors as methods on Characters rather than using
the Visitor pattern in the following cases:
*1* Frequent change of Character classes is pretty probable
in a C++ like single dispatch language.
*2* You need to supply the classes as a class library, in which
the user can add new classes of Character through
inheritance in a C++ like single dispatch language.
The book "Design Patterns" recommends the latter solution
(to implement facility of the visitors as methods on Characters),
but the applicability depends on the situation. in many cases,
run-time type checking may be better alternative than "polluting"
the Character classes with the methods which implements
the visitor facility.
Another solution of this problem is to use the VISITOR
pattern to build the class library and use run-time type
checking when extending the library.
This may seem confusing, but if the supplyer of the library
always uses the VISITOR pattern and the user
always uses run-time type checking, it's not confusing.
For example, if the class hierarchy of the class library is
fig.12, the user may extend the class library adding
the class SpecialCharacter which is a subclass of
Character and adding the class CharVisitor3:
==== fig.20 ===============================================
Character -- AlphaNumericCharacter -- AlphabeticCharacter
SpecialCharacter
CharVisitor -- CharVisitor2 -- CharVisitor3
===========================================================
and adding the following code:
==== fig.21 ===============================================
void CharVisitor3::visitCharacter
(Character& ch)
{
SpecialCharacter& c;
if (c = dynamic_cast<SpecialCharacter&>(ch)){
do something to c.......
} else
CharVisitor2::visitCharacter( ch );
}
===========================================================
This form of enhancement of the class library requires
no recompilation of the class library. It means, the supplyer
doesn't need to supply the source code.
Frequent change of Character classes is a serious problem
only to C++ like single dispatch languages.
[ Implementation of a Multiple Dispatch scheme 2 ]
As seen above, fig.6 shouldn't be expanded into
fig.8. It should be expanded into:
==== fig.24 =========================================
DefineMethod visit ((u IsOfType U1) v w x)
{
if (method_exits_p( v , visit_U1_*_?_?)
then {
RetVal = visit_U1_*_?_? ( v , u , w , x ) ;
if (RetVal is-equal-to :BackTrack)
then {call_parent_class_method(); }
else {return RetVal; }
} else { call_parent_class_method(); }
}
DefineMethod visit_U1_*_?_? ((v IsOfType V1) u w x)
{ if (method_exits_p( w , visit_U1_V1_*_? )
then {
RetVal = visit_U1_V1_*_? ( w , u , v , x ) ;
if (RetVal is-equal-to :BackTrack)
then { if (parent_class_method_exists_p())
then { call_parent_class_method(); }
else { return :BackTrack ;}
} else { return RetVal; }
} else { call_parent_class_method(); }
}
DefineMethod visit_U1_V1_*_? ((w IsOfType W1) u v x)
{ if (method_exits_p( x , visit_U1_V1_W1_* )
then {
RetVal = visit_U1_V1_W1_* ( x , u , v , w ) ;
if (RetVal is-equal-to :BackTrack)
then { if (parent_class_method_exists_p())
then { call_parent_class_method(); }
else { return :BackTrack ;}
} else { return RetVal; }
} else { call_parent_class_method(); }
}
DefineMethod visit_U1_V1_W1_* ((x IsOfType X1) u v w)
{ do something.....}
========================================================
This is a bit complicated. Because its a case of quadruple
dispatch. Cases of double dispatch is much simpler and
efficient. Becase consideration for Back-Tracking is not
needed.
For example, the following:
==== fig.25 ============================================
define-m-method visit
((u IsOfType U1)(v IsOfType V1))
{ do something.....}
========================================================
would be expanded into the following:
==== fig.25 ============================================
DefineMethod visit ((u IsOfType U1) v)
{ if (method_exits_p( v , visit_U1_*)
then visit_U1_*_?_? ( v , u , w , x ) ;
else call_parent_class_method(); }
DefineMethod visit_U1_* ((v IsOfType V1) u)
{ do something.....}
========================================================
There are two weekpoints of this approach when
it deals with multiple dispatch other than double
dispatch. Both of them are caused by Back-Tracking.
One is that if back tracking occurs often, the dispatch
becomes slow. The other is that the size of the expanded
code is big because back tracking should be considered.
[ Emulation of Multiple dispatch other than double dispatch ]
Emulation of double dispatch is distinctively different from
emulation of Multiple dispatch other than double dispatch.
In a C++ like single dispatch language, it's almost unrealistic
to emulate triple or quadruple dispatch. Programs which are
impossibly difficult to maintain would be produced.
On the other hand, in a single dispatch lisp like Interleaf Lisp,
the problem of the maintenability and readability of the program
can be solved by the macro explained above, but there may
be cases in which the program becomes unbearably heavy.
But fortunately, it seems to me that cases in which triple or
quadruple dispatch is inherently necessary is not frequent.
Most of the cases in which I used triple or quadruple dispatch
in CLOS could be rewritten into a set of double methods if
I modify the class structures.
Of course, triple or quadruple dispatch is sometimes
intrinsically necessary. When I developed a fuzzy knowledge
management system in CLOS, a triple dispatch generic
function played a central role in the system. I don't think
it's realistic to implement it in C++.
If you encounter a problem in which triple or quadruple
dispatch is inherently necessary, you had better think
about multiple dispatch languages like Dylan or CLOS
as candidates of the implementation language.
[ Polymorphism without inheritance ]
If you don't need to think about the inheritance of method,
emulation of multiple dispatch in a single dispatch suddenly
becomes very easy. Just create 3 dimensional array
for triple dispatch, and 4 dimensional one for quadruple
dispatch. If the size of the array is too big and sparse, then
it may be a good idea to replace it with a tree of hash tables.
Anyway, inheritance makes the problem difficult.
If you have to implement triple dispatch in C++,
it's a possible choice to forsake inheritance.
[ Conclusion ]
When we compare a single dispatch language with a multiple
dispatch language, the following points are important.
(1)Double dispatch should be discussed differently from
other kinds of multiple dispatch.
(2)Multiple dispatch without inheritance is a relatively
simple and easy problem. Inheritance makes multiple
dispatch complicated.
(3)Compile-time type checking makes it difficult to emulate
multiple dispatch in a single dispatch language.
A multiple dispatch scheme can be implemented as a macro
in a single dispatch lisp, but not in C++.
Emulation of triple or quadruple dispatch is possible
in a single dispatch lisp, whereas, it's a nightmare
in C++.
Emulation of multiple dispatch contains lots more things
than I discussed in this document. All of this would be just
a waste of time if C++ and other main stream computer languages
had a multiple dispatch scheme, or, if a Dylan like programming
language were the main-stream computer language.
Emulation of multiple dispatch in a single dispatch language
is a big eater of intellectual energy of capable software
engineers. I feel it's anachronistic that programmers train
themselves to work on inconvenient computer environment.
It is reminiscent of machine language programmers who
memorized all the machine language commands which consisted
of 0 and 1, with being proud of it.
The remedies described in this document are for transitional
use. It's just a step stone. The real solution would be to
incorporate a multiple dispatch scheme in C++, or, to replace
C++ environments with those of Dylan.
--
Yutaka Sumi (·····@phe.hitachi-sk.co.jp)
NOTE: The opinions and comments here are those of the writer ONLY!