Batory (2005) -- Feature-Oriented Software Development with AHEAD

The paper

D. Batory, “Feature-oriented programming and the AHEAD tool suite,” vol. 26, pp. 702–703, 2004.

doi:10.5555/998675.999478

A summary of the paper and how gen uses it.

Paper Summary

Batory presents Feature-Oriented Programming (FOP) and its theoretical foundation AHEAD (Algebraic Hierarchical Equations for Application Design) as a generalization of the principles behind relational query optimization to arbitrary software domains. The paper frames its contribution against the “perpetual crisis” of software engineering, arguing that future paradigms must unify generative programming (GP), domain-specific languages (DSLs), and automatic programming (AP) — and that relational query optimization already demonstrated this unification 25 years prior.

The central thesis is that programs should be described, differentiated, and constructed in terms of features — increments in program functionality. When features are modularized as first-class design entities, program synthesis reduces to algebraic expression evaluation. A program is a value; its design is the expression that produces that value.

GenVoca (Section 2.1) is the foundational model: programs are values, program extensions (features) are functions. A multi-featured application is an equation app = i . j . f where . denotes function composition. Features have multiple possible implementations (k1, k2), and selecting the optimal one is an expression optimization problem analogous to query plan selection. Design rules (Section 3.2) constrain legal compositions using grammars augmented with attribute predicates — ultimately reducible to propositional formulas amenable to SAT solving.

AHEAD (Section 2.2) generalizes GenVoca in four ways: (1) programs have multiple representations beyond source code (UML, makefiles, grammars, performance models); (2) each representation uses its own DSL; (3) feature addition updates any or all representations simultaneously; (4) modules are containment hierarchies of related artifacts. The composition operator . is polymorphic — its meaning depends on artifact type, but its algebraic laws hold uniformly. The Law of Composition (Equation 6) defines how containment hierarchies compose: aligned elements compose recursively, unmatched elements pass through.

Origami matrices (Section 6) address a fundamental problem in FOP: features that are not truly independent must be applied in lock-step. An Origami matrix captures orthogonal feature dimensions (e.g., data structure operations x data structure variants). Matrix folding — composing rows then columns, or vice versa — yields equivalent expressions. This provides exponential compression: a k-dimensional matrix with n terms per dimension yields O(nk) specifications for O(n^k) programs. The algebraic meaning of folding is permutation of summation order across matrix dimensions (Section 6.2).

The paper also introduces the derive-compose duality (Section 7.3, Equation 11): derive(a . b) = derive(a) . derive(b), establishing that composition and derivation distribute. This enables equational representations of build processes, opening the path to makefile optimization via algebraic rewriting.

Type systems for features (Section 7.4) are identified as an open problem: how to type arbitrary artifacts and their extensions in a general mechanism. The relationship between FOP and Aspect-Oriented Programming (Section 7.5) is clarified: FOP uses function composition for aspect combination (enabling algebraic reasoning), while AOP uses precedence-based composition models that complicate reasoning.

Key Concepts

• Feature = function. A feature is an incremental modification expressed as a function mapping programs to feature-augmented programs. Composition of features is function composition, yielding algebraic expressions that represent program designs.

• GenVoca algebra. A domain model is a set of values (base programs) and functions (extensions) whose compositions define the space of synthesizable programs. Algebraic identities enable expression optimization — the generalization of relational query optimization to arbitrary domains.

• Law of Composition (Eq. 6). Hierarchical modules compose by aligning same-named sub-artifacts and composing them recursively. Unmatched artifacts pass through unchanged. This is the structural recursion that makes AHEAD work at scale.

• Polymorphic composition operator. The . operator is artifact-type-dependent: Java file composition differs from makefile composition differs from grammar composition. But the algebraic laws hold across all types.

• Design rules as propositional formulas. Feature composition constraints are expressible as grammars that reduce to propositional formulas. SAT solvers can validate and debug feature models (guidsl tool, Section 3.2.1).

• Origami matrices. Multi-dimensional feature relationships captured as matrices. Folding (summation across dimensions) produces equivalent expressions regardless of fold order, exponentially compressing product-line specifications.

• Derive-compose distributivity (Eq. 11). derive(a . b) = derive(a) . derive(b) — derivation and composition commute, enabling equational build specifications that can be algebraically optimized.

• Metamodels. Models whose instances are themselves models. Metamodel composition uses the same operator as model composition, enabling recursive model synthesis.

How gen uses this

gen-aspects

gen-aspects takes the core GenVoca idea that features are the primary unit of composition. A gen aspect is a feature in Batory’s sense: an incremental modification that composes with others through module merge semantics.

• Aspects as GenVoca features. aspectType realises feature = incremental modification. An aspect such as networking, composed with a base configuration, adds networking. The includes key (includes = [ aspects.fonts ]) is feature composition, networking . fonts in GenVoca notation.
• Key classification as a polymorphic operator. keyCategory interprets each key of an aspect by its declared category (structural, class, channel or facet). The same aspect body is composed differently depending on a key’s category, as AHEAD’s . has different semantics for different artifact types.
• Containment hierarchies. A key with no declared category becomes a nested aspect, which mirrors AHEAD’s recursive module containment. desktop.wayland.sway is a three-level hierarchy composed by the Law of Composition.
• Classes as multiple representations. AHEAD holds that a program has several representations (code, makefiles, grammars). One gen aspect produces nixos, darwin and homeManager content, and adding a feature updates every relevant representation.

gen-dispatch

gen’s terminology credits AHEAD’s feature composition with inspiring gen-dispatch’s rule combinators. The named operations are gen-dispatch’s own design.

• restrict extraCondition rule narrows when a rule fires, as GenVoca’s design rules constrain legal compositions.
• override { original; replacement; } replaces one rule with another. Batory observes that a feature can have several implementations (k1, k2) and one can replace another, and override is the rule-level analogue.
• chain extract ruleA ruleB applies A, feeds A’s actions to B as context through extract, then applies B. This is GenVoca function composition B . A at the rule level.

gen-graph

Group ordering constraints (entryAfter, entryBefore, entryBetween, entryAnywhere) and their topological order (phaseOrder) live in gen-graph. They parallel Batory’s design rules that constrain composition order, as grammar-based ordering does in Section 3.2.

A configuration as a design expression

AHEAD’s thesis is that “a program is a value; the design of a program is the expression that produces its value” (Section 1.2). In gen a host’s design is its part of the scope graph: the entity node, the aspects reached from it and their class content. Evaluating the graph reduces that expression. When several aspects provide the same declaration, scope-graph resolution decides which contribution wins, as expression evaluation does in GenVoca. A single aspect update changes NixOS, darwin and home-manager content together, which is AHEAD’s “when a feature is added, any or all of the program’s representations may be updated” (Section 2.2).

Appendix: Follow-up Work

Unexploited Ideas

Origami matrix compression (Sections 6.2, 7.3). The paper’s strongest result, that Origami matrices exponentially compress product-line specifications, has no counterpart in gen. Aspects compose linearly through graph edges. Declaring orthogonal feature dimensions explicitly, for example {desktop, server} x {networking, storage, security}, would give consistent composition by structure. The identity Sigma_i Sigma_j M_ij = Sigma_j Sigma_i M_ij (fold-order equivalence) could serve as a correctness invariant for such a decomposition.

Derive-compose distributivity (Section 7.3, Equation 11). derive(a . b) = derive(a) . derive(b) is unused. In gen, “derive” corresponds to delivering class content as modules and “compose” to aspect merging. The law would guarantee that delivering a composed aspect equals composing the deliveries of its parts, a property of the class output path that could be verified formally.

SAT-based design rule validation (Section 3.2.1). Batory reduces feature models to propositional formulas checked by a SAT solver. Aspect guards are evaluated during scope-graph traversal. Extracting the constraint graph and checking satisfiability before evaluation would detect impossible configurations early.

Expression optimisation (Sections 1.2, 7.3). The paper envisions algebraic optimisation of feature expressions, generalising relational query optimisation. Aspect compositions are algebraic expressions, so domain identities could apply: eliminating aspects whose class output is entirely shadowed, reordering compositions for evaluation cost, and sharing common sub-expressions across entities.

Potential New Libraries or Features

Multi-dimensional feature decomposition. A library for declaring and validating Origami matrices over aspect sets: declare orthogonal dimensions, check that folding in any order gives equivalent results, and detect missing cells (incomplete feature interactions). It would read aspect identity from gen-aspects and use scope-graph positions as matrix indices.

Static constraint analysis. A tool that extracts the constraint graph from rules and aspect guards, translates it to a propositional formula and checks satisfiability. It could find unreachable aspects (guards never satisfied), conflicting constraints and rules subsumed by more general ones. builtins.functionArgs gives the structural information, and translating gen-dispatch’s fromFunction conditions to propositional logic is direct.

Aspect-level optimisation passes. A pass over the resolved scope graph that applies algebraic identities: removing nodes with no class content and no channel contributions, pruning edges to aspects already reachable another way, and factoring common subgraphs. gen-graph’s reachability queries supply the analysis.

Research Directions

Fold-order equivalence over scope graphs. Batory proves fold-order equivalence for matrix composition. The analogous question for scope graphs asks when the order of import-edge resolution yields equivalent class output. Néron 2015’s specificity ordering (D < I < P) answers part of it, and rules and guards add cases. A formal treatment would establish when aspect composition is order-independent.

Feature interaction detection. Batory identifies feature interaction (Section 6.1: compositions where a structural change is only partly propagated) as a fundamental FOP problem. gen-dispatch could gain interaction analysis: when two rules modify the same scope, check that their combined effect is consistent. Thüm 2014’s analysis strategies for product lines are the related work.

Algebraic cost models. Batory’s analogy with relational query optimisation suggests cost-based choice of evaluation order for a scope graph, since orders differ in which thunks they force. A cost model parameterised by graph shape would connect to Mokhov 2018’s analysis of demand-driven build systems.