\subsection{Class Evolution} The motivation to improve the class organization of an object-oriented application often arises after a large part of the application/knowledge base has already been written. It is typically a case of hindsight by which one decides that the class organization can be improved. This presents a dilemma to the application writer/knowledge engineer. He can easily continue to write the application with the poorly designed classes or take on the tougher task of improving his classes and adapt the already written software, with the hope that it will pay off in the long run. In the presence of deadlines and other forms of pressure to finish his task, the application writer might be tempted to take the easy way out, even though it may cost him more time in the long run. It is understandable that application writers/ knowledge engineers do not like to rewrite running and tested software "only" to make it cleaner and more amenable to future growth. Indeed, the transformations one has to perform to the methods are often very mechanical. Therefore we discuss now common class transformations and their implications on the updating of method and object descriptions: There is an opportunity to develop a successful CASE tool which will assist in performing the updating of method and object descriptions. To talk about classes in a programming language independent way, we use the \cm\ notation. We distinguish between four cases of \cm\ transformations: \begin{enumerate} \item Method and object upward compatibility. \label{mi-up} The change does not require any modification of methods or object descriptions. By an object description we mean a textual description defined by a \cm. Recall that a \cm\ defines both classes and languages. Examples of these transformations are: add optional parts, add parts which are a possibly empty list, add an alternative, generalize (A construction class {\tt B} is replaced by an alternation class {\tt B1} which has {\tt B} as an alternative), required to optional, non-empty list to possibly empty list. \item Object upward compatibility. \label{o-up} The methods need to be changed but the object descriptions stay the same. All the transformations from (\ref{mi-up}) and: instance variable name change, class name change, additional level (a new construction class with one part is introduced), parameterize (see later section), factor (the same repeating pattern is captured by a new production), promotion of structure (an alternation production with common parts is introduced to simplify construction productions, see the example given below), part to inherit (and inverse), add method argument. \item Method upward compatibility. The methods are invariant, but the object descriptions need to be modified. All transformations from (\ref{mi-up}) and: add parts (optional or required), optional to required, possibly empty list to non-empty list, concrete syntax changes which keep abstract syntax invariant. \item No compatibility. The methods and object descriptions need to be changed. \end{enumerate} To illustrate these transformations we expand one example from case 2: promotion of structure. \bv Basket = Apple Number. Apple = Number SIG cost() RETURNS Number. \end{verbatim} is replaced by \bv Basket = Fruit Number. Fruit : Apple COMMON Number VIRTUAL SIG cost() RETURNS Number. Apple = SIG cost() RETURNS Number. \end{verbatim} {\tt Fruit} is an alternation class with common parts, namely all alternatives of {\tt Fruit}, in this case only {\tt Apple}, will have the parts listed after {\tt COMMON}. There is an inheritance link from an alternation class with common parts to all its alternatives. The motivation for this \cm\ transformation is that later more alternatives will be added to {\tt Fruit}. Therefore it pays off to factor out the common aspects of fruit. Software changes which have to be done (in C++) and which can be automated: \begin{itemize} \item Define new class called {\tt Fruit} (with protected constructor, since {\tt Fruit} is abstract): \bv class Fruit { public: virtual void cost() { ... }; \end{verbatim} \item add public inheritance from class {\tt Fruit} to {\tt Apple}. Update the constructor for {\tt Apple} class. \end{itemize} \subsection{Parameterizing existing software} We focus now on one special case of \cm\ evolution with upward compatible objects: type parameterization. This is an important aspect of \cm\ evolution. Writing software to make it more reusable is one kind of preventive software maintenance. When maintenance needs to be done, we are more likely to be able to reuse well-tested code, saving on debugging time during the maintenance phase. We introduce a process to automatically build polymorphic software from existing non-polymorphic software. We extend the facilities provided by \oop\ systems for software reusability by generating a generalization of the original class hierarchy while maintaining software compatibility. The importance of data-encapsulation, modularity and coding style is reinforced, as these properties point the way to the solutions of the problems. %To get the best return from the time and cost invested in software %development it is important that future systems can benefit in %real terms from the development of current systems. %Reusable software development and reusability techniques are %important issues in ensuring those benefits %\cite{habermann:hicss-88}. But, what does it %mean for a program, or a piece of code to be reusable? At the basic %level, it is simply the duplication of sections of code from one program to %another. At a higher level, it is a program or piece of software which %is generic, i.e., %it solves a problem in the abstract without any dependency %on the specific instances of the problem. % %For example, a program which %traverses the elements of a tree (any tree, independent of the types %of the tree nodes). %Polymorphism is the term used to describe such flexibility. %A program is said to be polymorphic if one of its parameters %is a type. %Many programming languages in the past have not supported user defined %polymorphism, e.g., Pascal and Modula-2. Even Ada has rather %limited capabilities in this area. While a programmer may solve a %problem generically (as they often do when thinking about abstract data %structures), when it comes around to writing the program, specific type %details are hard-coded into the programs. Thus, when it is time to %`reuse' the software, time must be taken to extract and replace type %dependent information. Our work on a parameterization tool follows from our work on \oop \/ style \cite{LHLR:law-paper} in our investigation into easily modifiable, reusable software. We propose a new technique to automatically parameterize programs with respect to types from a given example which is written in good style (defined earlier). The main goal of automatic parameterization is to free the user from writing polymorphic programs, i.e., the programmer still writes programs for a specific instance of a general problem. The user provides a program for specific types, decides which types should be parameterized and then gets the parameterized program for free. The advantage of the parameterized program is that it is more reusable than the non-parameterized version. The parameterization process specifies constraints on the actual parameters which may be substituted for the actual type parameters. There is a large body of literature on inferring types, including parameterized types, from programs. A good survey of this literature can be found in \cite{cardelli-wegner:types-85}. All these type inferencing algorithms make use of unification \cite{milner:unification-78}, and the type systems have the principal type property. Recently, these type inferencing methods have been applied to \oo\/ languages \cite{cardelli:mult-84}. Our contribution is to provide a useful tool for type parameterization for \oo\/ languages which do not have the principal type property. Instead of inferring types from programs we infer parameterized types from unparameterized types, updating the programs accordingly. The control of the parameterization process is given to the user. We describe an example which illustrates the motivations, notations and problems involved in the parameterization process. \subsubsection{Parameterizing classes} The Demeter system allows the creation of parameterized classes. The way these classes are handled by the Demeter system shows how the polymorphism goal can be achieved. These parameterized classes are described in much the same notation indicated above. The difference is that the class names on the left hand sides of the productions may have parameters. A \dd\/ with parameterized classes acts as a template class hierarchy description for an infinite set of hierarchies. To use a member of this set we simply specify actual parameters for the parameterized classes. Suppose we have the following \cm\ which describes a generic tree data structure: \bv Tree(Nodetype) : Leaf(Nodetype) | Deeptree(Nodetype). Leaf(Nodetype) = Nodetype. Deeptree(Nodetype) = Nodetype Tree(Nodetype) Tree(Nodetype). Example = Tree(Number). \end{verbatim} The {\tt Tree} class has a parameter {\tt Nodetype } whose actual value will be a name of another class. This parameter specifies the kind of tree we want for our current application, e.g., a tree of numbers, identifiers, records etc. When an instantiation of this class is needed, as in the case of {\tt Example } above, the Demeter system expands the template to arrive at a standard class-dictionary. The following is generated for the example. \bv Example = Number-Tree. Number-Tree : Number-Leaf | Number-DeepTree. Number-Leaf = Number. Number-DeepTree = Number Number-Tree Number-Tree. \end{verbatim} In addition, abstract classes {\tt Tree, Leaf and DeepTree } are generated from which classes {\tt Number-Tree, Number-Leaf, Number-DeepTree} inherit. This enables software to be written for the template which can then be used for all the derived \dds. The names of the derived classes are calculated using a formula which ensures unique naming. The semantics of parameterized classes are specified relative to the semantics of normal classes. For a discussion of the considerations and restrictions of the expansion process see \cite{lieber-riel:oop}. Class parameterization (our goal) performs the inverse of this expansion process. We start with the \dd\ \bv Example = Number-Tree. Number-Tree : Number-Leaf | Number-DeepTree. Number-Leaf = Number. Number-DeepTree = Number Number-Tree Number-Tree. \end{verbatim} and specify that we want to parameterize with respect to {\tt Number} and that we want to call the parameterized classes {\tt Tree, Leaf} and {\tt DeepTree}. The result is the parameterized \cd\ shown earlier. Parameterization of the structure of classes is not enough. We also have to parameterize the methods. For the method parameterization process to work properly, we require that the methods are written in good style. It is beyond the scope of this paper to explain the parameterization of methods.