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

This page is our reading of it, not a substitute for 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.

Implementation Mapping

Current Usage in Gen Ecosystem

gen-aspects (Minor influence)

Gen-aspects implements the core GenVoca insight that features are the primary composition unit. Aspects in gen-aspects ARE features in Batory’s terminology: each aspect is an incremental modification that composes with others through the module system’s merge semantics.

• Aspects as GenVoca features. The aspectType (in aspectSubmodule) realizes Batory’s feature = incremental modification. An aspect like networking is a function that, when composed with a base configuration, adds networking capability. The includes mechanism (includes = [ aspects.fonts ]) is direct feature composition — networking . fonts in GenVoca notation.
• Key classification as artifact-type polymorphism. The trifecta (class keys, collection keys, nested keys) parallels AHEAD’s polymorphic composition operator: the same aspect key is interpreted differently depending on its registered type, just as . has different semantics for different artifact types.
• Containment hierarchies. Nested aspects (non-structural, non-class keys become sub-aspects) mirror AHEAD’s recursive module containment. An aspect desktop.wayland.sway is a three-level containment hierarchy composed via the Law of Composition.
• Classes as multi-representation. AHEAD’s insight that programs have multiple representations (code, makefiles, grammars) maps to den’s class system: a single aspect produces nixos, darwin, and homeManager representations simultaneously, and feature addition updates all relevant representations.

gen-derive (Minor influence)

Gen-derive’s rule composition combinators are named after and inspired by AHEAD’s feature interaction operators, adapted to the rule dispatch domain.

• restrict combinator. Narrows a rule’s firing condition. This parallels GenVoca’s design rules that constrain legal compositions — restrict adds constraints that limit when a feature (rule) applies. Defined in gen-derive’s API as restrict extraCondition rule.
• override combinator. One rule replaces another, using the overrides field. This maps to Batory’s observation that features have multiple implementations (k1, k2) and one can replace another. override original replacement is the rule-system analogue of choosing between feature implementations.
• chain combinator. Sequential composition where A’s actions feed as context to B. This is direct GenVoca function composition (B . A), applied to the rule domain: chain { extract; } ruleA ruleB means “apply A, extract its results into context, then apply B” — step-wise development at the rule level.
• Phase DAG as design rules. Gen-derive’s phase ordering (entryAfter, entryBefore, entryBetween) parallels Batory’s design rules that constrain legal composition ordering. The topological sort of phases is the rule-system analogue of grammar-based composition ordering from Section 3.2.

Relevance to Den v2 HOAG Pipeline

Den v2’s demand-driven HOAG architecture is a direct realization of AHEAD’s vision, translated from the Java/file-system domain to the Nix/scope-graph domain.

Aspects ARE GenVoca features. Each den aspect is an incremental modification expressed as a scope graph node. Aspect composition (includes, neededBy) is feature composition. The scope graph’s I-edges are the wiring that connects features, and resolution (D < I < P specificity from Neron 2015) determines which feature’s contribution wins when multiple features provide the same declaration — the scope-graph analogue of GenVoca’s expression evaluation.

The scope graph IS the design expression. In AHEAD, a program’s design is the algebraic expression that produces it (app = i . j . f). In den v2, a host’s design is the scope graph rooted at its entity node — the tree of aspects, their I-edges, and their class emissions. The graph IS the expression; evaluation IS expression reduction. This is AHEAD’s core thesis (Section 1.2: “a program is a value; the design of a program is the expression that produces its value”) realized over graphs rather than linear compositions.

Multi-class output as multi-representation AHEAD. Den’s class system (nixos, darwin, homeManager) directly maps to AHEAD’s multi-representation model. A single aspect update modifies NixOS config, darwin config, and home-manager config simultaneously — exactly AHEAD’s “when a feature is added, any or all of the program’s representations may be updated” (Section 2.2).

Policies as design rules. Den v2’s policy system (rules dispatched via gen-derive over scope graph positions) is the constraint system that governs legal feature composition. Policies fire based on context (entity type, scope position) and produce effects (spawn, edge, drop, reroute, inject). This is Batory’s design rule checking transported into a demand-driven graph evaluation context, with gen-derive providing the dispatch substrate.

Collections as Origami dimensions. Den’s collection system (named data aggregation routed via pipes) introduces orthogonal data dimensions that cut across the aspect composition dimension. Pipe routing (pipe.from, pipe.gather, pipe.ascend) governs how collection data flows across the scope graph — a dynamic, demand-driven analogue of Origami’s matrix folding where the fold order is determined by graph structure rather than static matrix layout.

Appendix: Follow-up Work

Unexploited Ideas

Origami matrix optimization (Section 6.2, Section 7.3). The paper’s most powerful result — that Origami matrices exponentially compress product-line specifications — has no direct implementation. Den v2 composes aspects linearly through graph edges. A structured Origami decomposition could allow declaring orthogonal feature dimensions explicitly (e.g., {desktop, server} x {networking, storage, security}) with guaranteed consistent composition, rather than relying on policy rules to enforce consistency. The algebraic identity Sigma_i Sigma_j M_ij = Sigma_j Sigma_i M_ij (fold-order equivalence) could serve as a correctness invariant for multi-dimensional aspect decomposition.

Derive-compose distributivity (Section 7.3, Equation 11). The duality derive(a . b) = derive(a) . derive(b) is not exploited. In den’s context, “derive” maps to class emission (translating scope graph content into NixOS modules) and “compose” maps to aspect merging. The distributive law would guarantee that emitting modules from a composed aspect produces the same result as composing the emissions of individual aspects — a correctness property for the class-output pipeline that could be formally verified.

SAT-based design rule validation (Section 3.2.1). Batory demonstrates that feature models reduce to propositional formulas checkable by SAT solvers. Den’s constraint system (meta.guard, meta.drop, meta.substitute) is currently runtime-evaluated during scope graph traversal. A compile-time analysis that extracts the constraint graph and checks satisfiability could detect impossible configurations before evaluation begins.

Expression optimization (Section 1.2, Section 7.3). The paper’s grand vision — algebraic optimization of feature expressions, generalizing relational query optimization — is entirely unexploited. Given that den aspects form algebraic expressions (compositions of features), there may be domain-specific identities that enable optimization: dead-aspect elimination (aspects whose class output is entirely shadowed), composition reordering for evaluation efficiency, or common sub-expression sharing across entities.

Potential New Libraries or Features

gen-origami — Multi-dimensional feature decomposition. A library for declaring and validating Origami matrices over aspect sets. Scope: declare orthogonal dimensions, validate that folding in any order produces equivalent results, detect missing cells (incomplete feature interactions). Complexity: moderate — the core is matrix folding with equivalence checking. Interactions: consumes gen-aspects (aspect identity), gen-derive (dispatch for fold-order validation), gen-scope (graph positions as matrix indices).

Static constraint analysis for den. A gen-derive extension or standalone tool that extracts the constraint graph from policy rules and aspect guards, translates it to a propositional formula, and checks satisfiability. Could detect: unreachable aspects (guards never satisfied), conflicting constraints (mutual exclusion violated), and redundant policies (subsumed by more general rules). Complexity: moderate — Nix’s functionArgs introspection provides the structural information; the translation to propositional logic is straightforward for the fromFunction condition form. Interactions: gen-derive (rule introspection), gen-select (selector analysis).

Aspect-level optimization passes. A post-resolution optimization phase in den v2 that applies algebraic identities to the resolved scope graph: dead-node elimination (aspects with no class emissions and no collection contributions), redundant-edge pruning (I-edges to aspects already reachable via P-edges), and common-subgraph factoring. Complexity: moderate to high — requires defining the identity laws formally. Interactions: gen-scope (graph structure), gen-graph (reachability analysis).

Research Directions

Formal equivalence of fold orders in den’s scope graph. Batory proves Origami fold-order equivalence for matrix composition. The analogous question for scope graphs: under what conditions does the order of I-edge resolution produce equivalent class output? Neron 2015’s specificity ordering (D < I < P) provides a partial answer, but den’s policies and constraints add complexity. A formal treatment could establish when aspect composition is order-independent, strengthening correctness guarantees.

Feature interaction detection via gen-derive. Batory identifies feature interaction (Section 6.1: error compositions where structural changes are only partially propagated) as a fundamental FOP problem. Gen-derive’s rule dispatch could be extended with interaction analysis: when two rules both modify the same scope, detect whether their combined effect is consistent. This connects to Thum 2014’s analysis strategies for software product lines (cited in INDEX.md).

Algebraic cost models for scope graph evaluation. Batory’s analogy to relational query optimization suggests that scope graph evaluation could benefit from cost-based optimization. Different evaluation orders for the same scope graph may have different performance characteristics (thunk forcing patterns, memoization cache hit rates). A cost model parameterized by graph shape could guide evaluation strategy selection, connecting to Mokhov 2018’s build-systems-a-la-carte framework for analyzing demand-driven evaluation.