A Software Product Line ( SPL ) is a family of similar programs. Each program is defined by a unique set of features, called a configuration , that satisfies all feature constraints. “What configuration achieves the best performance for a given workload?” is the SPL Optimization ( SPLO ) challenge. SPLO is daunting: just 80 unconstrained features yield 10 24 unique configurations, which equals the estimated number of stars in the universe. We explain (a) how uniform random sampling and random search algorithms solve SPLO more efficiently and accurately than current machine-learned performance models and (b) how to compute statistical guarantees on the quality of a returned configuration; i.e., it is within x% of optimal with y% confidence.

Real-world Software Product Lines (SPLs) need Numerical Feature Models (NFMs) whose features have not only boolean values that satisfy boolean constraints but also have numeric attributes that satisfy arithmetic constraints. An essential operation on NFMs finds near-optimal performing products, which requires counting the number of SPL products. Typical constraint satisfaction solvers perform poorly on counting and sampling. Nemo (Numbers, features, models) is a tool that supports NFMs by bit-blasting, the technique that encodes arithmetic expressions as boolean clauses. The newest version, Nemo2, translates NFMs to propositional formulas and the Universal Variability Language (UVL). By doing so, products can be counted efficiently by #SAT and Binary Decision Tree solvers, enabling finding near-optimal products. This article evaluates Nemo2 with a large set of synthetic and colossal real-world NFMs, including complex arithmetic constraints and counting and sampling experiments. We empirically demonstrate the viability of Nemo2 when counting and sampling large and complex SPLs.

Model Driven Engineering ( MDE ) is a general-purpose engineering methodology to elevate system design, maintenance, and analysis to corresponding activities on models. Models (graphical and/or textual) of a target application are automatically transformed into source code, performance models, Promela files (for model checking), and so on for system analysis and construction. Models are instances of metamodels . One form an MDE metamodel can take is a [class diagram, constraints] pair: the class diagram defines all object diagrams that could be metamodel instances; object constraint language ( OCL ) constraints eliminate semantically undesirable instances. A metamodel refactoring is an invertible semantics-preserving co-transformation, i.e., it transforms both a metamodel and its models without losing data. This article addresses a subproblem of metamodel refactoring: how to prove the correctness of refactorings of class diagrams without OCL constraints using the Coq Proof Assistant.

Abstract Many analyses on configurable software systems are intractable when confronted with colossal and highly-constrained configuration spaces. These analyses could instead use statistical inference, where a tractable sample accurately predicts results for the entire space. To do so, the laws of statistical inference requires each member of the population to be equally likely to be included in the sample, i.e., the sampling process needs to be “uniform”. SAT-samplers have been developed to generate uniform random samples at a reasonable computational cost. However, there is a lack of experimental validation over colossal spaces to show whether the samplers indeed produce uniform samples or not. This paper (i) proposes a new sampler named , (ii) presents a new statistical test to verify sampler uniformity, and (iii) reports the evaluation of and five other state-of-the-art samplers: , , , , and . Our experimental results show only satisfies both scalability and uniformity.

2.3 should be "Method 3: Measure the distance between the theoretical variable probabilities with the empirical variable frequencies in a sample", and the title of Section 2.2.4 should be "Method 4: A statistical goodness-of-fit test that compares the theoretical variable probabilities with the empirical variable frequencies in a sample".

Regression testing checks that recent project changes do not break previously working functionality. Although important, regression testing is costly when changes are frequent. Regression test selection (RTS) optimizes regression testing by running only tests whose results might be affected by a change. Traditionally, RTS collects dependencies (e.g., on files) for each test and skips the tests, at a new project revision, whose dependencies did not change. Existing RTS techniques do not differentiate behavior-preserving transformations (i.e., refactorings) from other code changes. As a result, tests are run more frequently than necessary.

Software Product Lines (SPLs) are highly configurable systems. This raises the challenge to find optimal performing configurations for an anticipated workload. As SPL configuration spaces are huge, it is infeasible to benchmark all configurations to find an optimal one. Prior work focused on building performance models to predict and optimize SPL configurations. Instead, we randomly sample and recursively search a configuration space directly to find near-optimal configurations without constructing a prediction model. Our algorithms are simpler and have higher accuracy and efficiency.

Refactoring engines are standard tools in today's Integrated Development Environments (IDEs). They allow programmers to perform one refactoring at a time, but programmers need more. Most design patterns in the Gang-of-Four text can be written as a refactoring script -- a programmatic sequence of refactorings. In this paper, we present R3, a new Java refactoring engine that supports refactoring scripts. It builds a main-memory, non-persistent database to encode Java entity declarations (e.g., packages, classes, methods), their containment relationships, and language features such as inheritance and modifiers. Unlike classical refactoring engines that modify Abstract Syntax Trees (ASTs), R3 refactorings modify only the database; refactored code is produced only when pretty-printing ASTs that reference database changes. R3 performs comparable precondition checks to those of the Eclipse Java Development Tools (JDT) but R3's codebase is about half the size of the JDT refactoring engine and runs an order of magnitude faster. Further, a user study shows that R3 improved the success rate of retrofitting design patterns by 25% up to 50%.

Retrofitting design patterns into a program by hand is tedious and error-prone. A programmer must distinguish refactorings that are provided by an Integrated Development Environment (IDE) from those that must be realized manually, determine a precise sequence of refactorings to apply, and perform this sequence repetitively to a laborious degree. We designed, implemented, and evaluated Reflective Refactoring (R2), a Java package to automate the creation of classical design patterns (Visitor, Abstract Factory, etc.), their inverses, and variants. We encoded 18 out of 23 Gang-of-Four design patterns as R2scripts and explain why the remaining are inappropriate for refactoring engines. We evaluate the productivity and scalability of R2with a case study of 6 real-world applications. In one case, R2automatically created a Visitor with 276 visit methods by invoking 554 Eclipse refactorings in 10 minutes - an achievement that could not be done manually. R2also sheds light on why refactoring correctness, expressiveness, and speed are critical issues for scripting in next-generation refactoring engines.

A software product line (SPL) is a family of programs that are differentiated by features --- increments in functionality. Systematically testing an SPL is challenging because it requires running each test of a test suite against a combinatorial number of programs. Feature models capture dependencies among features and can (1) reduce the space of programs to test and (2) enable accurate categorization of failing tests as failures of programs or the tests themselves, not as failures due to illegal combinations of features. In practice, sadly, feature models are not always available.

How do experts navigate the huge space of implementations for a given specification to find an efficient choice with minimal searching? Answer: They use "heuristics" -- rules of thumb that are more street wisdom than scientific fact. We provide a scientific justification for Dense Linear Algebra (DLA) heuristics by showing that only a few decisions (out of many possible) are critical to performance; once these decisions are made, the die is cast and only relatively minor performance improvements are possible. The (implementation x performance) space of DLA is stair-stepped. Each stair is a set of implementations with very similar performance and (surprisingly) share key design decision(s). High-performance stairs align with heuristics that prescribe certain decisions in a particular context. Stairs also tell us how to tailor the search engine of a DLA code generator to reduce the time it needs to find implementations that are as good or better than those crafted by experts.

Many programs can be configured through dynamic and/or static selection of configuration variables. A software product line (SPL), for example, specifies a family of programs where each program is defined by a unique combination of features. Systematically testing SPL programs is expensive as it can require running each test against a combinatorial number of configurations. Fortunately, a test is often independent of many configuration variables and need not be run against every combination. Configurations that are not required for a test can be pruned from execution. This paper presents SPLat, a new way to dynamically prune irrelevant configurations: the configurations to run for a test can be determined during test execution by monitoring accesses to configuration variables. SPLat achieves an optimal reduction in the number of configurations and is lightweight compared to prior work that used static analysis and heavyweight dynamic execution. Experimental results on 10 SPLs written in Java show that SPLat substantially reduces the total test execution time in many cases. Moreover, we demonstrate the scalability of SPLat by applying it to a large industrial code base written in Ruby on Rails.

A classical approach to program derivation is to progressively extend a simple specification and then incrementally refine it to an implementation. We claim this approach is hard or impractical when reverse engineering legacy software architectures. We present a case study that shows optimizations and pushouts---in addition to refinements and extensions---are essential for practical stepwise development of complex software architectures.

Customizable programs and program families provide user-selectable features to allow users to tailor a program to an application scenario. Knowing in advance which feature selection yields the best performance is difficult because a direct measurement of all possible feature combinations is infeasible. Our work aims at predicting program performance based on selected features. However, when features interact, accurate predictions are challenging. An interaction occurs when a particular feature combination has an unexpected influence on performance. We present a method that automatically detects performance-relevant feature interactions to improve prediction accuracy. To this end, we propose three heuristics to reduce the number of measurements required to detect interactions. Our evaluation consists of six real-world case studies from varying domains (e.g., databases, encoding libraries, and web servers) using different configuration techniques (e.g., configuration files and preprocessor flags). Results show an average prediction accuracy of 95%.

A software product line (SPL) is a family of related programs, each of which is uniquely defined by a combination of features. Testing an SPL requires running each of its programs, which may be computationally expensive as the number of programs in an SPL is potentially exponential in the number of features. It is also wasteful since instructions common to many programs must be repeatedly executed, rather than just once. To reduce this waste, we propose the idea of shared execution, which runs instructions just once for a set of programs until a variable read yields multiple values, causing execution to branch for each value until a common execution point that allows shared execution to resume. Experiments show that shared execution can be faster than conventionally running each program from start to finish, despite its overhead.

Software architectures can be presented by graphs with components as nodes and connectors as edges. These graphs, or models, typically encode expert domain knowledge, which makes them difficult to understand. Hence, instead of presenting a complete complex model, we can derive it from a simple, easy-to-understand model by a set of easy-to-understand transformations. In two controlled experiments, we evaluate whether a derivation of a model is easier to understand than the model itself.

The efforts of an expert to parallelize and optimize a dense linear algebra algorithm for distributed-memory targets are largely mechanical and repetitive. We demonstrate that these efforts can be encoded and automatically applied to obviate the manual implementation of many algorithms in high-performance code.

The relationship between feature modules and feature interactions is not well-understood. To explain classic examples of feature interaction, we show that features are not only composed sequentially, but also by cross-product and interaction operations that heretofore were implicit in the literature. Using the Colored IDE (CIDE) tool as our starting point, we (a) present a formal model of these operations, (b) show how it connects and explains previously unrelated results in Feature Oriented Software Development (FOSD), and (c) describe a tool, based on our formalism, that demonstrates how changes in composed documents can be back-propagated to their original feature module definitions, thereby improving FOSD tooling.

Refactoring is the process of applying behavior-preserving transformations to a program with the objective of improving the program's design. A specific refactoring is identified by a name (e.g., Extract Method), a set of preconditions, and a set of transformations that need to be performed.

Mechanized proof assistants are powerful verification tools, but proof development can be difficult and time-consuming. When verifying a family of related programs, the effort can be reduced by proof reuse. In this paper, we show how to engineer product lines with theorems and proofs built from feature modules. Each module contains proof fragments which are composed together to build a complete proof of correctness for each product. We consider a product line of programming languages, where each variant includes metatheory proofs verifying the correctness of its semantic definitions. This approach has been realized in the Coq proof assistant, with the proofs of each feature independently certifiable by Coq. These proofs are composed for each language variant, with Coq mechanically verifying that the composite proofs are correct. As validation, we formalize a core calculus for Java in Coq which can be extended with any combination of casts, interfaces, or generics.

A Software Product Line (SPL) is a family of programs where each program is defined by a unique combination of features. Developing a set of programs with commonalities and variabilities in this way can significantly reduce both the time and cost of software development. However, as the number of programs may be exponential in the number of features, testing an SPL, the phase to which the majority of software development is dedicated, becomes especially challenging [12].

Recent advances in mechanical techniques for systematic testing have increased our ability to automatically find subtle bugs, and hence, to deploy more dependable software. This paper builds on one such systematic technique, scope-bounded testing, to develop a novel specification-based approach for efficiently generating tests for products in a software product line. Given properties of features as first-order logic formulas in Alloy, our approach uses SAT-based analysis to automatically generate test inputs for each product in a product line. To ensure soundness of generation, we introduce an automatic technique for mapping a formula that specifies a feature into a transformation that defines incremental refinement of test suites. Our experimental results using different data structure product lines show that an incremental approach can provide an order of magnitude speedup over conventional techniques. We also present a further optimization using dedicated integer constraint solvers for feature properties that introduce integer constraints, and show how to use a combination of solvers in tandem for solving Alloy formulas.

Programs can be composed from features. We want to verify automatically that all legal combinations of features can be composed safely without errors. Prior work on this problem assumed that features add code monotonically. We generalize prior work to enable features to add and remove code, describe our analyses and implementation, and review case studies. We observe that more expressive features increase the complexity of developed programs rapidly -- up to the point where tools and automated concepts as presented in this paper are indispensable for verification.

Features express the variabilities and commonalities among programs in a software product line (SPL). A feature model defines the valid combinations of features, where each combination corresponds to a program in an SPL. SPLs and their feature models evolve over time. We classify the evolution of a feature model via modifications as refactorings, specializations, generalizations, or arbitrary edits. We present an algorithm to reason about feature model edits to help designers determine how the program membership of an SPL has changed. Our algorithm takes two feature models as input (before and after edit versions), where the set of features in both models are not necessarily the same, and it automatically computes the change classification. Our algorithm is able to give examples of added or deleted products and efficiently classifies edits to even large models that have thousands of features.

Programs of a software product line can be synthesized by composing features which implement a unit of program functionality. In most product lines, only some combination of features are meaningful; feature models express the high-level domain constraints that govern feature compatibility. Product line developers also face the problem of safe composition - whether every product allowed by a feature model is type-safe when compiled and run. To study the problem of safe composition, we present Lightweight Feature Java (LFJ), an extension of Lightweight Java with support for features. We define a constraint-based type system for LFJ and prove its soundness using a full formalization of LFJ in Coq. In LFJ, soundness means that any composition of features that satisfies the typing constraints will generate a well-formed LJ program. If the constraints of a feature model imply these typing constraints then all programs allowed by the feature model are type-safe.

A functional aspect is an aspect that has the semantics of a transformation; it is a function that maps a program to an advised program. Functional aspects are composed by function composition. In this paper, we explore functional aspects in the context of aspect-oriented refactoring. We show that refactoring legacy applications using functional aspects is just as flexible and expressive as traditional aspects (functional aspects can be refactored in any order), while having a simpler semantics (aspect composition is just function composition), and causes fewer undesirable interactions between aspects (the number of potential interactions between functional aspects is half the number of potential interactions between traditional aspects). We analyze several aspect-oriented programs of different sizes to support our claims.

Modeling languages are a fundamental part of automated software development. MDD, for example, uses UML class diagrams and state machines as languages to define applications. In this paper, we explore how Feature Oriented Software Development (FOSD) uses modern mathematics as a modeling language to express the design and synthesis of programs in software product lines, but demands little mathematical sophistication from its users. Doing so has three practical benefits: (1) it offers a simple and principled mathematical description of how FOSD transforms, derives, and relates program artifacts, (2) it exposes previously unrecognized commuting relationships among tool chains, thereby providing new ways to debug tools, and (3) it reveals new ways to optimize software synthesis.

Feature modules are the building blocks of programs in software product lines (SPLs). A foundational assumption of feature-based program synthesis is that features are composed in a predefined sequence called a natural order. Recent work on virtual separation of concerns reveals a new model of feature interactions that shows that feature modules can be quantized as compositions of smaller modules called derivatives. We present this model and examine some of its consequences, namely, that (1) a given program can be reconstructed by composing features in any order, and (2) the contents of a feature module (as expressed as a composition of derivatives) is determined automatically by a feature order. We show that different orders allow one to adjust the contents of a feature module to isolate and study the impact of interactions that a feature has with other features. We also show the utility of generalizing safe composition (SC), a basic analysis of SPLs that verifies program type-safety, to demonstrate that every legal composition of derivatives (and thus any composition order of features) produces a type-safe program, which is a much stronger SC property.

We present a novel specification-based approach for generating tests for products in a software product line. Given properties of features as first-order logic formulas, our approach uses SAT-based analysis to automatically generate test inputs for each product in a product line. To ensure soundness of generation, we introduce an automatic technique for mapping a formula that specifies a feature into a transformation that defines incremental refinement of test suites. Our experimental results using different data structure product lines show that incremental approach can provide an order of magnitude speed-up over conventional techniques.

The automation of software product line (SPL) analyses is of growing interest to both practitioners and researchers. In particular, automated analyses of variability models (like feature or decision models) and languages that foster declarative specifications of programs using those models are now common. We note that many of the problems that SPL engineers face are related to configuration problems that have been addressed by the Artificial Intelligence (AI) community. Indeed, the SPL community is using some of their results, e.g., BDD, CSP and SAT solvers.

Programs of a software product line can be synthesized by composing modules that implement features. Besides high-level domain constraints that govern the compatibility of features, there are also low-level implementation constraints: a feature module can reference elements that are defined in other feature modules. Safe composition is the guarantee that all programs in a product line are type safe: i.e., absent of references to undefined elements (such as classes, methods, and variables). We show how safe composition properties can be verified for AHEAD product lines using feature models and SAT solvers.

Model driven development (MDD) is an emerging paradigm for software construction that uses models to specify programs, and model transformations to synthesize executables. Feature oriented programming (FOP) is a paradigm for software product lines where programs are synthesized by composing features. feature oriented model driven development (FOMDD) is a blend of FOP and MDD that shows how products in a software product line can be synthesized in an MDD way by composing features to create models, and then transforming these models into executables. We present a case study of FOMDD on a product line of portlets, which are components of web portals. We reveal mathematical properties of portlet synthesis that helped us to validate the correctness of our abstractions, tools, and specifications, as well as optimize portlet synthesis.

Future software development will rely on product synthesis, i.e., the synthesis of code and non-code artifacts for a target component or application. Prior work on feature-based product synthesis can be understood and generalized using elementary ideas from category theory. Doing so reveals (a) practical and previously unrecognized properties that product synthesis tools must satisfy, and (b) non-obvious generalizations of current techniques that will guide future research efforts in automated product development.

This paper presents a specification-based approach for systematic testing of products from a software product line. Our approach uses specifications given as formulas in Alloy, a first-order logic based on relations. Alloy formulas can be checked for satisfiability using the Alloy Analyzer. The fully automatic analyzer, given an Alloy formula and a scope, i.e., a bound on the universe of discourse, searches for an instance, i.e., a valuation to the relations in the formula such that it evaluates to true. The analyzer translates an Alloy formula (for the given scope) to a propositional formula and finds an instance using an off-the-shelf SAT solver. The use of an enumerating solver enables systematic test generation.

Software product lines aim to create highly configurable programs from a set of features. Common belief and recent studies suggest that aspects are well-suited for implementing features. We evaluate the suitability of AspectJ with respect to this task by a case study that refactors the embedded database system Berkeley DB into 38 features. Contrary to our initial expectations, the results were not encouraging. As the number of aspects in a feature grows, there is a noticeable decrease in code readability and maintainability. Most of the unique and powerful features of AspectJ were not needed. We document where AspectJ is unsuitable for implementing features of refactored legacy applications and explain why.

Aspect-Oriented Programming (AOP) and Feature-Oriented Programming (FOP) are complementary technologies that can be combined to overcome their individual limitations. Aspectual Mixin Layers (AML) is a representative approach that unifies AOP and FOP. We use AML in a non-trivial case study to create a product line of overlay networks. We also present a set of guidelines to assist programmers in how and when to use AOP and FOP techniques for implementing product lines in a stepwise and generative manner.

This roadmap describes ways that researchers in four areas---specification languages, program generation, correctness by construction, and programming languages---might help further the goal of verified software. It also describes what advances the "verified software" grand challenge might anticipate or demand from work in these areas. That is, the roadmap is intended to help foster collaboration between the grand challenge and these research areas.A common goal for research in these areas is to establish language designs and tool architectures that would allow multiple annotations and tools to be used on a single program. In the long term, researchers could try to unify these annotations and integrate such tools.

Feature refactoring is the process of decomposing a program into aset of modules, called features, that encapsulate increments in program functionality. Different compositions of features yield different programs. As programs are defined using multiple representations, such as code, makefiles, and documentation, feature refactoring requires all representations to be factored. Thus, composing features produces consistent representations of code, make files, documentation, etc. for a target program. We present acase study of feature refactoring a substantial tool suite that usesmultiple representations. We describe the key technical problems encountered, and sketch the tool support needed for simplifying such refactorings in the future.

Feature oriented refactoring (FOR) is the process of decomposinga program into features, where a feature is an increment in programfunctionality. We develop a theory of FOR that relates code refac-toring to algebraic factoring. Our theory explains relationshipsbetween features and their implementing modules, and why fea-tures in different programs of a product-line can have differentimplementations. We describe a tool and refactoring methodologybased on our theory, and present a validating case study.

Aspect-oriented programming is a promising paradigm that challenges traditional notions of program modularity. Despite its increasing acceptance, aspects have been documented to suffer limited reuse, hard to predict behavior, and difficult modular reasoning. We develop an algebraic model that relates aspects to program transformations and uncovers aspect composition as a significant source of the problems mentioned. We propose an alternative model of composition that eliminates these problems, preserves the power of aspects, and lays an algebraic foundation on which to build and understand AOP tools.

Feature Oriented Programming (FOP) is a design methodology and tools for program synthesis in software product lines. Programs are specified declaratively in terms of features. FOP has been used to develop product-lines in widely varying domains, including compilers for extensible Java dialects [6], fire support simulators for the U.S. Army [4], network protocols [1], web portlets [8], and program verification tools [9].

Monitoring is a task of collecting measurements that reflect the state of a system. Administration is a collection of tasks for control and manipulation of computer systems. Monitoring and Administering computer Resources (MARS) in a distributed grid computing environment (i.e. a distributed environment for coordinated resource sharing and problem solving in dynamic, multi-institutional virtual organizations) is an important, expensive, and critical task. We present a novel solution based on applying crosscuts using binary rewriters and an event-based model that allows developers to create non-trivial MARS programs easily and uniformly. Our approach converts low-level API resource calls into system-wide events that MARS programs can monitor. This is accomplished by introducing advice that contains event-generating code at join points in programs that represent computer resources. We categorize low-level resource APIs by imposing a transactional metaphor to simplify the complexity of interactions between resources and to enable reasoning about MARS programs. We report both a case study and simulation that supports the viability of our approach.

Common software design practices use object-oriented (OO) frameworks that structure software in terms of objects, classes, and packages; designers then create programs by inheritance and composition of classes and objects. Operational software components for advanced robotics (OSCAR) is one such framework for robot control software with abstractions for generalized kinematics, dynamics, performance criteria, decision making, and hardware interfacing. Even with OSCAR, writing new programs still requires a significant amount of manual labor. Feature-oriented programming (FOP) is method for software design that models and specifies programs in terms of features, where a feature encapsulates the common design decisions that occur in a domain. A set of features then forms a domain model for a product line architecture. Product variants in this product line can then be generated from a declarative specification. FOP and related technologies are emerging software engineering techniques for automatically generating programs. Our research applies FOP to robot controller software. As an example, the domain of hardware interfacing is analyzed and 41 features identified. A GUI for specifying and generating programs is presented as well. Analysis of features shows 200 possible different programs could be generated.

Feature oriented programming (FOP) is an emerging paradigm for application synthesis, analysis, and optimization. A target application is specified declaratively as a set of features, like many consumer products (e.g., personal computers, automobiles). FOP technology translates such declarative specifications into efficient programs.

Building systems from existing applications written in two or more languages is common practice. Such systems are polylingual. Polylingual systems are relatively easy to build when the number of APIs needed to achieve language interoperability is small. However, when the number of distinct APIs become large, maintaining and evolving polylingual systems becomes a notoriously difficult task. In this paper, we present a simple, practical, and effective way to develop, maintain, and evolve large-scale polylingual systems. Our approach relies on recursive type systems whose instances can be manipulated by reflection. Foreign objects (i.e. objects that are not defined in a host programming language) are abstracted as graphs and path expressions are used for accessing and manipulating data. Path expressions are implemented by type reification - turning foreign type instances into first-class objects and enabling access to and manipulation of them in a host programming language. Doing this results in multiple benefits, including coding simplicity and uniformity that we demonstrate in a complex commercial project.

Step-wise refinement is a powerful paradigm for developing a complex program from a simple program by adding features incrementally. We present the AHEAD (algebraic hierarchical equations for application design) model that shows how step-wise refinement scales to synthesize multiple programs and multiple noncode representations. AHEAD shows that software can have an elegant, hierarchical mathematical structure that is expressible as nested sets of equations. We review a tool set that supports AHEAD. As a demonstration of its viability, we have bootstrapped AHEAD tools from equational specifications, refining Java and nonJava artifacts automatically; a task that was accomplished only by ad hoc means previously.

Feature Oriented Programming (FOP) is a design methodology and tools for program synthesis. The goal is to specify a target program in terms of the features that it offers, and to synthesize an efficient program that meets these specifications. FOP has been used to develop product-lines in disparate domains, including compilers for extensible Java dialects [3], fire support simulators for the U.S. Army [5], high-performance network protocols [1], and program verification tools [14].

Step-wise refinement is a powerful paradigm for developing a complex program from a simple program by adding features incrementally. We present the AHEAD (Algebraic Hierarchical Equations for Application Design) model that shows how step-wise refinement scales to synthesize multiple programs and multiple non-code representations. AHEAD shows that software can have an elegant, hierarchical mathematical structure that is expressible as nested sets of equations. We review a tool set that supports AHEAD. As a demonstration of its viability, we have bootstrapped AHEAD tools solely from equational specifications, generating Java and non-Java artifacts automatically, a task that was accomplished only by ad hoc means previously.

Step-wise refinement (SWR) asserts that complex programs can be derived from simple programs by progressively adding features. The length of a program specification is the number of features that the program has. Critical to the scalability of SWR are multi-dimensional models that separate orthogonal feature sets. Let n be the dimensionality of a model and k be the number of features along a dimension. We show program specifications that could be O(kn) features long have short and easy-to-understand specifications of length O(kn) when multi-dimensional models are used. We present new examples of multidimensional models: a micro example of a product-line (whose programs are 30 lines of code) and isomorphic macro examples (whose programs exceed 30K lines of code). Our work provides strong evidence that SWR scales to synthesis of large systems.

GenVoca is a methodology and technology for generating product-lines, i.e. building variants of a program. The primitive components from which applications are constructed are refinements or layers, which are modules that implement a feature that many programs of a product-line can share. Unlike conventional components (e.g., COM, CORBA, EJB), a layer encapsulates fragments of multiple classes. Sets of fully formed classes can be produced by composing layers. Layers are modular, albeit unconventional, building blocks of programs. But what are the building blocks of layers? We argue that facets is an answer. A facet encapsulates fragments of multiple layers, and compositions of facets yields sets of fully formed layers. Facets arise when refinements scale from producing variants of individual programs to producing variants of multiple integrated programs, as typified byproduct families (e.g., MS Office). We present a mathematical model that explains relationships between layers and facets. We use the model to develop a generator for tools (i.e., product family) that are used in language-extensible Integrated Development Environments (IDEs).

This is a case study in the use of product-line architectures (PLAs) and domain-specific languages (DSLs) to design an extensible command-and-control simulator for Army fire support. The reusable components of our PLA are layers or "aspects" whose addition or removal simultaneously impacts the source code of multiple objects in multiple, distributed programs. The complexity of our component specifications is substantially reduced by using a DSL for defining and refining state machines, abstractions that are fundamental to simulators. We present preliminary results that show how our PLA and DSL synergistically produce a more flexible way of implementing state-machine-based simulators than is possible with a pure Java implementation.

A "refinement" is a functionality addition to a software project that can affect multiple dispersed implementation entities (functions, classes, etc.). In this paper, we examine large-scale refinements in terms of a fundamental object-oriented technique called collaboration-based design. We explain how collaborations can be expressed in existing programming languages or can be supported with new language constructs (which we have implemented as extensions to the Java language). We present a specific expression of large-scale refinements called mixin layers , and demonstrate how it overcomes the scalability difficulties that plagued prior work. We also show how we used mixin layers as the primary implementation technique for building an extensible Java compiler, JTS.

GenVoca PLA designs have been created for diverse domains: 2-way radios, extensible compilers, communication protocols, command-and-control fire support, avionics, and matrix computation libraries [7]. GenVoca designs are used in industry; its central concepts relate a wide variety of contemporary and classical research topics, including: aspect-oriented programming, parameterized programming, OO frameworks, Perry's lite semantics [8], generative programming [7], design maintenance [9], and layered software.

Domain-specific generators will increasingly rely on graphical languages for declarative specifications of target applications. Such languages will provide front-ends to generators and related tools to produce customized code on demand. Critical to the success of this approach will be domain-specific design wizards, tools that guide users in their selection of components for constructing particular applications. The authors present the P3 ContainerStore graphical language, its generator, and design wizard.

No abstract available.

Refactorings are behaviour-preserving program transformations that automate design-level changes in object-oriented applications. Our previous research established that many schema transformations, design patterns and hot-spot meta-patterns are automatable. This research evaluates whether refactoring technology can be transferred to the mainstream by restructuring non-trivial C++ applications. The applications that we examine were evolved manually by software engineers. We show that an equivalent evolution could be reproduced significantly faster and cheaper by applying a handful of general-purpose refactorings. In one application, over 14 K lines of code, that otherwise would have been coded by hand, were transformed automatically. Our experiments identify the benefits, limitations and topics of further research related to the transfer of refactoring technology to a production environment.

There are many reasons why one may model a domain: improved documentation, enhanced understanding of applications, etc. The author has only one motivation for domain modeling-to design product line architectures so that customized systems can be built quickly and cheaply from components. His goal is to cast and encapsulate existing artifacts, domain knowledge, and domain specific implementation techniques into software components that reflect the fundamental building blocks of domain applications. Every domain is characterized by a small set of fundamental abstractions. Each abstraction is characterized by many different realizations, which can be recognized as consistent "refinements" of the abstraction. The output of a domain analysis that the author performs is a GenVoca domain model (D. Batory et al., 1995): a list of fundamental domain abstractions; a list of refinements for each abstraction that identifies basic ways in which the abstraction can be realized; a parametric model which defines the abstractions that are imported and exported by a refinement; and rules-preconditions/postconditions-that express how refinements can be legally composed. In GenVoca terminology, abstractions correspond to realms, refinements correspond to parametrized components, and composition constraints correspond to design rules (D. Batory, 1997).

Domain-specific generators will increasingly rely on graphical specification languages-applets-for declarative specifications of target applications. Applets will provide front-ends to generators and related tools to produce customized code on demand. Critical to the success of this approach will be domain-specific design wizards, tools that guide users in their selection of components for constructing particular applications. In this paper, we present the P3 ContainerStore applet, its generator and design wizard.

The Jakarta Tool Suite (JTS) aims to reduce substantially the cost of generator development by providing domain-independent tools for creating domain-specific languages and component-based generators called GenVoca generators. JTS is a set of precompiler-compiler tools for extending industrial programming languages (e.g., Java) with domain-specific constructs. JTS is itself a GenVoca generator where precompilers for JTS-extended languages are constructed from components.

Object oriented (OO) classes are generally not reusable because they are not meaningful in isolation; most classes only have meaning as members of cooperating suites of classes (e.g., design patterns). These suites usually arise in designs, but rarely exist as encapsulated entities in OO implementations. We present a method for directly mapping cooperating suites of classes into encapsulated C++ implementations. Our method is an improvement over the VanHilst and Notkin approach (M. VanHilst and D. Notkin, 1996) for implementing collaboration based designs and constitutes a step towards more reusable (object oriented) components.

GenVoca generators synthesize software systems by composing components from reuse libraries. GenVoca components are designed to export and import standardized interfaces, and thus be plug-compatible, interchangeable, and interoperable with other components. We examine two different but important issues in software system synthesis. First, not all syntactically correct compositions of components are semantically correct. We present simple, efficient, and domain-independent algorithms for validating compositions of GenVoca components. Second, components that export and import immutable interfaces are too restrictive for software system synthesis. We show that the interfaces and bodies of GenVoca components are subjective, i.e., they mutate and enlarge upon instantiation. This mutability enables software systems with customized interfaces to be composed from components with "standardized" interfaces.

The tenet of subjectivity is that no single interface can adequately describe any object; interfaces to the same object will vary among different applications. Thus, objects with standardized interfaces seem too brittle a concept to meet the demands of a wide variety of applications. Yet, objects with standardized interfaces is a central idea in domain modeling and software generation. Standard interfaces make objects plug-compatible and interchangeable, and it is this feature that is exploited by generators to synthesize high-performance, domain-specific software systems. Interestingly, generated systems have customized interfaces that can be quite different from the interfaces of their constituent objects. In this paper, we reconcile this apparent contradiction by showing that the objects (components) in the GenVoca model of software generation are not typical software modules; their interfaces and bodies mutate upon instantiation to a "standard" that is application-dependent.

Generators synthesize software systems by composing components from reuse libraries. In general, not all syntactically correct compositions are semantically correct. We present domain independent algorithms for the GenVoca model of software generators to validate component compositions. Our work relies on attribute grammars and offers powerful debugging capabilities with explanation based error reporting. We illustrate our approach by showing how compositions are debugged by a GenVoca generator for container data structures.

From our experience, current rule-based query optimizers do not provide a very intuitive and well-defined framework to define rules and actions. To remedy this situation, we propose an extensible and structured algebraic framework called Prairie for specifying rules. Prairie facilitates rule-writing by enabling a user to write rules and actions more quickly, correctly and in an easy-to-understand and easy-to-debug manner. Query optimizers consist of three major parts: a search space, a cost model and a search strategy. The approach we take is only to develop the algebra which defines the search space and the cost model and use the Volcano optimizer-generator as our search engine. Using Prairie as a front-end we translate Prairie rules to Volcano to validate our claim that Prairie makes it easier to write rules. We describe our algebra and present experimental results which show that using a high-level framework like Prairie to design large-scale optimizers does not sacrifice efficiency.>

Article Free Access Share on Objects and domain engineering (panel) Authors: Sanjiv Gossain Cambridge Technology Partners Cambridge Technology PartnersView Profile , Don Batory University of Texas at Austin University of Texas at AustinView Profile , Hassan Gomaa George Mason University George Mason UniversityView Profile , Mitch Lubars Scientific and Engineering Software Inc. Scientific and Engineering Software Inc.View Profile , Christopher Pidgeon Cambridge Technology Partners Cambridge Technology PartnersView Profile , Ed Seidewitz NASA Goddard Space Flight Center NASA Goddard Space Flight CenterView Profile Authors Info & Claims OOPSLA '95: Proceedings of the tenth annual conference on Object-oriented programming systems, languages, and applicationsOctober 1995Pages 333–336https://doi.org/10.1145/217838.217872Published:17 October 1995Publication History 1citation274DownloadsMetricsTotal Citations1Total Downloads274Last 12 Months19Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

P2 is a scalable compiler for collection data structures. High-level abstractions insulate P2 users from data structure implementation details. By specifying a target data structure as a composition of components from a reuse library, the P2 compiler replaces abstract operations with their concrete implementations.LEAPS is a production system compiler that produces the fastest sequential executables of OPS5 rule sets. LEAPS is a hand-written, highly-tuned, performance-driven application that relies on complex data structures. Reengineering LEAPS using P2 was an acid test to evaluate P2's scalability, productivity benefits, and generated code performance.In this paper, we present some of our experimental results and experience in this reengineering exercise. We show that P2 scaled to this complex application, substantially increased productivity, and provided unexpected performance gains.

Many software libraries (e.g., the Booch C++ Components, libg++, NIHCL, COOL) provide components (classes) that implement data structures. Each component is written by hand and represents a unique combination of features (e.g. concurrency, data structure, memory allocation algorithms) that distinguishes it from other components.We argue that this way of building data structure component libraries is inherently unscalable. Libraries should not enumerate complex components with numerous features; rather, libraries should take a minimalist approach: they should provide only primitive building blocks and be accompanied by generators that can combine these blocks to yield complex custom data structures.In this paper, we describe a prototype data structure generator and the building blocks that populate its library. We also present preliminary experimental results which suggest that this approach does not compromise programmer productivity nor the run-time performance of generated data structures.

Genesis is a software system generator for database management systems that relies exclusively on as-is large scale component reuse. We review the general model of software components on which Genesis is based and discuss component libraries for relational database systems that we have implemented. We then explain how we have evolved Genesis and its libraries to be able to synthesize object-oriented database systems. We study a subproblem of creating “self-tuning” software systems by examining the performance of selected components for object-oriented database systems.

We present a model of the data structure domain that is expressed in terms of the GenVoca domain modeling concepts [7]. We show how familiar data structures can be encapsulated as realms of plug-compatible, symmetric, and reusable components, and we show how complex data structures can be formed from their composition. The target application of our research is a precompiler for specifying and generating customized data structures.

We present a domain-independent model of hierarchical software system design and construction that is based on interchangeable software components and large-scale reuse. The model unifies the conceptualizations of two independent projects, Genesis and Avoca, that are successful examples of software component/building-block technologies and domain modeling. Building-block technologies exploit large-scale reuse, rely on open architecture software, and elevate the granularity of programming to the subsystem level. Domain modeling formalizes the similarities and differences among systems of a domain. We believe our model is a blueprint for achieving software component technologies in many domains.

Summary form only given. Extensible DBMS (database management system) technology is aimed at simplifying the customization of DBMSs for specialized applications. Customization may involve the introduction of new data types and operators, support for new data languages and data models, new storage structures, and new relational operators. It is pointed out that to achieve these ambitious goals, an open system architecture is needed for database system software. One approach is to provide a toolkit which encompasses basic facilities and a supportive programming environment. Another approach is to standardize interfaces to promote the plug-compatibility, interchangeability, and reusability of modules. A third approach is to be more cautious, and provide a fixed software architecture that is amenable only to certain types of extensions. Despite differences, an underlying theme in all approaches is the software engineering of DBMSs. Prototypes are now operational which exemplify each (or combinations) of these approaches.>

The object-oriented functional data language (O/sup 2/FDL) is an interactive strongly typed database programming language that integrates the object-oriented and functional programming paradigms. It was designed for advanced applications that require a powerful and uniform database programming language supporting the software engineering principles of these tow paradigms. To this end, the O/sup 2/FDL supports inheritance and encapsulation of object-oriented languages, and an equational notation and strong typing of functional programming. Strong typing is extended with type restrictions to constrain the instantiations of type variables in function interfaces, while inheritance is augmented with a monotonic subtype rule for function redefinition. The O/sup 2/FDL also supports novel features. For the core of the O/sup 2/FDL, a denotational semantics based on an extended lambda -calculus is provided. For selected system-defined functions, operational semantics are provided and it is demonstrated that a subset of the O/sup 2/FDL is at least as expressive as the relational algebra.>

Domain analysis, a classical approach to the indentification of reusable software modules, relies on in-depth studies of existing systems, published algorithms, and structures to discern generic architectures for large classes of systems. An architecture is a template in which building-block modules can be plugged. Interfaces are standardized to make blocks interchangeable. The authors explain how domain analysis has led them to a building-blocks technology for file management systems (FMSs), and they describe their most recent prototype, an FMS synthesizer. The synthesizer enables a customized FMS to be assembled from prewritten components in minutes at virtually no cost.>

The Object-Oriented Functional Data Language (O/sup 2/FDL), an interactive, strongly typed database programming language, is discussed. It features inheritance and encapsulation of object-oriented languages and a functional notation for message expressions. The main contributions of the O/sup 2/FDL are: (1) functions of indefinite nesting levels that simplify nested list processing and form the basis of an efficient computation model; (2) path expressions that allow a flexible, graphical correspondence for database queries; (3) a type system featuring parametric and inclusion polymorphism, function restrictions, and type inferencing; and (4) system-defined functions that provide a concise and convenient notation for filtering aggregating, and combining objects. The versatility of the O/sup 2/FDL is demonstrated here for both relationally-complete expressions and more general computations.>

We propose a very simple formalism based on parameterized types and a rule-based algebra to explain the storage structures and algorithms of database management systems. Implementations of DBMSs are expressed as equations If all functions referenced in the equations have been implemented the software for a DBMS can be synthesized in minutes at little cost, in contrast to current methods where man-years of effort and hundreds of thousands of dollars are required. Our research aims to develop a DBMS counterpart to today's compiler-complier technologies

Future database systems must feature extensible data models and data languages in order to accommodate the novel data types and special-purpose operations that are required by nontraditional database applications. In this paper, we outline a functional data model and data language that are targeted for the semantic interface of GENESIS, an extensible DBMS. The model and language are generalizations of FQL [11] and DAPLEX [40], and have an implementation that fits ideally with the modularity required by extensible database technologies. We explore different implementations of functional operators and present experimental evidence that they have efficient implementations. We also explain the advantages of a functional front-end to ¬1NF databases, and show how our language and implementation are being used to process queries on both 1NF and ¬1NF relations.

A novel yet simple technology is presented that enables customized database management systems (DBMSs) to be developed rapidly. The authors are designing an extensible DBMS, called GENESIS, which is based on this theory. They give a detailed description of their first operational prototype. DBMS software components in GENESIS can be written in a few months. When all components for a target DBMS are present, writing the architecture specification of the DBMS and reconfiguring GENESIS takes a few hours and can be accomplished with negligible cost.>

This paper describes a general cost-benefit decision model that is applicable to the evaluation, comparison, and selection of alternative products with a multiplicity of features, such as complex computer systems. The application of this model is explained and illustrated using the selection of data management systems as an example. The model has the following features: (1) it is mathematically based on an extended continuous logic and a theory of complex criteria; (2) the decision-making procedure is very general yet systematic, well-structured, and quantitative; (3) the technique is based on a comprehensive cost analysis and an elaborate analysis of benefits expressed in terms of the decision maker's preferences. The decision methodology, when applied to the problem of selecting a data management system, takes into consideration the life cycle of a DMS and the objectives and goals for the new systems under evaluation. It allows the cost and preference analyses to be carried out separately using two different models. The model for preference analysis makes use of comprehensive performance (or preference) parameters and allows what we call a “logic scoring of preferences” using continuous values between zero and one, to express the degree with which candidate systems satisfy stated requirements. It aggregates preference parameters based on their relative weights and logical relationships to compute a global performance (preference) score for each system. The cost model incorporates an aggregation of costs which may be estimated over different time horizons and discounted at appropriate discount rates. A procedure to establish an overall ranking of alternative systems based on their global preference scores and global costs is also discussed.

New implementation techniques and new capabilities for database systems are being developed and proposed at a rapid rate. Novel file structures and improved algorithms for query optimization, buffer and recovery management, and transaction management have the potential of realizing significant gains in DBMS performance. The proposed integration of design objects, voice, text, rules, vector graphics, and images into databases promises exciting new capabilities for DBMSs. To accommodate advances in database technology and to support new classes of database applications, DBMSs must be extensible (i.e., customizable).

No abstract available.

Modeling the storage structures of a DBMS is a prerequisite to understanding and optimizing database performance. Previously, such modeling was very difficult because the fundamental role of conceptual-to-internal mappings in DBMS implementations went unrecognized. In this paper we present a model of physical databases, called the transformation model, that makes conceptual-to-internal mappings explicit. By exposing such mappings, we show that it is possible to model the storage architectures (i.e., the storage structures and mappings) of many commercial DBMSs in a precise, systematic, and comprehendible way. Models of the INQUIRE, ADABAS, and SYSTEM 2000 storage architectures are presented as examples of the model's utility. We believe the transformation model helps bridge the gap between physical database theory and practice. It also reveals the possibility of a technology to automate the development of physical database software.

VLSI CAD applications deal with design objects that have an interface description and an implementation description. Versions of design objects have a common interface but differ in their implementations. A molecular object is a modeling construct which enables a database entity to be represented by two sets of heterogeneous records, one set describes the object's interface and the other describes its implementation. Thus a reasonable starting point for modeling design objects is to begin with the concept of molecular objects. In this paper, we identify modeling concepts that are fundamental to capturing the semantics of VLSI CAD design objects and versions in terms of molecular objects. A provisional set of user operations on design objects, consistent with these modeling concepts, is also defined. The modeling framework that we present has been found useful for investigating physical storage techniques and change notification problems in version control.

Developing a commercial or specialized database system is an exceedingly costly and time consuming undertaking. A goal of this research is to demonstrate that a significant portion of a DBMS's software, specifically the physical database component, can be developed automatically from a small set of specifications.In this paper, we explain a new method of modeling physical databases and show that it provides a framework for realizing such a software development technology. Unlike any existing method, ours makes conceptual-to-internal mappings explicit. This enables the physical database component of operational DBMSs to be described in a systematic, precise, and simple way. Because our method also extends earlier research, it also provides a means for tieing physical database theory to practice.

A model for studying the combined problems of file design and file reorganization is presented. New modeling techniques for predicting the performance evolution of files and for finding optimal reorganization points for files are introduced. Applications of the model to hash-based and indexed-sequential files reveal important relationships between initial loading factors and reorganization frequency. A practical file design strategy, based on these relationships, is proposed.

A unifying model for the study of database performance is proposed. Applications of the model are shown to relate and extend important work concerning batched searching, transposed files, index selection, dynamic hash-based files, generalized access path structures, differential files, network databases, and multifile query processing.

An analytic method for comparing the performance of B+ trees and indexed sequential files is proposed. Preliminary results indicate that indexed sequential files may be more efficient than B+ trees in certain applications.

A transposed file is a collection of nonsequential files called subfiles. Each subfile contains selected attribute data for all records. It is shown that transposed file performance can be enhanced by using a proper strategy to process queries. Analytic cost expressions for processing conjunctive, disjunctive, and batched queries are developed and an effective heuristic for minimizing query processing costs is presented. Formulations of the problem of optimally processing queries for a particular family or transposed files are shown to be NP-complete. Query processing performance comparisons of multilist, inverted, and nonsequential files with transposed files are also considered.