multimethod + multiple inheritance
in [OOP]
|
From: S Perryman on 15 Mar 2006 03:52 "Laurent Deniau" <laurent.deniau(a)cern.ch> wrote in message news:dv6v27$o6o$1(a)sunnews.cern.ch... > Dmitry A. Kazakov wrote: >> On Mon, 13 Mar 2006 18:30:03 +0100, Laurent Deniau wrote: >>>In fact MI plays a role on both sides: on the dispacher side because >>>object's offset adjustment must be stored in the cache but also on the >>>call-site side because the address of the object must be passed to the >>>dispatcher to apply this offset adjusment, and this (roughly) double the >>>code generated to dispatch the message. >> I wouldn't count it on account of dispatch, because even if the target >> is >> statically known, you will need to shift the address. In fact, it is type >> conversion penalty. > This is on the side of the dispatcher where I agree, object must be > shifted according to their (most derived) types and the expected types of > the selected method. For the caller side, I am refering to the fact that > the address of the objects have to be passed. > for SI, the dispatch looks like: > return ((generic_type)find_method(generic, obj1, obj2)) (obj1, obj2); > but for MI, the dispatch looks like: > generic_type mth = (generic_type)find_method(generic, &obj1, &obj2); > return mth(obj1, obj2); > where find_method returns a pointer to the selected method to invoke. CLOS forms a topological ordering of the inheritance lattice does it not. How does this affect or compare to op selection (code size, performance etc) for a single inheritance hierarchy of similar size ?? Regards, Steven Perryman
From: Dmitry A. Kazakov on 15 Mar 2006 04:12 On Tue, 14 Mar 2006 18:37:52 +0100, Laurent Deniau wrote: > Dmitry A. Kazakov wrote: >> On Mon, 13 Mar 2006 18:30:03 +0100, Laurent Deniau wrote: >>>Dmitry A. Kazakov wrote: >>>>If dispatching tables are associated with functions >>>>then it is the dimension of the table to determine the penalty. >>>>MI, alone, should play no role here, as a guess. >>> >>>In fact MI plays a role on both sides: on the dispacher side because >>>object's offset adjustment must be stored in the cache but also on the >>>call-site side because the address of the object must be passed to the >>>dispatcher to apply this offset adjusment, and this (roughly) double the >>>code generated to dispatch the message. >> >> I wouldn't count it on account of dispatch, because even if the target is >> statically known, you will need to shift the address. In fact, it is type >> conversion penalty. > > This is on the side of the dispatcher where I agree, object must be > shifted according to their (most derived) types and the expected types > of the selected method. For the caller side, I am refering to the fact > that the address of the objects have to be passed. I didn't understand it. Why do you need addresses? To make dispatch decision you need type tags of the objects, not the objects themselves. [ If I designed an OO language I'd try not to embed tags into objects, but pass them independently in a dope. This could eliminate contamination of objects by type tags, which becomes especially disastrous for MI. Type tags could also support views, i.e. a tag could tell - this is B viewed as A. ] >>>I >>>expect that when you say "For safety reasons" you are referring to the >>>constraints applied to parameters (covariance / contravariance of >>>types). But these constraints do not apply to multimethod dynamic >>>dispatch because the overriding mechanism differs from static type >>>systems. For example, as you say, in a static type system like in C++ or >>>Java, it is important that f(B,B), f(B,C), f(C,B) use different slots in >>>the virtual table(s) and do not override each other (limiting somehow >>>the subtyping polymorphism), while in dynamic dispatch they use the same >>>slot: f(B,B) overrides f(B,C) which overrides the less specialized >>>method f(C,B), if we consider my 2nd list of linearization. This is >>>still safe since the dispatcher always propagates the most derived type >>>i.e. A. >> >> Hmm, I don't think that there is some special "dynamic" way. Whether f(B,B) >> may override f(B,C) depends solely on the relations between B and C. It >> depends on whether B is a specialization or generalization if C and on the >> parameter mode (in, out or in out.) The problem is that substitutability is >> not checkable either statically or dynamically, so the language should >> rather rely on the programmer here. > > No, the fact that B inherits from C is checkable at runtime (but not at > compile time of course). In fact multimethod dynamic dispatch is safer > than say Java interfaces since the method selection is done by the > dispatcher which ensures de facto the correctness of the objects types. I didn't mean type correctness, I did substitutability. You can check types, but you cannot map substitutability onto types, only partially. This is why famous Circle-Ellipse controversy arise. Consider B, a specialization of C. Then not every C is B. This means that Foo having B as an out parameter (or as a mutator in out) cannot be safely inherited in C, because it might change C to something that isn't C. Similarly generalization has problems with in parameters. And there are lots of practical cases where C is nether generalization, nor specialization of B. That means that all methods [= subprograms covariant in the corresponding parameters] are potentially unsafe to inherit. This problem need to be addressed. > While in Java interface, the programmer has to check the type of the > extra objects passed to the method since only the first one is truly > checked by the method dispatch, the static types of the other objects > being lost (e.g. compareTo, equalTo, lessThan, copyTo). This is because of design fault of Java, which does not have multiple dispatch. Many OO languages suffered from prefix notation. [ X.Foo() to be considered harmful! (:-)) ] > C++ on his side restricts subtyping polymorphism because static typing > cannot ensure the type correctness for such overriding. No. Formally, it is type correct. The second parameter is contravariant in C++. The problem is rather mental, the programmer uses a contravariant parameter as if that were covariant. The choices the language makes shall be safe. That is: all parameters and the results should be covariant by default. Prefix notation should be forbidden for multimethods. No "this", "self" rubbish. > This is a > tradeoff between flexibility and safety, but it has parametric > polymorphism to get round this restriction. Yes, parametric polymorphism is a crutch for the languages with underdeveloped types systems... (:-)) -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de
From: Laurent Deniau on 15 Mar 2006 06:38 S Perryman wrote: > "Laurent Deniau" <laurent.deniau(a)cern.ch> wrote in message > news:dv6v27$o6o$1(a)sunnews.cern.ch... > CLOS forms a topological ordering of the inheritance lattice does it not. > > How does this affect or compare to op selection (code size, performance > etc) for a single inheritance hierarchy of similar size ?? With SI, no DAG. Therefore, CLOS, Loops, C3 or Lin2 (by chronology of invention ;-) ) linearization are trivial for SI and equivalent do depth-search in the list of super classes. But it should not affect much code size nor speed performance since they apply only when a method loaded to the cache, not when it is looked. My case with tree only MI, no DAG, is also simple and requires only depth-first search and no linearization. But it is true that the complexity of these linearization is O(n^3) for a hierarchy of n classes while without DAG it is only O(n) and it may be of importance for fat class hierarchies (very uncommon in dynamic OO languages except maybe in Slate ;-) ). a+, ld.
From: Laurent Deniau on 15 Mar 2006 06:18 Dmitry A. Kazakov wrote: > On Tue, 14 Mar 2006 18:37:52 +0100, Laurent Deniau wrote: >>This is on the side of the dispatcher where I agree, object must be >>shifted according to their (most derived) types and the expected types >>of the selected method. For the caller side, I am refering to the fact >>that the address of the objects have to be passed. > > > I didn't understand it. Why do you need addresses? To make dispatch > decision you need type tags of the objects, not the objects themselves. Right. But in my orignal post I have specified that I am implementing MI using aggregation like in C++, and not with a composition (i.e. array of slots) like in most dynamic OO and Prototype-based langages where objects addresses shifts are meaningless. But these langages need to use setters/getters methods to access object members, including inside their own class methods. Therefore like in C++, I need to *shift* the objects reference (e.g. 'this') by some offset before the dispatcher invokes the method on them and this is done in the find_method dispatcher which performs the lookup and adjusts the objects. That is why the address of objects must be passed with the consequence of creating intermediate temporaries (a bit long to explain why here, but in a word it is related to how generics are implemented for MI) and multiple reload of objects addresses (since they may have changed). > [ If I designed an OO language I'd try not to embed tags into objects, but Embedding tags into objects have advantages beyond the scope of this discussion (e.g. predicate dispatch). > pass them independently in a dope. This could eliminate contamination of This is only possible for either SI, either MI using with slots for object's fields (or equivalent composition). > objects by type tags, which becomes especially disastrous for MI. Type tags > could also support views, i.e. a tag could tell - this is B viewed as A. ] The simplest things is that the object's tag views the class and the class has direct links (pointers) to the super classes (Assuming that classes are also objects (i.e. instance of another class). [...] > I didn't mean type correctness, I did substitutability. You can check > types, but you cannot map substitutability onto types, only partially. This > is why famous Circle-Ellipse controversy arise. Consider B, a > specialization of C. Then not every C is B. This means that Foo having B as > an out parameter (or as a mutator in out) cannot be safely inherited in C, > because it might change C to something that isn't C. Similarly > generalization has problems with in parameters. And there are lots of > practical cases where C is nether generalization, nor specialization of B. > That means that all methods [= subprograms covariant in the corresponding > parameters] are potentially unsafe to inherit. This problem need to be > addressed. Right, I agree that it is not only related to the type system. This is a very interesting point that many OO programmers do not catch ;-) and which is related to the fundamental difference between late binding (e.g. C++ virtual) and dynamic dispatch (e.g. Smalltalk message), that is how overriding is implemented: - late binding needs to know which method to invoke within a given class *definition* at compile time to store the target method address in a table of pointers (static vtable or compressed multidimmensionnal static tables). In a derived class definition a new table is created and either the same method address (no override) either new method address (overridden) is stored. Therefore substitutability must be constrained for any derived class to ensure the validity of this construction otherwise it may be broken as you pointed out. The constraints are managed by the type system which allows only covariance of returned types and contravariance of parameters types to ensure correct (but restricted) substitability. But again, these constraints are related to the choices of the implementation which focus more on efficiency than on flexibility. - dynamic dispatch is the opposite and do everything at runtime. No static construction, no type constraint (types? ;-) ), maximum flexibility, always safe, but less efficient... You can take as a picture that dynamic dispatch works with dynamic types (polymorphic types) like *overloading* works with static types. That is with dynamic dispatch (Circle <: Shape): virtual Circle Circle::intersect(Circle,Circle); would overrides virtual Shape Shape::intersect(Shape,Shape); while late binding like in C++ (even if considering only single-dispatch) does not allow the override and create a new slot in the vtable. In fact, the philosophy of the two overriding mecanisms can be summarised by a question (should I had started by them?): late binding: given a method, what are the types it can accept and return? (static construction must managed dynamic types) dynamic dispatch: given type(s), what is the most specialized applicable method? (dynamic types select static construction) a+, ld.
From: Dmitry A. Kazakov on 15 Mar 2006 09:58
On Wed, 15 Mar 2006 12:18:16 +0100, Laurent Deniau wrote: > Dmitry A. Kazakov wrote: >> On Tue, 14 Mar 2006 18:37:52 +0100, Laurent Deniau wrote: >> pass them independently in a dope. This could eliminate contamination of > > This is only possible for either SI, either MI using with slots for > object's fields (or equivalent composition). You will go this path anyway, when it will come to DAG. (:-)) What free flying tags allow is dispatching methods for very small objects, like Boolean. [The goal is a pure OO statically typed language.] >> I didn't mean type correctness, I did substitutability. You can check >> types, but you cannot map substitutability onto types, only partially. This >> is why famous Circle-Ellipse controversy arise. Consider B, a >> specialization of C. Then not every C is B. This means that Foo having B as >> an out parameter (or as a mutator in out) cannot be safely inherited in C, >> because it might change C to something that isn't C. Similarly >> generalization has problems with in parameters. And there are lots of >> practical cases where C is nether generalization, nor specialization of B. >> That means that all methods [= subprograms covariant in the corresponding >> parameters] are potentially unsafe to inherit. This problem need to be >> addressed. > > Right, I agree that it is not only related to the type system. This is a > very interesting point that many OO programmers do not catch ;-) and > which is related to the fundamental difference between late binding > (e.g. C++ virtual) and dynamic dispatch (e.g. Smalltalk message), that > is how overriding is implemented: > > - late binding needs to know which method to invoke within a given class > *definition* at compile time to store the target method address in a > table of pointers (static vtable or compressed multidimmensionnal static > tables). In a derived class definition a new table is created and either > the same method address (no override) either new method address > (overridden) is stored. Therefore substitutability must be constrained > for any derived class to ensure the validity of this construction > otherwise it may be broken as you pointed out. The constraints are > managed by the type system which allows only covariance of returned > types and contravariance of parameters types to ensure correct (but > restricted) substitability. But again, these constraints are related to > the choices of the implementation which focus more on efficiency than on > flexibility. > > - dynamic dispatch is the opposite and do everything at runtime. No > static construction, no type constraint (types? ;-) ), maximum > flexibility, always safe, but less efficient... You can take as a > picture that dynamic dispatch works with dynamic types (polymorphic > types) like *overloading* works with static types. That is with dynamic > dispatch (Circle <: Shape): > virtual Circle Circle::intersect(Circle,Circle); > would overrides > virtual Shape Shape::intersect(Shape,Shape); > while late binding like in C++ (even if considering only > single-dispatch) does not allow the override and create a new slot in > the vtable. Hmm, this is not determined by the time of bindings. For example, the above is legal in Ada 95, which is statically typed: type Shape is tagged ...; function Intersect (Left, Right : Shape) return Shape; type Circle is new Shape with ...; function Intersect (Left, Right : Circle) return Circle; -- This overrides Moreover, in Ada it is mandatory to override Shape.Intersect, because it is covariant in all parameters. The compiler will refuse to inherit it. In my view it is possible to make a statical types system right. Though it would require much work. > In fact, the philosophy of the two overriding mecanisms can be > summarised by a question (should I had started by them?): > > late binding: given a method, what are the types it can accept and > return? (static construction must managed dynamic types) > > dynamic dispatch: given type(s), what is the most specialized applicable > method? (dynamic types select static construction) Close, but not quite. In fact, there are two types involved. The concrete type which might remain unknown until run-time and the class, which is the set of types containing that potentially unknown type. The class is always statically known. In a dynamically typed language it is just "all types." We know in advance that there are [all] types! (:-)) -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de |