Beyond Objects: Generative Programming

Krzysztof Czarnecki Daimler-Benz AG Research and Technology Wilhelm-Runge-Str. 11, 89081 Ulm, Germany Tel. +49-731-505-4008 Fax +49-731-505-4210 czarnecki@dbag.ulm.DaimlerBenz.com

Ulrich W. Eisenecker Fachhochschule Heidelberg Fachbereich Informatik Bonhoefferstraße 11, 69123 Heidelberg, Germany Tel./Fax +49-6223-990466 Ulrich.Eisenecker@T-Online.de

Patrick Steyaert Programming Technology Lab Vrije Universiteit Brussel Pleinlaan 2, 1050 Brussel, Belgium Tel. +32-2-629-3581 prsteyae@vnet3.vub.ac.be

1. Introduction

The object-oriented paradigm constitutes a major advance in software engineering. Some of its main contributions include

• improvement of understandability and better management of complexity: According to some theories in cognitive science, humans organize knowledge into sets of interrelated concepts (which are modeled as semantic nets or frames [Min75]). Since concepts can be modeled as objects quite adequately, the object-oriented paradigm allows us to build "natural" and better understandable models. Furthermore, encapsulation results in hiding unnecessary detail (i.e. it supports abstraction). Last but not least, objects can be organized into inheritance and containment hierarchies which capture the relationships between the corresponding concepts (see [Col95] for a detailed discussion of the interrelations between objects and cognitive psychology).
• extensibility, adaptability, and reusability: Inheritance and overriding allow us to extend and modify objects. Polymorphism enables providing alternative implementations of components.
• maintainability: Encapsulation helps to reduce coupling and polymorphism allows us to avoid error-prone type switches.

A recent shift in the object-oriented community is the focus on developing reusable solutions for families of applications instead of developing single applications from scratch. Class libraries providing sets of classes to be reused in a larger application are being evolved into frameworks which allow us to reuse their components, flow of control, and the overall application structure. Additionally, frameworks provide sets of alternative components in order to allow for axes of variation (i.e. hot spots [Pre95]).

Our position is that there are a number of issues concerning the development of reusable models for application families (including frameworks) which have not yet been adequately addressed within the object-oriented community:

• systematic modeling approach for application families (until now, only inductive approaches have been proposed, e.g. patterns [GJHV95], evolution of frameworks [RJ96])
• adequate decomposition and specification of domain concepts
• management of the additional complexity resulting from the family-orientedness of the development
• avoiding efficiency penalties for improved understandability, adaptability, reusability, and maintainability of the design

In the remaining sections, we will explain these points and propose Generative Programming as a new software engineering paradigm which addresses these issues. We will also discuss the relationship of Generative Programming to Aspect-Oriented Programming and other generative approaches.

2. Domain Engineering: A Paradigm Oriented Towards the Development of Application Families

Domain Engineering (DE) is about the systematic development of a domain model (Domain Analysis, abbr. DA) and its implementation (Domain Implementation). A domain model is the representation of common and variant aspects of a number of representative systems of a domain and the rationale for variations [WISR8]. Examples of DA and DE methodologies are ODM [SCK+96], FODA [Kan+90], DARE [FPF95], and DSSA [TTC95]. A typical DA process involves

• scoping the domain of interest: The scoping process involves business goals, stakeholders, and setting (i.e. legacy systems and standards, existing domains, etc.).
• modeling the domain concepts, their defining features and typical feature variations: whereby a feature is a statement or assertion about a concept or a set of concepts ( [SCK+96]).

DA provides a systematic methodology for the development of frameworks. More work on the integration of existing DA and OOA/D methodologies is needed.

3. Capturing the Domain

A domain is defined as an area of knowledge or activity characterized by a set of concepts and terminology understood by practitioners in that area [UML1.0], i.e. an area of expertise. Knowledge engineering, expert systems, and DA are all concerned with capturing expertise, i.e. modeling a domain. The focus of DA is on capturing expertise for building certain classes of software systems. The kinds of knowledge contained in a domain include the following:

• decision knowledge (i.e. competence knowledge): knowledge defining the domain. Any domain has a decision procedure which utilizes the decision knowledge (e.g. a set of rules) and defines what is included in the domain and what is not.
• operational knowledge: knowledge defining the base concepts and aspects (which are partial specifications of concepts; see Section 4.2.1) of the domain.
• configuration knowledge: knowledge defining which combinations of concepts and aspects are valid and which aspects imply other default aspects in a given configuration. This type of knowledge can be represented as a set of configuration rules.
• design knowledge: We distinguish between
  • simple design rationale: configuration rules with conflict resolution (e.g. priorities)
  • design history (derivation history): full mapping between the end-user requirements and the system in form of a series of intermediate designs obtained by applying sets of formal transforms including the record of the used transforms.
• advanced expertise: knowledge involving heuristics, fuzzy reasoning, and several levels of metaknowledge.

A domain model can be classified according to the kind of knowledge it contains. Typical object-oriented frameworks model the operational knowledge (in form of base-level classes). They might also contain some configuration knowledge which is often represented implicitly in some methods. In some cases, the configuration knowledge is represented more explicitly in specially designated metacomponents. Examples of approaches capturing other types of knowledge than operational knowledge are found in Table 1.

4. Problem Decomposition

4.1. Problem Solving

Any software development activity can be thought of as a problem-solving activity. A general problem-solving strategy is problem reduction: Decompose a larger problem into a set of smaller problems and solve the larger problem by solving the smaller problems. [1] The resulting solution has a layered structure resembling the solving process. The structure of each layer is transformed according to the available knowledge which is reused. The structure need not be refined hierarchically over the layers: Concepts can be merged, the structure of one concept can be imposed on a number of other concepts. [2]

4.2. A Pragmatic View of Decomposition

4.2.1. Concerns and Aspects

Inspired by the work of [HL95], [Aks96], [KIL+96], and [SCK+96], we propose the notions of concerns and aspects to be used in the context of software decomposition. We define them as follows:

1. A concern is a domain used as a decomposition criterion for a system or another domain with that concern. Concerns can be used during analysis, design, implementation, and refactoring. [3]
2. An aspect is a partial specification of a concept or a set of concepts with respect to a concern.

4.2.2. Quality of Concerns

As stated, any domain contains a decision procedure which defines what is included in the domain and what is not. This decision procedure enables use of a concern in decomposition. The concerns used in decomposition should yield aspects which are

• loosely coupled,
• (nearly) orthogonal, and
• highly declarative.

4.2.3 How Are Concerns Discovered?

There are many types of decomposition currently used in software development. Some of them include functional decomposition, decomposition based on data structures, separation of interface and implementation, separation of implementation and policy, and separation of responsibilities. There are concerns corresponding to well-established domains, e.g. computational domains, such as synchronization, error detection and handling, communication, etc. Some domains define their own sets of concerns, e.g. application development (model, view, and controller). DA methods provide a systematic way of discovering adequate concerns by studying feature variations within a domain and performing an explicit feature-clustering step aimed at maximizing the orthogonality between the resulting features. The results of this procedure could be captured in systems of concerns which are typical for given domains. Such systems of concerns would also define the rationale for each of its concerns.

4.2.4. Properties of Aspects

Aspects, by definition, may have different scopes, i.e. they may refer to one concept or to a set of concepts. Aspects themselves may also be complex concepts having their own aspects.

The notions of an aspect and an aspect specification language correspond to the notions of a feature and a feature model in ODM [SCK+96], respectively.

An important issue is the coordination mechanism which is used to define the structural relationships between the aspects. Examples of such mechanisms are displayed in Table 1. More research on effective coordination mechanisms is needed.

4.3. Semantics of Decomposition

The structural relationships between (partial) specifications of concepts are studied in the field of algebraic specifications (e.g. see [LEW96]). In the algebraic view, specifications are theories (i.e. sets of logical formulas) using vocabularies defined by signatures. A signature consists of a set of sorts (i.e. symbols denoting sets) and of a set of operations (i.e. symbols denoting functions). For example, the sorts of a stack specification may include the symbols stack and item and the operations may include the operation name Push and its arity stack item stack. An algebra assigns concrete sets to sorts and functions to operations. An algebraic specification denotes classes of algebras. Classes of algebras are called Abstract Data Types (ADT) and can be used to represent domain concepts. As stated, a specification of an ADT is a set of formulas expressed in terms of the vocabulary defined by its signature. The formulas are well-formed formulas of some logical framework, e.g. equational logic (in which case they are universally quantified equations, e.g. Pop(Push(anElem, aStack)) = aStack).

Structural relationships between specifications of concepts (in our case ADTs, i.e. classes of algebras) can be represented as specification morphisms. A specification morphism between a source and a target specification is defined as a signature morphism (i.e. a mapping between the sorts and operation of the source and target signatures) which, if used to translate formulas, ensures that the translated theorems of the source specification are theorems of the target specification. Or in other words, the ADT specified by the source specification can be obtained from the ADT specified by the target specification by "forgetting" some of the structure of the latter ADT.

Examples of structural relationships between specifications are interpretations and refinements [Smi96]. Interpretations define the structural correspondence between a reusable problem specification and the specification of a problem at hand (e.g. interpretation relationship I in Figure 1). Refinements define relationships between the reusable problem specifications and their reusable solutions (e.g. refinement relationship R in Figure 1). Both types of relationships are defined in terms of specification morphisms.

As an example (adopted from [Smi96]), we consider the problem of sorting a list of numbers. The algebraic specification of this problem will be called SortingProblemSpec. The problem can be solved by applying divide and conquer problem solving strategy (the resulting solution is the Quicksort algorithm; see [Smi96] for details). Suppose that a GeneralProblemSpec and its corresponding Divide&ConquerSolution are stored in a library. It is interesting to note that the refinement relationship R (see Figure 1) implies that GeneralProblemSpec is a generic parameter of Divide&ConquerSolution. You can reuse this problem-solution pair by identifying the correspondence between the symbols in SortingProblemSpec and GeneralProblemSpec. This step defines the interpretation relationship I. A specification which structurally satisfies both SortingProblemSpec and Divide&ConquerSolution can be computed automatically (the resulting specification is referred to as the pushout of the commuting diagram). An example of a tool performing such compositions is SPECWARE [SJ95].

As demonstrated in [Smi96], refinements and interpretations allow us to create a refinement hierarchy of standard problem formulations as well as their solutions and to utilize this reusable knowledge for a constructive and iterative decomposition of new problems.

From the presented discussion, we conclude that the algebraic approach to specification promotes the modeling of a software system as a set of structurally-related partial specifications. Each partial specification can deploy its own vocabulary, i.e. signature, and the correspondence between the vocabularies is defined by signature morphisms. The differences between the specification languages used to specify each aspect need not be at the syntactic level only: The specification languages can deploy different logical frameworks whereby the foundation for the integration of different logical frameworks is given by theory of institutions [GB84]. [4]

5. Generative Programming

Generative Programming (GP) is a new paradigm merging domain engineering and object-oriented techniques. The goals of GP are

• increasing reusability and adaptability,
• improving control of complexity,
• managing a large number of variants, and
• increasing efficiency (space and execution time).

These goals are achieved by applying a number of fundamental principles:

• Separation of concerns: The discussion in Section 4.2 applies.
• Opening the model implementation: Each component provides access to its implementation strategies as aspects.
• Providing alternative aspects for a concern: An aspect is a component implementing a concern of another component. Relevant concerns of a component are modeled as its parameters.
• Propagation of aspects: Aspects can be passed from one component to another. Aspects can be propagated from containers to their parts and from parts to their containers. Propagation of aspects extends their scope to a set of components. It reduces redundancy and facilitates global domain-specific optimizations.
• Hiding complexity using layering and configuration rules: Components have some external aspects (features) and a usually larger number of internal aspects. The internal aspects can be derived automatically from the external aspects using configuration rules. Configuration rules are also used to express constraints (i.e. defining which configurations are valid and which are not).
• Zero-overhead rule: Overhead in the final product has to be avoided. Domain-specific and general-purpose optimization techniques are used in order to avoid efficiency penalties for good design. The time of binding can be controlled, so static binding is used instead of dynamic binding, if sufficient.

The main means of composition are type parameterization and delegation. The work of the first two authors has demonstrated that most of the GP concepts can be efficiently implemented in C++ using template metaprogramming techniques (some of these techniques are presented in [Eis97], other will be discussed in an upcoming paper).

6. Classification of Generative Approaches

An incomplete and tentative classification of a selection of approaches addressing the problems listed in Section 1 is shown in Table 1. The progress in DE technology is depicted in Figure 2.

7. Future Directions

We identify four major directions for future research:

• work on integrating the processes and work products of DA and OOA/D,
• work on coordination mechanisms,
• work on codifying systems of concerns,
• work on principles for building generators,

and the long-term goal:

• design maintenance systems.

Topics of Interest

• Discussion of the proposed terminology
• Refinement of the presented classification of approaches

approach	configuration time	kind of design knowledge	kind of optimization	concerns	coordination mechanism
Aspect-Oriented Programming [KIL+96]	static	??	local and global static optimizations	any	any
Demeter [Lie96]	static	constraints	inlining, ??	class structure and algorithms	succinct graph specifications
Subject-Oriented Programming [HO93], [OKH+95]	static and dynamic	constraints, configuration rules (composition rules)	??	any (modeled as subjects, i.e. a possibly incomplete OO programs)	object identity and composition rules
Composition Filters [ATB97]	dynamic	configuration knowledge in form of condition methods and filter specifications	none	interface, implementation, message dispatch, synchronization, real-time constraints, atomic transactions, error detection	messages sent and received
metaobject protocols (e.g. [Chi95])	dynamic (and static)	not specified	local and (gobal ??) static and dynamic optimizations	any	any
GenVoca [Bat96], [BG96], [BO92]	static	constraints, configuration rules	local and global static optimizations	components corresponding to any concerns	parameterization
Generative Programming	static & dynamic	constraints, configuration rules	local and global, static and dynamic optimizations	any (a systems of concerns for objects has been defined)	type parameterization (static) and delegation (dynamic)
Intentional Programming [Sim96], [Sim95]	static & dynamic	partial design history	local and global, static and (dynamic ??) optimizations	any	any
Specware [SJ95]	static	partial design history	local and global static optimizations	any	specification morphisms (interpretations and refinements)
Design Maintenance System [Bax92]	static & dynamic	design history	local and global static and (dynamic ??) optimizations	any	any

References

[Aks96] M. Aksit. Composition and Separation of Concerns in the Object-Oriented Model. In ACM Computing Surveys 28A(4), December 1996. http://www_trese.cs.utwente.nl/ Tresepapers/acm96.html

[ATB97] M. Aksit, B. Tekinerdogan, and L. Bergmans. Achieving adaptability through separation and composition of concerns. In Proceedings of the ECOOP Workshop on Adaptability in Object-Oriented Software Development, Special Issues in Object-Oriented Programming: Workshop Reader of ECOOP'96, dpunkt.verlag, 1997, pp. 12-28

[Bat96] D. Batory. Subjectivity and GenVoca Generatos. In [Sit96], pp. 166-175

[Bax92] I. Baxter. Design Maintenance System. In Communications ACM, Vol. 35, No. 4, April 1992, pp. 73-89

[BG96] D. Batory and B.J. Geraci. Validating Component Compositions in Software System Generators. In [Sit96], pp. 72-81

[BO92] D. Batory and S. O'Malley. The Design and Implementation of Hierarchical Software Systems With Reusable Components. In ACM Transactions on Software Engineering and Methodology, Vol. 1, No. 4, October 1992

[Chi95] S. Chiba. A Metaobject Protocol for C++. In Proceedings of OOPSLA'95, ACM SIGPLAN Notices, vol. 30, no. 10, October 1995, pp. 285-299

[Col95] D. Collins. Designing Object-Oriented User Interfaces. Benjamin/Cummings, 1995

[Eis97] U. W. Eisenecker. Generative Programming (GP) with C++. In Proceedings of the Joint Modular Language Conference '97, Lecture Notes 1204, Springer, 1997

[FPF95] W. Frakes, R. Prieto-Diaz, and C. Fox. DARE: Domain Analysis and Reuse Environment. In Proceedings of Seventh Annual Workshop on Software Reuse, St. Charles, IL, 1995

[GB84] J. Goguen and R. Burstall. Introducing institutions. Proceedings of Logics of Programming Workshop, Carnegie-Mellon. Springer LNCS 164, 1984, pp. 221-256

[GHJV95] E. Gamma, R. Helm, R. Johnson, and J. Vlissides. Design Patterns, Elements of Reusable Object-Oriented Software, Addison-Wesley, 1995

[HL95] W. L. Hürsch and C. V. Lopes. Separation of Concerns. Technical Report NU-CCS-95-03, Northeastern University Boston, College of Computer Science, MA 02115, USA, February 24, 1995. ftp://www.ccs.neu.edu/pub/people/crista/papers/separation.ps

[HO93] W. Harrison and H. Ossher. Subject-oriented programming (a critique of pure objects). In Proceedings of OOPSLA'93, 1993, pp. 411-428

[Kan+90] K. C. Kang et al. Feature-Oriented Domain Analysis (FODA) Feasibility Study. Technical Report CMU/SEI-90-TR21, Software Engineering Institute, Pittsburgh, PA, 1990

[KIL+96] G. Kiczales, J. Irwin, J. Lamping, J.-M. Lointier, C. V. Lopes, Ch. Maeda, and A. Mendhekar. Aspect-Oriented Programming: A Position Paper From the Xerox PARC Aspect-Oriented Programming Project. Position paper for the ACM Workshop on Strategic Directions in Computing Research, Working Group Object-Oriented Programming, MIT, USA, June 14-15, 1996, http://www.parc.xerox.com/spl/projects/ aop/

[LEW96] J. Loeckx, H.D. Ehrich, and M. Wolf. Specification of Abstract Data Types. Wiley & Teubner, 1996

[Lie96] K. Lieberherr. Adaptive Object-Oriented Software: The Demeter Method with Propagation Patterns. PWS Publishing Company, 1996

[Min75] M. Minsky. A framework for representing knowledge. In The Psychology of Computer Vision, P.H. Winston, editor, McGrow-Hill, New York, 1975, pp. 211-277

[OKH+95] H. Ossher, M. Kaplan, W. Harrison, A. Katz, and V. Kruskal. Subject-Oriented Composition Rules. In Proceedings of OOPSLA'95, ACM SIGPLAN Notices, vol. 30, no. 10, October 1995, pp. 235-250

[Pre95] W. Pree. Design Patterns for Object-Oriented Software Development. Addison-Wesley, 1995

[RJ96] D. Roberts and R. Johnson. Evolve Frameworks into Domain-Specific Languages. Submitted to PLOP'96, draft available at http://st-www.cs.uiuc.edu/users/droberts/evolve.html

[SCK+96] M. Simos, D. Creps, C. Klinger, L. Levine, and D. Allemang. Organization Domain Modeling (ODM) Guidebook, Version 2.0. Informal Technical Report for STARS, STARS-VC-A025/001/00, 14 June 1996, available at http://www.organon.com

[Sim95] Ch. Simonyi. The Death of Computer Languages, The Birth of Intentional Programming. Technical Report MSR-TR-95-52, Microsoft Research, 1995, ftp://ftp.research.microsoft.com/pub/tech-reports/Summer95/TR-95-52.doc

[Sim96] Ch. Simonyi, Intentional Programming - Innovation in the Legacy Age. Presented at IFIP WG 2.1 meeting, June 4, 1996

[Sit96] M. Sitaraman (Ed.). Proceedings of the Fourth International Conference on Software Reuse, April 23-26, 1996, Orlando Florida, IEEE Computer Society Press, 1996

[SJ95] Y. V. Srinivas and R. Jüllig. Specware^TM: Formal Support for Composing Software. In Proceedings of the Conference on Mathematics of Program Construction, Kloster Irsee, Germany, July 1995

[Smi96] D.R. Smith. Toward a Classification Approach to Design. In Proceedings of Algebraic Methodology & Software Technology, AMAST'96, Munich, Germany, July 1996, M. Wirsing and M. Nivat (Eds.), LCNS 1101, Springer, 1996, pp. 62-84

[TTC95] R.N. Taylor, W. Tracz, and L. Coglianese. Software Development Using Domain-Specific Software Architectures: CDRL A011A curriculum Module in the SEI Style. In ACM SIGSOFT Software Engineering Notes, 20(5), Dec. 1995, pp. 27-37

[UML1.0] UML Semantics Appendix M1: UML Glossary, version 1.0, Rational Software Corporation, January 13th, 1997

[WISR8] Definition based on the discussion at the WISR8 session on "Object Technology, Domain Analysis, and Architecture - What's the connection? - Is there a connection?", International Workshop on Software Reuse WISR8, Columbus, Ohio, March 1997

Footnotes

[1] Problem reduction may be a purely constructive process, so the term "decomposition" might seem to be inadequate; however, it is a well established term and it will be used in the rest of the paper.

[2] Apparently, one of the main ideas of AOP [KIL+96] is to specify concepts at the higher level instead of specifying the resulting merged concepts.

[3] Thanks to the participants of the WISR 8 session on "Object Technology, Domain Analysis, and Architecture - What's the connection? - Is there a connection?" for helping to refine the initial version of this definition.

[4] The theory of algebraic specification can be seen as the "correspondence calculus" sought after in [KIL+96, p. 7]. The "correspondence calculus" was suggested as a formal basis for the study of structural relationships between aspects.