\markboth{Singhal}{Singhal}
\documentstyle[11pt]{article}

% Standard Spacing for WISR - do not change!!
%
% Page dimensions.
%
\oddsidemargin  0.26in % Leave enough for binding margin
\evensidemargin 0.26in %
\topmargin      -1.00in % (adjusted for printer bias)
\headheight      .00in  % (no headers)
\headsep         .75in  % (top margin + headers + skip)
\footheight     12.0pt  % ??? (seems to work ok)
\footskip       25.0pt  % ??? ( "   "  )
\textheight     9.425in % (instructions: 9 1/8" min, 9 7/16" max)
\textwidth      6.5in   %
%
% Paragraph changes.
%

\markboth{Singhal}{Singhal}
\pagestyle{myheadings}

\parindent=0pt
\parskip=10pt
%
% can make the title box even smaller
%
\def\@maketitle{\vbox to 2.6in{\hsize\textwidth
    \linewidth\hsize \vfil \centering
    {\large \@title \par}
    \vskip 2em
    {\normalsize
    \begin{tabular}[t]{c}\@author
    \end{tabular}\par}
    \vfil}
}

\begin{document}

\bibliographystyle{ieeetr}

\title{P++: A Language for Large-Scale Reusable Software Components}

\author{Vivek Singhal and Don Batory\\
\\
Department of Computer Sciences\\
The University of Texas at Austin\\
Austin, Texas 78712\\
Tel: (512) 471-9711/9713\\
Email: \{singhal,batory\}@cs.utexas.edu\\
}
\date{}

\maketitle

\begin{abstract}
P++ is a programming language that supports the GenVoca model
\cite{batory92a}, a particular style of software design that is
intended for building software system generators.  P++ is an enhanced
version of C++: it offers linguistic extensions for component
encapsulation, abstraction, parameterization, and inheritance, where a
component is a subsystem, i.e., a suite of interrelated classes and
functions.

\vspace{0.2in}
\noindent
{\bf Keywords:} open architectures, program families, large-scale
reuse, software system synthesis, GenVoca, software system generators.

\vspace{0.2in}
\noindent
{\bf Workshop Goals:} feedback on our research; exposure to other
work in software reuse.

\vspace{0.2in}
\noindent
{\bf Working Groups:} reuse process models; domain
analysis/engineering; design guidelines for reuse; reuse and
object-oriented methods; tools and environments.

\end{abstract}

\newpage

\section{Background}

Almost two decades ago, Parnas observed that software design was
incorrectly taught as a technique which sought a unique
program/solution, because, over its lifetime, the program inevitably
would evolve into a family of similar programs \cite{parnas76}. When
programs are not designed for extensibility, the effort and expense
needed to modify them is often out of proportion to the changes
themselves. A different approach, one that achieves economies of
scale, was needed. He argued that since program families are
inevitable, designing program families from the beginning is the most
cost-effective way to proceed.

Recent work on domain-specific software architectures
\cite{coglianese93,sei90} has shown that software system generators
offer a promising means of economically building families of large,
complex software systems.  These generators are domain-specific; they
implement models (called {\em domain models}) which show how to
construct a family of similar software systems by composing reusable,
prefabricated components. The essential themes that Parnas espoused
are present in contemporary software generators; generators formalize
the design of software families as open architectures, where software
system synthesis and evolution can be quick and inexpensive.

Some examples of generators include Genesis (database systems)
\cite{batory88}, Avoca (network protocols) \cite{omalley92}, Ficus
(file systems) \cite{heidemann93}, Brale (host-at-sea buoy systems)
\cite{weiss90}, and Predator (data structures) \cite{batory93}.
Although each of these generators was developed independently and
targeted for a different problem domain, all were organized in
basically the same way. The GenVoca model captures their common design
strategy \cite{batory92a}: it defines a particular style of designing
and organizing reusable components that enables families of software systems to
be defined through component composition. An implementation of a
GenVoca model is a software system generator for a particular
domain.

Some of the important features of GenVoca are: (1) {\em Components}
are the building blocks of hierarchical software systems (a component
is a subsystem or module). (2) Components must import and export {\em
standardized} interfaces. (3) Component composition and customization
should be achieved through {\em parameterization}.

It is well-known that language support for a design paradigm can
tremendously simplify the application of that paradigm;
object-oriented languages, for example, have been instrumental in
popularizing and realizing object-oriented designs. For the same
reason, language support for GenVoca is important. In the next
section, we briefly describe the P++ programming language, which
codifies the GenVoca model. P++ offers several linguistic extensions
to C++ to support component encapsulation, abstraction,
parameterization, and inheritance.  From our experiences with the
Genesis and Predator projects, we believe that P++ would have
considerably simplified the implementations of these generators.

\section{The P++ Language}

\subsection{Encapsulation and Abstraction}

Encapsulation and abstraction are two program design techniques often
used to manage the complexity of large software systems.  {\em
Encapulation} is the technique of consolidating related code and data
fragments into atomic units of program construction.  The GenVoca
model has demonstrated that the scales of encapsulation currently
provided by programming languages, namely functions and classes, are
inappropriate for building large systems.  Instead, GenVoca advocates
the use of components, which correspond to subsystems or modules.  In
P++, a component consists of a suite of interrelated data members,
functions, and classes.

{\em Abstraction} is a design technique which separates the interface
of a component from its implementation.  In P++, the realm
construct specifies the interface of a component: it declares the
functions and classes which comprise a component's interface, without
revealing the implementation of those functions and classes.

\begin{figure}
\begin{scriptsize}
\begin{center}
\begin{minipage}[t]{3.5in}
\begin{verbatim}
realm collection<class T>
{
  class container
  {
    container ();               // container
  };
  class cursor
  {
    cursor (container *);       // constructor
    void first ();              // container traversal
    void next ();               // container traversal
    int eoc ();	                // beyond end of container?
    void insert (T);            // add item
    void remove ();             // delete item
    T& get_value ();            // get item
  };
};

component linked_list : collection<class T>
{
  class element
  {
    element (T);                // constructor
    T data;                     // the value of this node
    element *next, *prev;       // adjacent nodes on list
  };
  class container
  {
    element *head;              // first node of list
  };
  class cursor
  {
    element *current_pos;       // current position
    container *cont;            // container iterated upon
  };
};
\end{verbatim}
\end{minipage}
\end{center}
\end{scriptsize}
\caption{Sample realm and component declarations.}
\label{sampledecls}
\end{figure}

Figure~\ref{sampledecls} lists an example from the domain of data
structures.  First shown is the declaration of the {\tt collection}
realm: this is a standardized abstract interface for interacting with
data structures that store collections of objects.  {\tt collection}
declares two classes, {\tt container} (which actually stores the
objects) and cursor (which provides methods for manipulating objects
inside a {\tt container}).  Notice that the realm reveals no
implementation details about its classes, thus maintaining the
proper separation between a component's abstract interface and
concrete implementation.

The next declaration in Figure~\ref{sampledecls} is that of {\tt
linked\_list}, a component from the {\tt collection} realm.  Because
{\tt linked\_list} belongs to {\tt collection}, it is obligated to
implement (export) the methods listed in {\tt collection}'s
declaration.  The body of {\tt linked\_list}'s declaration introduces
a new class called {\tt element}, along with new data members for the {\tt
container} and {\tt cursor} classes.  This class and these data
members are part of {\tt linked\_list}'s private implementation; they
are not visible to other components or programs.

A fundamental feature of component encapsulation is evident in this
example: a component consists of several data members, functions,
and/or classes that are intimately intertwined.  Because of their
interrelated algorithms, the {\tt element}, {\tt cursor}, and {\tt
container} classes cannot be designed, implemented, or reused in
isolation.  P++ provides the programming language support to maintain
their cohesion as an atomic unit of system construction.

\subsection{Parameterization}

The use of components almost always entails some customization.
Direct source code modification may be appropriate for functions or
classes because of their (typically) small code volume; however, this
customization technique is rarely effective for components.  Component
parameterization, which permits an easy and controlled form of
modification, is widely believed to be the prescription for successful
component customization
\cite{prietodiaz93}.

Contemporary programming languages already offer constant and type
parameterization of classes; P++ extends these capabilities to
components and realms.  In addition, P++ uses the model of
parameterization to perform component composition: a component {\tt C}
may be parameterized by a realm {\tt R}, which means that {\tt C} may
be combined with any component that belongs to realm {\tt R}.

The {\tt collection} declaration of Figure~\ref{sampledecls} shows an
example of type parameters.  {\tt collection} is defined in terms of
the type parameter {\tt T}; this parameter determines the kind of
objects stored by the data structure.  Furthermore, because the
component {\tt linked\_list} is defined to be a member of the {\tt
collection} realm, {\tt linked\_list} is also implicitly parameterized
by the type {\tt T} (notice that the definition of {\tt element}
depends on the value of {\tt T}).

\begin{figure}
\begin{scriptsize}
\begin{center}
\begin{minipage}[t]{4.5in}
\begin{verbatim}
component linked_list <collection<element> next_layer> : collection<class T>
{
  class element { ... };
  class container { ... };
  class cursor { ... };
};

component binary_tree <collection<element> next_layer> : collection<class T>
{
  class element { ... };
  class container { ... };
  class cursor { ... };
};

component array : collection<class T>
{
  class element { ... };
  class container { ... };
  class cursor { ... };
};
\end{verbatim}
\end{minipage}
\end{center}
\end{scriptsize}
\caption{A parameterized component declaration.}
\label{paramdecl}
\end{figure}

Figure~\ref{paramdecl} shows three components of the {\tt collection}
realm, namely {\tt array}, {\tt binary\_tree}, and {\tt linked\_list}.
Note that the declaration of {\tt linked\_list} has been revised so
that it is now parameterized in terms of the {\tt collection} realm.
This means that {\tt linked\_list} imports the interface defined by
{\tt collection}.  Any component belonging to this realm would be a
legal value for this parameter (e.g. {\tt array}, {\tt binary\_tree},
or even {\tt linked\_list}).  Although not obvious, parameterizing
{\tt collection} components by realms forms the basis for generating a
vast family of data structures
\cite{batory93}.

P++'s realm parameterization facility is a powerful
language feature for designing and reusing software components:

\begin{itemize}

\item It encourages the development of components with standardized
abstract interfaces.  Such components are more likely to be reused
because they can be easily interchanged with other components of the
same realm \cite{batory93}.

\item When interchangeable components are available, it is easy to
tune the performance of a system: different components can be quickly
substituted for one another, thus greatly facilitating the process of
finding improved implementations for a system \cite{batory93}.

\item P++ integrates component definition and combination features in
a single language.  Other researchers have used module interconnection
languages to combine components \cite{prietodiaz86}.  However, such
languages typically are different from the language in which
components are written.

\end{itemize}


% The purpose of realm parameters is to accurately model the
% organization of actual software systems.  Large software systems
% typically consist of hierarchies of layered components --- each layer
% imports the interface of the layer ``below'', and exports an interface
% to the layer ``above''.  Similarly, parameterized components behave
% like layers --- imported layers correspond to realm parameters, and
% exported interfaces correspond to their realm membership.

\subsection{Inheritance}

Programming languages use inheritance to implement two kinds of
hierarchies: implementation hierarchies and type hierarchies
\cite{liskov87}.  Current object-oriented languages usually support
{\em implementation hierarchies}, where a subclass inherits {\em both}
the interface and the implementation of the superclass, unless
explicitly overridden (overloaded) by the subclass.  In contrast, when
a language implements {\em type hierarchies}, inheritance is being
used to support data abstraction.  In this context, a subtype inherits
only the interface of its supertype, but not its implementation.

To support type hierarchies, P++ allows new realm declarations to inherit
from existing realm declarations.  For example, suppose realms {\tt R}
and {\tt S} were defined as follows:

\begin{verbatim}
        realm R { ... };
        realm S : realm R { ... };
\end{verbatim}

These declarations indicate that {\tt S} inherits the interface of
{\tt R}; that is, the interface of {\tt S} includes not only its own
functions and classes, but also those of {\tt R}.  Therefore, {\tt S}'s
interface is a superset of {\tt R}'s, which means that all components
belonging to realm {\tt S} also belong to realm {\tt R}.  Realm
inheritance is important because it provides a structured technique
for evolving component interfaces.  Since realm inheritance is an
instance of type hierarchies, this form of inheritance ensures
interchangeability, a property which enhances the likelihood of reuse.

\section{Conclusions}

There is growing recognition that existing software system design
techniques are inadequate; they are aimed at producing one-of-a-kind
systems that are difficult to modify and evolve.  Software system
evolution is a critical requirement of future systems, to satisfy the
ever-increasing demands of new applications.  Concomitantly, the need
for software generators that can manufacture families of related
systems by composing reusable components is becoming progressively
more important, to meet the challenge of economical software system
evolution.

Research in domain analysis and program families has identified the
system organization concepts needed by software system generators.
The scale of these programming concepts (i.e. components) transcend
those found in conventional programming languages (functions,
classes).  The P++ programming language extends the encapsulation,
abstraction, parameterization, and inheritance capabilities of C++ to
components; we believe P++ is a prototype of future languages that
support the construction of families of systems and software system
generators.

\bibliography{singhal}

\section{Biography}

{\bf Vivek Singhal} is a doctoral candidate in the Department of
Computer Sciences at the The University of Texas, Austin.  He received
his S.B. from the Massachusetts Institute of Technology in 1990.  His
research interests include reuse systems, domain modeling, and
object-oriented database management systems.

{\bf Don Batory} is an Associate Professor in the Department of
Computer Sciences at The University of Texas, Austin.  He received his
Ph.D. from the University of Toronto in 1980, he was Associate Editor
of the IEEE Database Engineering Newsletter from 1981-84 and was
Associate Editor of ACM Transactions on Database Systems from
1986-1991.  He is currently a member of the ACM Software Systems Award
Committee, and his research interests are in extensible and
object-oriented database management systems and large-scale reuse.

\end{document}
