Batory, Liu & Sarvela (2003) — Refinements and Multi-Dimensional Separation of Concerns

The paper

D. Batory, J. Liu, and J. N. Sarvela, “Refinements and multi-dimensional separation of concerns,” ESEC/FSE03: Joint 9th European Software Engineering Conference 2003, pp. 48–57, 2003.

doi:10.1145/940071.940079

A summary of the paper and how gen uses it.

Paper Summary

This artifact — formerly misfiled under Tarr’s 1999 paper; corrected 2026-08-20 — is Batory, Liu, and Sarvela (2003) “Refinements and Multi-Dimensional Separation of Concerns” (ACM SIGSOFT/ESEC-FSE 2003), which builds directly on and reinterprets Tarr et al.’s (1999) original Multi-Dimensional Separation of Concerns (MDSOC) through the lens of Feature-Oriented Programming (FOP) and the AHEAD (Algebraic Hierarchical Equations for Application Design) formalism. The Tarr 1999 contribution — multi-dimensional separation of concerns (“hyperspace” is Ossher & Tarr’s later term; the word does not appear in the 1999 paper) — is the conceptual foundation that Batory 2003 operationalizes with algebraic machinery. This summary covers both.

Tarr et al. (1999) observe that traditional software decomposition privileges one dimension of modularity (typically classes or procedures) and treats all others as cross-cutting. This is the tyranny of the dominant decomposition. MDSOC proposes that modularity should be understood as a multi-dimensional space of primitive software artifacts called units, where each dimension represents a different modularization (by class, by feature, by aspect, by function). That no dimension is privileged is Batory 2003’s reading (“no preference is given to a particular dimension”, its l.58-59); Tarr 1999 itself retains the dominant decomposition and supplements it — “hyperslices are intended to encapsulate concerns in dimensions other than the dominant one” (§3.2). A program can be decomposed along any dimension, and each decomposition cross-cuts every other. The hyperspace approach — Ossher and Tarr’s implementation of MDSOC — provides composition rules that specify how units from different dimensions are integrated.

Batory 2003 connects this to step-wise refinement (SWR). In AHEAD, programs are algebraic constants and features are functions that transform programs: app = i(j(f)) synthesizes a program with features i, j, and f by functional composition. An AHEAD model is a set of constants and functions; the set of legal compositions defines a product-line. Each function (refinement) encapsulates a cross-cut — fragments of multiple classes that collectively implement one feature. Composition merges these fragments into their target classes.

The paper’s central contribution is the Origami matrix — a multi-dimensional abstraction of a one-dimensional AHEAD model. In a 2D case, rows represent one feature dimension (e.g., data structure variants: singly-linked, doubly-linked) and columns represent another (e.g., operations: insert, delete). Matrix entries are refinements. A program is synthesized by folding the matrix: composing entries along each dimension via dimensional equations. The linked list micro-example (Section 3.1) demonstrates that the four refinements {sgl, dbl, sgldel, dbldel} in the 1D model L abstract into a 2x2 matrix where rows are structure variants and columns are operations. The constraint that structural upgrades must consistently update all operations — the lock-step requirement — is enforced by the matrix structure: folding first composes columns (yielding a base program plus a consistent refinement per row), then composes rows. Invalid compositions like dbl . sgldel . sgl (doubly-linked insert with singly-linked delete) cannot be derived by folding.

The scalability theorem (Section 3.1.2) establishes the key quantitative result: given an n-dimensional matrix with k units per dimension, a program specified in the 1D model requires O(k^n) terms, while the same program specified via n dimensional equations requires only O(kn) terms. Multi-dimensional models provide exponentially more compact specifications.

Section 4 reinterprets Origami within AHEAD using the Principle of Uniformity — the assertion that all artifacts (code and non-code: UML, makefiles, performance models) can be given a class structure and refined. File types become classes with tool methods; refinements extend both the type’s structure and its tools. An Origami matrix maps to a standard AHEAD model where each row is a unit (constant or function), and a special toolset unit encodes the column-folding equations. Additional dimensions (Section 4.4) map to additional feature sets refined in lock-step — extra dimensionality requires no new AHEAD machinery.

Section 4.5 provides the definitive interpretation: MDSOC is a design abstraction process. A low-level 1D model M can express huge numbers of equations, many nonsensical. An n-dimensional model D is a higher-level view where all interesting equations derivable from M are derivable from D, but D has far fewer units, each easier to explain, compose, and constrain. D generates equations for M; it is not a replacement but an abstraction.

The macro examples — the Bali matrix (2D, 4x4, programs of ~14K LOC, Section 3.2) and the Jak matrix (3D, 8x6x8, programs of ~30K LOC, Section 3.3) — demonstrate that the same ideas scale across three orders of magnitude in program size, from 30-line list implementations to 30K-line compiler tools.

Key Concepts

• Tyranny of the dominant decomposition — Traditional software privileges one modularization dimension (classes, procedures). All other concerns cross-cut it. Batory 2003 reads MDSOC as eliminating this privilege by treating all dimensions equally; Tarr 1999’s own construct keeps the dominant dimension and adds hyperslices for the others (§3.2).

• N-dimensional concern space — Software artifacts are points in an N-dimensional space. Each dimension is a modularization: classes, features, aspects, operations, structure variants. No dimension is inherently primary.

• Origami matrix — Multi-dimensional matrix where entries are refinements, dimensions are orthogonal feature sets. Folding the matrix composes entries along each dimension to synthesize a target program. Named “origami” because the matrix is folded into progressively lower dimensionality until a single expression remains.

• Dimensional equations — One equation per dimension specifying how to fold (collapse) that dimension. Each equation is a “projection” of the target program; their intersection uniquely identifies the program to be synthesized.

• Lock-step refinement — When features along one dimension (e.g., structural variant) affect multiple features along another dimension (e.g., operations), they must be applied atomically. The matrix structure enforces this — you cannot fold a row without composing corresponding entries in all selected columns.

• Scalability theorem — O(kn) dimensional specifications vs O(k^n) flat specifications. The exponential compression makes large product-lines tractable.

• Principle of Uniformity — All artifacts can be given class structure and refined. Code, UML, makefiles, performance models — the same algebraic formalism applies uniformly. File types are classes; tools are methods; refinements extend both.

• MDSOC as abstraction of AHEAD — An n-dimensional model D is a higher-level view of a 1D model M. D generates equations for M with fewer, more comprehensible units. The space of correct D-derivable equations is a subset of M-derivable equations containing all interesting ones.

• Cross-cuts as refinement packages — A feature refinement encapsulates fragments of multiple classes that collectively implement one cross-cutting concern. Composition merges fragments into their targets. This is the FOP realization of aspect-oriented cross-cutting.

• Subjectivity — An object does not have a single interface; the interface given to it is specific to the task at hand (Harrison and Ossher 1993). In Origami, refinement F means different things to different tools, and each tool has its own interpretation of F.

How gen uses this

gen-aspects

gen-aspects realises the MDSOC model at the type level.

• Classes along one dimension. A framework registers its output targets (nixos, darwin, homeManager) as keys with category = "class" in keySemantics, the configuration passed to aspectsType. The class axis is one dimension of Tarr’s concern space, and each class is a unit along it. Adding a class extends that dimension.

• Aspects as cross-cuts. An aspect holds fragments for several classes at once. A networking aspect might contribute nixos.networking.hostName and homeManager.programs.ssh.enable, two fragments of different class outputs bound into one composable unit. This is Batory’s AHEAD refinement encapsulating a cross-cut (Section 2): one feature, implemented by fragments scattered across several classes, composed together.

• Lock-step through aspect atomicity. An aspect’s contributions to different classes are included as a unit. A configuration includes the aspect or it does not, and cannot take only the nixos fragment. This is the lock-step constraint of Origami matrices (Section 3.1.1).

• Key classification before folding. keyCategory sorts each key of an aspect into one category: structural, class, channel or facet, and a key with no declared category becomes a nested aspect. Knowing which dimension each entry belongs to before folding is the same step the matrix requires.

• deferredModule as the dimension boundary. Class content is kept as a deferredModule, a lazy constructor that can be inspected before it is forced (Lorenzen 2025). This is where content leaves the multi-dimensional aspect space and enters one class’s evaluation (NixOS evalModules, darwin evalModules). In MDSOC terms the folded matrix entry exits the concern space there.

gen-algebra

gen-algebra’s record primitives supply the algebra that folding needs.

• record.combine is left-biased combination (⊕), the composition operator of Batory’s Section 2.
• record.compose is mixin composition (Bracha 1990), M1 ⋆ M2 = fun(i) M1(M2(i) ⊕ i) ⊕ M2(i), the associative operator dimensional equations need.

Dimensions in a gen configuration

A gen configuration has at least three orthogonal dimensions: classes (the output target), entities such as hosts and users (the structural identity) and aspects (the functional concern). A single setting, such as the hostname of one host, sits at the intersection of all three. The same aspect can contribute nixos content at a host and homeManager content at a user. Plain NixOS configuration privileges the class dimension, since users write NixOS modules directly. gen places classes as one dimension among several, reached through the same aspect mechanism, which is Tarr’s point that no dimension should be privileged.

Batory 2003 defers design rules, the constraints on legal compositions (Section 2, reference [5]), to separate work. In gen, rules are the place such constraints live: gen-program turns a framework’s rule declarations into a logic program and solves it.

Appendix: Follow-up Work

Unexploited Ideas

Explicit dimensional equations (Section 3.1.2). The paper writes one equation per dimension, each naming a folding strategy. gen has no user-facing counterpart. Users declare entities and aspects, and the framework folds the concern space implicitly. An explicit per-dimension equation would let users choose folding order and strategy, for example folding the entity dimension first for fleet-scale builds or the class dimension first for debugging one host. The paper’s observation that independent refinements fold to the same result in any order could be checked as an invariant.

Subjectivity as per-consumer interpretation (Section 5). The paper inherits Harrison and Ossher’s (1993) observation that an object’s interface depends on the task. A gen aspect has one definition regardless of who consumes it. Subjectivity would let a networking aspect present firewall rules to a host, network namespace configuration to a microVM and nothing to a container. Parametric aspects ({ host, ... }: { ... }) and aspect guards cover part of this, and a guard decides inclusion without reshaping the interface.

Origami matrix views (Section 3.1.1, Tables 1-4; Section 3.2, Table 5). The paper’s matrix notation, with labelled rows and columns, refinement names in the entries and folded versions showing composed expressions, communicates a product line compactly. A matrix view of a configuration, with entity kinds on one axis, classes on another and aspect contributions in the cells, would carry that notation over.

Tool suite synthesis from file type models (Sections 4.1-4.3). The Principle of Uniformity and the file type, method and tool model (Section 4.2) describe synthesising families of tools from shared designs. The same model, where file types are classes, tools are methods and refinements extend both, could generate CI tooling, documentation generators and diagram tools from one design.

Higher-dimensional matrices (Section 3.3). The paper describes a 3D (8x6x8) Jak matrix with Frontal and Horizontal sub-matrices for feature-feature interactions. A gen configuration has three implicit dimensions (entity, class, aspect), and interactions between aspects, such as a desktop aspect that behaves differently when wayland is also included, are handled case by case through guards and includes. Encoding interactions as a separate matrix dimension, folded in lock-step with the primary ones, is a more principled approach.

Potential New Libraries or Features

Matrix introspection. Expose the implicit N-dimensional structure of a configured aspect set as an explicit matrix. Given the class keys in keySemantics (one dimension) and a set of entity kinds (another), produce a matrix whose entries are the aspect fragments contributing to each (entity kind, class) cell, for example { rows = [ ... ]; cols = [ ... ]; cells = { "host/nixos" = [ ... ]; }; }. gen-graph’s materialize could build the cell index. This serves diagnostics, visualisation and checking lock-step completeness.

Folding order control. An API that lets a consumer choose which dimension to fold first. Folding entity first produces per-host aspect bundles, folding class first produces per-class module sets across hosts, and folding aspect first produces per-aspect summaries across entities. The paper proves order does not affect the result when refinements are independent (Section 3.1, equations 4 and 5), and tests could check that invariant.

Matrix-aware attributes in gen-scope. Attributes are functions self id -> value. A dimension-aware variant, self id dimension -> value, would allow per-dimension attribute computation with cross-dimension queries. gen-select’s adapters.scope.mkContext would need dimension-aware context construction.

Subjective aspect interfaces. Harrison and Ossher’s subjectivity applied to aspects: an aspect presents different content depending on the consuming scope. Extending aspect guards from a predicate returning a boolean to one returning an interface transform would let a networking aspect expose different options to a bare-metal host, a microVM and a container. gen-dispatch rules could select transforms, and gen-select selectors could describe consumer properties.

Research Directions

Verifying dimensional independence. The O(kn) versus O(k^n) result depends on refinements along different dimensions being independent. A gen configuration assumes this without checking it, and aspects whose guards depend on entity context break it. Analysis of gen-select selectors or gen-dispatch rule conditions could flag aspects whose contributions are sensitive to composition order.

Category-theoretic folding. The paper characterises folding algebraically without a category-theoretic treatment. Formalising origami folding as a functor from the product of the dimension categories to the output category would connect MDSOC to the pushout-based rewriting of Ehrig 2006, which informs gen-dispatch’s negative application conditions. Aspect composition, graph rewriting and scope-graph resolution (Néron path-finding) might then be instances of one categorical construction.

Incremental re-folding. The dimensional structure suggests that a change affecting one dimension, such as a new operation column, needs only that dimension refolded. Recording which scope-graph attributes depend on which dimensions would give gen-memo a sharper dirty set when an aspect changes, connecting to Mokhov 2018’s build-system traces.

A fleet dimension. The paper’s examples are single programs. A fleet is many programs (hosts) with shared structure, and which hosts receive which configuration is not well modelled by Origami matrices. A fleet dimension whose entries are host-specific overrides, folded into per-host configurations, would describe the host and user entity model as a dimensional decomposition.