Generative Programming and Component Engineering

abc is an extensible, optimising compiler for AspectJ. It has been designed as a workbench for experimental research in aspect-oriented programming languages and compilers. We outline a programme of research in these areas, and we review how abc can help in achieving those research goals.

Code generators based on template expansion techniques are easier to build than purely deductive systems but do not guarantee the same level of assurance: instead of providing “correctness-by-construction”, the correctness of the generated code depends on the correctness of the generator itself. We present an alternative assurance approach, in which the generator is extended to enable Hoare-style safety proofs for each individual generated program. The proofs ensure that the generated code does not “go wrong”, i.e., does not violate certain conditions during its execution.

The crucial step in this approach is to extend the generator in such way that it produces all required annotations (i.e., pre-/postconditions and loop invariants) without compromising the assurance provided by the subsequent verification phase. This is achieved by embedding annotation templates into the code templates, which are then instantiated in parallel by the generator. This is feasible because the structure of the generated code and the possible safety properties are known when the generator is developed. It does not compromise the provided assurance because the annotations only serve as auxiliary lemmas and errors in the annotation templates ultimately lead to unprovable safety obligations.

We have implemented this approach and integrated it into the AutoBayes and AutoFilter program generators. We have then used it to fully automatically prove that code generated by the two systems satisfies both language-specific properties such as array-bounds safety or proper variable initialization-before-use and domain-specific properties such as vector normalization, matrix symmetry, or correct sensor input usage.

Domain-Specific Languages (DSLs) represent a proven approach to raising the abstraction level of programming. They offer high-level constructs and notations dedicated to a domain, structuring program design, easing program writing, masking the intricacies of underlying software layers, and guaranteeing critical properties.

This paper presents a methodology to develop DSL compilers, centered around the use of generative programming tools. Our approach enables the development of a DSL compiler to be structured on facets that represent dimensions of compilation. Each facet can then be implemented in a modular way, using aspects, annotations and specialization. Because these tools are high level, they match the needs of a DSL, facilitating the development of the DSL compiler, and making it modular and re-targetable.

We illustrate our approach with a DSL for telephony services. The structure of the DSL compiler is presented, as well as practical uses of generative tools for some compilation facets.

We present a domain-specific-language (DSL) for writing instances of a class of filter programs. The values in the language are symbolic and independent of a concrete precision. Efficient code generation is required to fit the program onto a target device limited in both memory and processing power. We construct an interpreter for the DSL in a language specific to the device which contains the semantics of the target instruction set embedded within a declarative meta-language. The compiler is automatically generated from the interpreter through specialisation. This extension of the instruction set allows the construction of an interpreter for the DSL that is both simple and clear. In particular it allows us to declare static representations of the symbolic values, and have the specialisation of the code produce operate upon these values in the instruction set of the target device.

Domain-specific languages (DSL) provides high-level functions making applications easier to write, and to maintain. Unfortunately, many applications are written from scratch and poorly documented, which make them hard to maintain. An ideal solution should be to rewrite them in a appropriate DSL. In this paper, we present TeMa (Template Matcher), an automatic tool to recognize high-level functions in source code. Preliminary results show how TeMa can be used to reformulate Fortran code into Signal Processing Language (SPL) used in SPIRAL. This opens new possibilities for domain-specific languages.

Domain-specific languages (DSLs) have been proposed as a solution to ease the development of programs within a program family. Sometimes, however, experience with the use of a DSL reveals the presence of subfamilies within the family targeted by the language. We are then faced with the question of how to capture these subfamilies in DSL abstractions. A solution should retain features of the original DSL to leverage existing expertise and support tools.

The Bossa DSL is a language targeted towards the development of kernel process scheduling policies. We have encountered the issue of program subfamilies in using this language to implement an encyclopedic, multi-OS library of scheduling policies. In this paper, we propose that introducing certain kinds of modularity into the language can furnish abstractions appropriate for implementing scheduling policy subfamilies. We present the design of our modular language, Bossa Nova, and assess the language quantitatively and qualitatively.

This paper presents AOP++, a generic aspect-oriented programming framework in C++. It successfully incorporates AOP with object-oriented programming as well as generic programming naturally in the framework of standard C++. It innovatively makes use of C++ templates to express pointcut expressions and match join points at compile time. It innovatively creates a full-fledged aspect weaver by using template metaprogramming techniques to perform aspect weaving. It is notable that AOP++ itself is written completely in standard C++, and requires no language extensions. With the help of AOP++, C++ programmers can facilitate AOP with only a little effort.

Model-driven architecture (MDA) aims at automating software design processes. Design models are divided into platform-indepen- dent models (PIMs) and platform-specific models (PSMs). A model compiler transforms the former models into the latter automatically. We can regard PIMs as a new kind of reusable software component because they can be reused even if a platform is changed. However, a generated PSM is useless if it does not satisfy system limitations such as memory usage and real-time constraints. It is necessary to allow a modeler to customize transformation rules because model modifications for dealing with these limitations may be specific to an application. However, current model compilers do not provide the modeler sufficient customization methods. In order to tackle this problem, we propose a method for constructing an extensible model compiler based on aspect orientation, a mechanism that modularizes crosscutting concerns. Aspect orientation is useful for platform descriptions because it crosscuts many model elements. A modeler can extend model transformation rules by defining new aspects in the process of modeling. In this paper, an aspect-oriented modeling language called AspectM (Aspect for Modeling) for supporting modeling-level aspects is introduced. Using AspectM, a modeler can describe not only crosscutting concerns related to platforms but also other kinds of crosscutting concerns. We believe that MDA is one of the applications of aspect-oriented mechanisms. The contribution of this paper is to show that a model compiler can actually be constructed based on aspect-oriented mechanisms.

This paper presents FeatureC++, a novel language extension to C++ that supports Feature-Oriented Programming (FOP) and Aspect-Oriented Programming (AOP). Besides well-known concepts of FOP languages, FeatureC++ contributes several novel FOP language features, in particular multiple inheritance and templates for generic programming. Furthermore, FeatureC++ solves several problems regarding incremental software development by adopting AOP concepts. Starting our considerations on solving these problems, we give a summary of drawbacks and weaknesses of current FOP languages in expressing incremental refinements. Specifically, we outline five key problems and present three approaches to solve them: Multi Mixins, Aspectual Mixin Layers, and Aspectual Mixins that adopt AOP concepts in different ways. We use FeatureC++ as a representative FOP language to explain these three approaches. Finally, we present a case study to clarify the benefits of FeatureC++ and its AOP extensions.

The expressiveness of AspectJ’s dynamic join point model has been shown in many useful applications, while the static join point model (also called lexical shadows) has been studied less. We propose a notion of shadow programming that exposes a program’s adapted lexical shadow information to compile time language constructs to enable customized static analysis and more expressive join point selection mechanisms. In particular, within the framework of the AspectJ language and compiler, we have designed and implemented two compile time language constructs, called Statically Executable Advice and Pointcut Evaluator respectively, to show how the lexical shadow information can be used.

An inverse of a program is a program that takes the output of the original program and produces its input. A semi-inverse of a program is a program that takes some of the input and some of the output of the original program and produces the remaining input and output. Inversion is, hence, a special case of semi-inversion.

We propose a method for inverting and semi-inverting programs written as guarded equations. The semi-inversion process is divided into four phases: Translation of equations into a relational form, refining operators, determining evaluation order for each equation of the semi-inverted functions and translation of semi-inverted functions back to the original syntax. In cases where the method fails to semi-invert a program, it can suggest which additional parts of the programs input or output are needed to make it work.

We describe the application of generative programming to a problem in interactive information retrieval. The particular interactive information retrieval problem we study is the support for ‘out of turn interaction’ with a website – how a user can communicate input to a website when the site is not soliciting such information on the current page, but will do so on a subsequent page. Our solution approach makes generous use of program transformations (partial evaluation, currying, and slicing) to delay the site’s current solicitation for input until after the user’s out-of-turn input is processed. We illustrate how studying out-of-turn interaction through a generative lens leads to several valuable insights: (i) the concept of a web dialog, (ii) an improved understanding of web taxonomies, and (iii) new web interaction techniques and interfaces. These notions allow us to cast the design of interactive (and responsive) websites in terms of the underlying dialog structure and, further, suggest a simple implementation strategy with a clean separation of concerns. We also highlight new research directions opened up by the generative programming approach to interactive information retrieval such as the idea of web interaction axioms.

One of the themes in building reusable and maintainable software is identifying similarities and designing generic solutions to unify similarity patterns. In this paper, we analyze capabilities of J2EE to effectively unify similarity patterns found in Web Portals (WP). Our experimentation involved a family of WPs to support information sharing and team collaboration, built by our industry partner. While J2EE provides useful mechanisms for reuse of common services across components, we found its limitations in systematic across-the-board reuse in application domain-specific areas. To solve these problems, we applied a generative programming (GP) technique of XVCL on top of J2EE. By unifying similarity patterns, we increased the clarity of portal’s conceptual structure as perceived by developers, reducing also the size of the original J2EE WP by 61%. Our solution enhanced traceability of information that mattered during changes. Based on that we hypothesized that XVCL-enhanced J2EE WP would be easier to maintain than the original J2EE WP. In the paper, we describe our solution and evaluate its engineering merits in both quantitative and qualitative ways.

With Gaussian Elimination as a representative family of numerical and symbolic algorithms, we use multi-stage programming, monads and Ocaml’s advanced module system to demonstrate the complete elimination of the abstraction overhead while avoiding any inspection of the generated code. We parameterize our Gaussian Elimination code to a great extent (over domain, matrix representations, determinant tracking, pivoting policies, result types, etc) at no run-time cost. Because the resulting code is generated just right and not changed afterwards, we enjoy MetaOCaml’s guaranty that the generated code is well-typed. We further demonstrate that various abstraction parameters (aspects) can be made orthogonal and compositional, even in the presence of name-generation for temporaries and other bindings and “interleaving” of aspects. We also show how to encode some domain-specific knowledge so that “clearly wrong” compositions can be statically rejected by the compiler when processing the generator rather than the generated code.

To illustrate the proposed approach, we design and implement a translation to a subset of C suitable for numerical computation, and show that it preserves static typing. The translation is implemented, and evaluated with several benchmarks. The implementation is available in the online distribution of MetaOCaml.

SafeGen is a meta-programming language for writing statically safe generators of Java programs. If a program generator written in SafeGen passes the checks of the SafeGen compiler, then the generator will only generate well-formed Java programs, for any generator input. In other words, statically checking the generator guarantees the correctness of any generated program, with respect to static checks commonly performed by a conventional compiler (including type safety, existence of a superclass, etc.). To achieve this guarantee, SafeGen supports only language primitives for reflection over an existing well-formed Java program, primitives for creating program fragments, and a restricted set of constructs for iteration, conditional actions, and name generation. SafeGen’s static checking algorithm is a combination of traditional type checking for Java, and a series of calls to a theorem prover to check the validity of first-order logical sentences constructed to represent well-formedness properties of the generated program under all inputs. The approach has worked quite well in our tests, providing proofs for correct generators or pointing out interesting bugs.

In this paper we describe a type system for a generative mechanism that generalizes the concept of generic types by combining it with a controlled form of reflection. This mechanism makes many code generation tasks possible for which generic types alone would be insufficient. The power of code generation features are carefully balanced with their safety, so that we are able to perform static type checks on generator code. This leads to a generalized notion of type safety for generators.

Motivated by a wish to sort an array A while simultaneously permuting another array B, iteration over array pairs (A,B) is considered.

Traditional solutions to this problem require an adaption of either the algorithm or of the data structure. The generic programming approach described in this paper involves the construction of an iterator adaptor: an iterator pair. The different approaches are implemented in C++ and compared with respect to flexibility and performance.

Our design is also compared with another iterator-based design. When examining our solution, we identify the relationship between a reference type and a value type as an independent abstraction. We find that a valid “reference type” to a value type T is not necessarily T&. The reference pair developed in this paper serves as an example of a reference type which refers to a standard value pair without being a standard reference.

Our understanding of the relationships between iterator pairs, value pairs, and reference pairs, makes our design simpler than the alternative. It is argued that a recognition of these relationships is useful in many other generic programming contexts as well.

Extending a programming language by new language constructs often implies extending its compiler by additional machinery. To reduce the complex interweaving of compiler and extension implementations we present a simple and modular concept of lifting the often needed additional preprocessing out of the base compiler implementation. Avoiding the introduction of standalone tools, this preprocessor framework for extensions of Haskell is designed as a separate portable library of monadic preprocessing functions based on Template Haskell. Additional preprocessing passes expressed in this framework can then much easier be carried along the series of ever advancing base compiler versions. Taking Eden, a parallel programming extension of Haskell, as an example we show that besides achieving improved portability and reusability pass code sizes can be reduced considerably.

In this paper, we show how to combine a component system and a macro system. A component system separates the definition of a program fragment from the statements that link it, enabling independent compilation of the fragment. A macro system, in contrast, relies on explicit links among fragments that import macros, since macro expansion must happen at compile time. Our combination places macro definitions inside component signatures, thereby permitting macro expansion at compile time, while still allowing independent compilation and linking for the run-time part of components.

Component-oriented programming yields a tension between higher-order features (deployment, reconfiguration, passivation), encapsulation, and component sharing. We propose a discipline for component-oriented programming to address this issue, and we define a process calculus whose operational semantics embodies this programming discipline. We present several examples that illustrate how the calculus supports component sharing, while allowing strong encapsulation and higher-order primitives.

The past decade of experience has demonstrated that the generic programming methodology is highly effective for the design, implementation, and use of large-scale software libraries. The fundamental principle of generic programming is the realization of interfaces for entire sets of components, based on their essential syntactic and semantic requirements, rather than for any particular components. Many programming languages have features for describing interfaces between software components, but none completely support the approach used in generic programming. We have recently developed \(\mathcal{G}\), a language designed to provide first-class language support for generic programming and large-scale libraries. In this paper, we present an overview of \(\mathcal{G}\) and analyze the interdependence between language features and library design in light of a complete implementation of the Standard Template Library using \(\mathcal{G}\). In addition, we discuss important issues related to modularity and encapsulation in large-scale libraries and how language support for validation of components in isolation can prevent many common problems in component integration.

Although a feature model can represent commonalities and variabilities in a very concise taxonomic form, features in a feature model are merely symbols. Mapping features to other models, such as behavioral or data specifications, gives them semantics. In this paper, we propose a general template-based approach for mapping feature models to concise representations of variability in different kinds of other models. We show how the approach can be applied to UML 2.0 activity and class models and describe a prototype implementation.

CAM/DAOP is a component and aspect based model and platform implemented using Java/RMI and reflective techniques. Using CAM/DAOP we have developed several collaborative applications, where the most relevant one is a Virtual Office application, which allows dispersed users to collaborate as if they were co-located. Attendees of the demonstration will see how to develop dynamic and adaptable applications with CAM/DAOP, from the design through to the implementation phases. We will place emphasis on showing how to adapt the behavior of CAM/DAOP applications at runtime, simply by modifying the architectural information provided during the application development.

Many current metamodeling environments still require manual programming to build full tool support for the modeling language, especially for language constraints, representational elements and graphical editing tools. Because of this, a considerable part of development resources has to be reserved for secondary assets of the final environment instead of its main vehicle, the modeling language itself. In this demonstration, we present the MetaEdit+ metaCASE tool, and show how metamodeling and tool support for domain-specific modeling languages can be completed without programming. We will describe the metamodeling tool set of MetaEdit+ and explain how conceptual and representational metamodeling is carried out with it. Finally, we will look at the executable modeling environment derived from the metamodel.