Hi,
This is a question pertaining to CLOS. So, if I am posting to
the wrong newsgroup, I apologize.
I have been programming in C++ for the past few years.
Recently, I came across a problem phrased as
"the double dispatch problem" which has no direct solution in
C++.
I have heard that CLOS has a direct solution to this problem.
I would be glad if someone could explain to me how to code
the solution to this problem in CLOS:
I have an abstract class "shape" from which I derive classes
"square" and "circle". Now I want to write a function "draw"
which takes one argument - the shape to be drawn. This is a
single dispatch and can be solved in C++. I also want to write
a function "intersect_area" which takes as arguments two
shapes. The algorithm for intersecting square and square is
different from that for circle and circle which is different
from that for circle and square which in turn, is different
from that for square and circle.
Please give (in CLOS source code) the organization of the
classes shape, square, and circle, and also, the methods
"draw" and "intersect_area".
Thanking you,
With regards,
Mayur
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
·········@my-dejanews.com writes:
> I have an abstract class "shape" from which I derive classes
> "square" and "circle". Now I want to write a function "draw"
> which takes one argument - the shape to be drawn. This is a
> single dispatch and can be solved in C++. I also want to write
> a function "intersect_area" which takes as arguments two
> shapes. The algorithm for intersecting square and square is
> different from that for circle and circle which is different
> from that for circle and square which in turn, is different
> from that for square and circle.
First off, I don't understand why this would be difficult in C++. Would it
not involve declaring the function intersect as virtual, and attaching it
to the root class Geometric_Object? Then each subclass (Circle and Square)
could specialize this virtual class for the second argument. Why would this
fail?
> Please give (in CLOS source code) the organization of the
> classes shape, square, and circle, and also, the methods
> "draw" and "intersect_area".
(defclass geometric-object ()
())
(defclass circle (geometric-object)
())
(defclass square (geometric-object)
())
(defmethod intersect-area ((obj1 circle) (obj2 circle))
...)
(defmethod intersect-area ((obj1 circle) (obj2 square))
...)
(defmethod intersect-area ((obj1 square) (obj2 circle))
...)
(defmethod intersect-area ((obj1 square) (obj2 square))
...)
Sunil
[comp.lang.clos removed.
http://world.std.com/~pitman/pfaq/cross-posting.html]
Sunil Mishra <·······@cleon.cc.gatech.edu> writes:
> ·········@my-dejanews.com writes:
>
> > I have an abstract class "shape" from which I derive classes
> > "square" and "circle". Now I want to write a function "draw"
> > which takes one argument - the shape to be drawn.
>
> First off, I don't understand why this would be difficult in
> C++. Would it not involve declaring the function intersect as
> virtual, and attaching it to the root class Geometric_Object? Then
> each subclass (Circle and Square) could specialize this virtual
> class for the second argument. Why would this fail?
I understood the question to be about what I always call
"the ability to implement vs the ability to express".
C++, like any Turing-powerful language, lets you "implement"
this. Maybe it's not even hard. But CLOS allows you
to "express" this in that the language primitively understands
your desire to the point where you don't really have
to know whether it does the lookup in a cascaded call such
as you just described or in an n-dimensional lookup table.
(If you look hard, you can see that in tie-breaking, it is
cascaded calling, since the args still have a precedence order,
but the point is still that you don't write code that implements
the tie-breaking--it's all linguistic. So, for example, if a
faster implementation technique comes along, all programs
benefit from it. That is, in general, the virtue of taking
any common user problem and promoting it to language level.)
> > Please give (in CLOS source code) the organization of the
> > classes shape, square, and circle, and also, the methods
> > "draw" and "intersect_area".
>
> (defclass geometric-object () ())
> (defclass circle (geometric-object) ())
> (defclass square (geometric-object) ())
> (defmethod intersect-area ((obj1 circle) (obj2 circle)) ...)
> (defmethod intersect-area ((obj1 circle) (obj2 square)) ...)
> (defmethod intersect-area ((obj1 square) (obj2 circle)) ...)
> (defmethod intersect-area ((obj1 square) (obj2 square)) ...)
The middle two of these being the same, I should note that we discussed
even as early as the late 1970's (when CLOS didn't exist but everyone
along my hallway at MIT had implemented their own class system because the
time for the idea had come ... and because it was fun) that object systems
should accomodate not only multimethods (dispatch on multiple objects) but
also declarations of transitivity and associativity and other things that
mathemeticians have known for years are issues.
Actually, the notion of transitivity and associativity are independent of
the issue of dispatch, because you can want them on regular functions,
too. In 1985, for example, when I converted the source code of Macsyma, a
large symbolic algebra system, from the hodgepodge of older dialects to
Common Lisp, I gave it a facility to declare such things for functions
rather than have something in the function bodies that noticed extra args
and did explicit calls to REDUCE, or worse, in the body. It didn't solve
all the world's problems, but it had a very nice look to it. And it
reaffirms a claim that MIT's Programmer's Apprentice group (Rich and
Waters) had often made--that 90% of everything you do is cliche'
(repetitive drudge), and that if you could only automate that, you'd
free yourself to worry about the other 10% which was interesting...
and the corrolary: that 90% of that interesting part, once you could
focus on it, would also end up being cliche' ... so it's a never-ending
spiral. But at least it gets you to more and more interesting problems.
So for now in CLOS we write what you've written above, but I look forward
to a day when reality catches up to dreaming and one can write:
(defgeneric intersect-area (obj1 obj2)
(:argument-variations :commutative :associative)
(:singleton :self)
(:nary :singleton-is-identity t :degenerate-case +everywhere+))
or some such thing. (I just made this up off top of my head, and if I did
it for real I'd talk to a mathemetician to get the terminology right,
since it's been too long since I looked at that.) The idea would be to
allow you to write only one of the circle/square definitions and then
still make calls like (intersect-area x1 x2 x3) involving any number of
circles and squares. Or to allow you to use (intersect-area x1) or
(intersect-area). Or whatever.
Always there are problems to be solved. The reason to go with Lisp
is only partly that it offers you a solution to the multimethod
problem. The real underlying reason is that it offers you a community
of people who care about powerful expressive tools and who stand
half a chance of offering things like this one day. AND in the
meantime, you could probably extend the language yourself to compensate
until they do...
Lisp is a language that's worried not only about how your programs speak
to the computer for the purpose of compilation, but how your programs
speak to the future for the purpose of readability, maintainability, and
taking advantage of future advances in compilation technology.
Sunil Mishra (·······@cleon.cc.gatech.edu) wrote:
: ·········@my-dejanews.com writes:
: > I have an abstract class "shape" from which I derive classes
: > "square" and "circle". Now I want to write a function "draw"
: > which takes one argument - the shape to be drawn. This is a
: > single dispatch and can be solved in C++. I also want to write
: > a function "intersect_area" which takes as arguments two
: > shapes. The algorithm for intersecting square and square is
: > different from that for circle and circle which is different
: > from that for circle and square which in turn, is different
: > from that for square and circle.
: First off, I don't understand why this would be difficult in C++. Would it
: not involve declaring the function intersect as virtual, and attaching it
: to the root class Geometric_Object? Then each subclass (Circle and Square)
: could specialize this virtual class for the second argument. Why would this
: fail?
I don't understand what you mean by "specialize this virtual class for
the second argument". Could you clarify? I know how to specialize
functions based on their arguments. How do you specialize classes
based on particular arguments? And in C++, how can you specialize a
function so that it dispatches on anything but its first argument? (as
opposed to being statically overloaded on more than one argument).
As far as I know, multiple dispatch in C++ is doable but messy (not
directly supported by the language). See Scott Meyers, _More Effective
C++_, pp. 228-251, "Making functions virtual with respect to more than
one object"/"Implementing Multiple Dispatch" for a discussion of the
practicalities of doing it.
(Or, if you really get intensely serious about it, see also "Fast
Algorithms for Compressed Multimethod Dispatch Generation", by Eric
Dujardin, Eric Amiel, and Eric Simon, _ACM Transactions on Programming
Languages and Systems_, 20:116-165 (1998), which I can't claim to
understand, but how often will I get a chance to cite a paper by three
people with the same name? It professes to let you do multiple
dispatch in constant time. As long as you're rolling your own multiple
dispatch system, why not do it right?:-)
Bill Newman
·······@netcom.com (Bill Newman) writes:
> Sunil Mishra (·······@cleon.cc.gatech.edu) wrote:
> : ·········@my-dejanews.com writes:
>
> : > I have an abstract class "shape" from which I derive classes
> : > "square" and "circle". Now I want to write a function "draw"
> : > which takes one argument - the shape to be drawn. This is a
> : > single dispatch and can be solved in C++. I also want to write
> : > a function "intersect_area" which takes as arguments two
> : > shapes. The algorithm for intersecting square and square is
> : > different from that for circle and circle which is different
> : > from that for circle and square which in turn, is different
> : > from that for square and circle.
>
> : First off, I don't understand why this would be difficult in C++. Would it
> : not involve declaring the function intersect as virtual, and attaching it
> : to the root class Geometric_Object? Then each subclass (Circle and Square)
> : could specialize this virtual class for the second argument. Why would this
> : fail?
>
> I don't understand what you mean by "specialize this virtual class for
> the second argument". Could you clarify? I know how to specialize
> functions based on their arguments. How do you specialize classes
Well, what I had meant was that you could declare the function virtual and
specialize on both arguments. But I think I now have a better feel for why
this is difficult for C++ (based on Kent's response).
> based on particular arguments? And in C++, how can you specialize a
> function so that it dispatches on anything but its first argument? (as
> opposed to being statically overloaded on more than one argument).
This is what I had not understood. I didn't know this was the case in C++.
Sunil
Stig Hemmer <····@pvv.ntnu.no> writes:
> Briefly:
>
> (defclass shape () ...)
> (defclass circle (shape) ...)
> (defclass square (shape) ...)
> (defclass wobble (shape) ...)
> ...
>
> (defmethod intersect_area ((a1 circle) (a2 circle)) ...)
> (defmethod intersect_area ((a1 circle) (a2 square)) ...)
> (defmethod intersect_area ((a1 square) (a2 circle)) ...)
> (defmethod intersect_area ((a1 square) (a2 square)) ...)
>
> (defmethod intersect_area ((a1 shape) (a2 shape))
> (error "No valid intersect_area method found."))
>
> Stig Hemmer,
> Jack of a Few Trades.
>
> PS: I'm also a newcomer to CLOS, so the above may be incorrect.
You *can* do that, but it's not necessary. If none of the methods defined
fit, then CLOS will signal an error. This is, of course, nicer... You can
in fact leave out the type in the case you just added, so that it catches
*any* invalid invocation.
Sunil