multimethod + multiple inheritance
in [OOP]
|
From: Laurent Deniau on 15 Mar 2006 12:39 Dmitry A. Kazakov wrote: > 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, if a DAG is possible yes (or I would use C++ virtual inheritance that I don't like), and since I prefer simplicity, I would be in favor of SI unless somebody show that MI is crucial in my context (my original question ;-) ) > when it will come to DAG. (:-)) What free That is for sure not. DAG is a mess in MI and I don't want to go up to this point. I prefer by far SI + dynamic inheritance. > flying tags allow is dispatching methods for very small objects, like > Boolean. [The goal is a pure OO statically typed language.] Yes, but remember that I am talking about pure C99 code (no intermediate preprocessor, no extra compiler). It is not a new langage, just some macros and some C code. > Hmm, this is not determined by the time of bindings. Not the time of bindings, but the way it is done, that is the override mechanism. > For example, the above > is legal in Ada 95, which is statically typed: Unfortunately, I don't know the Ada 95 internals (just some syntax) > 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 I would be interested to know how Ada 95 manages a Shape object in the second function if the static type of Left and Right would be an ADT (or a Shape) from the point of view of the intersect call. Most OO langages which use late binding and accept this override, will silently introduce a downcast to the expected type in the method (i.e. chunk) to ensure correctness when the type system has lost the original type and raise a type exception in case of failure. OO languages which use dynamic dispatch are not concerned by this problem and maybe Ada one of them. Some language even switch between the two modes (e.g. Objective-C). Note that compilers may replace dynamic dispatch by late binding or even by static binding if enough information is available to ensure correctness. But this is not what I am interested in here. > 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. What it essentially required is the knowledge of the type. Since I like ADT, most of my code do not know the 'true' type of objects. Then each time the barrier of 'compiler lost the knowledge of static types' is crossed, explicit downcast are required (e.g. C++) or silently introduced (e.g. Java or even Haskell) with a runtime error raised in case of failure. >>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." Yes and no ;-) When the discussion starts to go into some technical details (like here) then I prefere to make the difference between static types, concrete types and classes. In language where subtyping and inheritance are combined (e.g. C++), static types and classes are usually indistingable, classes are not objects and concrete types take a simplified form (e.g. typeid, vtable address, tag). But when the distinction is made, classes are objects (because you get this flexibility for free), classes and types are two complementary notions, and concrete types are used for method dispatch. While static types are only used for early error detection or optimization, but they are not used for method dispatch, this would be a non-sense. > We know in advance that there are [all] types! (:-)) This is true in my case where I have many classes but one type, but it is not always true (CLOS, Cecil). a+, ld.
From: Dmitry A. Kazakov on 16 Mar 2006 05:55 On Wed, 15 Mar 2006 18:39:33 +0100, Laurent Deniau wrote: > Dmitry A. Kazakov wrote: >> On Wed, 15 Mar 2006 12:18:16 +0100, Laurent Deniau wrote: >> > That is for sure not. DAG is a mess in MI and I don't want to go up to > this point. I prefer by far SI + dynamic inheritance. Yes, but one indeed needs DAG, i.e. in C++ terms: both virtual and non-virtual bases, there are important practical uses for both. >> flying tags allow is dispatching methods for very small objects, like >> Boolean. [The goal is a pure OO statically typed language.] > > Yes, but remember that I am talking about pure C99 code (no intermediate > preprocessor, no extra compiler). It is not a new langage, just some > macros and some C code. BTW, I saw an implementation of multiple dispatch for C++ somewhere, unfortunately I have lost the link. The syntax looked like: Foo (virtual Bar& X, virtual Baz& Y); >> 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 > > I would be interested to know how Ada 95 manages a Shape object in the > second function if the static type of Left and Right would be an ADT (or > a Shape) from the point of view of the intersect call. It cannot be called on Shape, that would be a compile-time type error. Ada differentiates classes and specific types, a revolutionary concept, IMO. Dispatch happens only on a class object (=polymorphic object.) That is not Shape, but Shape'Class. These two are different types in Ada. So it goes as follows: A : Shape; -- I know for sure it is nothing, but shape B : Circle; -- That's a circle C : Shape'Class; -- This can be anything derived from Shape .... A := Intersect (A, A); -- This does not dispatch, it calls to Shape.Intersect B := Intersect (B, B); -- This calls directly to Circle.Intersect C := Intersect (A, C); -- This dispatches in the result and the second parameter There is no chance to call Circle.Intersect on anything, but Circle or its descendant. However, Ada does not have multimethods fully implemented. A dispatching call on parameters of different concrete types raises Constraint_Error exception. In other words, the dispatching table of a multimethod has only the diagonal to override. Non-diagonal elements are sinks to Constraint_Error. The idea that T and T'Class are two different types makes things a lot easier. It is also far more efficient, because once you have dispatched you don't do it again. Within Shape.Intersect the parameters are of Shape. So all internal calls will never dispatch. Their targets are statically known. A C++ equivalent would be to write T:: prefix for each call within any implementation of methods of T. This is also more consistent to the contract model, and prevents nasty surprises. As an additional plus it allows constants folding which of course would be impossible otherwise. > What it essentially required is the knowledge of the type. Since I like > ADT, most of my code do not know the 'true' type of objects. Then each > time the barrier of 'compiler lost the knowledge of static types' is > crossed, explicit downcast are required (e.g. C++) or silently > introduced (e.g. Java or even Haskell) with a runtime error raised in > case of failure. Yes, but you seems to overestimate the number of cases where the objects are indeed polymorphic. In fact they are quite minor, provided that you dispatch only once. Then in all implementation of all methods the concrete types of parameters become known. So one can have highly optimized >>>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." > > Yes and no ;-) When the discussion starts to go into some technical > details (like here) then I prefere to make the difference between static > types, concrete types and classes. In language where subtyping and > inheritance are combined (e.g. C++), static types and classes are > usually indistingable, classes are not objects and concrete types take a > simplified form (e.g. typeid, vtable address, tag). But when the > distinction is made, classes are objects (because you get this > flexibility for free), What do you mean here? Provided the following a hierarchy of things: 1. Value 2. Type (set of values + operations) 3. Types type (set of types + operations = types algebra) 4. Types types types (dunno what (:-)) 5. ... "classes are objects" could read as "class is n-thing." In my view class is a 2-thing. We take 3-thing (a set of types), make closure of all values of all types in the set and the result is a type (2-thing) called "class." > classes and types are two complementary notions, > and concrete types are used for method dispatch. While static types are > only used for early error detection or optimization, but they are not > used for method dispatch, this would be a non-sense. But you can use them to narrow dispatch, that's the whole idea. I agree that ideally types should not exist at run-time, but in reality it is rather impossible and too constraining. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de
From: Laurent Deniau on 16 Mar 2006 09:00 Dmitry A. Kazakov wrote: > On Wed, 15 Mar 2006 18:39:33 +0100, Laurent Deniau wrote: >>That is for sure not. DAG is a mess in MI and I don't want to go up to >>this point. I prefer by far SI + dynamic inheritance. > > > Yes, but one indeed needs DAG, i.e. in C++ terms: both virtual and > non-virtual bases, there are important practical uses for both. I fully agree that it is essential in C++. But when dynamic dispatch + dynamic inheritance are available (both missing in C++), I am not so sure and I don't know design pattern which would absolutely require it. >>>flying tags allow is dispatching methods for very small objects, like >>>Boolean. [The goal is a pure OO statically typed language.] >> >>Yes, but remember that I am talking about pure C99 code (no intermediate >>preprocessor, no extra compiler). It is not a new langage, just some >>macros and some C code. > > > BTW, I saw an implementation of multiple dispatch for C++ somewhere, > unfortunately I have lost the link. The syntax looked like: > > Foo (virtual Bar& X, virtual Baz& Y); Yes, this is a proposal extension for C++ from the D&E, not C++98. I am only interested by standardized languages with high conformant compilers widely available. But I have about a hundred of papers on this topic, including these one (n1463, n1529). >>>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 >> >>I would be interested to know how Ada 95 manages a Shape object in the >>second function if the static type of Left and Right would be an ADT (or >>a Shape) from the point of view of the intersect call. > > > It cannot be called on Shape, that would be a compile-time type error. Ada > differentiates classes and specific types, a revolutionary concept, IMO. > Dispatch happens only on a class object (=polymorphic object.) That is not > Shape, but Shape'Class. These two are different types in Ada. So it goes as > follows: > > A : Shape; -- I know for sure it is nothing, but shape > B : Circle; -- That's a circle > C : Shape'Class; -- This can be anything derived from Shape > ... > A := Intersect (A, A); > -- This does not dispatch, it calls to Shape.Intersect > > B := Intersect (B, B); > -- This calls directly to Circle.Intersect > > C := Intersect (A, C); > -- This dispatches in the result and the second parameter > > There is no chance to call Circle.Intersect on anything, but Circle or its > descendant. > > However, Ada does not have multimethods fully implemented. A dispatching > call on parameters of different concrete types raises Constraint_Error > exception. In other words, the dispatching table of a multimethod has only > the diagonal to override. Non-diagonal elements are sinks to > Constraint_Error. Here is the constraint related to the implementation overriding mechanism. Seems to me that Ada did the choice of efficiency. [...] >>What it essentially required is the knowledge of the type. Since I like >>ADT, most of my code do not know the 'true' type of objects. Then each >>time the barrier of 'compiler lost the knowledge of static types' is >>crossed, explicit downcast are required (e.g. C++) or silently >>introduced (e.g. Java or even Haskell) with a runtime error raised in >>case of failure. > > > Yes, but you seems to overestimate the number of cases where the objects > are indeed polymorphic. In fact they are quite minor, provided that you > dispatch only once. Then in all implementation of all methods the concrete > types of parameters become known. So one can have highly optimized I do not overestimate. But I really like encapsulation and ADT because once an implementation is finihed, I can forget it and remember only the interface. The second point is if you know that all your methods are "virtual" from the beginning whatever you will do, simplify a lot the design of large project (think about C++ virtual inheritance of top base class in fat and deep hierarchy and the implication on a large project, cf. Lakos book). [...] >>Yes and no ;-) When the discussion starts to go into some technical >>details (like here) then I prefere to make the difference between static >>types, concrete types and classes. In language where subtyping and >>inheritance are combined (e.g. C++), static types and classes are >>usually indistingable, classes are not objects and concrete types take a >>simplified form (e.g. typeid, vtable address, tag). But when the >>distinction is made, classes are objects (because you get this >>flexibility for free), > > > What do you mean here? Provided the following a hierarchy of things: > > 1. Value > 2. Type (set of values + operations) > 3. Types type (set of types + operations = types algebra) > 4. Types types types (dunno what (:-)) > 5. ... > > "classes are objects" could read as "class is n-thing." In my view class is > a 2-thing. We take 3-thing (a set of types), make closure of all values of > all types in the set and the result is a type (2-thing) called "class." This is a limited version of what is possible and useful. Think about an object which changes dynamically its class to change its behavior. The closure is unknown at compile time and the reduction never occurs. And BTW the new class could have been dynamically loaded at runtime ;-) >>classes and types are two complementary notions, >>and concrete types are used for method dispatch. While static types are >>only used for early error detection or optimization, but they are not >>used for method dispatch, this would be a non-sense. > > > But you can use them to narrow dispatch, that's the whole idea. I agree > that ideally types should not exist at run-time, but in reality it is > rather impossible and too constraining. It is exactly my point. Except that I am in C99 and do not have a compiler in hand to do these optimizations. This leads to the status of one type (e.g. object), many classes (e.g. defclass), dispatch everywhere and therefore dispatch should be as fast as possible (despite it is not the dominating part of a program runtime). On top of this, simplicity would advise SI only. a+, ld.
From: Dmitry A. Kazakov on 17 Mar 2006 04:34 On Thu, 16 Mar 2006 15:00:52 +0100, Laurent Deniau wrote: > Dmitry A. Kazakov wrote: >> On Wed, 15 Mar 2006 18:39:33 +0100, Laurent Deniau wrote: >>>That is for sure not. DAG is a mess in MI and I don't want to go up to >>>this point. I prefer by far SI + dynamic inheritance. >> >> Yes, but one indeed needs DAG, i.e. in C++ terms: both virtual and >> non-virtual bases, there are important practical uses for both. > > I fully agree that it is essential in C++. But when dynamic dispatch + > dynamic inheritance are available (both missing in C++), I am not so > sure and I don't know design pattern which would absolutely require it. Is dynamic inheritance = creating types in local scopes at run-time? Anyway, I don't see how to avoid "diamond diagram" if not by shifting all the burden to the programmer. IMO, it is like multiple dispatch, one can emulate it using SI, and have countless problems with implementing quite idiotic patterns. >> However, Ada does not have multimethods fully implemented. A dispatching >> call on parameters of different concrete types raises Constraint_Error >> exception. In other words, the dispatching table of a multimethod has only >> the diagonal to override. Non-diagonal elements are sinks to >> Constraint_Error. > > Here is the constraint related to the implementation overriding > mechanism. Seems to me that Ada did the choice of efficiency. Yes, but one could extend it to full mutimethods. It should not have much of distributed overhead. Because all tags are mandatory to compare anyway. So they could be used for indexing a dispatch table instead. >>>What it essentially required is the knowledge of the type. Since I like >>>ADT, most of my code do not know the 'true' type of objects. Then each >>>time the barrier of 'compiler lost the knowledge of static types' is >>>crossed, explicit downcast are required (e.g. C++) or silently >>>introduced (e.g. Java or even Haskell) with a runtime error raised in >>>case of failure. >> >> Yes, but you seems to overestimate the number of cases where the objects >> are indeed polymorphic. In fact they are quite minor, provided that you >> dispatch only once. Then in all implementation of all methods the concrete >> types of parameters become known. So one can have highly optimized > > I do not overestimate. But I really like encapsulation and ADT because > once an implementation is finihed, I can forget it and remember only the > interface. You don't loose that. If you want to design a program that would work for a class rather than for a concrete type, then you declare it as such: procedure Foo (X : Shape'Class); -- This works for all descendants of Shape This Foo is so-called "class-wide' subprogram. It is not a method, because it has the same implementation for all members of the class. It is not inherited, it cannot be overridden and in its body all calls are dispatching. > The second point is if you know that all your methods are > "virtual" from the beginning whatever you will do, simplify a lot the > design of large project (think about C++ virtual inheritance of top base > class in fat and deep hierarchy and the implication on a large project, > cf. Lakos book). I agree and that is exactly what I want. In Ada's model it is exactly so. If you have any covariant parameter that makes the subprogram a method. In C++ terms it is virtual. To make subprogram non-virtual is not easy in Ada [when the parameter is not a class as in Foo.] My pet idea to completely outlaw non-virtual subprograms and leave only methods and class-wide subprograms. >>>Yes and no ;-) When the discussion starts to go into some technical >>>details (like here) then I prefere to make the difference between static >>>types, concrete types and classes. In language where subtyping and >>>inheritance are combined (e.g. C++), static types and classes are >>>usually indistingable, classes are not objects and concrete types take a >>>simplified form (e.g. typeid, vtable address, tag). But when the >>>distinction is made, classes are objects (because you get this >>>flexibility for free), >> >> What do you mean here? Provided the following a hierarchy of things: >> >> 1. Value >> 2. Type (set of values + operations) >> 3. Types type (set of types + operations = types algebra) >> 4. Types types types (dunno what (:-)) >> 5. ... >> >> "classes are objects" could read as "class is n-thing." In my view class is >> a 2-thing. We take 3-thing (a set of types), make closure of all values of >> all types in the set and the result is a type (2-thing) called "class." > > This is a limited version of what is possible and useful. Think about an > object which changes dynamically its class to change its behavior. Do we need that? We can change object's type within the same class. This also changes the behavior within the constraint defined by the class. The question is, when and if we'd really like to change the class itself. > The > closure is unknown at compile time and the reduction never occurs. And > BTW the new class could have been dynamically loaded at runtime ;-) Again, the same question. Is it a class or a type to be dynamically loaded? My point is that it is never so, that you really load anything. What could be done with anything? Probably nothing. I think that supertyping could eliminate need in dynamic classes. Consider a language, where you could create ad-hoc supertypes and use the corresponding classes. > It is exactly my point. Except that I am in C99 and do not have a > compiler in hand to do these optimizations. This leads to the status of > one type (e.g. object), many classes (e.g. defclass), dispatch > everywhere and therefore dispatch should be as fast as possible (despite > it is not the dominating part of a program runtime). On top of this, > simplicity would advise SI only. 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. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de
From: Laurent Deniau on 20 Mar 2006 05:00
Dmitry A. Kazakov wrote: > On Thu, 16 Mar 2006 15:00:52 +0100, Laurent Deniau wrote: > > >>Dmitry A. Kazakov wrote: >> >>>On Wed, 15 Mar 2006 18:39:33 +0100, Laurent Deniau wrote: >>> >>>>That is for sure not. DAG is a mess in MI and I don't want to go up to >>>>this point. I prefer by far SI + dynamic inheritance. >>> >>>Yes, but one indeed needs DAG, i.e. in C++ terms: both virtual and >>>non-virtual bases, there are important practical uses for both. >> >>I fully agree that it is essential in C++. But when dynamic dispatch + >>dynamic inheritance are available (both missing in C++), I am not so >>sure and I don't know design pattern which would absolutely require it. > > > Is dynamic inheritance = creating types in local scopes at run-time? 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. > 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, 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. [...] > 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. a+, ld. |