%last changed 1/5/94
%Ira Baxter   email: baxter@austin.slcs.slb.com   ph: 1-512-331-3714
%Schlumberger Laboratory for Computer Science
%8311 North RR 620   [for snail mail, use PO Box 200015 instead]
%Austin, Texas, 78720
%
%Scope:  This group will explore those facilities that are needed to
%support the representation of generic architectures in code.  Issues
%could include, but should not be limited to, support for module
%interconnection, parameterization, object modeling, library
%organization, concurrency, specification semantics, the mapping from
%generic design to generic code, and module certification issues.
%Issues that we might focus on include local certifiability,
%concreteness, generic algorithm representation, the relationship
%between program generation and composition, and the limits of what a
%language for code representation should provide.  The breadth of this
%topic area will require a careful scoping based on the strengths and
%interests of the participants.
%
%Goals: o Develop a workable definition of ``Generic Code''
%       o Develop a framework for what should and shouldn't be supported
%         in a language for representing the output of the
%         design -> implementation process.
%       o Share experiences with users of existing production AND
%         research languages (to generate a table of features
%         supported/not supported - a domain model of languages)
%       o Given a fixed language (Ada, C++, Fortran), how can it be
%         augmented to support generic code generation?  (macros,
%         code generators, etc.)
%------------------------------------------------------------------------
%
%Report on WISR6
%Working Group on Generic Architectures
%Ira Baxter
%Schlumberger Laboratory for Computer Science
%baxter@austin.slcs.slb.com
%Larry Latour, Group Leader
%Don Batory
%Ted Biggerstaff
%Prem Devanbu
%Steve Edwards
%Wojtek Kozaczynski
%Jim Q. Ning
%Jeffrey Poulin
%Vivek Singhal
%Yinyau Shih
%
%November 5, 1993

%Abstract
%At the 6th Workshop on Software Reusability, the Working Group on Generic Architectures
%examined several systems that produce real applications using some type of generic architectures. The group
%found it useful to consider each system from a transformational perspective to allow comparison of mecha-
%nisms, capabilities and limitations. We believe this perspective may be useful for other generic architecture
%systems.

% Working Group on Generic Architectures

An important idea for reuse of design is:

{\bf Generic Architecture:} a system of components with rules specifying consistent
compositions.

Such architectures can be used to implement instance systems by choosing
compatible components, and combining them by using the composition mechanism
implied by the rule structures.
These architectures are especially useful when supported by tools to manage
the selection and composition of components.

The working group met with the initial intention of determining sets of features
and mechanisms useful for constructing systems from generic architectures.
Discussion led the group to examine several real systems built by some of the
group participants, with the hopes that identifiable concepts would emerge.
Further examination suggested that the composition mechanisms themselves were
crucial, and therefore interesting to examine in detail.
The results of this examination appear in the sequel in the discussion on
refinements.

The systems considered were:
\begin{description}\itemsep -3pt
\item [Sinapse:] Generates numerical solvers for partial differential
equations [Kant91].

\item [Predator (P++):] Database system generator [Batory92]
(language incorporating composition principles [Batory93]).

\item [RESOLVE(/Ada):] Language and discipline for describing and reusing
software architectures [RESOLVE93], [WOZ91], [Murali93]
(for Ada components [Hollingsworth92]).
\end{description}
Details as to the operation of these systems is deferred to the references.
Implementors of these systems were present in the working group so that hypotheses about
system mechanisms could be formulated and verified.

\subsection*{Transformation Systems as an Explanatory Model
for Generic Architectures}

One of the major difficulties in comparing such systems is the diversity of
terminology, mechanisms, and representations used.
In an effort to find commonality, it was proposed that the group
use a {\it transformational} model of program generation to provide standard
vocabulary, concepts, and mechanisms, and attempt to map relations between
generic architecture systems via the standard.
Part of the reason for this proposal is that one of the systems ({\bf
Sinapse})
is transformational, and so a straightforward mapping already existed.

A transformational model provides a number of concepts and mechanisms:
\begin{description}\itemsep -3pt
\item   [Specification language:] used to specify desired properties of the
        desired instance system.
        Such a language may consist of atomic symbols representing concepts
        to implement (e.g., ``database''), or expressions of constraints over
        desired results (e.g., $<$In,Out$>$:In=Out*Out) or some domain specific
        notation with implicit intent (a partial differential equation with
        the implicit requirement to solve it).

\item   [Synthesis mechanisms:] convert specifications into program
abstractions with constraints.
        This requires the system to choose some set of mechanisms, which when
        composed, implement the specification. As an example, the system having
        both an integer enumeration and summing components might notice that
        the sum of integers 1..n is n*(n+1)/2, and use that fact to generate
        an integer square root algorithm by enumerating successively larger
        values of n, summing, and comparing.
        Synthesis in effect generates a refinement.

\item  [Refinement (transformations):] map high-level abstrac- tions to
       abstractions at a lower level.
       An example refinement is the conversion of the abstract notion of
       matrix inverse into more concrete code using multiply nested loops for
       a Gauss-Jordan procedure.

\item  [Optimizations (transformations):] replace configurations of
abstractions
       by ``simpler'' configurations of abstractions at the same abstraction
       level. As an example, the SQL query:\\
       SELECT cost$<$50 AND month=March FROM invoices\\
       can be to optimized to
       SELECT cost$<$50 FROM (SELECT month=March FROM invoices)\\
       assuming the statistical fact that there are usually fewer records from
       March than records with low cost value.

\item [ Control:] guides application of transforms (any of synthesis,
refinement or optimization) to produce the implemented system.
       Usually a control mechanism chooses among several legal transforms,
       each introducing certain levels of performance, to optimize for a
       performance property, such as execution speed or storage requirements.
\end{description}

To produce a desired program, a transformation system accepts a specification,
and then, under the guidance of the control mechanism, repeatedly chooses
transforms from a library to incrementally convert the original specification
into a final specification, representing the desired program.
(We remark that any of synthesis, refinement, and/or optimization can be
implemented using rewrite rules or arbitrary procedures).

A correspondence to generic architecture systems is obtained when one realizes
that any principled composition of instance components must itself have
well-understood properties, and therefore both the components and the
composition mechanism must have well-defined properties.
Oversimplifying, the key property required of an implementation I for a
specification S, is that important properties M (for ``meaning'') of the
specification are preserved: M(S) $<=$ M(I), i.e., the
implementation must have at least the properties required by the specification;
this is precisely the notion of {\it refinement} used in transformation
systems.
Any generic architecture system must somehow combine components c1, c2,...
to form an I for its input specification S.

The question is then, how can the example systems be described using the
conceptual framework of transformation systems?

\subsection*{Example Systems viewed Transformationally}

A correspondence between example system mechanisms and that of transformation
systems was established and is summarized in the following table:
\begin{tiny}
\begin{table}[h]
%begin{center}
\begin{tabular}{|p{0.4in}|p{0.5in}|p{0.4in}|p{0.5in}|p{0.5in}|p{0.5in}|}
%\begin{tabular}{|l|l|l|l|l|l|}
\hline
&
{\bf Specification}
&
{\bf Synthesis}
&
{\bf Refinement}
&
{\bf Optimization}
&
{\bf Control}
\\ \hline
{\bf Sinapse}
&
Partial differential equations (PDEs).
Implicit requirement that PDEs be solved.
&
Map PDEs to finite-difference solver.
&
Individual application of bundle of consistent transforms.
&
Many explicit array and scalar simplifications;
code motion, common subexpression elimination.
&
Internal sequencing of refinements and decision resolution.
Decision objects have resolution heuristics.
\\ \hline
{\bf Predator (P++)}
&
Component name (implies functionality) + signature.
&
N.A.
&
Substitution of named component instance.
&
Procedural transforms for query optimization.
&
User-supplied refinement sequence given by ``type'' expression
\\ \hline
{\bf Resolve - Ada}
&
Model-based predicate calculus description over math domains
(sets, tuples, etc.).
&
Refinements manually synthesized from existing components
&
Generic instantiation constrained by [Goguen86/89] style views.
&
Manual; rare. Believes refinement choice gives sufficient performance.
&
Manual; user-supplied transformation sequence
                       \\ \hline
\end{tabular}
\caption{Transformational view of several generic architecture systems}
\end{table}
\end{tiny}

Discovering how the instance systems fit into the transformational perspective
led to a number of insights about how or why the various systems worked.
As examples:

\begin{itemize}\itemsep -3pt
\item  System ``inputs'' mixed different kinds of knowledge needed by a
       transformation system.
       This suggests that generic architecture systems are likely to have mixed
       input information whose parts can be classified, which helps explain why
       such input information is needed to enhance automation or output
       quality.
       The sample systems mixed, to some degree, specification and control
       knowledge in their inputs:
  \begin{itemize}\itemsep -3pt
  \item   Functional specification:\\
   Sinapse: PDEs\\
 Predator/P++: Name/signature of desired system function\\
 RESOLVE: Predicate calculus specification of behavior supplied by a component.

  \item   Control knowledge:\\
 Sinapse: Decision resolutions controlling synthesis process\\
 Predator/P++: Explicit specification of choice of refinement of sub-components\\
 RESOLVE: Not in specification [user interactively selects from catalog]
  \end{itemize}

\item  One can't hide from control knowledge; it is present in all the systems
       in different forms.
\begin{itemize}\itemsep -3pt
  \item   Sinapse has explicit control knowledge, built into the system
  \item   Predator/P++ uses supplied control-knowledge to apply component
  refinements
  \item   Resolve leaves choice of refinement to the user. But he must choose.
\end{itemize}

\item  The key notion of refinement appears in each system in different forms,
       with differing levels of robustness.
       How robustness is ensured is important if we wish to trust systems
       produced by generic architecture schemes.
\begin{itemize}\itemsep -3pt
  \item   For each Sinapse abstraction, there are multiple sets of transforms
          that refine the abstraction consistently; set members are applied
          incrementally.

  \item   For each Predator abstraction (``realm''), there is a set of
          components, each being a monolithic refinement.
          Each refinement may introduce new abstractions which must
          be further refined; if the new subcomponents are refined correctly,
          then the refinement is itself correct.

  \item   RESOLVE specifications are monolithically refined only when
          Goguen-style constraints are satisfied.
\end{itemize}

Sinapse has multiple sets of transforms for which selected subsets must be
applied consistently.
Consistent transforms are applied individually, interleaved with other actions,
i.e., the refinement step is {\it not} monolithic.
This is accomplished by establishing an explicit intent, recorded by the
resolution of a design decision, and only selecting transforms
which are marked as consistent with that intent.
A similar method was used for the Draco transform system [Neighbors84] in
which applied transforms asserted they provided certain properties by posting
a tag symbol representing those properties, and potentially applicable
transforms required the presence of transform-specific tag symbols to
become truly applicable.
This method for consistent refinement is documented in [Katz93].

Some Predator components, while having the same conceptual specification and
identical signatures by virtue of being members of the same ``realm'', do not
always provide the functionality required by a true refinement.
This is handled by a (proposed) mechanism which notes when a particular
subcomponent is used, and ensures that only compatible components are used to
refine other parts of that component.
The transformational perspective allowed us to recognize that this was similar
if not identical to the Draco tagging method.
So two systems, Sinapse and Predator, use essentially the same idea present in
a third.
This hints that this idea may be somehow fundamental, or least a standard
heuristic.

A second consequence of the transformational perspective is an insight into
how refinements are packaged.
Predator packages refinements as entire, consistent components, ensuring that
refined Predator specifications lead to working code.
The price for this is that if one has n transforms, A, B, C,... N,
which taken individually are not refinements, but which taken in pairs (often)
form consistent refinements, they must be encoded as (up to) N$^{2}$
monolithic refinements.
There is a trade-off between flexibility (application of smaller transforms in
a larger variety of ways) vs. reuse of useful compositions (application of a
larger transform known to be useful).
In order to factor monolithic refinements into smaller transforms, one must be
able to express the constraints between the smaller transforms in order to
have the option of the trade-off.
It would convenient if sets of transforms chosen to form an incomplete
refinement somehow constrained further choices to compatible transforms in a
manner less ad hoc than the Draco tagging method.

RESOLVE has such a mechanism.
Components have import/export interface specifications and an implementation.
Components depend on explicit properties rather than directly on other
components.
Refinement of a module part by use of a consistent component then creates a
composite which has its own import/export specifications, which continue
to reflect the component's property dependencies.
This method appears to scale well: rather than worrying about the interactions
of all the (exponentially large) possible subsets of N components, one can
instead simply state necessary formal properties.
The price for this is that one needs a theorem prover to verify that
properties match instead of a simpler tag matching mechanism.

\item  Optimizations may be required for efficient code generation.
\begin{itemize}\itemsep -3pt

  \item   Sinapse offers many because of the performance demanded by
          supercomputing tasks.
          The Sinapse authors believe in the Draco model of a repeated
          refine-then-optimize cycle to remove redundancies introduced by
          juxtaposed refinements, and to perform optimizations at high levels
          of abstraction where they can be easily detected.

  \item   Predator uses relatively simple optimizations that appear mostly in
          the form of partial evaluation of conditional expressions.
          The most complex optimizations (and the most important) are those
          involving query optimizations, which involve the selection of
          which data structure to traverse and the factoring of predicates to
          avoid repeated subpredicate evaluation.

  \item   RESOLVE does currently not provide any automated method for
          optimizing a particular composition of refinements beyond inlining.
          The RESOLVE philosophy is that the best performance gains are to be
          had by choosing the most appropriate refinement at each step, rather
          than {\it a posteriori} optimization of a completed series of
refinements. \end{itemize}

This implies that the choice of each refinement, a manual process in RESOLVE,
is an important way of tailoring the performance of the resulting product
[Murali92].
\end{itemize}

It is remarkable that these insights were obtained even though two of the
systems examined were designed without a transformational model in mind.

\subsection*{Unresolved Issues}

In a single day, one cannot realistically explore the value of a model;
at best, one can determine there is some utility.
A number of obvious issues remain:

\begin{itemize}\itemsep -3pt
\item  Does a transformational model apply to other generic architecture
       systems?

\item  More detailed models exist (c.f. [Baxter90], covering explicit
       performance constraints and providing considerable flexibility in
       the explicit statement of control knowledge).
       How well do they hold up, and what, if any, extra insights might they
       provide?

\item  How does a transformational view explain architecture of components
       for systems?

\item  How does it explain architectures of the generated systems?

\item  How does the composition mechanism affect the components of
       generic architecture?

\item  Are there alternative hypotheses that explain the commonalities better?
\end{itemize}

The main value of the transformational perspective is to allow comparison of
features of the mechanisms used.
Such a perspective can be used to determine the robustness of the composition
process, how complete the specification language is for both problem and
components, and to determine what mechanisms a particular generic architecture
system may need.

\subsection*{References}

[Batory92] Batory, Don and Sean O'Malley. The Design and Implementation of
Hierarchical Software Systems Using Re- usable~Components. ACM Transactions on
Software
Engineering and Methodology, 1(4) 355-398, October 1992.

[Batory93] Batory, Don, V. Singhal, M. Sirkin and J. Thomas. Scalable Software
Libraries. Proceedings of CM SIGSOFT 93.

[Baxter92] Baxter, Ira. Transformational Maintenance by Reuse of Design
Histories. Ph.D. Thesis, University of California at Irvine, Department of
Computer Science, 1991. Available as University Microfilms International
document \#9109634.

[Goguen86] Goguen, Joseph, Reusing and Interconnection\\ Software Components,
IEEE Computer, 19(2), February, 1986.

[Goguen89] Goguen, Joseph A. Principles of Parameterized Programming.
In Software Reusability, Volume I: Concepts and Models, Biggerstaff,
Ted J. and Alan J. Perlis, ACM Press,
New York, New York,1989, pp. 159-225.

[Hollingsworth92] Hollingsworth, Joe. Software Component Design-for-Reuse:
A Language Independent Discipline Applied to Ada, Dept. of Computer and
Information Science, The Ohio State University, Columbus, Ohio, 1992.

[Kant91] Kant, Elaine, F. Daube, W. MacGregor and J. Wald. Scientific
Programming by Automated Synthesis.
In M. Lowry and R. McCartney, editors, Automating Software Design.
AAAI Press, 1991.

[Katz92] Katz, Martin and Dennis Volper. Constraint Propagation in Software
Libraries. Journal of Software and Knowledge Engineering, 2(3): pp. 355-375,
September 1992.

[Neighbors84] Neighbors, James. The Draco Approach to Constructing Software
from Reusable Components, IEEE Transactions on Software Engineering, SE-10(5),
September 1984.

[Murali92] Sitaraman, Murali. Performance-Parameterized Reusable Software Components.
International Journal of Software Engineering and Knowledge Engineering,
2,(4):pp. 567-587, October 1992.

[Murali93] Sitaraman, M., Lonnie R. Welch and Douglas E. Harms. On
Specification of Reusable Software Components. International Journal of
Software Engineering and Knowledge Engineering3(2):pp. 207-229, June 1993.

[RESOLVE93] The Reusable Software Research Group at The Ohio State University,
RESOLVE Reading/Reference List, available via anonymous ftp from
ftp.cis.ohio-state.edu in the directory pub/rsrg as the file RESOLVE-refs.txt,
1993.

[WOZ91] Weide, Bruce W., William F. Ogden and Stuart H. Zweben.
Reusable Software Components. In Yovits, M.C., Advances in Computers,
Volume. 33, Academic Press,1991.

