%\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.