More On Multiple Inheritance

[Matthew Tuck]

Hans-Dieter.Dreier@materna.de wrote:

>> Sure.  Languages with object-based inheritance, also known as
>> prototyping, do not have classes, only objects.  Inheritance is done via
>> the cloning (copying) of objects along with the ability the update
>> methods (overriding except at run time).
> I see. Object-based inheritance does not need the concept of "class",
> which appeals to me (as all simple, somewhat elegant solutions do).
> But I wouldn't like it, nevertheless, because it should make typing
> and all related stuff (type checking, coercing...) much harder if not
> impossible.

Not as far as I can see.  Types can still stay the same, it's just that
there are no fixed implementations.

> Actually, changing an object's class membership or inheritance hierarchy
> might be needed (since that may occur when the program is changed during
> development, at the user's request), but in many cases there have to be
> some manual adjustments to take care of the environment change.

Agreed.  It would be interesting to be able to play around with things
at run-time using the environment, but things like changing types have
to be handled properly.

> Example: The user decides that an edit field is no longer sufficient
> in some place and he want to replace that with a combo box (edit field +
> drop down list box), which is quite a different class. Here it would be
> nice if he simply could change the object's class and all matching
> attributes (font, screen position, message handlers...) would migrate.
> All attributes that have no equivalent in the new class would turn to
> comments (so the code is not lost in case it will be needed later on).

Most GUI's expect "component" type and don't care what subtype or
implementation is, so you should be able to change this at runtime.  The
main problem with this, and dynamic inheritance, is ensuring state is
preserved.  With public state this is not too bad - private state is
much harder - but if there's sufficient interface for the purposes of
universal conversion, it should be possible.

This is one reason why I try not use the word class anymore except when
using the traditional connotation of a unified type and implementation. 
It can confuse the situation.  Some people and languages have tried to
use class to refer to impl only, but I don't think that's a good idea,
since it's confusing.

> If we follow the C++ way but have no true MI, inter-class optimisation
> would not be needed: You specify something as "non-virtual", and it *is*
> non-virtual: Static "dispatch" is used everywhere; the (static) address
> is known as soon as the item in question has been compiled/linked (if it
> is a class item, like a method), or as soon as the instance layout is
> known (if it is an instance item). No inter-class optimisation needed,
> as far as I can see.

Well if you want to define non-overridable methods then yeah, you can,
but this defeats the spirit of OOP.  You should always have the
opportunity to override.  I have never come across a use of non virtual
methods other than as a kludge to avoid dynamic dispatch.  Flexibility,
runtime-efficiency, compile-time efficiency, choose two.

>> That's true.  You couldn't do MI with the scheme with making it
>> fragile.  Although I don't see cMI is any different.
> Both schemes have some fragility. tMI has it implicitly, requiring
> recompilation and global optimisation, where cMI has it explicitly
> (forcing the user to write the superclass "MI-ready"). Correct?

Yes, but I was talking about your language level true MI using
composition as the implementation.

> class A {
>  int a;
> };
>
> class B {
>  int b;
>  A& ab;  // contains an A <------------------ here is the reference to a
>                                               in B
> // default constructor for standalone use of B
>  B(): ab (new A) {};
> // constructor for MI use of B
>  B(A& a): ab (a) {};
>  };

Yes but normally the B will physically contain an a, hence no matter
whether you have an A or B, you can look inside the object to find the
a.  With composition, you don't know this.  If it's impl A, you can, if
impl B, you have to follow a pointer.  Then problem is that you're no
longer extending the layout.

You could generate if/then code for each access, but that's going to
cause very bloated code.

If you had get/sets for all fields, you could direct it to the correct
place, but this introduces a dynamic dispatch where there previously
would not have been one.

>> Why aren't they transparent?  You have a tradeoff between compilation
>> time and run time.  Both take time and are visible, but you can't say
>> they affect what the programmer has to do.
> To me, "transparent" means that everything that compiled without the
> optimisation in question will continue to do so with the optimisation
> applied. Different compile/run times & memory consumptions do not
> make a difference (except when they tend towards infinity).

Sure.  How is it not transparent in this situation?

> I think that if you apply a cast in C++ to select a base class for some
> object, then the this pointer *may* change (usually not, but what happens
> when MI is involved?)

I don't think the pointer would change, just the typing aspects.  If you
have a fixed layout the pointer wouldn't need to change.

> Although the object itself is not changed (I never meant this!), the
> pointer points to a different location inside the object, rendering the
> a and c parts inaccessible from within B.

It could work, but:

(a) It means object equality can no longer be determined by a pointer
comparison.
(b) The actual object impl can no longer be determined from looking at
the layout.  This means you can't use run-time type identification (e.g.
converting a pointer to a subtype if allowed).  Although object
polymorphism and parameterised types can often replace the uses of this,
not always.
(c) We're introducing pointers into objects, and sometimes these will be
intermixed with pointer to the start of objects.

The first two could be fixed if we could find the object header.  This
could be done by either storing information in each mixin or passing the
pointer to the memory manager and asking it which object this falls in.
The third I don't have a solution to.

>> Few compilers do static dispatch optimising I think, and even in those
>> that do, there's going to be a lot of methods that can't be statically
>> dispatched on all of the time.  C non "virtual" items can always by
>> statically dispatched on, but I've never seen a use for that feature.
> This greatly surprises me. I always thought that static dispatch is (at
> least in C++) the *standard* dispatch mechanism and is used in at least
> 80% of all cases.

Well I guess it depends on the way you program.  A lot of C++ uses
legacy C and hence it is static dispatch.  When I've written in C++,
I've always written virtual or pure virtual calls.

If efficiency is that important I can change it later, just as I'd like
a language where if efficiency was that important I could optimise it
later.  Except I wouldn't need to keep writing "virtual" everywhere
(although it's possible to make virtual default and nonvirtual an
override).  Java is similar with "final", except you can't override it
at all (I like this facility, but on implementation inheritance, not
type inheritance).

> At least this is true in all rpograms I know of. I do not even regard
> generating a direct call for static dispatch as an optimisation. If you
> got only one instance of an item (here: a method), the address of which
> is known at compile (or link) time, there is no need for indirect
> access.

Well if the compiler generates a static dispatch straight away it's not.
But if you want all methods to be potentially dynamically dispatched
it's usually not possible to do that without optimisation.

> Of course, if you look at other programming languages, the situation may
> be different (e.g. Smalltalk, but you also note their performance).

Yes I do note its performance.  But I have been interested in aggressive
optimisation since the beginning
(http://www.box.net.au/~matty/ultra/docs/charter.html).  I want a
*really* cool optimiser, of the calibre of nothing you would find
commercially.  Also Smalltalk's lack of typing makes extracting
efficiency harder.

I might point out that even C is quite inefficient compared to assembly,
if you use optimisation, you can get comparable, or even better speed
than your standard assembly implementation.  Hence, if we go higher
level, we're going to need more optimisation, although you're always
free to not use it.  And inter-class optimisations are a fairly untapped
reservoir of possible optimisations.  Hence if the optimiser is good
enough, we might eventually do better than C on the highest setting. 
Inter-module optimisation is really just increasing the fragility and
therefore compile-time, like any other optimisation.

>> I meant syntactically, like you'd have to do with cMI.
> You mean at compile time? Well, that doesn't hurt. It simply is the price
to pay for not having a single, flat name space.

No I meant at type time, so instead of typing Object.Object2.Method you
type Object.Method.

> References (&) in C++ are an example: They actually are pointers,
> but you need not write the * (deref)-operator - it's assumed by the
> compiler.

This is not really the same.  A pointer traversal optimisation would be
statically determining a memory pointer that is potentially many levels
deep.

> If the compiler just needed to look up information that was gathered
> when the base class was compiled, I would not call that "program-wide
> optimisation". I imagine it would be stored in some symbol table
> associated with the base class and could be looked up there quite fast.

On second thoughts I'll change this statement.  If you leave addresses
as symbolic names throughout optimisation, this can work, and the
dereferencing of these names in code generation is where the program
wide stuff is done (since the sizes and addresses of things will affect
where the other things go).

-- 
     Matthew Tuck - Software Developer & All-Round Nice Guy
             mailto:matty@box.net.au (ICQ #8125618)
       Check out the Ultra programming language project!
              http://www.box.net.au/~matty/ultra/