From: pk@rwthi3.informatik.rwth-aachen.de (Peter Klein)
Subject: Re: MI - clutching at straws
Reply-To: pk@rwthi3.informatik.rwth-aachen.de
Organization: Lehrstuhl fuer Informatik III, RWTH Aachen, Germany
Date: Mon, 31 Aug 92 15:36:41 GMT

In article 92Aug23173050@Dr_No.mitre.org, eachus@Dr_No.mitre.org (Robert I. Eachus) writes:
>In article <1992Aug23.171350.27117@Urmel.Informatik.RWTH-Aachen.DE> pk@rwthi3.informatik.rwth-aachen.de (Peter Klein) writes:
>
>   Consider the following example: I start with an abstract data type
>   for a graph.  Now I augment the basic type in several independant
>   ways, let's say to make attributed, node- and edge-labeled graphs.
>   Finally, I would like to have some special graphs, e.g. abstract
>   syntax graphs or binary trees, which combine one or more of the
>   above extensions. How can I express this without violating the
>   abstractness of the involved data types? Maybe somebody's got some
>   clever answer. Otherwise, I will keep thinking that MI is sometimes
>   appropriate.
>
>   Okay, challenge accepted...
>
>   First, let's create the basic graph package.  The "normal" way to
>do this in Ada is to use a model where different graphs are different
>instances of a generic package, but other models are possible.  So
>lets use a generic which exports an abstract type...
>
> [ ... some ada syntax deleted ... ]
>
>    In any case now most of the augmentations are natural and done by
>different instantiations.  The special graphs, such as binary trees,
>would be done by instantiating the GRAPHS package then adding
>additional operations at a higher level.  In Ada 9X this can be done
>by writing a binary tree generic which takes an instantiation of
>GRAPHS as a parameter.  In Ada 83, you can do the same sort of thing,
>but the declaration gets much messier.  (All of the visible types and
>operations of the GRAPHS package must be passed as individual generic
>parameters.)
>
>    Now it is possible to decorate a single GRAPHS instance with all
>of the various special graph add ons.  In general, many of the
>combinations wouldn't make sense, but that is an issue (in Ada) for
>the programmer not the compiler.
>
>    I could ring a lot of changes on the theme, but in general, the
>lesson is that, IN ADA, anything that might possibly be done with
>multiple inheritance is probably better done with generics.  Notice
>that in this example, I went out of my way to make single inheritance
>possible.  A pure generic solution seems much more appropriate.  This
>says nothing about whether or not MI is useful in other languages,
>just that there is no reason to add it to Ada.

Well, I'm not overly surprised by this answer. In fact, when I posted
the same example to the Modula-3 discussion, a similar solution was
proposed. But this will not do.

It is important to keep in mind that genericity and inheritance are
orthogonal concepts (see Betrand Meyer's "Genericity versus Inheritance,
Journal of Pascal, Ada, & Modula-2, Vol. 7, No. 2, pp. 13-30,
Wiley 1988 on this). In restricted cases, one can be simulated by
the other. But this is pointless when we talk about the usefulness
of the concepts as such.

What actually is lost when simulating inheritance with genericity
is polymorphism. In your example, the implementation of the extensions
is hidden from the base type. But the implementation of the basic
type reveals *which* extensions are planned. This has some severe
disadvantages:
  -  No new extensions to the base type can be made without modifying
     the base type.
  -  Every client of the basic type *must* provide implementations for
     the extensions, even if he doesn't need them.
So, in OO terminology, you violate the open/closed principle for data
abstraction using classes.

In a more general sense, it cannot be reasonable to extend a basic type
by inheritance or by genericity depending on the fact whether you want
to combine some extensions later on. If you think that the extensions
should be done by inheritance, you'll end up missing MI if you want to
combine extensions on a higher level. On the other hand, if you say that
the extensions should be done using genericity, you won't need MI. But
in this case, you don't need inheritance at all.

Peter

---
Peter Klein                        E-Mail: pk@rwthi3.informatik.rwth-aachen.de
Lehrstuhl fuer Informatik III      Tel.: +49/241/80-21320
Ahornstrasse 55                    Fax.: +49/241/80-21329
RWTH Aachen
D-5100 Aachen
Germany

Newsgroups: comp.lang.ada