%\documentstyle{article}
\documentstyle[12pt]{article}
%\pagestyle{headings}
%\hyphenation{Sa-mi-chlaus}
%\hyphenation{Weih-nach-ten}



\makeatletter
\def\section{\@startsection {section}{1}{\z@}{-1.5ex plus -1ex minus -.2ex}{1.5ex plus .2ex}{\large\bf}}
\def\subsection{\@startsection{subsection}{2}{\z@}{-1.25ex plus -1ex minus -.2ex}{1.5ex plus .2ex}{\large\bf}}
\def\subsubsection{\@startsection{subsubsection}{3}{\z@}{-1.25ex plus -1ex minus -.2ex}{1.5ex plus .2ex}{\large\bf}}
\oddsidemargin 0cm
\textwidth 17cm
%\textwidth 20cm
\addtolength{\topmargin}{-2.5cm}
\raggedbottom
\textheight 22cm
%\textheight 27cm
\parskip 8pt plus 1pt minus 1pt
\parindent 0pt

\begin{document}
\bibliographystyle{alpha}
%\bibliographystyle{abbrv}

%\title{Object-oriented programming: \\ 
%{\normalsize Grammars = Datastructures}}
%\author{Karl Lieberherr, Northeastern University}

%\maketitle
%\pagestyle{empty}
\input common
\input pictures
%\documentstyle[12pt]{article}
%\documentstyle[proc]{article}

%\begin{document}

%\title{Demeter: A CASE Study of Software Growth\\
%Through Parameterized Classes}
%\author{Karl J. Lieberherr, Arthur J. Riel\\
%Northeastern University, College of Computer Science\\
%360 Huntington Avenue, Boston MA 02115}
%
%\maketitle
%\input /fiona/csfaculty/lieber/papers/new-obj/common.tex
%%\input /fiona/csfaculty/wand/tex/time.tex 
%\centerline{Texed at \thetime\ \today}

\begin{abstract}
The $Demeter^{TM}$ system
is a CASE (Computer-Aided Software Engineering) tool
designed for the development of large software projects using 
a new software design methodology 
which focuses on growing rather than building software.  
We describe the software development
process as one of growth and evolution as opposed to building and rebuilding
because
most complex objects in the real world are grown 
and not built.   Since software design is obviously a complex process this new
paradigm may be helpful in unraveling some of the problems associated with current
software design practices.
Demeter begins by providing an ideal environment for the sprouting and nuturing of a seed 
(class dictionary) into a plant (large scale software project).  In addition, through
the combined use of object-oriented programming technology, 
and parameterized classes, Demeter provides a facility for the reuse of software
which was developed in previous software projects.  
\end{abstract}

\noindent
A short form of this paper was published in \cite{lieber-riel:singapore}.

\begin{itemize}
\item
To appear in {\em Journal of OBJECT-ORIENTED PROGRAMMING}, Vol.1, No.3, 1988.
\end{itemize}

\newpage

%\noindent {\bf Keywords:}
%\medskip
%{
%\settabs \+\indent\quad&\cr
%\+&Automatic Programming\cr
%\+&Parameterized Classes \cr
%\+&Object-oriented Programming\cr
%\+&Program Generation\cr
%\+&Program Transformation\cr
%\+&Software Engineering\cr
%\+&Software Reusability\cr
%}
%\bye

\section{Introduction}
%\noindent {\bf Introduction}

The primary purpose of the
$Demeter^{TM}$ system 
is to provide a medium for efficient growth and evolution of large scale software projects.
We describe the software development process as one of growth and evolution as opposed to building and 
rebuilding because most complex objects with few repetitive building blocks are grown
and not built \cite{mills:grow-71} \cite{brooks:silver}.  Examples of these are plant and animal life.
Software, being a very complex creature, should not be built from bits and
pieces of inanimate code which is sewn together and shocked into life with a
marathon session of debugging.  A creature created in such a fashion is assured of 
sharing the same fatal flaws as other creatures created in this fashion (e.g.
the Frankenstein\footnote{The American Heritage Dictionary defines a Frankenstein as ``An agency or creation that slips from the control of and ultimately destroys its creator''.}
monster).  Instead, the software plant should be grown from a small 
but animate sprout.  At each stage of growth the creature will become more 
complex but will always exhibit characteristics appropriate for that stage of 
development.  
%Any addition which changes the behavior of the creature in an
%adverse way can be removed, modified, and replaced with very little effort.

Demeter, appropriately named for the Greek goddess of the earth, provides an
ideal environment for the planting of a small prototype system
(sprout) and its nurturing into a fully developed software system.  In addition, Demeter provides
the necessary facilities for grafting whole or part of previously developed
software systems to the new system or even grafting the new system
onto a suitably developed root stock (a parameterized class).
The Demeter system creates such an environment by marrying object-oriented
programming techniques with a common data structure description language and 
the concept of parameterized class.  Through the use of this environment,
large software environments can be grown from humble beginnings, borrowing
at each stage of development the experience (code) gained in any 
previously grown projects.


%\section{A Problem in Software Design Philosophies}
%\noindent {\bf A Problem in Software Design Philosophies}
%
%Most of the current philosophies on the design and development of large 
%software projects hinge on the method of breaking the large project into
%manageable pieces and assigning pieces to individuals or small groups.
%The completed pieces are then integrated into the large software system.
%The expectation is that so long as a common interface is understood by all
%involved then integration can be accomplished in reasonable time and the 
%result will be a good working system.
%This paradigm seems adequate for many real world examples such as the 
%construction of buildings and
%the manufacture of automobiles. However, when this method is applied to 
%large software projects the result is usually less than a success.
%Software is a much more complex system than buildings or automobiles, both of
%which can be mapped by a two-dimensional diagram.   As Brooks has 
%pointed out, software cannot be mapped
%by any single two-dimensional diagram$\lbrack$Brooks87$\rbrack$.
%
%When many modern day
%software developers find that their large software projects can
%not be completed by one person in the allotted time they follow this divide and
%integrate philosophy.  In many cases the individuals who work on a fragment
%of the system are not capable of visualizing the whole working system.
%When a system is fragmented it is often impossible to see generalizations
%which run through the design.  It is the realization of these common threads 
%in a project
%which leads to a clean system and possibly interesting discoveries.  Consider
%an insight discovered by the Unix developers that was one factor leading to the success
%of their operating system.  The idea of treating every device as a file and
%thereby creating a common interface for all known devices was
%unique at the time of the discovery.  The chance of this type of discovery
%in systems developed under the divide and integrate model is close to nil.
%Of course there is always the chance of the integration team detecting such common
%threads at the time of integration, but at that stage in the development
%process no one would dare to request a system rewrite.  Recall that it is a 
%lack of schedule time which forces the software developer into this particular
%design philosophy in the first place.
%
%The Demeter philosophy avoids this destructive paradigm completely.  

%We claim
%that large software systems cannot be successfully built from inanimate code
%fragments just as other complex organisms are not built from inanimate pieces
%which are sewn together at the end of the development process.  Demeter
%attempts to grow a large software system from small seeds or by reusing
%code from old plants which have been grown earlier from seeds.  Demeter provides
%the growing medium, and an 
%application specific fertilizer for the growing system.
%%a means
%%of easy evolution from one form to another, and a facility for using any code
%%written for previous systems.

The Demeter 
system makes extensive use of parameterized classes.  Parameterized classes
are best thought of as generic software modules which can be used and 
reused by a large
assortment of projects so long as they are of the same species.  We 
consider the relationship between parameterized classes and software projects 
to be similar to the relationship between root stocks
and fruit trees.
A root stock is a
tree grown solely for its roots.  The variety of the tree is typically winter
hardy and disease resistant but otherwise uninteresting in fruiting habit.
This root stock is used as a strong generic rooting system for trees of the
same species which have spectacular fruiting habits but poor immunity to 
cold and disease.  We graft the desired variety onto the root stock and get
a superior tree.  We could have produced such a tree by years of selective
breeding within the desired variety, but by using the root stock we save a
significant amount of time.  
The parameterized classes of Demeter have much in common with root stocks.  They provide
a base of software with some very desirable properties.  
%We use this base
%without modification
%to build a spectacular system which is specific to a given problem.
We present several clear examples of these constructs in the appropriate
section below.

\section{Demeter Class Dictionaries (The Seeds)}
%\noindent {\bf Demeter Class Dictionaries (The Seed)}

All large software projects should begin with a description of the underlying data
structure.  It is the underlying data structure which is the backbone of any
software system. A poor design at this level is the shortest road to 
disaster.
In Demeter, the first step in designing a software environment is the construction
of a class dictionary.  The class dictionary is a natural description of the 
object
hierarchies which make up the underlying data structure.  Demeter class 
dictionaries are defined by an LL(1) language whose description appears in a form
similar to EBNF.  Any actions which are to be carried out in the ``program''
are reduced to manipulations of the object hierarchy.  The machine readable
data structure is automatically generated, along with an abundance of support
software, by the Demeter system.  When a user describes his or her
data structure abstractly, he or she gains the advantage of having a common data 
structure for all software
 projects.  This allows for the
building of a facility for reusing any software previously written in the
Demeter system regardless 
of the nature of the old software project.

The Demeter system 
is currently implemented in Franz Lisp/Flavors.  In this implementation an
object hierarchy is built out of Flavor instances and object manipulations
are written as method definitions.  The Demeter system could be ported to any
language which has facilities for defining objects and classes of objects,
instance variables attachable to an object or class, and a multiple inheritance 
mechanism.  
%Demeter will run under an object-oriented version of Prolog via
%a translator which translates Lisp objects into Prolog objects.  In addition,
The porting of the Demeter system to the following languages
is now under review: Objective-C, C$++$, Common Lisp (CLOS),
PC Scheme with Scoops and Prolog with an object-oriented extension.

Many complex class dictionaries have been written, tested, and developed 
into full fledged software systems.  We begin by constructing a class
dictionary which represents a real world system, namely, a meal. 
We first construct this class dictionary in English 
and then transcribe it into the language of Demeter in order to illustrate the
naturalness of the system.

At some point in defining a class dictionary we must decide what
we consider to be atomic objects.  In a meal a steak might be considered atomic
since we are not interested in breaking the meat down into its molecular
structure.  A shrimp cocktail might be considered by some to be atomic, but for
the purpose of this example we assume that we are ignorant of the 
notion of a shrimp cocktail and need to break it down further.  Atomic objects 
are presented as terminal symbols in our grammar (typically strings).  We 
define our meal as follows:
%\medskip
\begin{enumerate}
\item A meal is an appetizer, an entree, and a dessert.  While a 
dessert may be considered optional in many households, we consider it a
required part of a meal.

\item An appetizer is a melon or a shrimp cocktail.

\item A shrimp cocktail is lettuce, one or more shrimp, and possibly
cocktail sauce.

\item Cocktail sauce is ketchup and horseradish.

\item An entree is a steak platter or a baked stuffed shrimp platter.

\item A steak platter is a steak and the trimmings.

\item A baked stuffed shrimp platter is a stuffed shrimp and the trimmings.

\item The trimmings are a potato and two veggies.

\item A veggie is carrots, peas, or corn.

\item A dessert is pie, cake, or jello.

\item We assume that the following items are atomic and need no 
further description: melon, shrimp, lettuce, ketchup, horseradish, steak,
stuffedshrimp, potato, carrots, peas, corn, pie, cake, and jello.  
\end{enumerate}
The
decision as to whether an object is atomic or built up from other objects is 
not only domain
specific but also specific to the person performing the data abstraction.

Each of the eleven descriptive phrases falls into one of three 
categories.  Either we are constructing an object in terms of other objects
(a construction production), or we are defining an object as being an
ordered 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 Demeter notation below.




\begin{description}
\item[Construction] 
An element of class {\tt A} has a first part which 
is an element of class {\tt B} followed
by an element of class {\tt C}, possibly an element of class {\tt D},
and an element of class {\tt E}.
\bv
  A = B C [D] E.
\end{verbatim}

A construction class may inherit from another construction class.
An element of class X has a first part which is an element of class X
followed by a second part which is an element of class Z
followed by all parts of class A.

\bv
  X = Y Z *inherit* A.
\end{verbatim}

\item[Repetition]
An element of class {\tt A} is a collection of zero (one) or more elements
of {\tt B}.
\bv
  A ~ { B }.
  A ~ B { B }.
\end{verbatim}
\item[Alternation]
An element of class {\tt A} is either an element of classes {\tt B} or
{\tt C} or {\tt D}.
\bv
  A : B | C | D.
\end{verbatim}

%An element of class {\tt E} is either an element of classes {\tt F}
%or {\tt G} or {\tt H}. All these alternatives have common objects which
%belong to classes {\tt X} and {\tt Y}.
%
%\bv
%  E : F | G | H *common* X Y.
%\end{verbatim}

If the alternatives have common properties, we use alternation
with implied inheritance. An element of class A is either an element
of class B or C and both B and C have two parts, the first being
an object of class X and the second an object of class Y.
(X and Y are the last two parts of B and C.)
\bv
  A : B | C *common* X Y.
\end{verbatim}

\end{description}
Many times we want to add keywords to our object descriptions.  These may be
necessary to satisfy the LL(1) restriction on the grammar or may be used to
``sweeten'' the syntax of a class dictionary.  In any event they have 
no effect on the object 
hierarchy descriptions.
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 to the whims of the user with no risk to
the reliability of the system.  This modification can be done at any point in the
system development. The only restriction is that the structure of the 
underlying object hierarchy must remain static.
Below are examples of construction and repetition
productions which demonstrate where concrete syntax can be inserted into the
object descriptions. 

\begin{description}

\item[Construction Production]
.

\begin{verbatim}
  A = "a" B "followed" "by" "a" C 
      "inherits-from-Q"
        *inherit* Q
      "end-inherit"
      ["maybe" D "!!"] 
      "followed by" E.
\end{verbatim}

\item[Repetition Production]
.

\begin{verbatim}
  A ~ "first" B 
      {"prefix" "String" B "suffix"}
      "terminating".
\end{verbatim}

\item[Alternation Production]
.

\begin{verbatim}
  Fruit : Orange | Apple
    *common* "weight" <weight> Number "terminating".
\end{verbatim}
\end{description}

Many class dictionaries make use of descriptive labels in their construction 
productions.  A descriptive label is an identifier which is enclosed in angle
brackets and preceeds a given nonterminal.  The sole purpose of descriptive 
labels is to rename a sub-object in the class dictionary.  This renaming is 
required if two (or more) of the same nonterminal are identified on the right
hand side of a construction production.  The following is an example of such
a production, it defines an object A which is comprised of two B's.
\begin{verbatim}
  A = <first> B <second> B.
\end{verbatim}
The other case in which descriptive labels
are often used is with class terminals.  When 
a class terminal is used without a label it is not descriptive.  We use
labels to make the objects more self describing.  The following example 
illustrates this point.
\bv
  GradeReport = Ident Number.
\end{verbatim}
\noindent is not self describing.  The following is semantically equivalent
but makes the class dictionary, and any methods written for it, easier to
read.
\bv
  GradeReport = 
    <studentName> Ident 
    <testScore> Number.
\end{verbatim}

It is important to note that the object stored at a symbol position remains
the same whether or not it is labeled.  The labels are used only for descriptive
purposes and are analogous to the renaming of variables.
Labels are also used to override instance variable types in connection with
inheritance in construction or alternation productions.
(We use class and type as synonyms.)

\bv
A = B <label> K.
X = D *inherit* A *override* <label> L.
M : P | Q *common* *inherit* A *override* <label> L. 
\end{verbatim}

An element of class {\tt X} is an element of class {\tt D} followed
by all elements of class {\tt A}. The type of the instance variable
called {\tt label} is {\tt L} and not {\tt K}.
An element of class {\tt M} is either an element of class {\tt P} or
{\tt Q}. Both {\tt P} and {\tt Q} have in common all the instance
variables of {\tt A}, with the type of instance variable {\tt label}
changed to {\tt L}.

Certain instance variables
are inherited by all objects.  The instance variables {\it attribute} and
{\it father} are inherited by all Demeter defined objects.  The instance
variable {\it attribute} is an application specific variable which can be
used to ``decorate'' the objects.  The latter instance variable
is used in constructing backward pointers in an object hierarchy.  There
are also some instance variables which are inherited by certain classes of objects.
All repetition objects inherit the instance variable {\it child}.  This 
instance variable contains a list of the repeated objects used to define the 
repetition object.  In addition, each class terminal (i.e.,
Ident, Number, String)
inherits the instance variable {\it val} which contains the value of the 
identifier, number, or string (respectively).

The instance variables father, attribute, child and val are attached
to classes as shown in Fig. ``Class hierarchy organization''.
Each repetition class inherits from class repetition and each
construction class inherits from construction. Class terminals (e.g. Ident)
inherit
from terminal and all three classes: construction, repetition
and terminal inherit from universal.

\begin{figure}
\begin{verbatim}
                     universal
                [father, attribute]
                        | 
                        | 
       |----------------|---------------|
       |                |               |
       |                |               |
   construction      repetition      terminal
       |             [child]         [val] 
       |                |               |
       |                |               |-----|-------|
       |                |               |     |       |
   construction      repetition       Ident Number String
   classes           classes
\end{verbatim}
\caption{Class hierarchy organization}\index{basic class hierarchy}
\end{figure}


\noindent The description of our meal in Demeter notation is as follows:
\begin{verbatim}
  Meal = 
    "Appetizer:" Appetizer 
    "Entree:" Entree 
    "Dessert:" Dessert.
  Appetizer : Melon | ShrimpCocktail.
  ShrimpCocktail = Shrimps Lettuce 
    [CocktailSauce].
  CocktailSauce = Ketchup HorseRadish.
  Entree : SteakPlatter | BakedStuffedShrimp.
  SteakPlatter = Steak Trimmings.
  BakedStuffedShrimp = StuffedShrimp 
    Trimmings.
  Trimmings = Potato 
    <veggie1> Veggie <veggie2> Veggie.
  Veggie : Carrots | Peas | Corn.
  Dessert : Pie | Cake | Jello.
  Shrimps ~ Shrimp {Shrimp}. 
  Shrimp = "shrimp".  Melon = "melon".  etc.
\end{verbatim}
%  Lettuce = "lettuce".
%  Ketchup = "ketchup".
%  Steak = "steak".
%  Potato = "potato".
%  Carrots = "carrots".
%  Peas = "peas".
%  Cake = "cake".
We can now input this class dictionary to Demeter and generate 
an environment skeleton.
We can then create object hierarchies representing meals,
e.g. an input of the form
\begin{verbatim}
Appetizer: melon
Entree: steak potato carrots peas
Dessert: cake
\end{verbatim}
defines a meal. 
%\itemitem{1.} Meal = ``Appetizer:'' Appetizer ``Entree:'' Entree ``Dessert:'' Dessert.
%
%\itemitem{2.} Appetizer $:$ Melon $\vert$ ShrimpCocktail.
%
%\itemitem{3.} ShrimpCocktail = Shrimps Lettuce $\lbrack$ CocktailSauce $\rbrack$.
%
%\itemitem{4.} CocktailSauce = Ketchup HorseRadish.
%
%\itemitem{5.} Entree $:$ SteakPlatter $\vert$ BakedStuffedShrimp.
%
%\itemitem{6.} SteakPlatter = Steak Trimmings.
%
%\itemitem{7.} BakedStuffedShrimp = StuffedShrimp Trimmings.
%
%\itemitem{8.} Trimmings = Potato $\langle$ veggie1 $\rangle$ Veggie $\langle$ veggie2 $\rangle$ Veggie.
%
%\itemitem{9.} Veggie $:$ Carrots $\vert$ Peas $\vert$ Corn.
%
%\itemitem{10.} Dessert $:$ Pie $\vert$ Cake $\vert$ Jello.
%
%\itemitem{11.} Shrimps \space $\sim$ \space Shrimp $\lbrace$ Shrimp $\rbrace$.
%
%\itemitem{12.} Shrimp = ``shrimp''.
%\itemitem{}\space Melon = ``melon''.
%\itemitem{}\space Lettuce = ``lettuce''.
%\itemitem{}\space Ketchup = ``ketchup''.
%\itemitem{}\space etc.
%
This example demonstrates the straight forward translation of our conceptual
understanding of a meal to the Demeter notation.  The representation of a 
system by a hierarchy of object descriptions is very natural to people.
\smallskip

\section{Sprouting and Fertilizer}
%\noindent {\bf Demeter Generation (Sprouting and Fertilizer)}

Once the seed of a project has been established we need to produce a 
working system from it.  In addition to producing this small working system we
would like to provide a large quantity of support code to aid the early system
in its first stages of growth. 
It is known that each plant in the agricultural world grows best when an applied
fertilizer was developed specifically for the given plant.  Similarly, each
system responds best to a set of utilities built specifically for the
class dictionary.  This set of utilities (fertilizer) is produced by the 
Demeter system through a series of software generation steps.
In these steps the following
utilities are generated or provided generically from the information stored in the class dictionary.
%\medskip
\begin{itemize}
\item The class definitions for each object defined in the class 
dictionary.  This frees the user from learning the syntax of defining classes
and frees Demeter from being totally dependent on its underlying implementation.

\item A set of methods for pretty-printing a hierarchy of objects.
It is considered advantageous to have data which is self-describing.  
In Demeter, the type definitions specify the external representation of the
objects.

\item A set of methods for ``drawing'' a hierarchy of objects.  The
current implementation is a simple hierarchical sketch of the object 
hierarchies.  Later implementations will include graphics to give a more
aesthetic image.

\item A scanner/parser for the LL(1) description of the class
dictionary.  This software allows the user to have a hierarchy of objects
built from an ASCII input file which contains the description of the object
hierarchy written in the LL(1) language.

\item A structure-directed editor which allows the user to build a hierarchy of objects by
answering questions about the hierarchy.  This object hierarchy could then
be printed to an ASCII file, via the pretty-printing methods, for later 
reloading by the scanner/parser.  This editor does not require the user
to know about the concrete syntax of the input language so one could refer to
it as a syntax-directed editor as well.

\item A skeleton program (sprout) which defines a sample method for each 
object in the hierarchy.  Each method includes a reference to all of the
instance variables of the object as well as a comment header describing the
object for which the method is defined.  This method is the initial working
system.  Its sole function is to walk through the object hierarchy printing
the value of any class terminals in the hierarchy.  The Demeter system 
supports the predefined class
terminals Ident, Number, and String as well as a facility for the definition
of additional class terminals.  The entire system is grown from this simple
skeleton program.  This simple program is the sprout from which the software
plant will be grown.

\item A growth plan generator which suggests in which order 
to grow the plant. The growth plan is determined by the
chromosomes (productions) in the class dictionary (seed).

\end{itemize}

\section{The Growth and Evolution of a System (Nurturing)}
%\noindent {\bf The Growth and Evolution of a System (Nurturing)}

Once a Demeter environment has been generated from the class dictionary
description we want our system to grow and evolve.  We will present two methods associated
with our Meal environment.  The first is to calculate the cost of a meal.  This
method will walk the object hierarchy and compute the cost of each object in 
the hierarchy.  The method is very modular, thanks to the object-oriented 
nature of Demeter, so we can use it to compute the cost of any 
component of a meal as well.  
We define food costs in the following menu:
%\begin{tabbing}
%Baked Stuffed Shrimp  \= 6.00 \kill
%Melon \> .75\\
%Shrimp Cocktail \> .65 per shrimp\\
% \> cocktail sauce .15 extra\\
%Steak Platter \> 5.00\\
%Baked Stuffed Shrimp \> 6.00\\
%Pie \> .60\\
%Cake \> .65\\
%Jello \> .35\\
%\end{tabbing}
Melon 0.75,
Shrimp Cocktail 0.65 per shrimp,
cocktail sauce 0.15 extra,
Steak Platter 5.00,
Baked Stuffed Shrimp 6.00,
Pie 0.60,
Cake .65,
Jello 0.35.

%  It is helpful to note that certain instance variables
%are inherited by all objects.  The instance variables {\it attribute} and
%{\it father} are inherited by all Demeter defined objects.  The instance
%variable {\it attribute} is an application specific variable which can be
%used to ``decorate'' the objects.  The latter instance variable
%is used in constructing backward pointers in an object hierarchy.  There
%are also some instance variables which are inherited by certain classes of objects.
%All repetition objects inherit the instance variable {\it child}.  This 
%instance variable contains a list of the repeated objects used to define the 
%repetition object.  In addition, each class terminal (i.e.,
%Ident, Number, String)
%inherits the instance variable {\it val} which contains the value of the 
%identifier, number, or string (respectively).
\bv
  ; Banquet ~ Meal { Meal }.
(defmethod (Banquet :cost) ()
  (let ((total-cost 
    (loop for each-meal in child sum
      (send each-meal ':cost))))
      (format t "cost of ~A meals: ~A.~%" 
        (length child) total-cost)))
  ; Meal = 
  ;   "Appetizer:" Appetizer 
  ;   "Entree:" Entree 
  ;   "Dessert" Dessert.
(defmethod (Meal :cost) ()
  (+ (send Appetizer ':cost) 
     (send Entree ':cost)
     (send Dessert ':cost)))
  ; Melon = "melon".
(defmethod (Melon :cost) () 0.75)
  ; ShrimpCocktail = Shrimps Lettuce 
  ;   [CocktailSauce].
(defmethod (ShrimpCocktail :cost) ()
  (+ (send Shrimps ':cost)
     (if CocktailSauce 
       then (send CocktailSauce ':cost) 
       else 0.0)))
  ; Shrimps ~ {Shrimp}.
(defmethod (Shrimps :cost) ()
  (loop for each-shrimp in child sum
    (send each-shrimp ':cost))))
  ; Shrimp = "shrimp".
(defmethod (Shrimp :cost) () 0.65)
  ; CocktailSauce = Ketchup HorseRadish.
(defmethod (CocktailSauce :cost) () 0.15)
  ; SteakPlatter = Steak Trimmings.
(defmethod (SteakPlatter :cost) () 5.00)
  ; BakedStuffedShrimp = 
  ;   StuffedShrimp Trimmings.
(defmethod (BakedStuffedShrimp :cost) ()
  6.00)
  ; Pie = "pie".
(defmethod (Pie :cost) () 0.60)
  ; Cake = "cake".
(defmethod (Cake :cost) () 0.70)
  ; Jello = "jello".
(defmethod (Jello :cost) () 0.35)
\end{verbatim}

We now examine a situation which is common in software development.  Our 
restaurant owner takes one look at our finished software and informs us
that our meal definition is all wrong.  The cocktail shrimp should come in
three sizes; small, medium, and large costing 0.20, 0.50, and 
1.00 (respectively).  We kindly ask the irate restaurant owner to have a seat
and relax.  We then make the following changes to our class dictionary without
the least concern of ruining our existing system.  We modify the atomic object
{\it Shrimp} to be an alternation production of the following form.
\bv
Shrimp : SmallShrimp | MediumShrimp | LargeShrimp.
\end{verbatim}
%\medskip
%\item{}Shrimp : SmallShrimp $\vert$ MediumShrimp $\vert$ LargeShrimp.
%\smallskip
We remove the cost method for shrimp and replace it by the following
three method definitions (one for each of the new atomic objects).
\bv
(defmethod (SmallShrimp :cost) () 0.20)
(defmethod (MediumShrimp :cost) () 0.50)
(defmethod (LargeShrimp :cost) () 1.00)
\end{verbatim}

%\medskip
%{
%\settabs\+\indent\quad&NNN&NNN&NNN&NNN&\cr
%\+&(defmethod (SmallShrimp :cost) ()\cr
%\+&&0.20)\cr
%\+\cr
%\+&(defmethod (MediumShrimp :compute-cost) ()\cr
%\+&&0.50)\cr
%\+\cr
%\+&(defmethod (LargeShrimp :compute-cost) ()\cr
%\+&&1.00)\cr
%}
%\smallskip
Modifications are made at or below the point at which the object 
hierarchy definitions are changed.  This allows the user the freedom of 
updating his underlying data structure without having to worry about the loss
of system integrity.


The next set of methods we will define are more complex.  We would like to 
simulate an action such as eating.  When we eat a meal we are left with 
objects which we refer to as garbage.  Each object in the hierarchy either
completely disappears or leaves some object behind.  For example, a melon
leaves a rind, a potato leaves a skin, a steak leaves a bone and possibly some
fat, etc.  The first step in such a task is to build a class dictionary
which will allow us to represent and build a hierarchy of garbage.
This class dictionary can be constructed as follows:
\begin{verbatim}
Gbanquet ~ Gmeal {Gmeal}.
Gmeal = 
  "Appetizer Garbage:" Gappetizer 
  "Entree Garbage:" Gentree 
  "Dessert Garbage:" Gdessert.
Gappetizer : Rind | GShrimpCocktail.
GshrimpCocktail = Shrimptails Lettuce 
  [CocktailSauce].
Shrimptails ~ Shrimptail {Shrimptail}.
Gentree : Gsteak | Gshrimp.
Gsteak = [ Bones ] [ Fat ] Gtrimmings.
Gshrimp = Shrimptail Gtrimmings.
Gtrimmings = PotatoSkin.
Gdessert : Crust | Frosting | GJello.
GJello = [ Jello ] [ WhippedCream ].
\end{verbatim}
The following symbols in this \dd
\bv
Rind, Shrimptail, Bones, Fat, PotatoSkin, 
Crust, Frosting, Jello, WhippedCream.  
\end{verbatim}
are defined by
construction productions each consisting of one or more strings,
e.g., 
\begin{verbatim}
Fat = "fat".
WhippedCream = "whipped" "cream".
etc.
\end{verbatim}

In this example steak and jello can return some optional garbage.  For these
optional choices we flip a coin.  For example, 
some steaks will leave behind bones
and fat when eaten but others will not.  

\bv
  ; Banquet ~ Meal { Meal }.
(defmethod (Banquet :eat) ()
  (make-instance 'Gbanquet 
    ':child 
; initialize Gbanquet slot called child 
      (loop for each-meal in child collect
        (send each-meal ':eat))))
  ; Meal = Appetizer Entree Dessert.
(defmethod (Meal :eat) ()
  (make-instance 'Gmeal 
    ':Gappetizer (send Appetizer ':eat)
    ':Gentree (send Entree ':eat)
    ':Gdessert (send Dessert ':eat)))
  ; ShrimpCocktail = Shrimps Lettuce
  ;   [CocktailSauce].
(defmethod (ShrimpCocktail :eat) ()
  (make-instance 'GshrimpCocktail
    ':Shrimptails (send Shrimps ':eat)
    ':Lettuce (send Lettuce ':copy)
    ':CocktailSauce 
      (send CocktailSauce ':copy)))
    ; copy returns a new object 
    ; which is a copy of the argument
  ; Shrimps ~ {Shrimp}.
(defmethod (Shrimps :eat) ()
  (make-instance 'Shrimptails 
    ':child (loop for each-shrimp 
      in child collect 
        (send each-shrimp ':eat))))
  ; Shrimp = "shrimp".
(defmethod (Shrimp :eat) ()
  (make-instance 'ShrimpTail))
  ; SteakPlatter = Steak Trimmings.
(defmethod (SteakPlatter :eat) ()
  (make-instance 'Gsteak
    ':Bones 
      (if (eql (flip) 'head) 
       then (make-instance 'Bones) 
       else nil)
    ':Fat 
      (if (eql (flip) 'head) 
        then (make-instance 'Fat) 
        else nil)
    ':Gtrimmings (send Trimmings ':eat)))
  ; BakedStuffedShrimp = 
  ;   StuffedShrimp Trimmings.
(defmethod (BakedStuffedShrimp :eat) ()
  (make-instance 'Gshrimp
    ':Shrimptail (send StuffedShrimp ':eat)
    ':Gtrimmings (send Trimmings ':eat)))
  ; Trimmings = Potato 
  ;   <veggie1> Veggie <veggie2> Veggie.
(defmethod (Trimmings :eat) ()
  (make-instance 'PotatoSkin))
  ; Pie = "pie".
(defmethod (Pie :eat) ()
  (make-instance 'Crust))
  ; Cake = "cake".
(defmethod (Cake :eat) ()
  (make-instance 'Frosting))
  ; Jello = "jello".
(defmethod (Jello :eat) ()
  (make-instance 'GJello
    ':Jello 
      (if (eql (flip) 'head) 
        then (make-instance 'Jello) 
        else nil)
    ':WhippedCream 
      (if (eql (flip) 'head) 
        then (make-instance 'WhippedCream) 
        else nil)))
\end{verbatim}

\noindent In such a system a meal input file might look like:
\bv
  Appetizer: 
    smallshrimp smallshrimp smallshrimp 
    lettuce
  Entree: steak potato corn peas
  Dessert: pie
\end{verbatim}

After sending this object hierarchy the :eat message we get a garbage hierarchy
returned to us.  We can send this returned hierarchy the pretty print message
(a Demeter generated method) and print the following ASCII text.  
\bv
Appetizer Garbage: 
  shrimptail shrimptail shrimptail 
  lettuce
Entree Garbage: bones fat potato skin
Dessert Garbage: crust
\end{verbatim}

This technique is powerful in that you can evolve one object hierarchy into
another fairly easily.  This easy evolution frees us from the bounds of 
ineffective programming languages and allows us the liberty of declaring
the following rule:
``If the language you are working with does not allow you to write a necessary
task comfortably, then create your own language and translate the current 
representation into the new representation.''
This rule is meaningful only if the task of creating a new language and 
building a translator is significantly easier than the original task.  This is
usually the case within the realm of Demeter.

%These examples have given an informal introduction to what 
%non-parameterized 
%class dictionaries are used for.


%\documentstyle[11pt]{article}
%\documentstyle[proc]{article}

%\begin{document}

%\title{Demeter: A CASE Study of Software Growth\\
%Through Parameterized Classes}
%\author{Karl J. Lieberherr, Arthur J. Riel\\
%Northeastern University, College of Computer Science\\
%360 Huntington Avenue, Boston MA 02115}
%
%\maketitle
%\input /fiona/csfaculty/lieber/papers/new-obj/common.tex
%%\input /fiona/csfaculty/wand/tex/time.tex 
%\centerline{Texed at \thetime\ \today}


\section{Inheritance (Grafting)}
%\noindent {\bf The Use of Inheritance in Demeter (Grafting)}

There are three ways of acquiring plants.  The easiest and most expensive way is
to buy mature plants.  The major drawback (besides cost) of this method is the 
unavailability of many varieties.  Many plant fanciers decide to
grow their favorite varieties from seed.  While the cost may be lower, the time
involved can be quite substantial.  In addition, there are many things which
can go wrong as our seed takes the long trip from sprout to mature plant.
In the world of software development
we find we have the same two choices.  Either we buy the necessary software
from someone who has already developed it or we develop it ourselves.  Again
we have the same advantages and drawbacks.  There is a fair chance that the 
available software will not be the specific variety we want or it may be of
dubious quality.  If we decide to develop it ourselves then we must be willing 
to wait a long time and there is always the chance of something going wrong 
during that long development process.

Many horticulturists look to a third alternative called grafting.  The process
of grafting involves splicing together part of a desired plant with a host
plant of a related type.  This method 
has the advantage in that the cost is low and much of the risk of nurturing
a seed to maturity is removed.  Software developers are usually at a loss
when they attempt this third alternative.  While plants have a common 
interface (typically a woody tissue) software systems do not.  The chances of 
two systems using the same underlying data structure, the same language, 
and being modular enough to take functions for reuse in a new system
are very low. The Demeter system avoids these problems by providing
a common language for the abstract data structure of each system, a means of 
easy language translation, and very modular coding.
This latter quality is enforced by the underlying object-oriented
technology and the Law of Demeter\footnote {The Law of Demeter states that 
messages may only be sent to self and  objects which are an instance
of a type which is associated with the instance variable types or
argument types of the given method.
This law is discussed in \cite{LHLR:law-paper}}.

The Demeter system grafts one software system onto another through the use
of the keywords $*$inherit$*$ and $*$override$*$ in the class descriptions.  If an 
$*$inherit$*$ keyword prefixes a symbol it specifies that the class is to be 
``copied'' into the host system. For the purpose of language definition
the copying is explicit. For example, 
\bv
A = Ident Number.
B = String *inherit* A "end".
\end{verbatim}
implies that 
the language {\tt B} is defined by
\bv
B = String Ident Number "end".
\end{verbatim}

For the purpose of class definition we use the inheritance semantics of
the underlying object-oriented system. In the above example we simply specify
that class B inherits from class A. We make the assumption that
the underlying \oos\ uses dynamic binding of the first argument, often
called {\tt self}. This implies that the methods attached to superclasses
of a class are available at that class.
A more detailed discussion of inheritance is given later.

The $*$override$*$ keyword is only
used in conjunction with the $*$inherit$*$ keyword.  It specifies that the 
class is to be inherited with some changes which will always be declared after
the $*$override$*$ keyword. A similar approach is taken in Trellis/Owl
\cite{schaffert:trellis-86}.

Our motivation for using override is as follows: A subclass is made from a number of 
superclasses by specifying additional properties (instance variables and methods)
that elements of the subclass must have compared to elements of the superclasses.  It is also necessary to make a 
subclass in which some of the properties inherited from superclasses are modified.  Inherited methods and instance variable types can be modified in a subclass,
subject to some restrictions that insure that the inheritance 
is conceptually a specialization hierarchy. 

The ability to modify the type of instance variables in subclasses is restricted in such a way that static type checking of the class definitions is still possible.
If this property is violated, a warning will be given.
We want the Demeter system to be able to guarantee that if B inherits from A then
all objects in class B may safely be treated as A-objects.
If B is defined by inheriting from A and adding additional variables, then the B-objects may be treated safely as A-objects.
If B is defined by inheriting from A and modifying some of the types of the inherited 
instance variables (i.e. using an $*$override$*$ clause) then the rule that the type
must be specialized will insure that B-objects may be treated safely as A-objects.
The B-objects will know about all the messages that are
known to A-objects.

There is an alternate way of specifying inheritance in the Demeter system:
we can use an alternation production with implied inheritance.
Syntactically this is expressed by using the
the *common* token after the alternatives.  For example,
\bv
   Object : Pen | Brick 
             *common* <weight> Number.
   Pen = ...
   Brick = ...
\end{verbatim}
defines an abstract class (one which will never be instantiated) Object
which is inherited by both Pen and Brick. Pen and Brick have a
common instance variable called weight.  It is helpful to think of these classes
in terms of like relations.  We say that a Pen is like a Brick in that they 
share a common data definition, namely, a weight.
Alternation productions
are the 
preferred way of introducing inheritance since it expresses the generalization principle in 
a natural way.  Of course, for the purposes of grafting from previously developed projects,
the explicit $*$inherit$*$ is necessary. We assume that the underlying \oos\
supports transitivity of the inheritance relation.



Our class dictionary notation requires that we give our 
data type information precisely for instance variables.
If we say that an instance variable x is of type A, where A is defined by a construction production then x cannot contain an instance of a subclass of A; 
it has to be an instance of A.  If we want to store a subtype of A in x we cannot define A
by a construction production; we have to use an alternation production which 
specifies the legal subtypes of A.

For the definition of legality of objects and for
subtyping, we need to define
the set of classes associated\index{associated classes} with a given class.
As an abbreviation of associated(S) we use S'.

\begin{definition}
For a construction,  repetition or terminal class $S$,
{\rm S'} is $S$.
For an alternation class $S$, {\rm S'} consists of
the union of the classes associated with the alternatives
on the \rhs\ of the alternation production.
\end{definition}

For the following \dd,
\bv
   Expression : Simple | Compound.
   Simple : Ident | Number.
   Compound = ...
\end{verbatim}
{\tt Expression'} consists of
{\tt Ident}, {\tt Number} and {\tt Compound}.

\begin{definition}
A construction object is {\rm legal} with respect to
a construction production 
if every instance variable contains
an object which is an instance of a
class associated with the instance variable class
given in the production. There is an exception
for optional instance variables: their value may be nil.

A repetition object is {\rm legal} with respect to
a repetition production 
if every element of the object is an instance of a class
associated with the class on the \rhs\ of the repetition
production. If the repetition production does not allow
an empty list, the repetition object must contain
at least one element.

A terminal object is {\rm legal} if it contains a value
which satisfies the rules defined in the
scanner generator specification (i.e. its lexical definition).
%(to be discussed later).
\end{definition}

For defining the subtype concept we need the following definitions:
\begin{definition}
A class T directly inherits from class S if the definition
of T is of one of the following forms:
\bv
   T =  ... *inherit* S ...
   S : T | ... *common* ...
\end{verbatim}
\end{definition}

\begin{definition}
A class T inherits from class S if there is a sequence of
intermediate classes which form direct inheritance links between
class T and S.
\end{definition}

For example, the following production implies that Orange inherits
from class EatableObject. Fruit is an intermediate class.

\bv
Fruit : Orange | Apple
  *common* *inherit* EatableObject.
\end{verbatim}

\begin{definition}
The class T is compatible with class S
if the classes associated with the  class T are a subset of the classes
associated with class S.
\end{definition}


\begin{definition}
A class T is a subtype (or subclass) of class S if 
%T and S
%are related by the transitive closure of the following relations:
\begin{itemize}
\item
T inherits from S or
\item
T is compatible with S.
\end{itemize}
Every class is a subtype (or subclass) of itself.
\end{definition}
We can summarize the subtype definition by:
 
 \begin{quotation}
 \fbox{Subtype} =
 \fbox{Inheritance} or 
 \fbox{Compatibility} 
 \end{quotation}

To illustrate the subtype definition,
consider the following example:

\bv
AutoDealer = <cars> List(Car).
Car :
  GasolineCar *override* <fuel> Gasoline |
  CombustionCar *override* <fuel> GasolineOrCoal 
    *common* "speed" <speed> Number *inherit* Machine.
List(S) ~ {S}.
GasolineCar = "gasolinecar".
CombustionCar = "combustioncar".
Machine = 
  "age" <age> Number "fuel" <fuel> FuelType.
FuelType : Coal | Gasoline | Electricity.
GasolineOrCoal : Gasoline | Coal.

Gasoline = "gas".
Coal = "coal".
Electricity = "electricity".
\end{verbatim}

We define a class {\tt Car} which inherits from class {\tt Machine}.
The {\tt Car} class has two alternatives: {\tt GasolineCar} and
{\tt CombustionCar}. Both override the inherited instance variable type
for {\tt fuel}. A machine can have any type of ``fuel'', be it gas, coal
or electricity. A combustion car can use only gasoline or coal.
Since we want to consider a combustion car as a special kind of
car, we have introduced compatibility into our definition of subtype.
There are other reasons to have both compatibility and inheritance in
the subtype definition: reduction of inheritance links, avoidance of
multiple inheritance, and efficiency.

The main idea behind the subtype definition is that if a type knows about a message then all 
objects belonging to subtypes of that type also know about that message.  
We want to prove that any combination of compatibility and inheritance will 
support this condition.  The combination of compatibility and inheritance tends
to constrain the form of class dictionaries.  This is partially due to the 
fact that we restrict inherited classes to those defined by construction 
productions.
We follow several definitions by a case analysis on the 
legal structure of class dictionaries for each of the four
compatibility/inheritance combinations.  We will define several semantic rules
to deal with class dictionary structures which violate our definition of 
subtype.

To support our subtype definition we
need need to introduce the
concept of a signature. 
Informally, signature(S) for a class S
consists of all messages m to which all classes in S' can react to
by having a method attached to them or by inheritance.

To define the concept of signature more formally, we use the following notation:

\begin{definition}
\begin{itemize}
\item
A class $S$ is {\em responsive} to message m if m is attached to S
or there is a class T such that m is attached to T and there are
direct inheritance links from S to T.

\item
A class $S$ knows message m if each class in S' is
responsive to m.

\item
$Signature(S) = \{m | S$ knows m $\}$.
\end{itemize}
\end{definition}

The distinction  between responsiveness and knowledge is useful;
knowledge involves the compatibility relationships while responsiveness
relies on inheritance.
%$signature(C) = \{m | m$ is a message to which any instance of $C$ will respond $\}$
% $attached(S)$ is the set of methods attached to class $S$.

We give now the rules for computing the signature of a class.
We define
$attached(C)$ to be the set of methods attached to $C$.
We assume that the subtype graph does not contain cycles
and we apply the following rules to a topologically
sorted order of the classes.
We assume that the signature
of the abstract classes universal, construction, repetition, and terminal
are given.
\begin{itemize}
\item
CONSTRUCTION:

\bv
S = <name> A ...
signature(S) = 
  {name, set-name, ...} union 
    signature(construction) union
      attached(S).

S = *inherit* A.
signature(S) = 
  signature(A) union 
    signature(construction) union
      attached(S).

S = <name1> A ... *inherit* B *override* <name2> C ...
signature(S) = 
  {name1, set-name1, name2, set-name2, ...} union 
    signature(B) union
      signature(construction) union
        attached(S).

\end{verbatim}

\item
REPETITION:

\bv
S ~ {R}. 
signature(S) = signature(repetition) union
  attached(S).
\end{verbatim}

\item
ALTERNATION:

\bv
   S : A | B.
\end{verbatim}

\bv
signature(S) = signature(A) intersection signature(B) 
\end{verbatim}

\item
ALTERNATION with implied inheritance:

\bv
S : A | B *common* X Y.
A = <b> Ident.
B = <c> Ident.

signature(S) = 
  (signature(A) intersection signature(B)) union
    {X, Y, set-X, set-Y} union
      attached(S).

signature(A) = 
  {b, set-b} union signature(S) union
    signature(construction) union
      attached(S).
signature(B) = 
  {c, set-c} union signature(S) union
    signature(construction) union
      attached(S).
\end{verbatim}
\end{itemize}

%This completes the definition of signature.

% \begin{definition}
% A class S is said to ``know'' about a message m if m is a member of
% Signature(S).
% \end{definition}

We are now ready to prove an important property of the subtype
predicate.

\begin{theorem}
{\rm Name-Signature-Theorem:}
If {\rm T} is a subtype of {\rm S} then {\rm signature(T)} is a superset
of {\rm signature(S)}.
\end{theorem}

To prove this theorem we need to define semantic rules
which are easily checked at compile-time.
We state those semantic rules in the proof at the place where they are needed
to highlight the exact dependency of of the theorem on the semantic rules.

The proof is divided into the proof of four claims.
They state that
knowledge of messages and responsiveness to messages are transmitted
properly along inheritance and compatibility links. 

\begin{claim}
If B inherits from A and A is responsive to m, then B is responsive to m.
\end{claim}

This follows immediately from the definition of responsiveness and the
transitivity of inheritance.

\begin{claim}
If B inherits from A and A knows m then B knows m.
\end{claim}

We have only to discuss the case where A knows m, but is not responsive to
m. This implies that A is defined by an alternation production and every
class in A' is responsive to m. If B is in A' then B is
not an alternation and is responsive to m 
and therefore knows about m. 
If B is not in A', we have two cases: In the first case,
B inherits from A using a *inherit* link. If we request that A be a construction
class, we know that A must be responsive to m (which implies that B is 
responsive to m and therefore B knows m.)
%If B is not in A', we must have that A=A'.
%This holds if A is a construction, repetition or terminal class.
%For reasons not mentioned here, we choose that A must be a construction class
%and we get therefore the following semantic rule.
Therefore we use the following semantic rule.

\begin{semantic-rule}
Inheritance with *inherit* is only allowed from construction classes.
\end{semantic-rule}

In the second case, B is a subclass of A through alternation productions
with implied inheritance and B is an alternation class itself.
The claim follows with the following
semantic rule:
\begin{semantic-rule}
In an alternation class with implied inheritance (i.e. using {\tt *common*})
the alternatives which are defined by
alternation productions must also
use implied inheritance.
\end{semantic-rule}

\begin{claim}
If B is compatible with A and A is responsive to m, then B is responsive to m.
\end{claim}

A must be defined by an alternation production. If A is responsive to m
then A has either m attached or inherits it. 
If A has m attached, we require that
the alternation production has implied inheritance with the following rule:

\begin{semantic-rule}
If an alternation class has a method attached, it must be defined with
implied inheritance (i.e. with *common*).
\end{semantic-rule}

As a side-effect,
this rule implies that if A is responsive to m then A knows m.
Note that an alternation class B can only inherit from another class
if B is an alternation class with implied inheritance.

\begin{claim}
If B is compatible with A and A knows m then B knows m.
\end{claim}

A must be defined by an alternation production. We have to discuss the
case where A knows m but is not responsive to m. All classes
in A' are responsive to m. If B is in A' then B is responsive to m
and therefore knows about m. 
If B' is a subset of A', the claim holds by the definition of knowledge
of a message.
%B  must be in A', since otherwise
%A = A' which in turn implies that knowledge of m and responsiveness
%to m coincide.

These four claims allow us to prove the theorem as follows: If T is a subtype
of S then there must be a sequence of compatibility
and/or inheritance links between T and S. The claims guarantee
that the knowledge relation is transitive along those links
which completes the proof of the Name-Signature-Theorem.





The subtype concept is used both for checking whether the type of
the first actual parameter of a method is a subtype of the first formal 
parameter type
and for checking the specialization hierarchy property for $*$override$*$.
The above proof guarantees the desirable property of name compatibility
for Demeter subtypes.  We have proven stronger forms of compatibility, but a 
discussion of this topic is beyond the scope of this paper.
We now prove the transitivity of
the subtype relation by examining four cases.  This proof is 
needed since our subtype definition contains a disjunction (or).
The subtype transitivity theorem is not essential for object-oriented programming.
It is the Name-Signature-Theorem that is important.


\begin{theorem}
{\rm Subtype-Transitivity-Theorem:}
The subtype relation is transitive.
\end{theorem}

Proof by case analysis.

\begin{itemize}

\item
If a class C inherits from a class B and the class B inherits from A then
the class C inherits from the class A.  

\begin{enumerate}
\item
True by definition of inheritance.

\end{enumerate} 

\item
If a class C is compatible with a class B and the class B is compatible with
a class A then the class C is compatible to the class A.

\begin{enumerate}
\item
C' $\subseteq$ B' \quad   by def. of compatibility \goodbreak
B' $\subseteq$ A'  \quad  by def. of compatibility \goodbreak
C' $\subseteq$ A'  \quad  by transitivity of subset \goodbreak
C is compatible to A \quad by definition of compatibility \goodbreak
\smallskip
\end{enumerate}


For the last two cases we present class dictionary templates which demonstrate
the relationship between class dictionary structure and subtype links.

\item
If a class C inherits from a class B and a class B is compatible to a class
A then:

\begin{enumerate}

\item
This third case combines inheritance with compatibility such that there exists
a class C which inherits from a class B and the class B is compatible with a
class A.  There are three possible class dictionary templates which will 
produce this type of subtype link.
In the second we use set notation
to restrict the classes which appear on the right hand side of B to be a 
subset of the classes appearing on the right hand side of A.  This is to ensure
the compatibility relation.
\bv

            inheritance            compatibility
    C <---------------------- B <---------------------- A

   case 3a:

      A : B | ..... *common*.
      B : C | ..... *common*.

   case 3b:

      A : C | {X1 ... XN}.
      B : C | { y | y is in subset of {X1 .. XN}} *common*.
      C = ......   

   case 3c (disallowed by semantic rule 5.4): 
     for guaranteeing transitivity, not needed
     for theorem 5.1.

      A : B | ......
      B = .....
      C = *inherit* B.

\end{verbatim}



In case 3a we can prove the subtype relation in two ways.  C is both compatible
to A via the definition of compatibility and C inherits from A via the
definition of inheritance.  This occurs because B is both compatible and 
inherits from A and C is both compatible and inherits from B.

\item
In case 3b the class C is compatible to A by definition of compatibility.  
C' is a subset of A' by inspection.

\item
We disallow the case 3c with the following semantic rule.

\begin{semantic-rule}
A class which is used for inheritance with *inherit* cannot be used as an 
alternative in an alternation production without implied inheritance (i.e.
without *common*).
\end{semantic-rule}

We need this restriction since we cannot reduce the combined subtype links in
class dictionaries of this form to either compatibility or inheritance
exclusively.  Our restriction does not reduce the expressiveness of our
notation.  We can simply add implied inheritance to the alternation production
in case 3c (i.e. we use *common*).

\end{enumerate}


\item
The fourth and final case is a class hierarchy where a class C is compatible
to a class B and the class B inherits from a class A.  There are four cases
where this can occur.  We will analyze these separately.

\bv

           compatibility            inheritance
    C <---------------------- B <---------------------- A

   case 4a:

      A = ......
      B : X | Y | Z *common* *inherit* A.
      C : X | Z.

   case 4b (disallowed by semantic rule 5.3):

      A : B | ..... *common*.
      B : X | Y | Z.
      C : X | Y.

   case 4c:

      A = ......
      B = ...... *inherit* A.
      C : B.

   case 4d:

      A : B | ...... *common*.
      B = ......  
      C : B.

\end{verbatim}


\begin{enumerate}

\item
In case 4a C inherits from A since all elements in C' inherit from
A.

\item
The case 4b has been defined as illegal by a semantic rule.

\item
In cases 4c and 4d the class C inherits from class A since all elements in C'
inherit from A.


\end{enumerate}

\end{itemize}

This completes the proof of the Subtype-Transitivity-Theorem.


\section {Parameterized Classes (The Root Stocks)}
%\noindent {\bf Parameterized Classes In Demeter (The RootStock)}

The notion of parameterized classes is related to grafting in that we 
inherit and/or override
classes when we want to use \mc es.  The difference is that these classes have
one or more formal type parameters.

This parameterization adds complexity to the construction of
a class dictionary, but the power endowed on such a system more than makes up 
for the additional complexity.  Systems which are built around parameterized  
class dictionaries are
constructed under a different philosophy than ones which are built around classes.
Parameterized class systems are typically not designed to be stand alone working 
systems, although they sometimes are.  These systems are built as generic 
foundations to be inherited by many software systems.  By way of analogy, they are
grown for their roots and not their fruit.  The fruiting portion will be grown
in other environments, and each will use the parameterized class system for roots.

%One problem might be that we would like to write 
For an example, consider 
a generic library of 
routines related to graphs.  Since all graphs have nodes and edges of different types we would
need a class dictionary for each graph application.  We could then exploit the use of inherit
and override to reuse the software.  However, it would be better to construct a
generic graph class dictionary through the use of parameterized classes.  Consider the
following class dictionary which specifies a generic graph as a list of 
edges where an edge is defined as two nodes.  We have added some concrete 
syntax, but recall that all applications are completely shielded from this
syntactic sugaring of the input language. 
%\medskip
%\item{}Graph(Node) = ``edgeList'' $\langle$ edgeList $\rangle$ List(Edge(Node)).
%\item{}Edge(Node) = ``from'' $\langle$ from $\rangle$ Node ``to'' $\langle$ to $\rangle$ Node.
%\item{}List(S) \space $\sim$ \space $\lbrace$ S $\rbrace$.
%\smallskip
\bv
Graph(Node) = "edgeList" 
  <edgeList> List(Edge(Node)).
Edge(Node) = 
  "from" <from> Node "to" <to> Node.
List(S) ~ {S}.
\end{verbatim}
We can now write a lot of generic graph software which can be used by all graphs
which can be represented as a list of edges where edges are represented as a
list of two nodes.  Let us assume we have made a large investment in this type of
graph software and it has served us well.  We now find that we have an application
which requires labeled edges.  This application happens to involve graphs where
the nodes are towns or villages and the labels are the distance in kilometers 
between the towns and/or villages.  We would like to write software which uses
our previous investment in generic graph software and, if possible, we would like
the new software to be generic for any graph with a labeled edge.  We accomplish
both goals by constructing the following class dictionary.
%\medskip
%\item{}LabeledGraph(Node, EdgeLabel) = $*$inherit$*$ \space Graph(Node) $*$override$*$ \space \hfil\break
%\quad\quad $\langle$ edgeList $\rangle$ List(LabeledEdge(Node, EdgeLabel)).
%\item{}LabeledEdge(Node, EdgeLabel) = $*$inherit$*$ Edge(Node) ``label''
%$\langle$ label $\rangle$ EdgeLabel.
%\smallskip
\bv
LabeledGraph(Node, EdgeLabel) = 
  *inherit* Graph(Node) 
    *override* <edgeList> 
      List(LabeledEdge(Node, EdgeLabel)).
LabeledEdge(Node, EdgeLabel) = 
  *inherit* Edge(Node) 
    "label" <label> EdgeLabel.
\end{verbatim}
We can use this parameterized class dictionary to define our regional map of towns,
villages, and distances by giving actual parameters to the above class dictionary.
%\medskip
%\item{}LabeledGraph(Community, Number).
%\item{}Community : Village $\vert$ Town.
%\item{}Village = ``village'' $\langle$ village $\rangle$ String.
%\item{}Town = ``Town'' $\langle$ town $\rangle$ String.
%\smallskip
\bv
Map = *inherit* 
  LabeledGraph (=> EdgeLabel Road, => Node Community).
Community : Village | Town 
  *common* <communityname>, <desc> String.
Village = "village".
Town = "town".
Road = "road" <roadname> String 
       <routeNumber>, <distance>Nnumber.
\end{verbatim}
This class dictionary is expanded by the Demeter system into the following
grammar:
\bv
map = 
  "edgelist" < edgelist > road_community-labelededge-list . 
community : village | town . 
village = 
  "village" < communityname > string < desc > string . 
town = 
  "town" < communityname > string < desc > string . 
road = 
  "road" < roadname > string 
  < routenumber > number < distance > number . 
community-edge = 
  "from" < from > community "to" < to > community . 
road_community-labelededge = 
  "from" < from > community 
  "to" < to > community 
  "label" < label > road . 
road_community-labelededge-list ~ 
  { road_community-labelededge } . 
community-edge-list ~ { community-edge } . 
community-graph = 
  "edgelist" < edgelist > community-edge-list . 
road_community-labeledgraph = 
  "edgelist" < edgelist > road_community-labelededge-list . 
\end{verbatim}
%{
%\settabs \+\indent\quad&\cr
%\+&Community-Number-LabeledGraph = Community-Graph.\cr
%\+&Community-Graph = ``edgelist'' $\langle$ edgeList $\rangle$ Community-Number-LabeledEdge-List.\cr
%\+&Community-Number-LabeledEdge-List \space $\sim$ \space $\lbrace$ Community-Number-LabeledEdge $\rbrace$.\cr
%\+&Community-Number-LabeledEdge = Community-Edge ``label'' $\langle$ label $\rangle$ Number.\cr
%\+&Community-Edge = ``from'' $\langle$ from $\rangle$ Community ``to'' $\langle$ to $\rangle$ Community.\cr
%}
%\smallskip
The following shows the inheritance relationships between the
generated classes.
We use the following notation: We use \verb|!| to introduce
an abstract class (i.e. a class which cannot be instantiated)
and \verb|!!| to introduce an instantiable class
in the underlying object-oriented system.
{\tt *inherit*} followed by several class names determines from
where where the class inherits.
These productions are generated by the system and can be drawn as
a directed acyclic graph.
\bv

map !! 
  *inherit* road_community-labeledgraph, 
  construction . 
community ! < communityname > , < desc > string . 
village !! "village" *inherit* construction . 
town !! "town" *inherit* construction . 
road !! 
  "road" < roadname > string 
  < routenumber > , < distance > number 
  *inherit* construction . 
labeledgraph ! *inherit* construction . 
labelededge ! 
  "label" < label > anytype *inherit* construction . 
graph ! 
  "edgelist" < edgelist > anytype *inherit* construction . 
edge ! 
  "from" < from > anytype 
  "to" < to > anytype *inherit* construction . 
list ! *inherit* repetition . 
community-edge !! *inherit* edge . 
road_community-labelededge !! 
  *inherit* labelededge , community-edge . 
road_community-labelededge-list !! *inherit* list . 
community-edge-list !! *inherit* list . 
community-graph !! *inherit* graph . 
road_community-labeledgraph !! 
  *inherit* labeledgraph , community-graph . 
\end{verbatim}
%}
%\smallskip
%\medskip
%{
%\settabs \+\indent\quad&Community-Number-LabeledEdge-List\quad&\cr
%\+&Class&Inherited Classes\cr
%\+\cr
%\+&Number-Community-LabeledGraph&LabeledGraph, Graph\cr
%\+&Community-Graph&Graph\cr
%\+&Number-Community-LabeledEdge-List&List\cr
%\+&Number-Community-LabeledEdge&LabeledEdge, Edge\cr
%\+&Community-Edge&Edge\cr
%}
%\smallskip
This inheritance 
allows us to write generic, reusable software.
A typical input file for this class dictionary might look like:
\bv
edgelist
  from village "Ebnat-Kappel"  "small"
    to town "Wattwil" "bigger" 
      label road "howart" 12 5
  from village "Diepoldsau" "on Austrian side"
    to village "Widnau" "on Swiss side" 
      label road "bridge" 34 2
\end{verbatim}

For a thorough description of the meanings of a parameterized
class dictionary we refer the reader to \cite{karl:demeter}.

%We generalize our definitions for classes to parameterized classes by ``lifting'' the
%concepts from classes to functions on classes.
%
%\noindent {\bf Definition 5} {\it An object is of metatype {\rm T} if it is an
%instance of parameterized class {\rm T}.}
%
%\noindent {\bf Definition 6} {\it We define an instance variable to be of metatype 
%{\rm T} if it only can contain instances of some instantiation of {\rm 
%associated(T)}.}
%
%\noindent {\bf Definition 7} {\it A metatype {\rm T} is a subtype of metatype {\rm S}
%if there is an inheritance link from metatype {\rm T} to metatype {\rm S} or if
%{\rm associated(T)} is a subset of {\rm associated(S)}.  Every metatype
%is a subtype of itself.  By an inheritance link we mean the transitive closure of the 
%the direct inheritance specification: {\rm T = $*$inherit$*$ S $\ldots$}  If
%override is used, the overriding type must be a subtype
%or submetatype of the type being overriden.
%}
%
%\noindent {\bf Definition 8} {\it The parameterized classes associated with an alternation
%parameterized class are the union of the parameterized classes associated with the classes or 
%parameterized classes on the right hand side of the alternation production.  The parameterized class
%associated with a parameterized construction or repetition production is that parameterized class itself.}
%
%\noindent {\bf Definition 9} {\it L2(S2) is a subtype of L1(S1) if L2 is a submetatype of L1 or, if L1=L2 and S2 is a submetatype or subtype of S1.  This 
%generalizes to several parameters.}
%
Thus far we have used parameterized classes 
without restrictions.  The following example illustrates the need for 
restrictions on the usage of parameterized classes.
It shows that parameterized context-free grammars
can define non-context-free languages. 
\bv
ContextSensitive = <example> A(U,V,W).
A(X,Y,Z) : L(X,Y,Z) | R(X,Y,Z).
L(X,Y,Z) = <first> X <second> Y <third> Z.
R(X,Y,Z) = <u> A(H1(X), H2(Y), H3(Z)).
H1(S) = "u" <t> S.
H2(S) = "v" <t> S.
H3(S) = "w" <t> S.
U = "u". V = "v". W = "w".
\end{verbatim}

%\medskip
%{
%\settabs \+\indent\quad&\cr
%\+&ContextSensitive = $\langle$ example $\rangle$ A(U,V,W).\cr
%\+&A(X,Y,Z) : L(X,Y,Z) $\vert$ R(X,Y,Z).\cr
%\+&L(X,Y,Z) = $\langle$ first $\rangle$ X $\langle$ second $\rangle$ Y $\langle$ third $\rangle$ Z.\cr
%\+&R(X,Y,Z) = $\langle$ u $\rangle$ A(H1(X), H2(Y), H3(Z)).\cr
%\+&H1(S) = $\langle$ t $\rangle$ ``u'' S.\cr
%\+&H2(S) = $\langle$ t $\rangle$ ``v'' S.\cr
%\+&H3(S) = $\langle$ t $\rangle$ ``w'' S.\cr
%\+&U = ``u''.\cr
%\+&V = ``v''.\cr
%\+&W = ``w''.\cr
%}
%\smallskip

When we apply the expansion process introduced with the labeled graph example
to this \cd\ we get into an infinite loop: the expansion process would generate 
infinitely many intermediate classes. Our implementation has to be protected
from this condition.

Also, the language defined by this grammar is a well-known context-sensitive language
which is known not to be context-free: {\it $u^nv^nw^n$,n $>$ 0.}  
The recursive descent-parsing approach is not capable of parsing
such languages.  Therefore we will restrict the recursive parameterized class definitions
so that any instance defines a context-free language.  In applications one does not 
need the generality of the ContextSensitive  example.  The following condition 
places a bound on the parameterization but
does not limit the practical applications.

\begin{definition}
A parameterized class T is {\rm bounded}, if every recursive
use of T satisfies the restriction that every actual parameter of the
recursive use is 
either:
\begin{itemize}
\item
a formal parameter of T
\item
an instance of some parameterized class which does not have a formal parameter
of T as an actual parameter.
\item
a class.
\end{itemize}
\end{definition}

\noindent Some interesting examples of bounded parameterized class definitions are:
%\medskip
%\item{1.}Permutation
%\smallskip
%{\settabs \+\indent\quad&\cr
%\+&MyT = $\langle$ ex $\rangle$ T(Ident, Number).\cr
%\+&T(X,Y) : E $\vert$ N(X,Y).\cr
%\+&E = ``e''.\cr
%\+&N(X,Y) = ``n'' $\langle$ first $\rangle$ X $\langle$ second $\rangle$ Y $\langle$ third $\rangle$ T(Y,X).\cr
%}
\begin{itemize}
\item
Permutation

\begin{verbatim}
MyT = <ex> T(Ident, Number).
T(X,Y) : E | N(X,Y).
E = "e".
N(X,Y) = "n" <first> X <second> Y <third> T(Y,X).
\end{verbatim}

\item Exponential

%\item{2.} Exponential
A parameterized class instantiation can generate an exponential number of parameterized class instances
(exponential in the size of the parameterized class definition and the size of the actual
parameters).  Consider the following example which basically generates all 
permutations of the symmetric group on 4 elements:

\begin{verbatim}
MyA = <ex> A(C1,C2,C3,C4).
C1 = "c1".
C2 = "c2".
C3 = "c3".
C4 = "c4".
A(X1,X2,X3,X4) =
  ["t1" <t1> A(X2,X1,X3,X4)]
  ["t2" <t2> A(X1,X3,X2,X4)]
  ["t3" <t3> A(X1,X2,X4,X3)].
\end{verbatim}

%%\smallskip
%%{
%%\settabs \+\indent\quad&\quad\quad&\cr
%%\+&MyA = $\langle$ ex $\rangle$ A(C1,C2,C3,C4).\cr
%%\+&C1 = ``c1''.\cr
%%\+&C2 = ``c2''.\cr
%%\+&C3 = ``c3''.\cr
%%\+&C4 = ``c4''.\cr
%%\+&A(X1,X2,X3,X4) = $\lbrack$ ``t1'' $\langle$ t1 $\rangle$ A(X2,X1,X3,X4) $\rbrack$\cr
%%\+&&$\lbrack$ ``t2'' $\langle$ t2 $\rangle$ A(X1,X3,X2,X4) $\rbrack$\cr
%%\+&&$\lbrack$ ``t3'' $\langle$ t3 $\rangle$ A(X1,X2,X4,X3) $\rbrack$.\cr
%%}
%%\smallskip
The instantiation of parameterized class A on the first line generates 24 = 4 $*$ 3 $*$ 2 $*$ 1 parameterized class instantiations or in general $n!$ (i.e. the size of the symmetric
group on $n$ elements).
In practical applications this ``permutation feature'' is seldom used.  One 
could exclude this exponential behavior by requiring that every parameter 
of a parameterized class be in the same position throughout a given rule(s).
\item Splitting

\begin{verbatim}
MyT = <ex> T(Ident,Number).
T(X,Y) : E(X) | N(Y).
E(X) = String <first> X .
N(Y) = "n" <erstes> T(Y, List(Number)).
List(S) ~ "list" {S}.
\end{verbatim}
A legal input is:
\begin{verbatim}
n n n n n "ab" list 45
\end{verbatim}
\end{itemize}

%%\smallskip
%%\item{3.} Splitting
%%\smallskip
%%{
%%\settabs \+\indent\quad&\cr
%%\+&MyT = $\langle$ ex $\rangle$ T(Ident, Number).\cr
%%\+&T(X,Y) : E(X) $\vert$ N(Y).\cr
%%\+&E(X) = String $\langle$ first $\rangle$ X.\cr
%%\+&N(Y) = ``n'' $\langle$ erstes $\rangle$ T(Y, List(Number)).\cr
%%\+&List(S) \space $\sim$ \space ``list'' $\lbrace$ S $\rbrace$.\cr
%%}
%%\smallskip
%%\item{4.} Hiding
%%\item{}Sometimes the recursive application of a class might be hidden.  In the example below
%P(Q) is a recursive application of the divide and conquer network.
%%\smallskip
%%{
%%\settabs \+\indent\quad&DivideAndConquer&\cr
%%\+&DivideAndConquerNetwork(Q) = $\langle$ input $\rangle$ anytype\cr
%%\+&&$\langle$ output $\rangle$ anytype\cr
%%\+&&$\langle$ internals $\rangle$ Induction(DivideAndConquerNetwork, Q).\cr
%%\+&Induction(P,Q) : NonTrivial(P,Q) $\vert$ Trivial.\cr
%%\+&NonTrivial(P,Q) = $\langle$ left $\rangle$ P(Q) $\langle$ right $\rangle$ P(Q) $\langle$ postProcessing $\rangle$ Q.\cr
%%\+&Trivial = $\langle$ input $\rangle$ anytype $\langle$ output $\rangle$ anytype.\cr
%%}
%%\smallskip
The following
theorems guarantee that bounded parameterized classes always define 
context-free languages and that the expansion of parameterized classes
is finite.

\begin{theorem}
An instance of a bounded parameterized class generates 
a finite number of classes.
\end{theorem}

\begin{theorem}
The language defined by an instance of a 
bounded parameterized class is context-free.
\end{theorem}

The concept of subtype is easy to generalize to parameterized classes.

\section{Organizing the Garden}
We need a structuring mechanism to organize class dictionaries and the
associated software. Therefore we introduce the concept of a module
which is a collection of (parameterized) class and method definitions.
We follow the Modula-2 rules and group our modules into two parts:
a definition part and an implementation part. 
In the definition part we put all the classes which are important
for clients and the method headings with type information for
arguments and result.
In the implementation part we put the implementation related class definitions
and the complete methods. The implementation part also contains
a list of file names which refer to the files containing
the 
methods written in the language of the underlying
object-oriented system.
Modules and their organization into pairs have the following
advantages:
\begin{itemize}
\item
Information hiding. We can hide method bodies, the internals of construction
classes and auxiliary classes which are only used for implementation.
\item
Separate environment generation and separate compilation.
\item
Avoiding conflicts between class names.
\end{itemize}

\section{Related Work}
The Demeter system has benefitted from work done in three areas:
Programming languages, Artificial Intelligence and Data Bases.
A detailed comparison exceeds the space requirements of this paper
and can be found in the forthcoming book \cite{karl:demeter}.
We give here a few pointers:
\begin{itemize}
\item
Object-oriented programming: Object-oriented programming is 
promoted by Simula-67 \cite{dahl-nygaard:simula-67}, Smalltalk-80 \cite{goldberg:smalltalk-l-i},
Flavors \cite{moon:flavors},
Objective-C \cite{cox:oop}, C++ \cite{stroustrup:c++}, 
Eiffel \cite{meyer:param-86}. Our
prototype implementation uses Flavors and Franz Lisp.
Demeter extends
the object-oriented languages mentioned above in a useful way.

The override mechanism of Demeter exists in similar form
in Galileo \cite{albano-cardelli:conceptual-85} and Taxis \cite{mylopoulos-bernstein:taxis-80}
and in \cite{thomsen-override:86}. 

\item
Language design and parsing: We use the ideas promoted
by 
N. Wirth on language design \cite{wirth-lang-des:ifip-74}, 
\cite{wirth:modula-2}, data structure
and parser design \cite{wirth:a+d=p-76}, 
grammar notation \cite{wirth:ebnf}
and type checking \cite{wirth:pascal-acta-71}.

\item
Grammar-based programming:
A grammar-based approach to meta programming in Pascal
has been introduced in \cite{cameron-ito:gramps}.
\cite{fraser:syntax-81} uses grammars for defining data structures.
\cite{kristensen:fragments-85} introduce an algebra of
program fragments. The POPART system treats grammars as objects
\cite{wile:popart-83}. 
The synthesizer generator project also uses a grammar based approach
\cite{reps-teitelbaum:84}.
GEM described in \cite{andrew:gem} is the predecessor
of Demeter.
 
Our work is novel in that it combines language definition and
data structure definition for object-oriented programming into
one coherent framework. Such an integration has not been attempted
before. It supports a succinct, clear, modular programming style.

\item Artificial intelligence: Many papers in knowledge engineering
propose a similar approach as Demeter. One which comes close is
\cite{freiling:knowledge-86}. 

\item
Parameterized data types:
An excellent survey is in \cite{cardelli-wegner:types-85}.
Solomon introduces the concept of bounded parameterized classes 
\cite[page 25]{solomon:param}.
Parameterized data types
are provided in several programming languages, including
CLU \cite{liskov:abstr-77}, Trellis/Owl \cite{schaffert:trellis-86} and Ada.
Parameterization of data type specifications is used  in
the algebraic approach to data types
\cite{kreowski:alg-spec-87} and \cite{thatcher:param-82}.
\cite{macqueen:ml-85}, \cite{macqueen:modular-86}
discusses many of the important issues
related to generic software design.

\item
Program transformation systems:
Our development of Demeter has been motivated by work on
program transformation systems
\cite{partsch:survey},\cite{cameron-ito:gramps}, \cite{boyle:reusability-84}, 
\cite{wand-kohlbecker:by-example-87}.
The MENTOR system \cite{kahn-lang:struct-75}, \cite{huet:mentor-80}
is designed for manipulating structured data represented
by abstract syntax trees.
The Mj{\o}lner project uses a Demeter-like approach, but without
parameterization and multiple inheritance \cite{madsen-norgard:hicss-88}.

\item Data base design:
Our class dictionaries share some properties with data dictionaries.
The data dictionary
approach in the data base field is described 
in the survey \cite{allen:dictionary-82}.
A paper by John and Diane Smith \cite{john-diane:abstr-77} outlines some
of the
features of the Demeter system. Their aggregation/generalization concepts
correspond to our construction/alternation concepts.

\item Program enhancement:
\cite{balzer:sigsoft-86} proposes
a frame-based object model 
to simplify program enhancement
which has some similarities to the
Demeter system. 

\item Exchange of structured data:
The programming language independent data structure language of Demeter
supports the exchange of structured data between different programming
languages. The work on IDL \cite{lamb:idl-87} is related.

\item Demeter Project:
\cite{karl1:class} introduces the formal syntax for parameterized class
dictionaries and discusses class dictionary design techniques.
\end{itemize}

\paragraph{Conclusions}
We have presented a new software design methodology based on growing 
and reusing software.
We find growing software to be a better paradigm than building software.  The philosophy of
growing software requires that a running system be in place from the earliest stages of 
project development.  This methodology has been implemented and tested in the
prototype system ``Demeter'' which uses this growth paradigm to provide an ideal environment
for the development and reuse of large software systems.

The Demeter system has been used by over 200 graduate and undergraduate students
over the past 18 months.  The feedback from these students has been very 
favorable and has indicated that the class dictionary is a very natural way of 
describing an abstract data structure.  In addition, the learning curve for Demeter is short.
For example, a group of 35 CS sophomore students have used Demeter within the 
framework of a software design and development course.  Most of the students 
were beginning work on fairly complex systems in three weeks.  All of these 
students had no previous experience with either Demeter or object-oriented programming,
however, they did have some experience with Franz Lisp (one course).

In addition to the pedagogical uses of Demeter we have implemented many applications.
Some of the more interesting ones include all the Demeter code generators and
the generic programs, a simulator for the parallel
language Zeus-2, simulators for subsets of Scheme and Prolog, a Fortran-77 to Pascal
Translator, a Pascal parser generator, an expert system shell for modelling transportation
systems, a generic adventure game generator, and a prototype environment for 
the modelling and simulation of arbitrary worlds of objects and rules.  The
latter five projects were developed by groups of five sophomore students in 
an eleven week course.  This time includes the learning  curve for Demeter
and object-oriented programming.

We are continuing our work with Demeter and the philosophy of growing software
both for teaching and research. We will investigate many exiting areas
of research: Object-oriented specification, abstraction by example, class 
dictionary design from examples, expert system for \dd\ design.
%
%
%and will be investigating the following open areas of research.
%\medskip
%%\item{1.} Formal Specifications $-$ How do formal specifications change under 
%this new design methodology?  The notion of a formal implementation specification
%written before coding begins is not compatible with the paradigm of growing
%software.  Perhaps a better method would be to write many small documents which
%together form a growth record of the software system. One or several of these
%specifications would be written as the next growth phase is planned.  Modifications
%during the implementation phase of a project would be easier with this method.
%What other changes are necessary in other design documents?
%
%
%%\item{2.} Can we write a system into which a user inputs his or her class 
%dictionary and receives suggestions on how to improve the data abstraction?
%Our experience shows that there are common errors in data abstraction which 
%can result in a kludgy system.  How far can we carry this automatic 
%improvement of data abstraction?
%
%%\item{3.} Can optimal class dictionaries be constructed from example inputs?
%What factors are involved in this process?
%How many examples are needed to give us a good class dictionary? or an optimal one?
\paragraph{Acknowledgments}

The design and implementation of the predecessor system of Demeter
(called GEM, Pascal based) was done at GTE Laboratories in collaboration
with Andrew Goldberg  and with management support from
Sandy Hirschhorn and Bill Griffin. At Northeastern, the Demeter project is
supported by numerous dedicated graduate students, including (in
alphabetical order):
Bill Brown, 
Ian Holland, 
Gar-Lin Lee, Kathy Lee, 
David Lincoln,
Beno\^{\i}t Menendez, Jing Na,
Robert Paul, 
Johannes Sujendro and Carl Woolf.

Mitchell Wand taught us that a parameterized context-free
grammar does not necessarily define a context-free language.
He brought the example, which we called {\tt ContextSensitive} in this paper,
to our attention. This example appeared originally
in Michael Fischer's thesis at MIT.
Mitchell's seminar on semantics of programming languages was very useful
for learning about several key contributions to the field.

Carl Woolf has improved the proof of theorem 5.1. He proposed the terminology
of responsiveness to a message and knowledge of a message.

Professors Brown, Bugrara, Casey and Rasala provided valuable feedback on
this paper.

\end{document}