Hello,
I am not a stranger to Lisp or to Object-Oriented programming. However, I am
new to OO in Lisp and I am trying to understand the need for multiple
dispatch. I hypothesize that CLOS uses generic methods to fit with Lisp's
expression oriented syntax and semantics rather than because it is necessary
to express an object-oriented design. And as a by-product of the flexibility
of generic methods..., we might as well allow multiple dispatch. Would
someone please educate me as to why multiple dispatch is necessary?
(Examples are welcomed, even encouraged.)
Next question, how is multiple dispatch implemented efficiently? (It appears
to me that selecting the function (method) to dispatch in Lisp would, of
necessity, be resolved at run time rather than compile time in most
instances. Does this entail a large overhead that would discourage one from
using OO rather than a (not necessarily pure) functional approach?)
TIA,
Mark
--
Mark K. Gardner (········@cs.uiuc.edu)
University of Illinois at Urbana-Champaign
Real-Time Systems Laboratory
--
In article <·······················@perts6.cs.uiuc.edu>,
Mark K. Gardner <········@cs.uiuc.edu> wrote:
>I am not a stranger to Lisp or to Object-Oriented programming. However, I am
>new to OO in Lisp and I am trying to understand the need for multiple
>dispatch. I hypothesize that CLOS uses generic methods to fit with Lisp's
>expression oriented syntax and semantics rather than because it is necessary
>to express an object-oriented design. And as a by-product of the flexibility
>of generic methods..., we might as well allow multiple dispatch. Would
>someone please educate me as to why multiple dispatch is necessary?
>(Examples are welcomed, even encouraged.)
Often the implementation of an operation is dependent on the types of
multiple parameters, and multiple dispatch allows this to be expressed
easily. The most common examples are graphical output, where the
implementation is dependent on both the shape and output device, and
arithmetic, where different coercions need to be done with different
combinations of input types.
>Next question, how is multiple dispatch implemented efficiently? (It appears
>to me that selecting the function (method) to dispatch in Lisp would, of
>necessity, be resolved at run time rather than compile time in most
>instances. Does this entail a large overhead that would discourage one from
>using OO rather than a (not necessarily pure) functional approach?)
Even single dispatch requires runtime resolution, although you only have to
search a single dispatch table so it's easier to do it efficiently.
Most CLOS implementations make heavy use of caching. The first time you
make a call with a particular combination of classes it has to do some work
to compute the combined method, but future calls can look this up in the
cache and dispatch quickly.
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Don't bother cc'ing followups to me.
········@cs.uiuc.edu (Mark K. Gardner) writes:
> Hello,
>
> I am not a stranger to Lisp or to Object-Oriented
> programming. However, I am new to OO in Lisp and I am trying to
> understand the need for multiple dispatch. I hypothesize that CLOS
> uses generic methods to fit with Lisp's expression oriented syntax
> and semantics rather than because it is necessary to express an
> object-oriented design. And as a by-product of the flexibility of
> generic methods..., we might as well allow multiple dispatch. Would
> someone please educate me as to why multiple dispatch is necessary?
> (Examples are welcomed, even encouraged.)
Well, I guess that multiple dispatch is not really necessary, lots of
popular OO languages do not include it. However, it can be really
helpful when designing solutions to problems. The problem with single
dispatch is that you are only using the dynamic property of one object
to determine the behavior of the method. Lets assume that I am a
painter and I would like to have a method (paint object color), not to
complicated. Now I could say (paint car red) as well as (paint house
red) to invoke two different painting behaviors. For instance, when
painting a car you would not use latex paint, it looks really bad;-).
This works fine in the world of single dispatch. The benefits of
multiple dispatch arise when I need to also change the behavior of
'paint' based on the color chosen, like to model the fact that
translucent colors need a base coat. Then since candy-apple-red is a
translucent color I simple call (paint car candy-apple-red) and the
correct paint method which is specialized on translucent colors is
invoked. To handle this case using single dispatch you either need to
add tests for the type of paint being used, invoke a second dispatching
call from the first method called to do the actual work, or ensure
that the type of the color argument is statically specified. None of
which are very appealing.
> Next question, how is multiple dispatch implemented efficiently?
> (It appears to me that selecting the function (method) to dispatch
> in Lisp would, of necessity, be resolved at run time rather than
> compile time in most instances. Does this entail a large overhead
> that would discourage one from using OO rather than a (not
> necessarily pure) functional approach?)
It is not really hard to implement it efficiently but it will be
slightly less efficient that single dispatch, simply for the reason
that you are dispatching on my things and need to make more
decisions. But the thing to keep in mind if you need to make the
distinctions that are being made in the multiple dispatch you would
still have to pay for them under the single dispatch model, either as
additional conditional statements or additional dispatching method
invocations. All that dispatching is in any OO language is a nifty
shorthand for a big typecase statement, that may be complied a little
more efficiently in some cases.[1]
All OO languages select the appropriate method to invoke at run time,
that is their benefit. The only time that lookup can be eliminated is
when type analysis can show that only one method could be invoked and
then you can get a direct function call. This is all language
neutral.
There is an overhead associated with using OO features in any language
but don't let them scare you away. There is no free lunch, if you
would honestly make use of the features of OO to modify behavior based
on the types of the objects you are using then you don't lose. For
you would need to write your own tests and conditional statements to
get the same behavior. And I personally know that the complier does a
better job of making bizarre lookup tables than I do, so I'll let it
do the work.
Hope that helps,
-Eric
[1] There are a whole host of ways that OO dispatch is implemented and
the best choice is not always obvious. This naive big typecase model
actually can win over techniques like C++'s virtual method tables on
some types of hardware. Newer processors with fancy branch prediction
abilities can often find their way through a typecase with little
effort while they choke on a VMT lookup.
> TIA,
>
> Mark
>
> --
> Mark K. Gardner (········@cs.uiuc.edu)
> University of Illinois at Urbana-Champaign
> Real-Time Systems Laboratory
> --
> someone please educate me as to why multiple dispatch is necessary?
Well, even objects aren't NECESSARY -- all of UNIX was written without
them. Moreover, the Symbolics LispM OS was written using only
single dispatch of Flavors as well.
A good real-world example is printing: it needs at least two arguments,
a printer and a file. The mechanism for printing depends on the
type of both. Geez, compare how printing is done using UNIX:
there is a /etc/printcap file, and filters, and, and, and.... AHHHH.
Now imagine there is a generic function (print-file printer file &key)
Each class of printer object handles the different file types.
(defmethod print-file ((p postscript-printer)
(f postscript-file) &rest keys)
(apply #'add-to-queue p f keys))
(defmethod print-file ((p postscript-printer)
(f gif) &rest keys)
(apply #'print-file p (gif-to-postscript f) keys))
However, I'd probably use a macro to defined the methods:
(defmacro define-postscript-method ((var type) form)
`(defmethod print-file ((p postscript-printer) (,var ,type) &rest keys)
(apply #'print-file p ,form keys)))
(define-postscript-method (f gif) (gif-to-postscript f))
(define-postscript-method (f jpeg) (jpeg-to-postscript f))
Of course, further, I would eliminate files altogether, there
would only be gif images, not gif files...
(print-file (printer-named "epson-color") (gif-image-named "logo.gif"))
Ahh, for a real object-oriented operating system...
>
> Next question, how is multiple dispatch implemented efficiently?
My object implementation is unlike the "standard" PCL-based
implementations. I've optimized for the single-dispatch case,
which is used in the vast majority of cases. In this case, it works
like C++, in that I use a dispatch-table that holds functions.
i.e. (roughly)
(defun print-file (p f &rest keys)
(let methods = (std-instance-methods p)
function = (svref methods (gf-index 'print-file))
do
(apply function p f keys)))
In the multiple dispatch case, the function in the method table
is a dispatch function that does a series of type tests on
the second argument, i.e. (roughly)
(defun print-file-postscript (p f &rest keys)
(if (object-typep f 'gif)
then
..code-for p=postscript f=gif
elseif (object-typep f 'jpeg)
then
..code-for
else
(no-next-method..)
))
This isn't the best if there are 20 cases to check for,
but in the real-world, it's usually just a handful
after you've selected on the first argument already.
It is much more complicated than shown, but that's the basic idea.
Whenever a new method is added for the postscript printer,
believe it or not, I cons-up a new dispatch function
with the additional conditionals, and compile it,
and replace the old dispatch function with the new one.
This can make it a bit slow to load in compiled method code,
whereas the PCL-based implementations do all this kind
of function composition at RUNTIME.
This implementation makes generic functions very fast,
really as fast or faster than you could do it yourself
if you hand-optimized the code to deal with all the
cases you must deal with.
(btw, this object system is used for my OODB)
-Kelly Murray ···@intellimarket.com
Kelly Murray <···@IntelliMarket.Com> writes:
>
> > someone please educate me as to why multiple dispatch is necessary?
>
> Well, even objects aren't NECESSARY -- all of UNIX was written without
> them. Moreover, the Symbolics LispM OS was written using only
> single dispatch of Flavors as well. [...]
Heh. Well, without trying to detract from your long answer, let me offer
a short answer from the point of view of a career language designer:
Principle: Languages should reasonably anticipate common usage patterns
and try to provide a means of expressing those patterns that is
recognizable by the compiler writer to provide optimal code.
Common Lisp is pretty much built on the principle that a relatively
complex compiler means relatively simple programs. (Scheme, by
contrast, seems to me always to be the other way around.) You can
quibble with the theory that the compiler should be the one to have
the complexity, but it's just a design trade-off and the position IS
defensible. The idea is in this modular hub that the optimizations
for many common optimizations reside so that a single upgrade to the
compiler will speed up many programs. The alternative is that when
new technology comes along, individual programs must be each rewritten
to accomodate that new technology.
By failing to provide a linguistic way of expressing multiple dispatch
to occur, you don't keep it from happening--you only assure that the
compiler won't recognize it when it happens and consequently won't be
able to help assure that it's done optimally fast.
Seen in this light, the real question becomes: What purpose would be
served by NOT supporting multiple dispatch? Is it reasonable to
suppose that the large majority of applications would not simulate it?
I think not. Your mileage may vary. Is it reasonable to suppose that
each user who simulates it does so optimally? I hope we'd both agree
that this is not a reasonable supposition. (If you really think all
programmers always program optimally, we shouldn't be talking about
multiple dispatch--we have more basic disagreements in our world model. :-)
But Kelly is right--nothing is "necessary". The issue is really
what's desirable. And I hope I've made a case that at least defends
why the CL design community thought it desirable... Of course, the
fact that people disagree on design principles is why more than one
language is out there...
In article <·······················@perts6.cs.uiuc.edu>,
········@cs.uiuc.edu wrote:
>
> Hello,
>
> I am not a stranger to Lisp or to Object-Oriented programming. However, I am
> new to OO in Lisp and I am trying to understand the need for multiple
> dispatch. I hypothesize that CLOS uses generic methods to fit with Lisp's
> expression oriented syntax and semantics rather than because it is necessary
> to express an object-oriented design. And as a by-product of the flexibility
> of generic methods..., we might as well allow multiple dispatch. Would
> someone please educate me as to why multiple dispatch is necessary?
> (Examples are welcomed, even encouraged.)
I have been programming in C++ for the past 4 years. Recently, I came across
an object oriented design problem and realized that the solution for it lies
in multi-methods. Multi-methods are so important that they classify OOP
languages into two groups: one which supports them (ex. CLOS, Dylan, Cecil,
Common Loops) and another which does not support them (ex. C++, Java, Ada-95,
Modula-3, Simula, Smalltalk, Eiffel) In fact, i am most impressed by this
feature of CLOS.
The motivation for multi-methods is well explained in the paper "Object
Oriented Multi-Methods in Cecil". This paper is available online at the
University of Washington's Web Site. Go to the Cecil/Vortex project home page
there and you should find it.
>
> Next question, how is multiple dispatch implemented efficiently? (It appears
> to me that selecting the function (method) to dispatch in Lisp would, of
> necessity, be resolved at run time rather than compile time in most
> instances. Does this entail a large overhead that would discourage one from
> using OO rather than a (not necessarily pure) functional approach?)
>
Since i am new to Lisp/CLOS, i really dont have any idea about how efficient
implementations can be in these languages.
Much research is still going on in this field to support multi-methods for
the other class of languages.
> TIA,
>
> Mark
>
> --
> Mark K. Gardner (········@cs.uiuc.edu)
> University of Illinois at Urbana-Champaign
> Real-Time Systems Laboratory
> --
>
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
In article <·······················@perts6.cs.uiuc.edu>,
········@cs.uiuc.edu wrote:
> I am not a stranger to Lisp or to Object-Oriented programming. However, I am
> new to OO in Lisp and I am trying to understand the need for multiple
> dispatch.
I recently did a quick analysis of one of our scheduling applications. Around
10% of the generic functions used multiple dispatch.
I categorised the tasks performed as follows:
1) Writing or reading some data based on a multi-object look-up.
2) Comparing two objects.
3) Linking two objects.
4) Supporting flow of control other generic-functions e.g. drag and drop
In the drag & drop example, we usually specialise on three of the parameters -
object being dragged, area being dragged to & type of drag (move, copy).
In an extreme case you can specialise on additional parameters e.g. area being
dragged from, object being dragged to, although we haven't had any need to do
this yet.
Mark
----------------------------------------------------------------
Mark Dalgarno, Phone +44 1223 421221
R & D Manager Fax +44 1223 421218
Scientia, Email ····@scientia.com
St. John's Innovation Centre,
Cowley Road, Cambridge, England
CB4 0WS
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
········@cs.uiuc.edu (Mark K. Gardner) writes:
> of generic methods..., we might as well allow multiple dispatch. Would
> someone please educate me as to why multiple dispatch is necessary?
In one case I use multiple dispatch to define binary _relations_ on
objects, i.e. I use a double-dispatching generic function which
returns boolean values. By adding some syntactic sugar to the
'defmethod's, I get at a very compact, declarative way of describing my
relations (which define protections of objects in a database, btw.),
suitable for use in a user-configurable part of my program.
--
regards,
Espen Vestre