multimethod + multiple inheritance
in [OOP]
|
From: Dmitry A. Kazakov on 20 Mar 2006 09:10 On Mon, 20 Mar 2006 11:00:56 +0100, Laurent Deniau wrote: > No. It is the ability to change the class (and the type) of an object at > runtime. It is usually supported by language with dynamic typing or > Prototype language both with dynamic dispatch and it can be simulated by > language with predicate dispatch. The only languages I am aware of which > support static type checking and dynamic multiple inheritance (but with > some constraints) are the gbeta and caesarJ languages, see the papers > "Safe dynamic multiple inheritance" and "A virtual class calculus" from > E. Ernst for more information. I don't see use cases for changing the class. One could allow changing the specific type. I.e. let you have a polymorphic object, which consists of the type tag and the corresponding specific object. You could change the tag and replace the specific object. The following is legal Ada: X : T1; -- T1 is derived from T Y : T1; -- T1 is derived from T Z : T2; -- T2 is derived from T Chameleon : T'Class := X; begin Chameleon := Y; -- This is OK Chameleon := Z; -- Raises Constraint_Error Ada does not allow changing type tags, but this is not a compile-time constraint! BTW, there are good arguments for not changing the type tags (stack memory allocation issues.) Then with a really good ADT one could achieve the same effect using safe referential types (handles.) >> Anyway, I don't see how to avoid "diamond diagram" if not by shifting all >> the burden to the programmer. > > This is exactly my question except that I do not have examples (in this > context: SI + dynamic multimethod + dynamic inheritance) where MI is > required ;-) IMO, there is no any. For mutating classes one should just use Any'Class. Mutating types are not so obvious, but transparent handles could do the job. >> IMO, it is like multiple dispatch, one can >> emulate it using SI, and have countless problems with implementing quite >> idiotic patterns. > > Yes but in this case, you have a problem solved by O(2N^P) methods > instead of O(N*P) multimethods, where N is the number of the classes > overriding the less specialized multimethod and P the number of > specializer of the multimethod. Looks like something hard to do by hand > with SI when N > 2 and P >= 2. Geometrical explosion is not the only problem, IMO, unknown siblings seem worse. >> From a bird's perspective, either MI should have a feasible and efficient >> implementation, or there must be something badly wrong with the whole >> concept of inheritance, subtyping, subclassing etc. I don't believe in the >> latter. > > Implementing MI *is* feasible with good efficiency (both size and speed) > otherwise I would not ask my question ;-) But when you want to implement > MI as aggregation with nearly the efficiency of SI then you start to > touch the state of the art of MI implementation, specially when > implementing object construction and destruction, "virtual" method > invocation and C++ like dynamic_cast operator. Ah, construction and destruction is complete rubbish in all languages I know! (:-)) This is yet another unsolved problem: extensible polymorphic methods. In my view one cannot solve construction/destruction controversy without separation classes and types. If you have it, then you can have distinct class and type constructors. Class constructors could then take care of MI components, and dispatch within the body. I think that T != T'Class is the crux of types systems yet to come. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de
From: Laurent Deniau on 20 Mar 2006 13:11 Dmitry A. Kazakov wrote: > On Mon, 20 Mar 2006 11:00:56 +0100, Laurent Deniau wrote: > > >>No. It is the ability to change the class (and the type) of an object at >>runtime. It is usually supported by language with dynamic typing or >>Prototype language both with dynamic dispatch and it can be simulated by >>language with predicate dispatch. The only languages I am aware of which >>support static type checking and dynamic multiple inheritance (but with >>some constraints) are the gbeta and caesarJ languages, see the papers >>"Safe dynamic multiple inheritance" and "A virtual class calculus" from >>E. Ernst for more information. > > > I don't see use cases for changing the class. One could allow changing the > specific type. I.e. let you have a polymorphic object, which consists of > the type tag and the corresponding specific object. You could change the > tag and replace the specific object. The following is legal Ada: > > X : T1; -- T1 is derived from T > Y : T1; -- T1 is derived from T > Z : T2; -- T2 is derived from T > Chameleon : T'Class := X; > begin > Chameleon := Y; -- This is OK > Chameleon := Z; -- Raises Constraint_Error > > Ada does not allow changing type tags, but this is not a compile-time > constraint! > > BTW, there are good arguments for not changing the type tags (stack memory > allocation issues.) Then with a really good ADT one could achieve the same > effect using safe referential types (handles.) But dynamic inheritance (or predicate dispatch) allows a lot of simplification when algorithms and/or objects use states to drive their behavior. As a simple example, you can read the slides (very short and easy): http://tunes.org/~eihrul/talk.pdf This is a Slate example about the multimethod dispatch with protypes, something very close to what I do. Another example with MI is shown in the Cecil documentation, p22: http://www.cs.washington.edu/research/projects/cecil/www/Release/doc-cecil-lang/cecil-spec.ps.gz >>>Anyway, I don't see how to avoid "diamond diagram" if not by shifting all >>>the burden to the programmer. >> >>This is exactly my question except that I do not have examples (in this >>context: SI + dynamic multimethod + dynamic inheritance) where MI is >>required ;-) > > > IMO, there is no any. For mutating classes one should just use Any'Class. > Mutating types are not so obvious, but transparent handles could do the > job. But handles + multimethod bring us back to a geometric complexity behind the scene and/or problems with unforeseen extensions. >>>IMO, it is like multiple dispatch, one can >>>emulate it using SI, and have countless problems with implementing quite >>>idiotic patterns. >> >>Yes but in this case, you have a problem solved by O(2N^P) methods >>instead of O(N*P) multimethods, where N is the number of the classes >>overriding the less specialized multimethod and P the number of >>specializer of the multimethod. Looks like something hard to do by hand >>with SI when N > 2 and P >= 2. > > > Geometrical explosion is not the only problem, IMO, unknown siblings seem > worse. I agree, this is why I prefer SI+multimethods than MI+single_methods, the former being even simpler than the later to implement. a+, ld.
From: Dmitry A. Kazakov on 21 Mar 2006 07:49 On Mon, 20 Mar 2006 19:11:28 +0100, Laurent Deniau wrote: > Dmitry A. Kazakov wrote: >> On Mon, 20 Mar 2006 11:00:56 +0100, Laurent Deniau wrote: >> >>>No. It is the ability to change the class (and the type) of an object at >>>runtime. It is usually supported by language with dynamic typing or >>>Prototype language both with dynamic dispatch and it can be simulated by >>>language with predicate dispatch. The only languages I am aware of which >>>support static type checking and dynamic multiple inheritance (but with >>>some constraints) are the gbeta and caesarJ languages, see the papers >>>"Safe dynamic multiple inheritance" and "A virtual class calculus" from >>>E. Ernst for more information. >> >> I don't see use cases for changing the class. One could allow changing the >> specific type. I.e. let you have a polymorphic object, which consists of >> the type tag and the corresponding specific object. You could change the >> tag and replace the specific object. The following is legal Ada: >> >> X : T1; -- T1 is derived from T >> Y : T1; -- T1 is derived from T >> Z : T2; -- T2 is derived from T >> Chameleon : T'Class := X; >> begin >> Chameleon := Y; -- This is OK >> Chameleon := Z; -- Raises Constraint_Error >> >> Ada does not allow changing type tags, but this is not a compile-time >> constraint! >> >> BTW, there are good arguments for not changing the type tags (stack memory >> allocation issues.) Then with a really good ADT one could achieve the same >> effect using safe referential types (handles.) > > But dynamic inheritance (or predicate dispatch) allows a lot of > simplification when algorithms and/or objects use states to drive their > behavior. As a simple example, you can read the slides (very short and > easy): > > http://tunes.org/~eihrul/talk.pdf > > This is a Slate example about the multimethod dispatch with protypes, > something very close to what I do. I still don't see how this could justify need in mutating types. In the example given, in all its roles a fish remains fish. It is clear that Encounter(X : in out Fish; Y : in out Fish); must be a multimethod. But the effect of this method does not change the types of any objects involved. When X eats Y both remain in the class of fishes. Their specific types stay constant as well. Even if the prey were contaminated with radioactive elements, that wouldn't cause the predator to become, say, a star ship, in the next generation, maybe. (:-)) >>>>Anyway, I don't see how to avoid "diamond diagram" if not by shifting all >>>>the burden to the programmer. >>> >>>This is exactly my question except that I do not have examples (in this >>>context: SI + dynamic multimethod + dynamic inheritance) where MI is >>>required ;-) >> >> IMO, there is no any. For mutating classes one should just use Any'Class. >> Mutating types are not so obvious, but transparent handles could do the >> job. > > But handles + multimethod bring us back to a geometric complexity behind > the scene and/or problems with unforeseen extensions. Right. Handles as subtypes of the objects they point to, are only to solve the problem of mutating types. They don't solve the problem of multiple dispatch, which I see as an independent problem. The signature matching rules don't solve that problem either. They reduce the space of choices by projecting it onto another space of lesser dimension. For example, delegation presumes that the space is decomposable to a Cartesian product. But, alas, there is no such projection which would fit for all possible scenarios. So it is a fundamentally flawed way, IMO. A right one, could be to allow the programmer to specify a-priory known [= from the application domain] groups of symmetry and let the compiler to use them to reduce the number of variants. For example, I'd like to be able to express things like: "this operation is commutative." In the example with fishes, you have a parallel hierarchy of prey-predator relation. The problem there is, IMO, not in MD, but in an inability to express and handle parallel types hierarchies. This is tightly related to MI and interfaces. Shark is a fish, it is a predator and it also is a prey. But it is not so that it becomes not a shark when you hunt it. It is still a shark. So take care, it can bite you! -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de
From: Laurent Deniau on 21 Mar 2006 10:00 Dmitry A. Kazakov wrote: > On Mon, 20 Mar 2006 19:11:28 +0100, Laurent Deniau wrote: > I still don't see how this could justify need in mutating types. In the > example given, in all its roles a fish remains fish. It is clear that > > Encounter(X : in out Fish; Y : in out Fish); > > must be a multimethod. Yes. > But the effect of this method does not change the > types of any objects involved. Yes it does. > When X eats Y both remain in the class of > fishes. Their specific types stay constant as well. Not in the example. Shark is a specialization of (derived from) Fish and HealthyShark and InjuredShark are specializations of (derived from) Shark. Therefore in MD: Encounter(X : in out Shark; Y : in out Fish); - is also a multimethod refering to the same generic method - overrides Encounter(Fish; Fish); (differs from C++) - has a different behavior from Encounter(Fish; Fish); Same for Encounter(HealthyShark; Fish) vs Encounter(Shark; Fish) and Encounter(HealthyShark; Shark) vs Encounter(HealthyShark; Fish), the latter being the most specialized override of Encounter(Fish; Fish) of this example. In Encounter(HealthyShark; Shark), the type of X will switch from an HealthyShark to an InjuredShark. The type of X is used to modelize a *state* change of X and this is call predicate dispatch or sometimes (more restrictive) dynamic inheritance. Then instead of having all the methods of Shark (or even Fish which may not be aware of this state) checking whether X is Healthy or not, the MD does the work automatically and no more code is required. This is one of the most flexible pattern I know and it is extensively use in class' clusters design. This makes the algorithm of slide 15 much simpler than its original version slide 5. > A right one, could be to allow the programmer to specify a-priory known [= > from the application domain] groups of symmetry and let the compiler to use > them to reduce the number of variants. For example, I'd like to be able to > express things like: "this operation is commutative." This is not possible since it is related to a combination of the operation plus an ordered set of parameter types. This is one of the problems of C++ templates that concept checking tries to solve (see C++ n1886). That is specializing properties of operations for a set of types without describing all the variant. Otherwise complex types hierarchies, intermediate template functions and template specializations must be produced to achieve the same result (see boost concept). On the side of MD, you can use something like if (respondsTo(generic, classA, classB) && respondsTo(generic, classB, classA)) { code assuming the method specialization of the generic is commutative for classA and classB } 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); } > In the example with fishes, you have a parallel hierarchy of prey-predator > relation. The problem there is, IMO, not in MD, but in an inability to > express and handle parallel types hierarchies. This is tightly related to > MI and interfaces. Shark is a fish, it is a predator and it also is a prey. No, this is related to relation between types. A Shark is a Fish in any context but it is a Predator only for some other types and a Prey for say the complementary set of applicable types. IMHO, this has nothing to do with MI nor interfaces except that the latter can simulate the behavior in a very inflexible way. This where MD is very useful. a+, ld.
From: Dmitry A. Kazakov on 22 Mar 2006 05:57
On Tue, 21 Mar 2006 16:00:31 +0100, Laurent Deniau wrote: > Dmitry A. Kazakov wrote: >> On Mon, 20 Mar 2006 19:11:28 +0100, Laurent Deniau wrote: >> I still don't see how this could justify need in mutating types. In the >> example given, in all its roles a fish remains fish. It is clear that >> >> Encounter(X : in out Fish; Y : in out Fish); >> >> must be a multimethod. > > Yes. > >> But the effect of this method does not change the >> types of any objects involved. > > Yes it does. > >> When X eats Y both remain in the class of >> fishes. Their specific types stay constant as well. > > Not in the example. Shark is a specialization of (derived from) Fish and > HealthyShark and InjuredShark are specializations of (derived from) > Shark. Therefore in MD: > > Encounter(X : in out Shark; Y : in out Fish); > > - is also a multimethod refering to the same generic method > - overrides Encounter(Fish; Fish); (differs from C++) > - has a different behavior from Encounter(Fish; Fish); I don't understand this. Encounter is polymorphic in both parameters. This precisely means, that it is defined on each combination of specific types T1 x T2, derived from Fish. Because Shark is in Fish'Class this of course includes Encounter(X : in out Shark; Y : in out Fish); Which is in my view just an overriding. It is not a separate method but an implementation of Encounter(X : in out Fish; Y : in out Fish); for Shark x Fish. > In Encounter(HealthyShark; Shark), the type of X will switch from an > HealthyShark to an InjuredShark. The type of X is used to modelize a > *state* change of X and this is call predicate dispatch or sometimes > (more restrictive) dynamic inheritance. 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. You can describe that without type mutators: Encounter ( X : in Fish; Y : in Fish; NewX out Fish'Class; -- It cannot become a star ship NewY out Fish'Class ); Now Encounter dispatches on two original objects and creates two new. It is just a double abstract factory. Though I doubt that an InjuredShark is a distinct type of species. > Then instead of having all the > methods of Shark (or even Fish which may not be aware of this state) > checking whether X is Healthy or not, the MD does the work automatically > and no more code is required. This is one of the most flexible pattern I > know and it is extensively use in class' clusters design. It is a misuse of type system in my eyes. To me healthy, injured, fat are states, not types. 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. Unless you'd introduce indiscrete, non-deterministic type system [that might turn an interesting speculation.] My rule of thumb is: anything that can be a value must be. Only if it cannot, then consider it being a type. If that is impossible, consider it class. Things sufficiently grow in complexity as we ascend the ladder: value->type->class->types set->... > This makes the algorithm of slide 15 much simpler than its original > version slide 5. >> A right one, could be to allow the programmer to specify a-priory known [= >> from the application domain] groups of symmetry and let the compiler to use >> them to reduce the number of variants. For example, I'd like to be able to >> express things like: "this operation is commutative." > > This is not possible since it is related to a combination of the > operation plus an ordered set of parameter types. This is one of the > problems of C++ templates that concept checking tries to solve (see C++ > n1886). That is specializing properties of operations for a set of types > without describing all the variant. Otherwise complex types hierarchies, > intermediate template functions and template specializations must be > produced to achieve the same result (see boost concept). > > On the side of MD, you can use something like > > if (respondsTo(generic, classA, classB) && > respondsTo(generic, classB, classA)) { > code assuming the method specialization of the generic is commutative > for classA and classB > } > > 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. Basically, what is needed is to define implementations for some combination of types through implementation for other combination on the whole class. For example, in some imaginary syntax, a symmetric relation could be described as: function Symmetric (C1, C2 : T) return Boolean when C1'Tag < C2'Tag or C1'Tag = C2'Tag is abstract; -- To be overridden in all descendants function Symmetric (C1, C2 : T) return Boolean when C2'Tag <: C1'Tag is begin return Symmetric (C2, C1); end Symmetric; -- To be inherited by all descendants Here "when" clause filters out some variants, namely ones where the first parameter is closer to the root of the class. C'Tag denotes the object type tag. The compiler is required to check that the union of all "when" statically yields true. >> In the example with fishes, you have a parallel hierarchy of prey-predator >> relation. The problem there is, IMO, not in MD, but in an inability to >> express and handle parallel types hierarchies. This is tightly related to >> MI and interfaces. Shark is a fish, it is a predator and it also is a prey. > > No, this is related to relation between types. A Shark is a Fish in any > context but it is a Predator only for some other types and a Prey for > say the complementary set of applicable types. Ah, but that would mean that the type changes even if the value does not. I'm not ready to accept that. > IMHO, this has nothing to > do with MI nor interfaces except that the latter can simulate the > behavior in a very inflexible way. This where MD is very useful. Yes it is, but only to save types. MD moves the issue of "predator hunts prey" from individual objects to the tuples of objects. If Hunt is associated with one type then there indeed mutating objects could appear. But if it is with a tuple then whether shark is a prey would depend on Hunt, not on Shark. MI is here to mix prey->predator pyramid with species hierarchy. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de |