\section{Introduction} One of the important tasks of the \oo\ research community is to develop novel tools and methods for teaching object-oriented programming and design \cite{knudsen-madsen:teach}. This paper reports on our teaching approach which we have used since 1986 to present object-oriented programming and design both in academic and industrial environments. Our research is aimed at developing a programming language independent method for the study of object-oriented programming. \bv Copyright (C) 1989 Karl Lieberherr \end{verbatim} The key contribution of our method is to improve programmer productivity by several factors for an important part of the development process: The design of the structure of classes and the preparation of a library which is personalized by the structural class definitions. The key ideas behind our method are \bi \item to use a more expressive class notation than in existing object-oriented programming languages and \item to take advantage of the expressiveness by providing a large number of custom-made utilities similar to a personalized library. These utilities are provided in a specific object-oriented language, e.g., C++ or Flavors, and impressively simplify the programming task. \ei %We call our method the \demsign\ method and it is supported by the %Demeter system. %Examples of utilities which are generated or provided generically %by the Demeter system are: class definitions in a programming language, %application skeletons, %parsers, pretty printers, type checkers, object editors, %recompilation minimizers, pattern matchers and unifiers. %The Demeter system supports the user in defining the classes (both their %structure and functionality) %with the following support tools: Consistency checker (semantic rules and type %checking at the design level), learning tool which learns %class definitions from example %object descriptions, LL(1) corrector, script generator based on %wishlist, application development plan generator %\cite{karl1:class} \cite{lieber-riel:oop}. Our method includes an ordered set of objectives designed to guide the uninitiated user from zero knowledge about object-oriented programming through class definitions, inheritance, subtyping, and finally the most powerful level of data abstraction, the parameterization of classes. The method of teaching object-oriented programming by objectives is valuable since it provides a metric by which the user can gauge his or her progress. In addition to a useful metric, this method provides a facility through which users can begin their studies at a level commensurate with their experience. We divide the study of object-oriented programming both horizontally and vertically. The horizontal divisions occur along four major levels of difficulty. At each horizontal division we examine each objective using a two-tiered (vertical division) paradigm. The upper tier examines the data and other structural abstractions such as function signatures and inheritance links. The lower tier examines the functional details at the implementation level (in an underlying object-oriented language such as Lisp/Flavors or C++). This approach separates the definition of object manipulation from the definition of object structure. We gain the following advantages in separating a program into two tiers: \bi \item A separation of concerns and a division of effort: The structural aspects are written and checked first before the details of object manipulation are specified. \item Reusability: The structural definitions (upper tier) can be used with different programming languages. \item Ease of learning: The upper tier allows students the ability to explore concepts without having to deal with the underbrush of a programming language syntax. \ei We provide many interesting objectives which must be mastered at each horizontal division of the subject. Each of these divisions focuses on one large area of object-oriented programming while each objective is associated with one concept in the large area. The first horizontal division deals with simple class definition and application development. At this stage of learning, the student develops a solid foundation of class definition skills and a good object-oriented programming style. An integral part of learning class definition skills is a thorough understanding of the part-of hierarchy and methods for optimizing it. We introduce a method of modularizing class dictionaries which allows users to work with manageable pieces of the underlying data structure, and, at the same time, hide implementation detail. Once the student has mastered all the objectives at the first level of difficulty, he or she progresses towards the second level. This level provides an introduction to inheritance by focusing on the use of single inheritance for writing generic code. The study of inheritance continues on the third level which centers on multiple inheritance and its use as a method for reducing code size and complexity. In addition, much time is spent analyzing the use of inheritance for reusing classes and their software with the goal of increasing programmer productivity. In this section of the course we spend a large amount of time analyzing proper vs. improper uses of inheritance. We have found many examples where the improper use of inheritance has actually led to loss of reusability. The fourth and final horizontal division examines the use of parameterized classes. This powerful form of abstraction is discussed with respect to the production of generic software modules designed to be reused in a number of different applications. At each horizontal division we use a module notation for breaking up class hierarchies into pieces which are easier to design and implement. While modules are primarily used to break up large projects, we have found them useful to students working on small assignments as well. One major benefit of modules is the inclusion of function signatures with their corresponding classes. This provides the student with a high level view of the data structure along side of the code structure. For the purpose of this paper we have decided to avoid discussing the module notation at each horizontal division. Instead the module notation and a discussion of its motivation and use is provided in the last section of this paper. In coordination with our ordered set of objectives for the study of object-oriented programming, we have developed a programming language independent meta-tool called the \demsign\ system. The Demeter system supports our method and exhibits many of the objectives that we have developed, i.e., the system is capable of performing many of the lower-level objectives discussed. Since the Demeter system is written in its own technology, the students can bootstrap their knowledge by studying problems as they relate to this meta-tool. A major advantage of Demeter is that it can be built on top of any object-oriented programming language so long as the language contains a data abstraction mechanism and multiple inheritance. This allows for the incremental examination of the object-oriented programming paradigm without regard to a particular programming language. Our system currently generates code for C++ and Lisp/Flavors. \section{A Word on Notation} In our courses we have used an EBNF-based notation for describing class hierarchies. The benefits of this notation are plentiful. A major advantage is that a large class hierarchy combining both part-of and inheritance hierarchies can be cleanly displayed on one or two pages (one line per class). Another advantage is that the resulting class hierarchy can be sugared with concrete syntax to define an LL(1) language. This allows two views of the underlying data structure, a view as a collection of classes and a view as an application specific language. This helps the object-oriented design stage of projects whose class representations map to abstract rather than real world objects. For example, it may be difficult to find good objects to describe a simulator for a programming language but it is easy to see what the inputs to such a system would be (i.e. the syntax of the programming language itself). In such a system the language view makes the task of finding the objects very easy. In this paper we use an expanded version of our notation that is used in our classes. The abstract syntax of our expanded notation and the EBNF notation are identical. For a description of our EBNF notation see \cite{lieber-riel:oop}. %We have found that students learn this EBNF language quickly and enjoy using %it. For the uninitiated reader, however, the notation is cryptic and we felt %that a more verbose notation would make the paper easier and more enjoyable %to read. Therfore, we have developed a more %readable notation to describe data and function signature abstractions. It %is helpful to note that this new notation is equivalent to the EBNF notation %and is implemented simply as a separate front end parser to the Demeter system. %In fact, this separate front end is actually generated by the system itself. %For a description of our EBNF notation see \cite{lieber-riel:oop}. \section{Class Dictionaries -- The Beginning} The first knowledge that the object-oriented programmer must develop is a conceptual meaning for a class, an object, and the relationships between such entities. A common question among users of object-oriented environments is, ``Once I've decided to use object-oriented programming for a particular problem, how do I select my objects and how do I relate them to each other?''. This task is closely related to selecting an underlying data structure for an action-oriented program. The notation we use, called the class dictionary notation, converts the task of defining objects into an easier design step. In the \cd\ notation a given class is always constructed from other classes in one of three ways. Either a new class is made up of a fixed set of defined classes, or the new class is made up of a list of another class, or the new class is one of several possible classes. We refer to these methods of class creation as construction, repetition, or alternation (respectively). Thus, we are either constructing an object in terms of other objects (a construction production), or we are defining an object as being a collection of zero (one) or more of another object (a repetition production), or we state that an object is one of several possible objects (an alternation production). Examples of these three object descriptions are shown in expanded \cd\ notation below. \medskip \begin{itemize} \item Construction $-$ An object of class $A$ is an object of class $B$ followed by an object of class $C$, and possibly an object of class $D$. The optional concrete syntax appears when an object is pretty-printed. \smallskip \bv CLASS A HAS PARTS "any concrete syntax" b : B "more syntax if desired" c : C OPTIONAL d : D; END CLASS A. \end{verbatim} \smallskip \item Repetition $-$ An object of class $A$ is a list of zero or more objects of class $B$. \smallskip \bv CLASS A IS LIST "possible concrete syntax" REPEAT { "syntax" B "more syntax" } "even more syntax" END CLASS A. \end{verbatim} \item Alternation $-$ An object of class $A$ is either an object of class $B$ or an object of class $C$ or an object of class $D$ where $B$, $C$, and $D$ all have common components $X$ and $Y$ which are added to $B$, $C$ and $D$. \smallskip \bv CLASS A IS EITHER B OR C OR D HAS COMMON PARTS x : X "syntax if desired" y : Y END CLASS A. \end{verbatim} \smallskip \end{itemize} A collection of these class descriptions are called a class dictionary. The class dictionary is not only a description of a class hierarchy. It can be interpreted as a description of an application language defined across the object domain. Such a language is useful for creating objects from ASCII descriptions, for pretty printing objects, and for many other tasks. In the \cd\ notation we require that the application language be made a member of the LL(1) class of languages. If the LL(1) condition is not satisfied initially, it can be met by adding concrete syntax to the class definitions in appropriate places. % This is done by adding concrete syntax as is % shown in the examples above. The addition of concrete syntax only affects parsing and pretty printing of objects. It is stripped out of the class definitions for the purpose of class definition generation (e.g. Flavors or C++ classes), application skeleton generation, etc. The Demeter system guarantees that all user produced code is completely shielded from the concrete syntax. This implies that the input language for an object hierarchy can be modified at the whim of the user with no risk to the reliability of the system. This modification can be done at any point in the development of a class hierarchy. We took advantage of this feature to implement our expanded notation. Once the user has developed a class dictionary for his or her application, the Demeter system can generate many software modules to support object-oriented programming. The motivation for the software generation is to free the student from a lot of tedious programming. The following list describes some of the software which is provided in generic form or generated automatically by the Demeter system: Class definitions (in the underlying object-oriented language, pretty printing methods, a scanner/parser for the application language, an application skeleton, a structure-directed editor, and graphical object drawers. We like to introduce our students to class dictionary development by finding a real world example. %to which they can relate. Past examples have included Meals, Libraries, Airplanes, and most recently, a patchwork quilt \cite{sethi:bear}. We present such examples by first defining them in English and then in our notation. \begin{enumerate} \item A patchwork is made up of a list of primitives (i.e., pieces of cloth) followed by a description of a pattern defined as a sequence of nested turning and sewing commands. \item A primitive contains a pattern name (an identifier), a length and a width (both numbers). \item A pattern is either a primitive, a turning command or a sewing command. \item A turning command contains a nested pattern and a length and width. \item A sewing command contains two patterns and a length and width. \end{enumerate} \noindent The corresponding class descriptions are: \begin{verbatim} CLASS Patchwork HAS PARTS "The patchwork uses:" primitives : Primitive_list "The commands are:" pattern : Patchwork_exp END CLASS Patchwork. CLASS Primitive_list IS LIST REPEAT { Primitive } END CLASS Primitive_list. CLASS Patchwork_exp IS EITHER Primitive OR Turn_exp OR Sew_exp END CLASS Patchwork_exp. CLASS Primitive HAS PARTS "primitive" pattername : Ident OPTIONAL "length" length : Number; OPTIONAL "width" width : Number; END CLASS Primitive. CLASS Turn_exp HAS PARTS "(turn" arg1 : Patchwork_exp ")" OPTIONAL "length" length : Number; OPTIONAL "width" width : Number; END CLASS Turn_exp. CLASS Sew_exp HAS PARTS "(sew" arg1, arg2 : Patchwork_exp ")" OPTIONAL "length" length : Number; OPTIONAL "width" width : Number; END CLASS Sew_exp. \end{verbatim} The input language defined by the concrete syntax of this class hierarchy allows for the translation of an ASCII description of a Patchwork into an object hierarchy or a Patchwork object hierarchy into its associated ASCII representation. These utilities are automatically generated by the Demeter system from the class description above. A sample ASCII description is shown below: \begin{verbatim} The patchwork uses: primitive A length 3 width 3 primitive B length 4 The commands are: (sew (turn primitive A) (turn primitive A)) (sew (sew primitive A primitive B) (sew primitive A primitive B)) \end{verbatim} There are many objectives which revolve around the basic class dictionary model. The student should master these before moving on to some of the more difficult objectives since many of the later objectives are generalizations of these simpler ones. We have found it beneficial to first have students build object hierarchies using the constructor functions of each class, introducing the scanner/parser and ASCII representation of objects later. This allows students to concentrate on the core of each objective without getting bogged down with the principles related to the parsing and scanning of languages. Once the student has a grip on the objectives then parsing of object descriptions is discussed as an analogy to what they already know. The following list contains the objectives derived from this basic class dictionary model, i.e., unparameterized class dictionaries with no explicit inheritance. \begin{itemize} \newpage \item Legal Object Objective Given a class dictionary and an object hierarchy the student will determine whether the object hierarchy is legal with respect to the class dictionary. It is helpful to recall that the class dictionary stores all part-of (i.e., containment) links implicitly. These links determine whether an object is legal or not. (lower and upper tier when nested constructor functions are used, upper tier when a concrete syntax description is used) \item Object Drawing Objective Given a class dictionary and a legal object description, the student will draw (sketch) the object which results once the description has been used to create an object hierarchy. The legal object description takes the form of a function containing object constructor functions or a concrete syntax description of the object hierarchy (in the application specific notation defined by the class dictionary). (lower and upper tier when nested constructor functions are used, upper tier when concrete syntax descriptions are used) \item Object Printing Objective Given an object hierarchy and a class dictionary the student will describe the output of the Demeter provided pretty printing methods. In addition, the student will study the algorithm employed for the pretty printing of objects. (lower and upper tier when nested constructor functions are used, upper tier when concrete syntax descriptions are used) \item \smallskip Class Dictionary Objective The student will write a class dictionary for any real world system with which he or she is familiar. In the past some popular real world systems have been restaurants, beaches, universities, spaceships, and car engines. A good size for such a first class dictionary is 20 to 30 class abstractions. The use of all three data abstraction types (i.e., construction, repetition, and alternation) is desirable. (upper tier) \item Legal Input Objective Given a class dictionary the student will write several ASCII object descriptions which are legal with respect to the class dictionary. This provides the conceptual link between the class dictionary and its definition of an application specific language. (upper tier) \item Syntax Tree Objective Given a class dictionary and a legal object description, the student will draw (sketch) the object which results once the description has been used to create an object hierarchy. The legal object description takes the form of an ASCII input file which can be parsed by the Demeter provided parser. Before drawing the object the student will check the ASCII input for syntax errors. This task develops an understanding of the effect of concrete syntax in class dictionaries on the parsing of the application specific language defined by that class dictionary. (upper tier) \item Class Definition Objective This objective is a two part task. The student will first learn the syntax for defining classes in the chosen underlying object-oriented system (e.g. Flavors, C++). Once this skill has been mastered, the student will study the algorithm for generating class definitions from a class dictionary. Given this algorithm and any class dictionary the student will be expected to write down the class definitions for the system modelled by the class dictionary. Once this objective has been mastered the student can ignore class definitions, since the system will automatically generate the proper syntactic descriptions from the class dictionary. (upper and lower tier) \end{itemize} \section{Style Rules -- Writing methods} Once the user has acquired a firm foundation of knowledge concerning classes and their definitions, the role of class dictionaries in object-oriented design, and the functionality of the provided object-oriented utilities, he or she is ready to begin writing methods. The philosophy behind the \cd\ notation is to push the user into the right design decisions without cramping his or her style. Our ``push'' for forcing the right decisions when choosing class types and their relationship to each other was providing the class dictionary notation. We offer the user the choice between using a simple, natural description language for a class hierarchy or writing his or her classes in the syntax of the underlying system. Of course, we provide an additional incentive to use the class dictionary approach, i.e., we generate lots of nice utilities which the user would otherwise have to write by hand. Our users have found that the class dictionary approach gives them so much for so little that it would be silly to write their classes by hand. The class dictionary approach does not prevent them from modelling any domain which they could have modelled by writing their own class definitions. While the class dictionary provides a nice constraint or normal form on the data in the system we have not introduced a similar constraint or normal form on method writing. Such a constraint should not overburden the user with rules. It should be very concise and easy to follow. It should also demonstrate a large return on the time invested in learning to follow it. In addition, anything written without the constraint must be rewritable using the constraint, i.e., the constraint cannot restrict the power of the underlying object-oriented system. We have presented such a constraint in \cite{LHLR:law-paper}, \cite{karl-ian:soft1} and received much feedback, the most extensive in \cite{sakkinen:law-88}. For the purpose of this paper, we state this constraint (which we call the Law of Demeter) as follows: \medskip \begin{itemize} \item Law of Demeter In any method M attached to a class C only methods defined by the following classes may be used: \smallskip \begin{enumerate} \item The instance variable classes of C. \item The argument classes of method M. Note: Global objects or objects created inside the method M are considered arguments to M. \end{enumerate} \end{itemize} This Law simplifies both programming and maintenance. The complexity of a programming task is reduced since the Law reduces the number of classes a programmer has to be aware of when writing a method. We have found that the advantages of following the Law are sufficient incentive for users to follow the relatively simple constraint that the Law demands. The objectives which should be mastered by students at this level include: \begin{itemize} \item Object Traverser Objective The student will write an object traverser (skeleton) for each class defined in the class dictionary. This skeleton is the starting point for many application programs. It is automatically generated by the Demeter system but the student should practice generating it by hand. (upper tier) \item Design and Implementation Objective Given a simple problem domain familiar to the student and a simple task, the student will write a class dictionary and an object-oriented program which implements the task. (lower and upper tier) \item Program Modification Objective Given a class dictionary, an object-oriented program which performs a task, and a list of class modifications the student will update the class dictionary as prescribed by the list of class modifications and modify the object-oriented program to work with the new class dictionary. (lower and upper tier) \item Style Objective Given an object-oriented program and its class dictionary the student will determine if the program is written in good style (i.e., satisfies the Law of Demeter). If it is not written in good style then he or she will rewrite it in good style without changing the functionality. (lower and upper tier) \item Signature Objective Given a class dictionary and an object-oriented program the student will determine which classes can react to which methods, listing the argument types and return type of each method. (lower and upper tier) \item Type Finding and Checking Objective Given a class dictionary and an object-oriented program the student will list the type of each expression and/or statement. The student will check for type errors in the program and correct any that are found. The available type information consists of the class dictionary, the types of method arguments, and the return type of methods. (lower and upper tier) \end{itemize} \section{Generic Programming} In this section we introduce a collection of abstract classes from which all instantiable classes in the Demeter system inherit. These abstract classes, called Universal, Repetition, Construction, and Terminal, allow for some hidden common instance variables and provide a place to attach class dictionary independent methods. The programs we use to demonstrate this type of class organization are generic traversal, search and copy methods. The input to such a program is a table consisting of all the classes defined by construction productions (i.e., ``HAS PARTS" class descriptions). This input is generated from the class dictionary. The program itself is generic and defined only on the Demeter abstract classes. The end user of such a program need only send his object the ``traverse'', ``search'' or ``copy'' message. Typically, a user of the Demeter system does not write a lot of generic code attached to Universal, Repetition, Construction, and Terminal. We include it in a study of object-oriented programming because it provides an ideal framework for introducing students to single inheritance. The objectives mastered in this section will provide a foundation for the study of explicit multiple inheritance. We have found multiple inheritance to be troublesome for students who have not been properly introduced to simple inheritance. %The abstract class hierarchy in Demeter consists of four classes called %Universal, Repetition, Construction, and Terminal. The class Universal is at the top of the hierarchy. The abstract class Repetition inherits from the class Universal and is inherited by any user defined class which is specified by a repetition production (i.e., a ``LIST'' class description). Similarly, the abstract class Construction inherits from the class Universal and is inherited by any user defined class which is specified by a construction production (i.e., a ``HAS PARTS'' class description). The abstract class Terminal also inherits from Universal. It is inherited by all class terminals. The predefined class terminals are Number, String, Ident, and Keyword. The Demeter system also provides a facility for defining user specified class terminals. The Terminal class has one instance variable named val which class terminals use for storing their actual value. For example, the number 9 would be stored as a Number object whose val instance variable is set to 9. The program which clones a copy of an object from another can be implemented in an underlying language using the abstract classes along with some additional information gleaned from the class dictionary. In C$++$ this additional information is in the form of a generated function which takes the name of a class as an argument and returns an instance of that class. In Lisp/Flavors it is in the form of a collection of methods which return the names of the parts of classes. The objective which students are expected to master at this level is: \smallskip \begin{itemize} \item Generic Programming Objective Given a task which can be used with any class dictionary (e.g. traversing, searching, parsing, pretty printing, copying), the student will write the task in generic form. This may include generating some class dictionary dependent information %(e.g. :rhs) and attaching methods to the abstract classes Universal, Repetition, Construction, and/or Terminal. (lower tier) \end{itemize} \section{Multiple Inheritance} In the previous section we discussed how each object inherits from one of the abstract classes Repetition, Construction, or Terminal. It is often desirable to allow a class to inherit from other user defined classes. We have identified two distinct cases of inheritance which are vital to efficient object-oriented software development, commonality and specialization. In addition, we show that specialization is really just a kludgy form of commonality and should be avoided if reusable code is desired. \subsection{Commonality} The first case occurs when a user has developed many classes whose behavior is identical for one or more tasks or which contain some common data. In this case an abstract class should be defined from which all the user defined classes will inherit. The common task (data) can then be attached to (hidden in) the abstract class. For example, a particular restaurant may serve many different desserts of which most cost one dollar and one costs two dollars. Also, we know that all dessert objects contain the number of calories. If we need a set of member functions which computes the cost of a dessert we could define the dessert and methods as follows. \bv CLASS Dessert IS EITHER Cake OR Jello OR Cheesecake HAS COMMON PARTS calories : Number END CLASS Dessert. double Cake::cost() { return(1.00); } double Jello::cost() { return(1.00); } double Cheesecake::cost() { return(2.00); } \end{verbatim} These methods are obviously redundant. The redundancy occurs because a collection of classes have commonality with respect to a particular task, namely, computing cost. We rewrite member functions to take advantage of the commonality by using inheritance. \bv double Dessert::cost() { return(1.00); } double Cheesecake::cost() { return(2.00); } \end{verbatim} As can be seen from the example, classes defined in an ``IS EITHER" class description are defined as being abstract. The classes defined in the ``OR" clause are all derived classes (i.e., subclasses) of the abstract class. The abstract class is used as a convenient place to attach methods which will be used by subclasses via inheritance. \subsection{Specialization} A second case where a user will want to use multiple inheritance is the construction of new classes from old classes. This situation occurs when there is an existing class for which a lot of software has been written. A user wants to add some item to the old class thereby obtaining a new class, but wants to take advantage of all the old software attached to the original class. Consider a corporation where all new employees get a basic medical plan, a salary, and vacation (in days). Once an employee has been with the company for a year or more he or she gets some additional benefits such as a dental plan, sick time, and a company car. Assume the class NewEmployee has been defined as follows. \bv CLASS NewEmployee HAS PARTS medical : MedicalPlan salary : Number vacation : Number date_hired : Date END CLASS NewEmployee. \end{verbatim} Also assume we have written lots of software attached to NewEmployee which calculates medical benefits for a given illness, annual raises based on current salary and number of days with the company, etc. We now want to construct the class FullEmployee which includes extra benefits in addition to everything making up the NewEmployee. We could simply ignore the fact that NewEmployee exists and construct FullEmployee from scratch and rewrite lots of code, or we could simply inherit from NewEmployee. Inheritance of one class by another is achieved by adding an ``INHERITS FROM CLASSES" clause to the class description. The class FullEmployee can be defined as follows: \bv CLASS FullEmployee HAS PARTS dental : DentalPlan sicktime : Number company_car : Car INHERITS FROM CLASSES NewEmployee; END CLASS FullEmployee. \end{verbatim} Now we need only write the extra code to handle the extra benefits (i.e., the dental plan, sick time, and company car). The one drawback of specialization is that there is no way to change the definition of NewEmployee without also affecting the class FullEmployee. Consider the case of a company requiring identification badges of all new employees. Once the employee has been with the company for six months he or she becomes a full employee and is no longer required to have a badge. This model cannot support such a modification because specialization is a half-baked form of commonality. A better way to implement the class FullEmployee involves the construction of an abstract class from which NewEmployee and FullEmployee inherit. This model is shown below. \begin{verbatim} CLASS AllEmployees IS EITHER NewEmployee OR FullEmployee HAS COMMON PARTS medical : MedicalPlan salary : Number vacation : Number date_hired : Date END CLASS AllEmployees. CLASS NewEmployee HAS PARTS badge : Badge END CLASS NewEmployee. CLASS FullEmployee HAS PARTS dental : DentalPlan sicktime : Number company_car : Car END CLASS FullEmployee. \end{verbatim} In this model, changes which should affect both new and full employees can be implemented in the abstract class ``AllEmployees" while changes to just new employees can be safely implemented in the ``NewEmployee" class without affecting the rest of the inheritance hierarchy. In general, whenever specialization is used it should be replaced by an abstract class and the commonality use of inheritance. Unfortunately, inheritance is not always so straight forward. Often we would like to inherit from a class but we would like to override one or more of its instance variables with new classes of our own. For example, consider a graph of numbers which is stored as a list of edges (two nodes per edge). This class may be defined as: \bv CLASS CoordGraph HAS PARTS edgelist : CoordEdgeList END CLASS CoordGraph. CLASS CoordEdgeList IS LIST REPEAT { CoordEdge } END CLASS CoordEdgeList. CLASS CoordEdge HAS PARTS "from" from : Coord "to" to : Coord END CLASS CoordEdge. CLASS Coord HAS PARTS "(" x : Number "," y : Number ")" END CLASS Coordinate. \end{verbatim} Assume we have again written many routines attached to these classes. Some possibilities include graph traversal, tests for isomorphism, and graph permutation. A new user arrives on the scene and he or she would like to code the travelling salesman problem using a graph of numbers similar to the one defined above except each edge needs to be labeled by a number which corresponds to a weighted distance. We can construct a new class dictionary which accomplishes this goal but minimizes the amount of code our new user must write. This minimization is accomplished by using inheritance throughout our new class dictionary. We use the ``OVERRIDING" clause to replace some instance variables of the inherited classes. \bv CLASS LabeledCoordGraph HAS PARTS INHERITS FROM CLASSES CoordGraph; OVERRIDING edgelist : LabeledCoordEdgeList; END CLASS LabeledCoordGraph. CLASS LabeledCoordEdgeList IS LIST REPEAT { LabeledCoordEdge } END CLASS LabeledCoordEdgeList. CLASS LabeledCoordEdge HAS PARTS "label" distance : Number INHERITS FROM CLASSES CoordEdge; END CLASS LabeledCoordEdge. \end{verbatim} The student is made aware that inheritance can very easily be misused. The result of this misuse is software which is not inherently reusable. Misuse of inheritance is a trap into which many object-oriented programmers (both new and seasoned) fall. The problem is that multiple inheritance is used as a replacement for the part-of relation. For example, consider three classes called Wing, Cockpit, and Fuselage. If we wanted to create a class called Airplane we could do it in one of two ways. Either use a nested class definition (i.e. a part-of relation) or use multiple inheritance. The two implementations are shown below. \begin{verbatim} CLASS Airplane HAS PARTS f : Fuselage w : Wings c : Cockpit END CLASS Airplane. CLASS Airplane HAS PARTS INHERITS FROM CLASSES Fuselage, Wings, Cockpit; END CLASS Airplane. \end{verbatim} If we only examine the data portion of the class Airplane we find very little distinction between the two implementations. In C$++$, the constructor functions for both classes are syntactically identical. However, the design issues are dramatically different. In the first implementation (using part-of relations) the three classes Fuselage, Wings, and Cockpit are merely implementation details of the class Airplane. Users of the class Airplane do not have to learn about these three classes since they are considered hidden data. Any member functions attached to those classes are not visible to users of airplanes. In essence, the Airplane class is a black box. The second implementation is much different. Since an airplane inherits all of the functionality of Wings, Fuselage, and Cockpit, users of the class Airplane need to know about all of the functionality associated with those components. To carry the philosophy one step further, we could implement Wings as inheriting from Rivets and SheetMetal. In this example an Airplane would know about a function called ``heat'' simply because Rivets must know how to be heated. The result is a huge protocol in the Airplane class of which only a few functions are useful. The rest appear due to inheritance. This creates a white box atmosphere where users of the Airplane class must know about all of the inherited classes. %This misuse of inheritance is %briefly discussed in [HALPERN'S PAPER ON INHERITANCE]. Our philosophy for using inheritance is as follows: Only use inheritance if the use is one of specialization or commonality. Always favor the use of ``part-of" relations over inheritance since they produce black box implementations which are much easier to maintain than the white box implementations commonly associated with misused inheritance. %At this stage in teaching object-oriented programming we have brought a %student with a firm foundation in the principles of good object-oriented %design to the point where he or she can reuse both class definitions and %their methods to develop new classes and applications. In the process of %demonstrating good reusability techniques the student acquires the basic %concepts of multiple inheritance and its uses. These concepts are made %more palatable through the use of real world examples and a clean syntax %which presents the entire inheritance hierarchy in a clear %and concise manner. The objectives we discussed earlier have to be mastered again now in the presence of multiple inheritance. \section{Parameterized Classes -- Application Families} The \cd\ notation supports a powerful form of data abstraction called class parameterization. Although a class dictionary and its generated software provide a nice environment for developing a given application, it is often the case that a user will write %find %himself (herself) writing similar applications many times over. For example, a user may write an application which requires a binary tree of numbers as part of an underlying data structure. After that task is finished he or she is presented with a problem which requires a binary tree of identifiers. Our application writer realizes that much of the code he or she wrote for a binary tree of numbers is directly applicable to a binary tree of any type. Algorithms such as ordered traversals (preorder, postorder, inorder), node balancing, node addition, and tree searching are independent of the data stored at the nodes. This being the case our application writer would like to define a parameterized class dictionary which contains a generic tree. Individual application writers can then instantiate this generic tree to create trees of numbers, identifiers, meals, or anything else imaginable. A user who detects generic attributes between two or more data structures will extract them from their class dictionaries and create a new class dictionary which possesses the generic attributes as parameters. For example, our generic Tree class is defined and instantiated as follows. \bv CLASS Tree PARAMETERIZED BY CLASSES (N) IS EITHER Leaf(N) OR Node(N) END CLASS Tree. CLASS Leaf PARAMETERIZED BY CLASSES (N) HAS PARTS "leaf" data : N END CLASS Leaf. CLASS Node PARAMETERIZED BY CLASSES (N) HAS PARTS data : N left : Tree(N) right : Tree(N) END CLASS Node. A sample instantiation of trees: CLASS Trees IS EITHER Tree(Number) OR Tree(Ident) END CLASS Trees. \end{verbatim} The instantiation of the parameterized Tree class will be automatically expanded to look like a class of type NumberTree and a class of type IdentTree. However, the main advantage of parameterized classes is not their ability to automatically create new classes (although this feature saves lots of time). Their major contribution is the ability for an application writer to attach generic code to the Tree class. The expansion process creates inheritance links between the generic class Tree and Number-Tree, Ident-Tree, or any other type of tree. For a more thorough discussion of parameterized classes in the Demeter system refer to \cite{lieber-riel:oop}. The objectives discussed earlier have to be covered again now in the presence of parameterized classes. \section{Modules -- The Organization} Class dictionaries and the Law of Demeter can % good programming style help to gear the student towards a solid, clean underlying data structure and modifiable code. For large programming projects this is often not enough. It is necessary to have a logical method for breaking up the underlying data structure into manageable pieces which also provides for information hiding. We call these {\it class modules}. A \cm\ consists of a list of public and private parts. The idea of having modules arranged in public and private parts is motivated by the goal of information hiding. A public part consists of public class definitions and their corresponding method headings written in a programming language independent notation. A private part consists of programming language independent information such as extended or additional type definitions and method headings. These definitions are private to the module. It is helpful to note that a class defined in a public part of the module may later be extended in another private or public part of a module. The private parts of a class module have access to all of the classes defined in their corresponding public parts. In addition, modules can import selected classes and their methods from other modules. This importation is achieved by writing the module name followed by two colons and the desired class name. We present an example of a module by defining a public and a private part of a module for a stack. The stack, in this case, is parameterized with the type of object being placed on it. \bv MODULE Stack_related PUBLIC CLASS Stack PARAMETERIZED BY CLASSES (Kind) HAS PARTS IMPLEMENTS INTERFACE empty() RETURNS TYPE Boolean, push(element : Kind), pop() RETURNS Kind, display () {CALLS Kind => display()} END CLASS Stack. PRIVATE CLASS Stack PARAMETERIZED BY CLASSES (Kind) HAS PARTS elements : List_related::List(Kind) END CLASS Stack. END MODULE Stack_related. \end{verbatim} Modules and their organization into public and private parts provide the following advantages: \begin{itemize} \item Abstraction, Information Hiding Modules allow for the construction of abstraction hierarchies which cannot be built from classes alone. A module allows us to abstract from implementation details, allowing us to not only ignore the innards of the implementation but also hide them. The primary goal of hiding implementation details is to localize the area of error search in the case of a malfunctioning program. This is achieved since each module can have its functionality tested separately. A secondary goal is to make internal changes to a module invisible to those modules which use that module. For example, if we would like to implement our stack using an array instead of a list then any modules which import our stack module should not be affected. We provide three types of information hiding: \begin{itemize} \item Hiding method bodies The programming language dependent bodies of methods are hidden from the user of a module. All the auxiliary methods for implementing the exported methods are also hidden. \item Hiding of parts All the instance variables of a construction class may be hidden in the implementation modules (as in the Stack class defined above). This is directly analogous to data hiding in C$++$. \item Hiding auxiliary classes All the auxiliary classes which are needed for implementing the exported classes are hidden. This type of hiding is not available in C$++$. \end{itemize} \item Separate Environment Generation (in analogy to separate compilation) Modules can be kept in a library and automatically referenced when an environment skeleton is generated. Hence, it is possible to prepare collections of frequently used modules with the intention of avoiding their reprogramming. A sophisticated implementation goes even one step further and offers {\it separate environment generation}. In such an implementation, the modules are not only stored in source form, but also in generated form. Upon generation of an environment skeleton for a module M, the environment of module M is joined with the pregenerated environment skeletons of the modules from which M imports. Separate environment generation contributes to both the efficiency of program development and reliability of the resulting code. \item Name Conflict Avoidance When a project requires a large class dictionary, the likelihood of name conflicts is increased. The problem of name conflicts can be easily managed through the use of modules. All imported classes are prefixed by their module name. \item Type Checking at the Design Level If the function signatures include a ``CALLS" clause listing all of the message sends that will be implemented in the associated function then the Demeter system can check the design for message sends to which the application will not be able to respond. \end{itemize} Our notion of modules has been used in a number of programming languages, ranging from Mesa, to Modula-2, Ada, OBJ2, FOOPS, etc. However, our modules are above the programming language level and provide a programming language independent description of a system. \section{Design method} In \cite{alg-des:89}, Steier presents a theory of human algorithm design. He compares his theory with results about human design mechanisms in other areas (Lisp programming, Fortran programming, software design, mechanical design and architectural design) from a collection of seven papers. The theory of algorithm design as well as the other seven studies about human design support the following claim: {\bf Design is driven by evaluation in the context of examples: Designers run their solutions to evaluate them in the context of some input to the program.} This statement gives strong support for object-oriented design to incorporate objects and not only classes. This is done in \cite{booch:86} and other object-oriented design methods. In which form should objects be describable in the design notation? \bi \item object descriptions with their explicit parts. These object descriptions allow the designer to focus on the structure and concrete syntax representation of objects. \item object descriptions in concrete syntax form. Those object descriptions are useful since they are usually much shorter than object descriptions with explicit parts. \item communication histories. They show the interactions between objects, i.e., the messages which are sent by a given message sending. \ei We sketch now the design algorithm in \oo\ form. The following \cd\ contains only the information which is relevant for the design algorithm. \bv CLASS Design HAS PARTS modules : List(Module) END CLASS Design. CLASS Module HAS PARTS classes : List(Class) objects : List(ObjectDescription) communicationHistories : List(CommunicationHistory) END CLASS Module. CLASS Class HAS PARTS production : Rule interface : List(Operation) END CLASS Class. CLASS Operation HAS PARTS sig : Signature dependencies : List(Call) acquaintances : List(Acquaintance) END CLASS Operation. \end{verbatim} Design algorithm: \bv Design::design(req : Requirements) while not all modules completed select incomplete module m; m -> design(Requirements); Module::design(req : Requirements) while not all classes completed select incomplete class c: first focus on physical objects and input and output objects of the application. Then focus on the objects needed for supporting efficient algorithms. Write or update object descriptions representative for class c; c -> design(objects); Write or update communication histories representative for class c; c -> design(communicationHistories); Class::design(objects : List(ObjectDescription)) Generate or update production capable of generating the objects; Check for compatibility between all object descriptions and production; Class::design( communicationHistories : List(CommunicationHistory)) Generate or update interface corresponding to communicationHistories; Check for compatibility between all communication histories and interface; while not all operations in interface completed select operation op (follow growth plan order in method group); op -> design(communicationHistories); Operation::design( communicationHistories : List(CommunicationHistory)) Generate or update the dependencies corresponding to communicationHistories. Check for compatibility between all communication histories and dependencies. Generate or update the acquaintances. \end{verbatim} This description refers to the following concepts which we have not yet been introduced and which are briefly explained below: growth plan order: A \cd\ determines an ordering on the classes which is partitioned into growth phases \cite{ian-karl:preventive}. This ordering allows application development and testing in small steps. method group: It is a collection of methods which are collaborating for one task. Usually many methods in the same group have the same name. The design method as described above should be interpreted flexibly. Often, the control flow is different in the actual design process: there are even several parallel loci of control. For reasons of clarity we have omitted this flexibility from the design method description. \section{Conclusion} We have identified the need for a programming language independent method for teaching \oo\ design and programming. With this need as a guide, we have presented a formal curriculum for presenting the object-oriented programming paradigm to new users. The curriculum consists of a collection of progressively more difficult objectives supported by a programming language independent meta-tool named Demeter. The objectives provide a useful metric by which the user can gauge his or her progress while the Demeter system frees the user from tedious programming tasks which he or she has already mastered. The use of a structured set of objectives also provides a learning environment where users can begin their studies at a level commensurate with their experience. We divide the study of object-oriented programming into four horizontal divisions based on conceptual difficulty, i.e., simple class definitions and methods; single inheritance; multiple inheritance; and parameterized classes. %The %latter being a powerful form of data abstraction which focuses on building %reusable software modules adaptable to a wide variety of applications. We %present this method of data abstraction by drawing analogies between parameterized %classes and parameterized languages within one simple framework. This %framework is implemented as a collection of utilities with the Demeter system. Each level of difficulty contains a collection of objectives which are to be mastered before moving onto the next level. Many objectives are represented on each level in a modified form which takes advantage of new knowledge gained by the student. Each of these horizontal divisions are further broken up into a two-tiered, vertically divided analysis of each topic. The upper tier is concerned with data and other useful abstractions (e.g. signatures of methods). It is independent of the underlying object-oriented programming language. The lower tier is concerned with functional implementation details. This is programming language dependent and will vary according to the chosen host language. We have found the Demeter system to be an extremely effective tool in helping our students to become productive programmers in C++ and Flavors. We have noticed a significant productivity improvement in our students after they have learned the Demeter method using the behavioral objectives partially described in this paper. Both the Demeter system and the set of objectives have been developed in coordination with our students. %We have %found that students often provide the clearest indication of a well %formed objective. Our current objectives have been developed and refined by more than 300 students since 1986 in both academic and industrial courses. We have received much favorable feedback from students who have used their new data abstraction skills in commercial settings. %We will continue our refinement %of the current objectives and work on the addition of new ones wherever %appropriate. We invite the object-oriented programming %community to test our objectives with %both new and intermediate students of the object-oriented programming %paradigm and report on any modifications they find useful. \medskip \centerline{{\bf Acknowledgement}} We would like to thank the hundreds of students who took our courses and the dozens of implementors (Northeastern University students) of the Demeter system. Without their feedback and support, this paper would never have been written. Cindy Brown and Mitch Wand helped us several times along the way. Paul Steckler gave us feedback on the paper.