Recent research suggests that the goal of fully automatic and reliable program generation for a broad range of applications is coming nearer to feasibility. However, several interesting and challenging problems remain to be solved before it becomes a ...

Recent research suggests that the goal of fully automatic and reliable program generation for a broad range of applications is coming nearer to feasibility. However, several interesting and challenging problems remain to be solved before it becomes a reality. Solving them is also necessary, if we hope ever to elevate software engineering from its current state (a highly-developed handiwork) into a successful branch of engineering, capable of solving a wide range of new problems by systematic, well-automated and well-founded methods.We first discuss the relations between problem specifications and their solutions in program form, and then narrow the discussion to an important special case: program transformation. Although the goal of fully automatic program generation is still far from fully achieved, there has been some success in a special case: partial evaluation, also known as program specialization.A key problem in all program generation is termination of the generation process. This paper describes recent progress towards automatically solving the termination problem, first for individual programs, and then for specializers and "generating extensions," the program generators that most offline partial evaluators produce.The paper ends with a list of challenging problems whose solution would bring the community closer to the goal of broad-spectrum, fully automatic and reliable program generation.

Embedded systems represent fundamentally new challenges for software design, which render conventional approaches to software composition ineffective. Starting with the unique challenges of building embedded systems, this paper discusses key issues of ...

Embedded systems represent fundamentally new challenges for software design, which render conventional approaches to software composition ineffective. Starting with the unique challenges of building embedded systems, this paper discusses key issues of model-based technology for embedded systems. The discussion uses Model-Integrated Computing (MIC) as an example for model-based software development. In MIC, domain-specific, multiple view models are used in all phases of the development process. Models explicitly represent the embedded software and the environment it operates in, and capture the requirements of the application, simultaneously. Models are descriptive, in the sense that they allow the formal analysis, verification and validation of the embedded system at design time. Models are also generative, in the sense that they carry enough information for automatically generating embedded systems from them using the techniques of program generators.

Applications in an evolving computing environment should be designed to cope with varying data. Object-oriented programming, polymorphisms and parametric types often do not provide the required flexibility, which can be achieved with the use of metadata ...

Applications in an evolving computing environment should be designed to cope with varying data. Object-oriented programming, polymorphisms and parametric types often do not provide the required flexibility, which can be achieved with the use of metadata attached or extracted from objects by means of reflection. We present a general mechanism to support reflection in C++, exploiting template metaprogramming techniques. Metaclass objects are present at runtime and can be inspected to access information about objects, in particular about their fields. Metaobjects describing fields can be extended, through a mechanism similar to custom attributes in C#. The mechanism is self-reflective, allowing for metaclass objects to be described in turn. This allows storing and retrieving metaclasses from external storage and allows programs to understand and manipulate objects built by other programs. We present two case studies of the technique: building configuration objects and creating object-oriented interfaces to relational database tables.

DataScript is a language to describe and manipulate binary data formats as types. DataScript consists of two components: a constraint-based specification language that uses DataScript types to describe the physical layout of data and a language binding ...

DataScript is a language to describe and manipulate binary data formats as types. DataScript consists of two components: a constraint-based specification language that uses DataScript types to describe the physical layout of data and a language binding that provides a simple programming interface to script binary data. A DataScript compiler generates Java libraries that are linked with DataScript scripts.DataScript specifications can be used to describe formats in a programmatic way, eliminating the vagaries and ambiguities often associated with prosaic format descriptions. The libraries generated by the DataScript compiler free the programmer from the tedious task of coding input and output routines. More importantly, they assure correctness and safety by validating both the input read and the output generated. We show examples that demonstrate that DataScript is simple, yet powerful enough to describe many commonly used formats. Similar to how scripting languages such as Perl allow the manipulation of text files, the libraries generated by the DataScript compiler can be used to quickly write scripts that safely manipulate binary files.

We use a code generator--type-directed partial evaluation-- to verify conversions between isomorphic types, or more precisely to verify that a composite function is the identity function at some complicated type. A typed functional language such as ML ...

We use a code generator--type-directed partial evaluation-- to verify conversions between isomorphic types, or more precisely to verify that a composite function is the identity function at some complicated type. A typed functional language such as ML provides a natural support to express the functions and type-directed partial evaluation provides a convenient setting to obtain the normal form of their composition. However, off-the-shelf type-directed partial evaluation turns out to yield gigantic normal forms.We identify that this gigantism is due to redundancies, and that these redundancies originate in the handling of sums, which uses delimited continuations. We successfully eliminate these redundancies by extending type-directed partial evaluation with memoization capabilities. The result only works for pure functional programs, but it provides an unexpected use of code generation and it yields orders-of-magnitude improvements both in time and in space for type isomorphisms.

Traditional protocol implementation approaches capture the structural aspects of protocols in a common base that can be used accross layers. However, they are usually not very good at capturing the behavioral aspects. Two important implementation problems ...

Traditional protocol implementation approaches capture the structural aspects of protocols in a common base that can be used accross layers. However, they are usually not very good at capturing the behavioral aspects. Two important implementation problems result, namely, reprogramming similar behavior and configuration of crosscutting concerns. In this paper, we present an approach to solve the problems of reprogramming similar behavior and absence of systematic configuration mechanisms for crosscutting concerns in communication systems. Our approach is based on generative programming, has been implemented in C++ and has been validated with several protocols. We also sketch an approach for run-time reconfigurable protocol stacks.

The goal of aspect-oriented programming is to modularize crosscutting concerns (or aspects) at the code level. These aspects can be defined in either a general-purpose language or in a language that is fine-tuned to a specific aspect in consideration. ...

The goal of aspect-oriented programming is to modularize crosscutting concerns (or aspects) at the code level. These aspects can be defined in either a general-purpose language or in a language that is fine-tuned to a specific aspect in consideration. Aspect-specific languages provide more concise and more readable aspect declarations but are limited to a specific domain. Moreover, multiple aspects may be needed in a single application and composing aspects written in different aspect languages is not an easy task.To solve this composition problem, we represent both aspects and aspect languages as modularized logic metaprograms. These logic modules can be composed in flexible ways to achieve combinations of aspects written in different aspect-specific languages. As such, the advantages of both general-purpose and aspect-specific languages are combined.

The Know-It-All Project is investigating methodologies for the development, application, and evolution of frameworks. A concrete framework for database management systems is being developed as a case study for the methodology research. The methodology ...

The Know-It-All Project is investigating methodologies for the development, application, and evolution of frameworks. A concrete framework for database management systems is being developed as a case study for the methodology research. The methodology revolves around a set of models for the domain, the functionality, the architecture, the design, and the code. These models reflect the common and variable features of the domain.Refactoring of source code has been studied as a preliminary step in the evolution of object-oriented software. In cascaded refactoring, we view framework evolution as a two-step process: refactoring and extension. The refactoring step is a set of refactorings, one for each model. The refactorings chosen for a model determine the rationale or constraints for the choice of refactorings of the next model.There are several issues with respect to architecture that we have encountered and are exploring. These include (1) the choice of models for the architecture; (2) the design of the architecture and its evaluation; (3) the evolution of the architecture by extending the concept of refactoring from source code to architecture; and (4) the modeling of variation in architectures across the product line. Here we focus on the refactoring of the architecture.

We show how programming pearls can be systematically derived via fusion, followed by tupling transformations. By focusing on the elimination of intermediate data structures (fusion) followed by the elimination of redundant calls (tupling), we systematically ...

We show how programming pearls can be systematically derived via fusion, followed by tupling transformations. By focusing on the elimination of intermediate data structures (fusion) followed by the elimination of redundant calls (tupling), we systematically realise both space andtime efficient algorithms from naive specifications. We illustrate our approach using a well-known maximum segment sum (MSS) problem, anda less-known maximum segment product (MSP) problem. While the two problems share similar specifications, their optimisedco des are significantly different. This divergence in the transformed codes do not pose any difficulty. By relying on modular techniques, we are able to systematically reuse both code and transformation in our derivation.

Physical products come in many variants, and so does the software embedded in them. The software embedded in a product variant usually has to be optimized to fit its limited memory and computing power. Generative programming is well suited for developing ...

Physical products come in many variants, and so does the software embedded in them. The software embedded in a product variant usually has to be optimized to fit its limited memory and computing power. Generative programming is well suited for developing embedded software since it allows us to automatically produce variants of embedded software optimized for specific products. This paper reports on our experience in applying generative programming in the embedded domain. We propose an extended feature modeling notation, discuss tool support for feature modeling, describe a domain-independent system configuration editor, and comment on the applicability of static configuration in the area of embedded systems.

Aspect-Oriented Programming (AOP) promises separation of concerns at the implementation level. However, aspects are not always orthogonal and aspect interaction is an important problem. Currently there is almost no support for the detection and resolution ...

Aspect-Oriented Programming (AOP) promises separation of concerns at the implementation level. However, aspects are not always orthogonal and aspect interaction is an important problem. Currently there is almost no support for the detection and resolution of such interactions. The programmer is responsible for identifying interactions between conflicting aspects and implementing conflict resolution code.In this paper, we propose a solution to this problem based on a generic framework for AOP. The contributions are threefold: we present a formal and expressive crosscut language, two static conflict analyses and some linguistic support for conflict resolution.

Separation of Concerns is one of the software engineering design principles that is getting more attention from practitioners and researchers in order to promote design and code reuse. Separation of Concerns (SoC) separates requirements such as synchronization ...

Separation of Concerns is one of the software engineering design principles that is getting more attention from practitioners and researchers in order to promote design and code reuse. Separation of Concerns (SoC) separates requirements such as synchronization and scheduling from the core functionality. These requirements are often referred to as crosscutting-concerns. The implementation of such requirements is scattered throughout the system, which results in the code-tangling problem. Aspect Oriented Programming provides the user with the ability to modularize, and weave crosscutting-concerns in order to maximize code reusability and solves the code-tangling problem. Weaving is the process of combining crosscutting concerns with the core functionality. Using the UML to model and interweave these concerns is a craft that is hard to master due to the lack of formal modeling techniques based on SoC. In this paper we present a formal design methodology to model the system's concerns based on aspect-orientation.

Macros are often regarded as a sort of black magic: highly useful yet abstruse. The present paper aims to make macro programming more like a craft. Using R5RS Scheme macros as an example, we develop and present a general practical methodology of building ...

Macros are often regarded as a sort of black magic: highly useful yet abstruse. The present paper aims to make macro programming more like a craft. Using R5RS Scheme macros as an example, we develop and present a general practical methodology of building complex macros systematically, by combining simpler components by functional composition or higher-order operatorsMacro programming is complex because the systematic approach does not apply to many macros. We show that macros and other headfirst normal-order re-writing systems generally lack functional composition. However, macros written in a continuation-passing style (CPS) always compose. Making CPS macros practical still requires an encoding for macro-continuations. We have found this missing piece, with an insight for anonymous macro-level abstractions.In the specific case of R5RS macros, this paper presents a stronger result: developing R5RS macros by a translation from the corresponding Scheme procedures. We demonstrate the practical use of the technique by elaborating a real-world example.

Recall the size-change principle for program termination: An infinite computation is impossible, if it would give rise to an infinite sequence of size-decreases for some data values. For an actual analysis, size-change graphs are used to capture the ...

Recall the size-change principle for program termination: An infinite computation is impossible, if it would give rise to an infinite sequence of size-decreases for some data values. For an actual analysis, size-change graphs are used to capture the data size changes in possible program state transitions. Agraph sequence that respects program control flow is called a multipath. The set of multipaths describe possible state transition sequences. To show that such sequences are finite, it is sufficient that the graphs satisfy size-change termination (SCT): Every infinite multipath has infinite descent, according to the arcs of the graphs. This is an application of the size-change principle.SCT is decidable, but complete for PSPACE. In this paper, we explore efficient approximations that are sufficiently precise in practice.For size-change graphs that can loop (i.e., they give rise to an infinite multipath), and that satisfy SCT, it is usual to find amongst them an anchor-- some graph whose infinite occurrence in a multipath causes infinite descent. The SCT approximations are based on finding and eliminating anchors, as far as possible. If the remaining graphs cannot loop, then SCT is established.An efficient method is proposed to find anchors among fan-in free graphs, as such graphs occur commonly in practice. This leads to a worst-case quadratic-time approximation of SCT. An extension of the method handles general graphs and can detect some rather subtle descent. It leads to a worst-case cubic-time approximation of SCT. Experiments confirm the effectiveness and efficiency of the approximations in practice.

This paper presents a model-driven approach for generating Quality-of-Service (QoS) adaptation in Distributed Real-Time Embedded (DRE) systems. The approach involves the creation of high-level graphical models representing the QoS adaptation policies. ...

This paper presents a model-driven approach for generating Quality-of-Service (QoS) adaptation in Distributed Real-Time Embedded (DRE) systems. The approach involves the creation of high-level graphical models representing the QoS adaptation policies. The models are constructed using a domain-specific modeling language - the Adaptive Quality Modeling Language. Multiple generators have been developed using the Model-Integrated Computing framework to create low-level artifacts for simulation and implementation of the adaptation policies that are captured in the models. A simulation generator tool synthesizes artifacts for Matlab Simulink/Stateflow® (a popular commercial tool), providing the ability to simulate and analyze the QoS adaptation policy. An implementation generator creates artifacts for Quality Objects, a QoS adaptation software infrastructure developed at BBN, for execution of QoS adaptation in DRE systems. A case study in applying this approach to an Unmanned Aerial Vehicle - Video Streaming application is presented. This approach has goals that are similar to those specified in the OMG's Model-Driven Architecture initiative.

Content management systems support the dissemination and maintenance of documents. In software engineering terms, they separate the concerns of content, application logic and visual styling. Current systems largely maintain this separation of concerns ...

Content management systems support the dissemination and maintenance of documents. In software engineering terms, they separate the concerns of content, application logic and visual styling. Current systems largely maintain this separation of concerns after document deployment. Their runtime processing pipeline is a composition of generators, or document transformations. We exploit commutativity to enable new static evaluations of the composite during document deployment. Unlike traditional caching, we arrive at closed-form composites even for styled, database-driven documents. This eliminates the runtime penalties of a separation of concerns while preserving their software engineering benefits.

This paper presents techniques for a component-based style of programming in the context of higher-oder attribute grammars (HAG). Attribute grammar components are "plugged in" into larger attribute grammar systems through higher-order attribute grammars. ...

This paper presents techniques for a component-based style of programming in the context of higher-oder attribute grammars (HAG). Attribute grammar components are "plugged in" into larger attribute grammar systems through higher-order attribute grammars. Higher-order attributes are used as (intermediate) "gluing" data structures.This paper also presents two attribute grammar components that can be re-used across different language-based tool specifications: a visualizer and animator of programs and a graphical user interface AG component. Both components are reused in the definition of a simple language processor. The techniques presented in this paper are implemented in Lrc: a purely functional, higher-order attribute grammar-based system that generates language-based tools.

Altering the semantics of programs has become of major interest. This is due to the necessity of adapting existing software, for instance to achieve interoperability between off-the-shelf components. A system allowing such alterations should operate ...

Altering the semantics of programs has become of major interest. This is due to the necessity of adapting existing software, for instance to achieve interoperability between off-the-shelf components. A system allowing such alterations should operate at the bytecode level in order to preserve portability and to be useful for pieces of software whose source code is not available. Furthermore, working at the bytecode level should be done while keeping high-level abstractions so that it can be useful to a wide audience. In this paper, we present Jinline, a tool that operates at load time through bytecode manipulation. Jinline makes it possible to inline a method body before, after, or instead of occurrences of language mechanisms within a method. It provides appropriate high-level abstractions for fine-grained alterations while offering a good expressive power and a great ease of use.

Meta programs manipulate structured representations, i.e., abstract syntax trees, of programs. The conceptual distance between the concrete syntax meta-programmers use to reason about programs and the notation for abstract syntax manipulation provided ...

Meta programs manipulate structured representations, i.e., abstract syntax trees, of programs. The conceptual distance between the concrete syntax meta-programmers use to reason about programs and the notation for abstract syntax manipulation provided by general purpose (meta-) programming languages is too great for many applications. In this paper it is shown how the syntax definition formalism SDF can be employed to fit any meta-programming language with concrete syntax notation for composing and analyzing object programs. As a case study, the addition of concrete syntax to the program transformation language Stratego is presented. The approach is then generalized to arbitrary meta-languages.

In a multi-stage program generation (MSPG) system, a stage-s program generates a stage-s + 1 program when the values of some variables are known. We call such variables program parameters for stage-s.When program parameters for a stage change during ...

In a multi-stage program generation (MSPG) system, a stage-s program generates a stage-s + 1 program when the values of some variables are known. We call such variables program parameters for stage-s.When program parameters for a stage change during runtime, all later-stage program objects that are generated directly or indirectly based on them need to be dynamically regenerated. We make two contributions. a) We explore a metaobject protocol called reflection across stages (RAS), which allows later-stage program objects to refer back to earlier-stage program objects they originated from. Intercessory procedures can be specified by the earlier-stage program objects to be executed at, e.g., execution of the later stage objects. b) We apply RAS to automating runtime program regeneration, so that affected later-stage programs are automatically regenerated after program parameters change.In an initial experiment, RAS incurred an overhead of 10% when program parameters are invariant. The overhead of RAS plus regeneration is amortized to zero over1.5 executions of the generated program object.