\subsubsection{A Simple Example}

To illustrate the workings of the growth-plan, 
we present and explain a simple example.

\begin{example}
We give a \cm\ and the corresponding growth plan.

%\medskip
%\centerline{\bf Demeter Notation}
\bv
  Book = 
    Intro-or-preface 
    <main-text> Text
    [<appendix> Text]
      *SIG* insert_footnote(Footnote) 
	*RETURNS* Number 
    *COST* 2.
  Intro-or-preface : 
    Introduction | Preface *COST* 0.
  Text ~ String-or-number 
    {String-or-number} *COST* 2.
  Introduction = "Introduction to the book" 
    Text *COST* 2.
  Preface = 
    "Preface to the book" Text *COST* 1.
  Footnote = <contents> Text *COST* 2.
  String-or-number : 
    String | Number *COST* 0.
\end{verbatim}

%\medskip
%\centerline{\bf Intermediate Notation}
%
%\bv
%Book -> 
%  *COST* 2 
%  *REQUIRED* ( Number Footnote Text 
%    Intro-or-preface ) 
%  *OPTIONS* ( Text ). 
%Intro-or-preface -> 
%  *COST* 0 
%  *ALTERNATIVES* ( Introduction Preface ). 
%Text -> 
%  *COST* 2 
%  *REQUIRED* ( String-or-number ). 
%Introduction -> 
%  *COST* 2 
%  *REQUIRED* ( Text ). 
%Preface -> 
%  *COST* 1 
%  *REQUIRED* ( Text ). 
%Footnote -> 
%  *COST* 2 
%  *REQUIRED* ( Text ). 
%String-or-number -> 
%  *COST* 0  
%  *ALTERNATIVES* ( String Number ). 
%String -> *COST* 2.
%Number -> *COST* 1.
%\end{verbatim}

\medskip
\centerline{\bf Growth Plan}

Minimal Grammar:
{\tt Book  Number  Footnote  Text  Preface} 

Growth Phase 1:
{\tt String} 

Growth Phase 2:
{\tt Introduction} 
\end{example}

%The \cm\ given above,
%illustrates many of Demeter's features for specifying \cms:
%
%Each class is defined by exactly one production.
%The modified BNF of Demeter uses three kinds of productions, each of which 
%has its own symbol to connect the left-hand-side of the production with 
%the right-hand-side. 
%(We have various reasons for this tripartite approach. The main one is that we
%believe it facilitates the readability of \cms.)
%{\em Construction} productions, such as the one 
%for {\tt Book},
%use {\verb"="}, and their right-hand-sides are basically sequences of nonterminals
%or terminal symbols. Construction productions use square brackets to indicate
%that an item is optional.
%%, but they do not allow alternatives. For instance,
%%one cannot use
%%
%%\bv 
%%   Book = One-kind-of-book | Another-kind.
%%\end{verbatim}
%%
%%Moreover, each nonterminal is the left-hand-side of only one production,
%%so one cannot use
%%
%%\bv
%%   Book = One-kind-of-book.
%%   Book = Another-kind.
%%\end{verbatim}
%%
%%In short, we do not use construction productions for alternatives. Instead we 
%{\em Alternation} productions productions connect the left-hand-side to
%the right-hand-side via the symbol {\verb":"}. {\tt Intro-or-preface} 
%is such a production.
%Basically, the right-hand-side of an alternation is just a group of 
%alternatives -- in the case of {\tt Intro-or-preface}, two alternatives.
%
%The third type of Demeter production is the {\em repetition}
%production. It uses
%the symbol \verb|"~"|, and amounts to the operation * or + for regular expressions.
%Specifically, the production for {\tt Text} indicates that {\tt Text} consists of one
%or more {\tt String-or-number} -- if we omitted the first occurrence of 
%{\tt String-or-number} on the right-hand-side, then {\tt Text} would consist of 
%zero or more {\tt String-or-number}.
%
%In these productions, quoted strings such as {\tt Preface-to-the-book} are
%concrete syntax. Demeter \cms\ which
%define automatically readable objects, must be LL(1), so concrete syntax can help
%disambiguate our grammars, as well as making it easier to read the files 
%containing the ASCII representation of objects (namely, the strings of 
%the language specified by the grammar). Angle-bracketed terms, such as
%\verb|<| {\tt contents} \verb|>| provide official names for the objects they are next to. When
%a method refers to the constituent of a {\tt Footnote}, it uses the label-name, 
%{\tt contents} rather than the less-suggestive {\tt Text}. 
%These label-names become
%essential if an object has two constituents of the same type, for example,
%
%\bv
%Two-strings = 
%  <first> String <second> String .
%\end{verbatim}
%
%Note that in giving a production we can include a phrase beginning 
%with {\tt *SIG*}. This
%indicates signatures to associate with the class defined by the 
%production. For instance, we 
%specify in the above example that {\tt Book} uses a method called 
%{\tt insert\_footnote},
%whose parameter is an object of class {\tt Footnote}, and whose 
%return-value is an object of class {\tt Number}.
%
%We do not give productions for {\tt String} and {\tt Number}, 
%since these are basic classes
%supplied by Demeter. 
%
%There are several other features used in Demeter \cms\, including inheritance
%and parameterization. These add functionality,
%but at the expense of complicating somewhat the above rather basic account of
%\cms. For further information see \cite{lieber-riel:oop},
%\cite{karl1:class}.
%
%For convenience, our generator transforms \cms\ into an
%`intermediate notation', or `intermediate \cm', that is, a format
%more suitable for the present task. (We think this format is useful for other
%tasks as well.)
%Moving on to the intermediate notation in the example, 
%we see that with each production we
%associate a number (its cost, which is copied from
%the corresponding production in the \cm), 
%and three optional lists of productions, labelled
%"*REQUIRED*", "*ALTERNATIVES*", and "*OPTIONS*". 
%In most cases we automatically assign alternations a cost of zero. 
%This is because we do not write methods for alternations (unless we are using
%some of the advanced features of Demeter alluded to above).
We have extended the \cm\ notation to allow the specification
of a cost for each class.

To compute the growth plan, we look at the \cm. We begin
with the start-symbol ({\tt Book})
and find a cost-minimal sub-grammar. In the example,
the desired grammar must use all of the required parts of 
{\tt Book}, which are {\tt Intro-or-preface Text Footnote Number}.
Since one of the required parts is {\tt Intro-or-preface},
we must use this production. So we must use at least one of its 
alternatives, either {\tt Preface} or {\tt Introduction}. 
Since {\tt Preface} is
cheaper, we choose that. At later stages of the growth plan, we gradually 
add the productions that are not used in the minimal plan.

There are at least two applications of 
the growth plan idea to software maintenance.
\begin{itemize}
\item
Plans for program maintenance:

 Suppose we are                
  given two class modules, the first one reflecting the current
   classes, the second one the planned classes. We would like to
    compute a growth plan for the maintenance steps which decomposes
     the task into a number of subtasks, some of which might be automated.

\item
Testing of modifications.
The growth plan for a \cm\ can  be used to test software in
a systematic way.
A sequence of inputs corresponding to the growth phases of a \cm\
can be used to test the smallest number of additional
classes on successive test runs.
For example, if a program correctly processed the  test inputs for
the first 5 growth phases but failed to process the test input for
the 6th growth phase, we would probably want to examine the methods
attached to the classes introduced at growth phase 6.
Regression testing should be done in the order suggested by the growth plan
to localize a potential error.
\end{itemize}