FOP Theory and Software Plans
From SEWiki
Software plans is an approach for separating concerns that are tangled together within modules. Previous approaches to separating such tangled concerns employ language abstractions such as functions, classes, or aspects. In contrast, software plans achieves separation of concerns through the use of a concern-enhanced code representation and associated plan-aware source code editor. Software plans can thus be used to separate concerns at a fine-grained level without the use of new programming languages. More information on software plans can be found elsewhere.
To date our understanding of concerns (e.g. features) and their relationships has been informal. This evolving understanding has been reflected in our prototypes, which initially employed manual then automatic tagging of code with concerns, and an early separation of the concern and plan concepts which are now unified. We lack a rigorous theory of concern interactions that can help guide our development of the software plans concept and associated tools. For example, we currently do not have a full understanding of plan refactoring operations.
This document investigates Liu and Batory's theory for feature-oriented programming (FOP) as a possible formal basis for software plans. This discussion is based on two papers, "Feature-Oriented Refactoring of Legacy Applications" by Liu, Batory, and Lengauer, and "Modeling Interactions in Feature Oriented Software Designs" by Liu, Batory and Nedunuri.
It should be noted that this is not the only candidate theory. Concept lattices may also be a good starting point for developing a theory as well. Meghan Revelle's work has shown a strong relationship between concepts and concerns, and between the concept lattice structure and the inheritance structure of software plans.
We present our informal model of concern interactions in the context of software plans and our prototype editor, Spotlight. We then present a summary of Liu and Batory's theory, then draw parallels between the two.
An Informal Theory of Software Plans
We can characterize the relationships between concerns in two dimensions. First, concern A depends upon concern B if the implementation of concern A requires the implementation of concern B. A dependence relationship imposes an ordering on the implementation of the concerns, and usually indicates that the implementation of A extends and refines the implementation of B.
One consequence of this characterization of dependence is that two concerns can be independent of each other even though they may be implemented in terms of a third, shared concern. In this case we say that the two concerns depend not on each other, but rather on the shared concern.
A second type of concern interaction is interference. For two independent concerns A and B, concern A interferes with concern B if the presence of concern A prevents the correct operation of concern B. The severity of the interference can range from the conflicting use of a shared variable to conflicts in architectural assumptions.
The degree of interference indicates the difficulty with which the two independently developed concerns can be integrated. For example, some integration conflicts can be resolved by simply changing the order of code that implements the concerns, while other conflicts require wholesale re-engineering of the separately implemented concerns. In order for two interfering concerns to coexist in the same program, they must be reconciled.
Spotlight implements these notions of in terms of multiple plans, each of which implements a concern of interest. A plan contains the implementation of the plan's concern, as well as any code inherited from zero or more parent plans. Concern dependencies are modeled with the plan parents relation. That is if concern A depends on concern B, then the plan for A will have plan B as a parent.
The image to the right shows a plan being edited in Spotlight. Practically speaking, the user edits code in much the same way that they always have. Multiple plans are represented as tabs, and normal editing operations modify the view in the expected ways.
Spotlight treats the addition of a new feature the same way that it treats integration of multiple features. In the former case, a new plan derives from one or more dependent parent plans and adds new code for the new feature. In the latter case, the new plan derives from multiple plans and modifies them to reconcile any interference. The same plan inheritance mechanism is used in both cases. We've found that modifications (e.g. deletions) are uncommon.
To help the user integrate plans, Spotlight employs an ordering heuristic for code fragments. For plans that have a dependency relationship, the integration of the plans' concerns is specified by the user when he or she edits the derived plan. But for independent plans, the ordering of fragments specific to the plans is not defined. Our heuristic is similar to a topological sort of the code fragments, except that we employ cycle breaking and attempt to prevent interleaving code from independent plans.
A Summary of FOP Theory
FOP theory is influenced by Batory's work on product lines and generative programming. The focus is on behavioral concerns, i.e. features, and the design of a system that allows them to be composed in arbitrary combinations to create reduced-feature variants of the all-feature system.
Features are viewed as functions on programs that change the input code into the output code, adding the feature. So F(G(B)) means add feature G to B, then add feature F to the previous result.
The theory has four primary elements: features (represented as upper-case letters like "J"), feature specific code (represented as lower-case letters like "j" for feature J), changes with respect to features (∂/∂H or ∂2/∂H∂J), disjoint union of methods ("+"), and method modification by application of changes (∂h/∂J • h).
The theory has a calculus that mostly is what one would expect. "•" distributes over "+". ∂x/∂H•y=y (i.e. changes to x for feature H when applied to module y do nothing to module y). A fundamental formula regarding the extension of base code b to implement H is H(b) = h + ∂b/∂H•b.
∂b/∂H represents a change in code b needed for feature H. FOP theory works at the smallest level of a method, so these derivatives are expressed in terms of adding code before or after the original method, or by replacing the original method. "•" is a simple weave process where the derivative code is injected around the original method implementation. "+" adds new methods and classes.
Replacing a method in a derivative is probably not wise, since it breaks compositionality. Second derivatives involve changes that need to be made to changes, so presumably you could replace a method if you were willing to deal with potentially lots of second derivatives. Third derivatives are not mentioned. (They say that second derivatives are rare in practice.)
FOP equations provide a linear order of implementation of features in terms of previous features. Choosing a good order is important, since it can cause more and more substantial derivatives to appear. Although the authors don't discuss this, it seems that a bad ordering of interacting features would be similar to needing to refactor a codebase when features are implemented in a suboptimal ordering. For cases when features do not interact, the derivatives will be no-ops, and the order doesn't matter.
Application of FOP Theory to Software Plans
First we consider the notions of concern dependence and interference in FOP theory. Dependence is not explicitly represented in FOP theory, although presumably one would choose an ordering of feature applications in the feature equation such that the size of derivatives is minimized. For example, assuming that feature F depends on feature G, then F(G(B)) would have a smaller ∂G/∂F implementation than ∂F/∂G would have in in G(F(B)). Presumably in a product line context the feature designer would have placed a total ordering on the feature set based on feature dependence, and implemented only the first-order derivatives that will be needed for the particular sequence of feature compositions.
Concern interference in FOP theory is fairly straightforward. If feature F interferes with feature G, then one or both of the first and second order derivatives will be non-empty. In principle both ∂F/∂G and ∂G/∂F would be there, but in practice only one is necessary as per the previous discussion.
Like our approach (and unlike AOP), FOP theory operates on concrete instances. There is no quantification over all classes, methods, callstacks, etc. The method refinement is based on simple around advice. Similar to Murphy's AOP refactoring experience, Liu and Batory note that methods have to be restructured to be automatically tangled using this mechanism. Software plans, on the other hand, leaves tangling in the hands of the programmer. It therefore supports a finer level of granularity for concerns (characters), and supports heuristics to help the programmer compose features. We support deletions (although our support could be improved). In one paper they said that wise refactoring requires foresight regarding which features might be in the final system.
Rather than separate a feature into feature-specific and other-feature-modifying code, we unify the two in the derived plan. That is, the expression in FOP theory H(B) = b + h + ∂b/∂H•b represents the addition of feature H to base code B. In the equation, the code can be partitioned into the base code b, the feature-specific code h, and the changes required by H on b. We could have the programmer first implement b, then implement a derived plan containing the code for the latter two terms in the equation. Second derivative code can also appear in derived plans, but more often appears in "reconciliation plans" that merge two or more features.
Our interface is arguably more natural to the programmer. Programmers need not learn to separate feature code into zero-, first- and second-order derivatives, and express them in a new syntax. Our plans do not have non-local references to code specific to other features. As a result, our approach seems more suitable for the average programmer rather than for the "feature designer". Our approach also seems to require less planning, perhaps making it more suitable for forward engineering of novel software systems.
Our recent work on reverse engineering software plans using execution profiles and FCA seems to require less manual work then their approach. In their approach, the programmer must find the closure of feature-specific code using Robillard-like concern identification techniques. Our approach takes coverage information and uses FCA to infer concern relations.
Our work to date has focused on new code development, where features are added to a specific implementation in a specific order. FOP theory seems to be most applicable when one is manipulating an existing program's features. Refactoring, reverse-engineering, and program generation seem to be where FOP theory can be applied most usefully to software plans. For example, if we can automatically infer the derivative code from the edits made in a derived plan, then we may be able to automatically and safely remove features (and related derivative code) from the all-concerns plan. Similarly, tracking derivative code may make plan refactoring easier.
For our part, software plans and the Spotlight editor could be a visualization tool for FOP equations. With some enhancements we could possibly automatically generate the derivative fragments that they use in their code synthesizer. Our model also merges the derivative and feature-specific code, which seems to be simpler for from-scratch development.
