[munich-lisp] multimethods, generic functions, multiple dispatch, ...
hi, yesterday in the beer garden there was a discussion going on where i tried to explain the advantage of generic functions over the way that java or c++ implement their runtime type polymorphism on only one argument, the implicite 'this' argument. the example choosen to show the problems with only single method dispatching was the collission of two 2 dimensional shapes, e.g. triangle, circle, square, rectangle, ellipse, ... in java the 'best' way to achieve double dispatch is probably some variation of the visitor pattern, something along the lines: class Triangle implements Shape { public boolean collidesWith(Shape other) { other.collidesWithTriangle(this); } ...; public boolean collidesWithCircle(Circle s) {...;} public boolean collidesWithSquare(Square s) {...;} ...; } you avoid the if-then-elses, but if you add a shape later you will have to touch all sublasses of Shape and add the collidesWithNewShape method. because collission detection is symmetric, e.g. it does not matter if you say collidesWith(Triangle t, Circle c) or collidesWith(Circle c, Triangle t) it is not obvious if the actual code that does the collision detection between these two shapes should be in the Triangle or in the Circle class. probably it is best factored out in a third CollisionDetectionAlgorithm class which only contains static methods for each combination of shapes. as you can see you have to be already quite imaginative to implement double type dispatch and it will become even more complex with more than two types on which you would like to dispatch. you avoid the problem completely by using multimethods, e.g. CLOS in lisp or language extensions like NICE for java: http://nice.sourceforge.net/ i've also seen some time ago an extension to gcc that allows you to use multimethods in C++, but i cannot find it at the moment. there are two related documents that i found by quickly browsing through some google results: http://www.cs.technion.ac.il/~imaman/stuff/mm.ppt https://www.informit.com/content/images/0201704315/samplechapter/alexan11.pd... -- Christian Schuhegger http://www.el-chef.de/
Christian.Schuhegger wrote @ Sat, 10 Sep 2005 08:58:48 +0200: You seem to have forgotten to show the actual Lisp code.
class Triangle implements Shape { public boolean collidesWith(Shape other) { other.collidesWithTriangle(this); } ...; public boolean collidesWithCircle(Circle s) {...;} public boolean collidesWithSquare(Square s) {...;} ...; }
While having methods with the same name but different signatures is certainly something i like, maybe in this case you just have problems with the objects you designed. I guess, we all know Java is limited, but let's not forget, they call it a feature. class Triangle implements Shape { public 2Dspace space() { 2DSpace my_space = xy[screen.x_dim][screen.y_dim]; // fill the matrix with pixels the Triangle occuppies return my_space; } public boolean collidesWith(Shape other) { return overlap(other.space, this.space); } } So first, generalize the properties of your objects and then let them interact. I would also say that colliding and especially overlap() is something that the Object World should do. Andy
Andreas Hauser wrote:
Christian.Schuhegger wrote @ Sat, 10 Sep 2005 08:58:48 +0200:
You seem to have forgotten to show the actual Lisp code.
sorry :) (defmethod do-shapes-collide-p ((shape1 Triangle) (shape2 Circle)) (...)) (defmethod do-shapes-collide-p ((shape1 Circle) (shape2 Triangle)) (do-shapes-collide-p shape2 shape1)) (defmethod do-shapes-collide-p ((shape1 Triange) (shape2 Square)) (...)) ...
class Triangle implements Shape { public boolean collidesWith(Shape other) { other.collidesWithTriangle(this); } ...; public boolean collidesWithCircle(Circle s) {...;} public boolean collidesWithSquare(Square s) {...;} ...; }
While having methods with the same name but different signatures is certainly something i like, maybe in this case you just have problems with the objects you designed. I guess, we all know Java is limited, but let's not forget, they call it a feature.
class Triangle implements Shape { public 2Dspace space() { 2DSpace my_space = xy[screen.x_dim][screen.y_dim]; // fill the matrix with pixels the Triangle occuppies return my_space; } public boolean collidesWith(Shape other) { return overlap(other.space, this.space); } }
So first, generalize the properties of your objects and then let them interact. I would also say that colliding and especially overlap() is something that the Object World should do.
and what do you do if you talk about vector objects and not pixel objects :) -- Christian Schuhegger http://www.el-chef.de/
Christian.Schuhegger wrote @ Sat, 10 Sep 2005 10:07:09 +0200:
Andreas Hauser wrote:
Christian.Schuhegger wrote @ Sat, 10 Sep 2005 08:58:48 +0200:
You seem to have forgotten to show the actual Lisp code.
sorry :)
(defmethod do-shapes-collide-p ((shape1 Triangle) (shape2 Circle)) (...)) (defmethod do-shapes-collide-p ((shape1 Circle) (shape2 Triangle)) (do-shapes-collide-p shape2 shape1)) (defmethod do-shapes-collide-p ((shape1 Triange) (shape2 Square)) (...)) ...
And why don't you need: (defmethod do-shapes-collide-p ((shape1 Circle) (shape2 Triangle)) ?
and what do you do if you talk about vector objects and not pixel objects :)
It must be serialized somewhere (in Object World ?). Do the collision there. But it seems Java can do methods with different sigantures: public class foo { public foo() { } public void bar(int i) { System.out.println(i + 1); } public void bar(String s) { System.out.println(s + " world"); } public static void main(String args[]) { foo f = new foo(); f.bar(12); f.bar("Hello"); } } Andy
Andreas Hauser wrote:
(defmethod do-shapes-collide-p ((shape1 Triangle) (shape2 Circle)) (...)) (defmethod do-shapes-collide-p ((shape1 Circle) (shape2 Triangle)) (do-shapes-collide-p shape2 shape1)) (defmethod do-shapes-collide-p ((shape1 Triange) (shape2 Square)) (...)) ...
And why don't you need: (defmethod do-shapes-collide-p ((shape1 Circle) (shape2 Triangle)) ?
this is because collission of two objects is symmetric: a collides with b <=> b collides with a and i do not have to implement the same code again.
It must be serialized somewhere (in Object World ?). Do the collision there.
this is why i suggested:
probably it is best factored out in a third CollisionDetectionAlgorithm class which only contains static methods for each combination of shapes.
and you are right:
But it seems Java can do methods with different sigantures:
public class foo { public foo() { }
public void bar(int i) { System.out.println(i + 1); }
public void bar(String s) { System.out.println(s + " world"); }
public static void main(String args[]) { foo f = new foo(); f.bar(12); f.bar("Hello"); } }
but this overloading of methods is something "compile time" and not "run time", e.g. if you would have some code similar like this: -- snip start -- public class CollisionDetectionAlgorithm { public static boolean collides(Shape s1, Shape s2) {...;}// throw a runtime exception public static boolean collides(Triangle s1, Circle s2) {...;} public static boolean collides(Triangle s1, Square s2) {...;} public static void main(String[] args) { Shape s1 = new Triangle(); Shape s2 = new Circle(); System.out.println(collides(s1,s2)); } } -- snip end -- you would end up with the first collides method being called which would throw a runtime exception. the only runtime type polymorphism that java knows is subtype type polymorphism which only reacts on the type of the implicite 'this' type. the calls to the overloaded methods are fixed at compile time. -- Christian Schuhegger http://www.el-chef.de/
Christian.Schuhegger wrote @ Sun, 11 Sep 2005 16:48:49 +0200:
Andreas Hauser wrote:
And why don't you need: (defmethod do-shapes-collide-p ((shape1 Circle) (shape2 Triangle)) ?
this is because collission of two objects is symmetric: a collides with b <=> b collides with a and i do not have to implement the same code again.
I thought you had meant, that you don't need the second method at all. Like having an alias in the symbol table or something. I could imagine in a cool language you would only need one method and have some way to specify that the argument order doesn't matter. In Lisp i would at least have expected something like: (defmethod-all-combinations do-shapes-collide ((shape1 Circle) (shape2 Triangle)) where defmethod-all-combinations would produce all combinatios of the arguments, namely: do-shapes-collide ((shape1 Circle) (shape2 Triangle)) do-shapes-collide ((shape2 Triangle) (shape1 Circle)) And from the way you presented this at the biergarden, i tought, that CL even had some builtin magic for that case.
but this overloading of methods is something "compile time" and not "run time", e.g. if you would have some code similar like this: -- snip start -- public class CollisionDetectionAlgorithm { public static boolean collides(Shape s1, Shape s2) {...;}// throw a runtime exception public static boolean collides(Triangle s1, Circle s2) {...;} public static boolean collides(Triangle s1, Square s2) {...;}
public static void main(String[] args) { Shape s1 = new Triangle(); Shape s2 = new Circle(); System.out.println(collides(s1,s2)); } } -- snip end -- you would end up with the first collides method being called which would throw a runtime exception. the only runtime type polymorphism that java knows is subtype type polymorphism which only reacts on the type of the implicite 'this' type. the calls to the overloaded methods are fixed at compile time.
Even if Java was more dynamic, i don't see, why in this case it should not match the collides(Shape, Shape) signature, when you explicitly declare s1 and s2 to be of Shape. You would need them do be declared with the signatures you want to match. public static void main(String[] args) { Triangle s1 = new Triangle(); Circle s2 = new Circle(); System.out.println(collides(s1,s2)); } I don't get the point. Andy
participants (2)
-
Andreas Hauser -
Christian Schuhegger