\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?