%{Grammar-Based Application Planning \\for Object-Oriented Systems}
\subsection{Growth plan}

This section is a summary of \cite{lieber:89-11} 
from a maintenance point of view.
We follow again the theme that some extra effort spent during
software development will pay off during maintenance time.
The extra effort we discuss here is related to application development
planning which leads to layered system development as well as to
systematic regression testing.

In our approach to software development one first develops a list 
of \cms.
If they are complex, then one might implement the corresponding
object-oriented
program in phases, as follows: The phases correspond to increasingly 
detailed prototypes. At earlier phases, one writes methods for fewer 
or else easier objects. But at each phase, the new prototype works
on at least some 
of the objects specified by the \cm. Moreover, later phases 
subsume earlier phases -- that is, later prototypes
work on all of the objects that earlier prototypes worked on.
A nice feature of our object-oriented approach is that in general we
need only {\em add} new methods at later phases, {\em without changing the
old ones}.

Given a \cm, we can
find the objects necessary for a first prototype simply by 
finding a count-minimal sub-grammar of the \cm, where by 
{\em count-minimal sub-grammar} 
we mean a sub-grammar with the fewest possible productions.
Since it is a sub-grammar, any object specified by this count-minimal 
sub-grammar is legal according to the full \cm. But using this
sub-grammar as a guide, we can implement our prototype by writing methods 
for the fewest objects. We augment our prototypes by finding larger subgrammars
whose counts are still as low as possible. When we have reached the full
grammar, our program works for all of our objects.

In practice, we usually want a slightly different criterion for 
the productions in
our various prototypes. We want to assign a cost to each production in the 
\cm. Higher costing productions correspond to objects 
whose methods we would prefer to write later rather than sooner. We might 
assign a production a higher cost for two reasons: 
we want to implement the easier methods first, or, 
we want to tackle the tough methods first. 

In any case, once we have assigned costs we can then seek a prototype 
corresponding to the cost-minimal sub-grammar. By ``cost-minimal'' we
mean cheapest. Note that in general
this cost-minimal sub-grammar may fail to be count-minimal. That is, it may 
have more than the fewest possible productions.

Given a \cm\ D, along with the cost of each production, a
{\em growth-plan} finds for phase 1 a cost-minimal sub-grammar of D. 
Then, for each 
phase $n$ at which 
the sub-grammar, SG, has not yet grown to be D itself, the growth-plan
finds a cheapest sub-grammar of D that is a proper super-grammar 
of SG.
In other words, 
a growth plan helps you plan the cheapest first 
prototype, and then the cheapest increments, eventually handling all of D.
Thus the growth-plan is an abbreviation for {\em application software
development plan}.

We have implemented two growth-plan generators and added them to
Demeter.
The first
one gives cost-minimal growth plans, but is computation-time intensive
since we have shown that computing cost-minimal growth plans is NP-hard.
The second one gives ``good'' approximations to cost-minimal growth plans,
but runs fast.
Given a \cm\, the growth-plan generators
produce a list of new productions for each phase of the prototype, 
building -- from a (close to) cost-minimal prototype -- all the way up to the full 
\cm.