multimethod + multiple inheritance
in [OOP]
|
From: Laurent Deniau on 22 Mar 2006 09:45 Dmitry A. Kazakov wrote: > On Tue, 21 Mar 2006 16:00:31 +0100, Laurent Deniau wrote: > I see. But this is a different story. You want to dispatch to Shark and > then to make something different out of it. The question is how different > that might be. Will it be a Shark, a Fish etc. Again, it does not change. Only its type (hidden as part of its value) changes and this is something hidden to the user (like HealthyShark and InjuredShark are) and is managed automatically by MD. For example in some Objective-C implementation (Smalltalk?) when you create a String, it is never a String instance but something else with a mutating type which changes depending on the operations you will apply to it and some rules. String is only a king of interface (an ADT) to a cluster of classes. An even simpler example would be Complex as an interface (ADT) of RectComplex and PolarComplex and where toPolar(CartComplex) and toRect(PolarComplex) would be the methods which switch the intances type. I agree that MD + DI mix in behavior and state (in a very convenient way to my opinion) using the fact that behavior is related to type and type is a value, that is a state (remember classes are objects). In usual programming paradigm, the object would include an explicit state and all its applicable methods would check this state to select the correct behavior, leading to dozen of nested if-then-else branches in these methods. One might assume that nothing changes in the object except this state (state machine). Predicate dispatch allows the object type to be the state and MD describes naturally the different behaviors (method specialization) like in the slides I pointed out. No nested if-then-else are required. This programming approach is simply a natural extension of method overriding which can also be done by static binding and type-case tests after all. If you have read the slides, you should have seen the code improvement brought by combining dynamic inheritance and multimethod dynamic dispatch. I will not try to convince you, I was only looking for experiences and feedback on this programming approach since I am also a newbie in it (after 15 years of C++). > It is a misuse of type system in my eyes. To me healthy, injured, fat are > states, not types. The statement above just shows that combination of state and type (when possible) is poweful. > Moreover, there are definitely shades of healthiness, > which is not discrete, it is even not ordered, and might be fuzzy or > stochastic. I wouldn't map it onto types. You are mixin different things: order is a relation -> (generic) method fuzzy uses discrete states -> can be types or predicates stochastic relies on probability -> functions -> (generic) method. once these points are identified, design is easier and less confused. >>note that generic, classA and classB are polymorphic types which allows >>to write a generic version of say isCommutative >> >>bool isCommutative(Generic g, Class c1, Class c2) { >> return respondsTo(g, c1, c2) && respondsTo(g, c2, c1); >>} > > > It is still not what is needed. First it has an explicit parameter > "generic" which deals with the tags of the parameters. Secondly it does not > dispatches on c1 and c2, but on g. It is looks as a nasty hack. I start to understand why you do not see the point: you don't know what is a generic in the sens of multimethod. Let me explain a bit: - generics are instances of the class Generic. - methods are instances of the class Method (i.e. what is returned by the dispatcher). Each method is attached to its generic, that is the generic with the same name. For simplicity, you can see this relation as a dictionnary: generic -> list of methods where name(method) == name(generic). - each method instance has an implementation which corresponds to a unique specialization of its generic. - Methods are distinguished by their generic *and* by their specializer (the types of the parameters). Therefore in the above isCommutative example (which is a simple function, not a method nor a generic), the result changes if you change any value amongst g, c1 or c2. This is not a hack, this is how the dispatcher works for multimethod in many language and this gives a great flexibility. a method invocation looks like: c = add(a,b); where add is the generic, a, b and c are instance of some class say A, B and C and the method invoked is selected by taking into account the generic add, the type of the object a that is A and the type of the object b that is B. This method will be add(A,B) or a less specialized version if it does not exist (see my first post about list specialization). [...] > Ah, but that would mean that the type changes even if the value does not. Yes! A typical application is an IOStream. When you switch from an OutStream to an InStream, you flush the buffer (if any) and change the type OutStream->InStream, that's all. No need for MI, much simpler, no burden about duplicated states or incompatible behavior. What is *really* changing is the type, that is the set of applicable methods (read methods instead of write methods), that is the behavior. Of course, you can also change some fields values. What you have *really* done is changing the behavior of an object, nothing else. But this is one of the most difficult task in statically typed languages because in order to have the same effect, you need a consistent state machine manually managed in the back where DI+MMD does it naturally (see the slides ;-) ). And think about what happen when a new state is added! > I'm not ready to accept that. Why? a+, ld.
From: Laurent Deniau on 23 Mar 2006 04:07 Laurent Deniau wrote: > Dmitry A. Kazakov wrote: >>> note that generic, classA and classB are polymorphic types which >>> allows to write a generic version of say isCommutative >>> >>> bool isCommutative(Generic g, Class c1, Class c2) { >>> return respondsTo(g, c1, c2) && respondsTo(g, c2, c1); >>> } One more thing about this code since I already hear your question ;-) If you want to know if the behavior is commutative (usually the property that we are looking for), the code above is of course incomplete and must be extended to values, that is objects: bool isCommutative(Generic g, object o1, object o2) { return respondsTo(g, o1, o2) && respondsTo(g, o2, o1) && equal(g(o1,o2) , g(o2,o1)); } a+, ld.
From: Dmitry A. Kazakov on 23 Mar 2006 10:25 On Wed, 22 Mar 2006 15:45:05 +0100, Laurent Deniau wrote: > Dmitry A. Kazakov wrote: >> On Tue, 21 Mar 2006 16:00:31 +0100, Laurent Deniau wrote: >> I see. But this is a different story. You want to dispatch to Shark and >> then to make something different out of it. The question is how different >> that might be. Will it be a Shark, a Fish etc. > > Again, it does not change. Only its type (hidden as part of its value) > changes and this is something hidden to the user (like HealthyShark and > InjuredShark are) and is managed automatically by MD. For example in > some Objective-C implementation (Smalltalk?) when you create a String, > it is never a String instance but something else with a mutating type > which changes depending on the operations you will apply to it and some > rules. String is only a king of interface (an ADT) to a cluster of > classes. An even simpler example would be Complex as an interface (ADT) > of RectComplex and PolarComplex and where toPolar(CartComplex) and > toRect(PolarComplex) would be the methods which switch the intances type. If type changes what remains? In my view objects do not exist after types. If you change the type, you change the object as well. Maybe the new object is allocated at the same memory location and has the same bit pattern. That's irrelevant. It is a new object of another type. The example with Complex goes as follows. Complex'Class is the class of complex types. PolarComplex is derived from Complex (member of the class). RectComplex is a sibling. ToPolar can be defined as: function ToPolar (X : PolarComplex) return RectComplex; Note that it is not a member of Complex. There is a good reason why. Complex knows nothing about representations and interfaces of its descendants. A much better design is double dispatching assignment: function ":=" (Source : Complex) return Complex; X : PolarComplex; Y : RectComplex := X; -- Done! ":=" dispatches on its argument (PolarComplex) and the expected result (RectComplex.) As simple as that! > I agree that MD + DI mix in behavior and state (in a very convenient way > to my opinion) using the fact that behavior is related to type and type > is a value, that is a state (remember classes are objects). This is bad because switching of states associated with types is the behavior of higher order objects - classes. One should not mix them. Types define the behavior of values. When types are themselves values, then it is types type (a class) to define that. If you mix them, I can get nasty problems. You can easily finish up with sets having themselves as members. > Predicate dispatch allows the object type to be the state and MD > describes naturally the different behaviors (method specialization) like > in the slides I pointed out. No nested if-then-else are required. This > programming approach is simply a natural extension of method overriding > which can also be done by static binding and type-case tests after all. I don't object this. I do, that one would need type mutators to make this schemata working. One does not imply other. >>>note that generic, classA and classB are polymorphic types which allows >>>to write a generic version of say isCommutative >>> >>>bool isCommutative(Generic g, Class c1, Class c2) { >>> return respondsTo(g, c1, c2) && respondsTo(g, c2, c1); >>>} >> >> It is still not what is needed. First it has an explicit parameter >> "generic" which deals with the tags of the parameters. Secondly it does not >> dispatches on c1 and c2, but on g. It is looks as a nasty hack. > > I start to understand why you do not see the point: you don't know what > is a generic in the sens of multimethod. Let me explain a bit: You have explained the mechanics behind polymorphic subroutines. I have no problem with that. You can treat all polymorphic subroutines as objects of some common type. That's no problem. But it also solves nothing. Because it lies elsewhere. It is orthogonal to what happens with the classes c1 and c2. [ Potentially, one could derive some "Commutative" class from "Method", which would describe all commutative signatures and then, somehow tell "add" of c1 and c2 that it is from that class. Maybe it will work, maybe not. In any case, it is not a question about types. It is about types of types. And in any case the problem of parallel hierarchies will reappear. You have a hierarchy of Method<--Commutative and c1<--c2<--. "add" is present in both. If I derive Commutative<--Commutative_With_Identity_Element and c2<-c3. Then what if c3 will have 0? ] >> Ah, but that would mean that the type changes even if the value does not. > > Yes! It is a big NO-NO to me. > A typical application is an IOStream. When you switch from an > OutStream to an InStream, you flush the buffer (if any) and change the > type OutStream->InStream, that's all. Why should I? If I needed it, I would simply make it a constraint rather than a type. > No need for MI, much simpler, no > burden about duplicated states or incompatible behavior. What is > *really* changing is the type, that is the set of applicable methods > (read methods instead of write methods), that is the behavior. Of > course, you can also change some fields values. What you have *really* > done is changing the behavior of an object, nothing else. But this is > one of the most difficult task in statically typed languages because in > order to have the same effect, you need a consistent state machine > manually managed in the back where DI+MMD does it naturally (see the > slides ;-) ). And think about what happen when a new state is added! I derive a new subtype then. >> I'm not ready to accept that. > > Why? Because I want to go in exactly the opposite direction. That is - true ADT, which would completely abstract any representation. The goal is to have objects which behavior is fully independent on any concrete implementation. And if it is the type, to determine the behavior, then you simply cannot change it, because there is nothing you can apply this change to. Neither address, nor bit pattern, nor size is available beyond the type. Absolutely nothing. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de
From: Laurent Deniau on 24 Mar 2006 11:39 Dmitry A. Kazakov wrote: > On Wed, 22 Mar 2006 15:45:05 +0100, Laurent Deniau wrote: > > >>Dmitry A. Kazakov wrote: >> >>>On Tue, 21 Mar 2006 16:00:31 +0100, Laurent Deniau wrote: >>>I see. But this is a different story. You want to dispatch to Shark and >>>then to make something different out of it. The question is how different >>>that might be. Will it be a Shark, a Fish etc. >> >>Again, it does not change. Only its type (hidden as part of its value) >>changes and this is something hidden to the user (like HealthyShark and >>InjuredShark are) and is managed automatically by MD. For example in >>some Objective-C implementation (Smalltalk?) when you create a String, >>it is never a String instance but something else with a mutating type >>which changes depending on the operations you will apply to it and some >>rules. String is only a king of interface (an ADT) to a cluster of >>classes. An even simpler example would be Complex as an interface (ADT) >>of RectComplex and PolarComplex and where toPolar(CartComplex) and >>toRect(PolarComplex) would be the methods which switch the intances type. > > > If type changes what remains? In my view objects do not exist after types. > If you change the type, you change the object as well. It is a restrictive point of view. > Maybe the new object > is allocated at the same memory location and has the same bit pattern. > That's irrelevant. It is a new object of another type. What happens if you have many "views" of this object (e.g. reference to)? > The example with Complex goes as follows. Complex'Class is the class of > complex types. PolarComplex is derived from Complex (member of the class). > RectComplex is a sibling. ToPolar can be defined as: > > function ToPolar (X : PolarComplex) return RectComplex; I would have suggested: function ToPolar (X : RectComplex) return PolarComplex; > Note that it is not a member of Complex. There is a good reason why. > Complex knows nothing about representations and interfaces of its > descendants. > > A much better design is double dispatching assignment: > > function ":=" (Source : Complex) return Complex; > > X : PolarComplex; > Y : RectComplex := X; -- Done! > > ":=" dispatches on its argument (PolarComplex) and the expected result > (RectComplex.) As simple as that! It not that simple. What you describe is the visitor pattern known for at least a decade, nothing new then. Everybody knows the problems solved and inherent to this pattern. Multimethods are often seen as the solution to the problem of this pattern. And this pattern is often used to simulate multimethods when not supported. >>I agree that MD + DI mix in behavior and state (in a very convenient way >>to my opinion) using the fact that behavior is related to type and type >>is a value, that is a state (remember classes are objects). > > > This is bad because switching of states associated with types is the > behavior of higher order objects - classes. This is what I am talking about from the beginning. The switch of type is an internal behavior to simulate a state machine and automatically managed by the dispatcher instead by the programmer. Only a class can change the type of its instances and this change has to respect some constraints. > One should not mix them. Types > define the behavior of values. When types are themselves values, then it is > types type (a class) to define that. Also called metaclass, a powerful notion known for decades and well defined. > If you mix them, I can get nasty > problems. You can easily finish up with sets having themselves as members. Not possible. Metaclasses allow either parallel hierarchy (one metaclass per class), either a projection of hierarchy (one metaclass for many classes). Prototype bases langages (Self, Cecil, Slate) allow even more flexibility and complex constructions. > Because I want to go in exactly the opposite direction. That is - true ADT, > which would completely abstract any representation. The goal is to have > objects which behavior is fully independent on any concrete > implementation. In dynamic typing languages, all instances are ADTs. The user only sees methods and knows nothing about the representation or even the type of the objects including classes (except if he queries for knowing it using the appropriate method). This is fully *behavior* oriented, the topic of my question... May I suggest a simple thing? Write a formal implementation of the algorithm described in the slides I cited and let see if it is closer to what is shown p5, p8 or p15. Then we will see what needs to be modified to add a new type of Shark, say a BigShark with its states Healthy and Injured. a+, ld.
From: Dmitry A. Kazakov on 24 Mar 2006 18:09
On Fri, 24 Mar 2006 17:39:30 +0100, Laurent Deniau wrote: > Dmitry A. Kazakov wrote: >> On Wed, 22 Mar 2006 15:45:05 +0100, Laurent Deniau wrote: >> >>>Dmitry A. Kazakov wrote: >>> >> Maybe the new object >> is allocated at the same memory location and has the same bit pattern. >> That's irrelevant. It is a new object of another type. > > What happens if you have many "views" of this object (e.g. reference to)? Depends on what you mean under reference. When reference is an object (like pointer), then it is not a view, but a distinct object of different type. When reference means "by-reference", then it is an implementation detail. When you mean a partial view like "const", then it is a constrained type. In my world, each time you switch the type, even if that means just putting a constraint on it, you change the object. This types conversion might be an identity (null) operation, but it is present. Otherwise, one should consider multiple types of the same object, which is admittedly doable, but represents a sufficiently more complex model, which advantages are not obvious to me. >> The example with Complex goes as follows. Complex'Class is the class of >> complex types. PolarComplex is derived from Complex (member of the class). >> RectComplex is a sibling. ToPolar can be defined as: >> >> function ToPolar (X : PolarComplex) return RectComplex; > > I would have suggested: > > function ToPolar (X : RectComplex) return PolarComplex; Yes, of course. It was a typo error on my side. >> Note that it is not a member of Complex. There is a good reason why. >> Complex knows nothing about representations and interfaces of its >> descendants. >> >> A much better design is double dispatching assignment: >> >> function ":=" (Source : Complex) return Complex; >> >> X : PolarComplex; >> Y : RectComplex := X; -- Done! >> >> ":=" dispatches on its argument (PolarComplex) and the expected result >> (RectComplex.) As simple as that! > > It not that simple. What you describe is the visitor pattern known for > at least a decade, nothing new then. Everybody knows the problems solved > and inherent to this pattern. Multimethods are often seen as the > solution to the problem of this pattern. And this pattern is often used > to simulate multimethods when not supported. So we could agree upon. That multimethod would solve this particular case without mutating types? >>>I agree that MD + DI mix in behavior and state (in a very convenient way >>>to my opinion) using the fact that behavior is related to type and type >>>is a value, that is a state (remember classes are objects). >> >> This is bad because switching of states associated with types is the >> behavior of higher order objects - classes. > > This is what I am talking about from the beginning. The switch of type > is an internal behavior to simulate a state machine and automatically > managed by the dispatcher instead by the programmer. I fully agree with that. Dispatching changes the type from the class (polymorphic) to a specific type (non-polymorphic.) This is why I think that C++'s re-dispatch in methods was a big mistake. But in my view dispatch clearly changes the object. This is very important for handling the cases when objects are small. So changing the type of, say, polymorphic Boolean'Class might mean stripping away the type tag and producing exactly one bit Boolean. Note that this by no means would require mutating types. Even for in-out parameters: you create a new object pass it down to the method and then convert the result back. > Only a class can > change the type of its instances and this change has to respect some > constraints. You can simplify it by melting the constraints with the class and saying that the only constraint is that the result is in the class. >> Because I want to go in exactly the opposite direction. That is - true ADT, >> which would completely abstract any representation. The goal is to have > > objects which behavior is fully independent on any concrete > > implementation. > > In dynamic typing languages, all instances are ADTs. The user only sees > methods and knows nothing about the representation or even the type of > the objects including classes (except if he queries for knowing it using > the appropriate method). This is fully *behavior* oriented, the topic of > my question... Then I don't see why you insist on changing behavior of something that consists only of the behavior. You just cannot do that, because there is no way to mark the rest. You need some method to identify the object. But identification by a method is also a behavior. No way. > May I suggest a simple thing? Write a formal implementation of the > algorithm described in the slides I cited and let see if it is closer to > what is shown p5, p8 or p15. Then we will see what needs to be modified > to add a new type of Shark, say a BigShark with its states Healthy and > Injured. Ah, it is difficult, because I am not convinced that MD is needed for Encounter. The behavior of primitive animals does not vary that much. One estimates another and then tries to attack, ignore or flee. Depending on the intent of both, the result is an attack, hunt, ignoring, fight, dispersing or fleeing. So this is class-wide, i.e. all descendants of Fish share the behavior in Encounter: type Estimation is (Weaker, Same, Stronger); type Fish is ...; function Estimate (Self : X; Other : Y) return Estimation; procedure Attack (Predator, Prey : in out Fish); procedure Hunt (Predator, Prey : in out Fish); procedure Ignore (One, Another : in out Fish); procedure Fight (One, Another : in out Fish); procedure Disperse (One, Another : in out Fish); procedure Flee (Standing, Running : in out Fish); procedure Encounter (X, Y : in out Fish'Class) is begin case Estimate (X, Y) is when Weaker => case Estimate (Y, X) is when Weaker => Disperse (Y, X); when Same => Flee (Y, X); when Stronger => Hunt (Y, X); end case; when Same => case Estimate (Y, X) is when Weaker => Flee (X, Y); when Same => Ignore (X, Y); when Stronger => Attack (Y, X); end case; when Stronger => case Estimate (Y, X) is when Weaker => Hunt (X, Y); when Same => Attack (X, Y); when Stronger => Fight (X, Y); end case; end case; end Encounter; A more realistic model would be repetitive state modification and undertaking actions depending on the fish's state and the state of the environment. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de |