Bracha & Cook (1990) — Mixin-based Inheritance

The paper

G. Bracha and W. R. Cook, “Mixin-based inheritance,” OOPSLA/ECOOP ‘90: Object-oriented programming systems, languages, and applications, pp. 303–311, 1990.

doi:10.1145/97945.97982

This page is our reading of it, not a substitute for it.

Paper Summary

Bracha and Cook address a fundamental problem in object-oriented language design: the inheritance mechanisms of Smalltalk, Beta, and CLOS appear radically different, yet share a common algebraic substrate. The paper’s contribution is identifying this substrate and using it to derive a generalized inheritance model based on explicit mixin composition.

The paper begins by formalizing single inheritance in Smalltalk and Beta. Objects are represented as records whose fields contain methods. Record combination is a binary operator, written as a circled-plus, that forms a new record from two arguments with left-biased conflict resolution: {a -> 3, b -> 'x'} + {a -> true, c -> 8} yields {a -> 3, b -> 'x', c -> 8}. Inheritance is then an asymmetric combination of a parametric delta and a parent specification. In Smalltalk, the subclass formula is C = delta(P) + P — the delta (set of changes) receives the parent’s methods for super dispatch, and the combined result favors the delta’s definitions. In Beta, the formula inverts: C'(inner) = P'(delta'(inner) + inner) + delta'(inner) — the prefix (superpattern) controls behavior and may invoke inner to delegate to extensions. Both reduce to a single non-associative binary operator: delta triangle P = delta(P) + P, where the left operand has priority. Smalltalk places the child on the left (child overrides parent); Beta places the parent on the left (parent controls child). Section 2.3 and Figure 1 make this inversion explicit: the Smalltalk subclass/superclass relationship is analogous to the Beta superpattern/subpattern relationship.

Section 3 analyzes CLOS multiple inheritance. CLOS linearizes an ancestor graph so each ancestor appears once, then iterates the single-inheritance operator over the linearized list: C = delta_1 triangle (delta_2 triangle (... triangle (delta_n triangle empty))). Linearization has been criticized (Snyder 1986, 1987) for violating encapsulation — it can change parent-child relationships unpredictably. However, Bracha and Cook argue that linearization is really an implementation technique for mixins (abstract subclasses parameterized by their parent), and that making mixins explicit eliminates the encapsulation problem.

Section 4 presents the central contribution: the mixin composition operator. Rather than classes, mixins become the primary definitional construct. The composition formula is:

M1 * M2 = fun(i) M1(M2(i) + i) + M2(i)

In M1 * M2: M1’s super/inner is bound to M2; M2’s super/inner is bound to the formal parameter i of the result (allowing further composition). Assuming the base combination operator is associative, the star operator is also associative. This associativity is the key algebraic property — it means mixin chains can be regrouped without changing semantics, enabling modular reuse. Ordinary classes are degenerate mixins that ignore their parent parameter. A mixin is “complete” if it neither refers to its parent parameter nor leaves undefined fields; only complete mixins can be meaningfully instantiated.

Section 5 demonstrates a concrete extension to Modula-3 with mixin types, a super clause for declaring overridden method signatures, and static typing rules. The subtyping relation reflects associativity: if T1 = T2 * T3, then T1 is a subtype of both T2 and T3. The section establishes that all typing rules can be statically enforced — a necessary condition for safety and efficient implementation. This was the first treatment of mixin typing in a strongly-typed language.

The paper does not prove its theorems in formal detail — associativity of the star operator is stated as following from associativity of the base combination operator, and the typing rules are presented without a full soundness proof. These were subsequently addressed in Bracha’s dissertation (1992) and later work by Flatt, Krishnamurthi, and Felleisen on mixins in class-based languages.

Key Concepts

• Record combination operator — Left-biased binary merge of method records. The foundation for all three inheritance models. Associative when field values are independent of record structure.

• Delta/parent decomposition — Every inheritance step decomposes into a parametric delta (the new/modified methods, parameterized by what they override) and a parent specification. The delta-triangle-parent operator performs application of super/inner and combination in one step.

• Smalltalk vs. Beta as inverse directions — Smalltalk: child on left (delta overrides parent). Beta: parent on left (prefix controls suffix). Same operator, opposite operand order. Neither direction subsumes the other.

• Mixins as abstract subclasses — A mixin is a class definition parameterized by its parent. In CLOS, mixins rely on linearization to bind their parent; the paper makes this binding explicit via composition.

• Mixin composition formula — M1 * M2 = fun(i) M1(M2(i) + i) + M2(i). Left-biased: M1 has priority. Associative. Produces a new mixin, not a class — enabling arbitrary-length composition chains.

• Associativity of composition — Permits regrouping: (A * B) * C = A * (B * C). Enables defining reusable sub-chains without affecting semantics when composed into larger chains.

• Complete vs. partial mixins — A mixin is complete when it defines all fields it references and does not use its parent parameter. Only complete mixins are instantiable. Partial mixins are composition building blocks.

• Explicit linearization — Rather than implicit graph linearization (CLOS), the programmer explicitly specifies the composition order. This preserves encapsulation — no hidden reordering of parent-child relationships.

• Static typing for mixins — Subtyping via composition: T1 = T2 * T3 implies T1 <: T2 and T1 <: T3. Associativity reflected in the type system. super clause declares expected interface.

Implementation Mapping

Current Usage in Gen Ecosystem

gen-algebra (pure/rec.nix)

The most direct implementation. gen-algebra’s record algebra realizes Bracha’s constructs with Nix attrsets:

• record.combine a b — The base combination operator (circled-plus). Left-biased merge: a’s values shadow b’s. Maps to Section 2.1’s record combination.

• record.mixin delta parent — Smalltalk-direction inheritance: combine (delta parent) parent. The delta receives the parent record and can reference its fields (the super parameter), then the result is combined left-biased with the parent. Directly implements the formula C = delta(P) + P from Section 2.1.

• record.mixinBeta prefix suffix — Beta-direction inheritance: the prefix (parent) controls, the suffix (extension) is subordinate. Implements the inverted formula from Section 2.2 where the prefix has priority.

• record.compose m1 m2 — The mixin composition operator (star). Implements fun(i) m1(m2(i) + i) + m2(i) from Section 4. Returns a new mixin (function from inner parameter to record), preserving the associativity property. This is the paper’s central formula realized as a Nix function.

• Scoped labels via shadow stacks — While the shadow stack representation comes from Leijen 2005, the stacking behavior interacts with Bracha’s combination operator: combine on records with duplicate labels follows left-biased semantics per Bracha, while the stack preserves the shadowed value for potential restriction (Leijen’s contribution).

gen-schema (nix/lib/mixin.nix)

gen-schema lifts Bracha’s algebra to the schema/type level, applying mixin composition to kind definitions:

• schema.mkMixin { requires, provides, define } — Creates a first-class mixin with explicit interface declarations. The requires field lists labels the mixin expects on the parent record (analogous to Bracha’s partial mixin that references undefined fields). The provides field lists labels the mixin contributes. The define function receives a record-algebra record (the parent) and returns new fields — this is precisely Bracha’s parametric delta. Structural validation of requires against the target record implements the paper’s completeness check: composition fails if required fields are absent.

• schema.composeMixins [ m1 m2 m3 ] — Composes a chain of mixins. The requires/provides propagation across the chain ensures structural compatibility: earlier mixins’ provides can satisfy later mixins’ requires. This realizes Bracha’s associative composition chains with an added structural safety layer that the paper’s Modula-3 sketch handles via static typing but leaves to the type checker.

• schema.beta mixin — Annotates a mixin for Beta-direction application. When composeMixins encounters a beta-annotated mixin, it reverses priority so existing fields (the parent/prefix) take precedence over the mixin’s contributions. This is the direction switch from Section 2.3 — the same composition machinery, but the parent is on the priority side rather than the delta.

• schema.applyMixin mixin kindRecord kindName — Applies a single mixin to a concrete kind’s record-algebra record. Validates structural compatibility (the requires check), respects Smalltalk/Beta direction annotation, and produces the extended record. This is the point where a partial mixin becomes part of a complete kind definition.

• Kind mix-ins via imports — gen-schema’s imports = [ config.schema.user ] on a kind definition is a higher-level realization of Bracha’s mixin composition. Each kind definition is a deferred module (a delta); importing another kind composes them via the NixOS module system’s merge, which is itself left-biased (later definitions override earlier ones via priority). The sidecar merge of collections alongside module merge follows the paper’s combination-plus-application pattern.

Relevance to Den v2 HOAG Pipeline

Den v2 uses a demand-driven Higher-Order Attribute Grammar over scope graphs. Mixin composition enters at several points:

Schema kind extension. Independent modules (aspects, policies, user configuration) contribute kind fragments to den.schema.host, den.schema.user, etc. These fragments are exactly Bracha’s deltas — parametric modifications that compose associatively. The NixOS module system’s deferred module merge is the composition operator. Because composition is associative, the order of flake input evaluation does not affect the merged kind definition (modulo explicit priority overrides via mkForce/mkDefault).

Aspect composition. Aspects in den v2 are scope graph nodes whose content is classified into classes (output targets), collections (data aggregation), and nested sub-aspects. When multiple aspects contribute to the same class output (e.g., both networking and firewall aspects emit nixos modules), the class collector performs left-biased combination — the aspect with higher scope-graph specificity (D < I < P, per Neron 2015) shadows the other, paralleling Bracha’s priority in the combination operator.

Collection merging. Den’s named collections (declared via den.collections) aggregate contributions from multiple scopes using merge strategies (list ++, attrset //, custom). The collection merge is an instantiation of Bracha’s combination operator generalized beyond method records to arbitrary data types. The merge strategy parameter corresponds to choosing the semantics of the circled-plus operator for each collection.

Policy-driven extension. Policies in den v2 are rules (gen-derive) that fire based on scope context and produce effects (routes, includes, provides). When a policy fires, it composes new content into the scope — this is dynamic mixin application. The policy’s output is a delta; the scope’s existing content is the parent; composition follows Bracha’s formula with the policy’s contribution having priority (Smalltalk direction, since the policy is specializing the generic scope).

Appendix: Follow-up Work

Unexploited Ideas

Commutativity under commutative combination (Section 4). The paper notes that if the base combination operator were commutative (not just associative), the mixin composition operator would also be commutative. Neither gen-algebra nor gen-schema exploit this. For collections where merge order genuinely does not matter (e.g., set union for tags, commutative monoid aggregation), enforcing commutativity could enable parallel/unordered composition with guaranteed determinism. Currently, gen-schema’s composeMixins is order-dependent even when the underlying merge strategy is commutative.

Complete vs. partial mixin classification (Section 4). The paper distinguishes complete mixins (instantiable) from partial mixins (composition-only). gen-schema’s mkMixin does not track this distinction — all mixins are partial until applied to a kind. A completeness check could catch orphan mixins that are never composed into a complete kind, providing earlier error detection at schema definition time rather than at instance creation time.

Modula-3 super clause as interface declaration (Section 5.3). The super clause in Bracha’s Modula-3 extension declares the expected interface of overridden methods, enabling static type checking of mixins in isolation (before composition). gen-schema’s requires field approximates this but only checks field presence, not type compatibility. The paper’s approach validates method signatures (parameter types, return types), which would catch type mismatches between a mixin’s expectations and the actual parent.

Mixin-procedure distinction (Section 5.3.1). The paper introduces mixin procedure as a distinct callable form — procedures that reference super are tagged and can only be invoked as methods, preventing the overridden methods of a mixin instance from being accessed externally. This encapsulation property is not enforced in gen-schema. A mixin’s define function can produce any attrset, and nothing prevents external code from reaching into the parent record’s shadowed fields via record.restrict.

Potential New Libraries or Features

gen-algebra: record.composeCommutative — A variant of record.compose that asserts commutativity of the base merge for each label. Scope: small addition to pure/rec.nix. Would take a commutativity witness (or check) per label and throw if composition order would change the result. Useful for den collections with commutative merge strategies.

gen-schema: mixin completeness checker — A schema.isComplete predicate that checks whether a mixin (or composed chain) defines all fields it references and does not use its parent parameter. Scope: moderate, requires tracking the requires closure across composition chains. Interactions: gen-schema’s mkSchemaEntryType could warn when a kind with unsatisfied requires has instances created.

gen-schema: typed requires — Extend mkMixin’s requires from field names to field name + type pairs. applyMixin would validate not just presence but type compatibility against the target kind’s option declarations. Scope: moderate, requires accessing the kind’s option types during mixin application. Interactions: builds on gen-schema’s existing _kindMeta introspection and gen-algebra’s validation pipeline.

gen-bind: mixin-aware wrapping — gen-bind injects external values into NixOS modules. A mixin-aware variant could compose binding sets using Bracha’s formula: a “binding mixin” would be a function from parent bindings to extended bindings, with super access to see what the previous binding layer provided. This would formalize gen-bind’s current composeWith as explicit mixin composition. Scope: small-medium. Interactions: gen-bind’s existing merge strategies (bind-wins, system-wins) map to Smalltalk/Beta direction.

Research Directions

Mixin composition in attribute grammars. gen-scope evaluates demand-driven attributes over scope graphs. Attribute definitions from different aspects are currently merged by the consumer (den) before being passed to eval. Formalizing attribute composition as mixin composition — where each aspect contributes a delta over the attribute set, with super access to the previous aspect’s attribute definitions — would give principled conflict resolution for attribute name collisions. The associativity property would guarantee that aspect ordering within a priority tier does not affect evaluation.

Scope-graph-aware linearization. Bracha’s paper eliminates linearization in favor of explicit ordering. However, den v2’s scope graph already provides a natural linearization via resolution specificity (D < I < P). Investigating whether scope-graph resolution order satisfies Bracha’s associativity requirements could yield a principled automatic linearization that respects encapsulation — unlike CLOS linearization, scope-graph resolution is local (each node resolves independently) rather than global.

Typed mixin composition for NixOS modules. The NixOS module system performs untyped merge — type checking happens at evaluation time, not at composition time. Bracha’s static typing rules for mixins suggest a path toward compile-time (or at least definition-time) validation of module compositions. gen-schema’s refinement contracts (Findler 2002) and gen-algebra’s validators provide the predicate infrastructure; combining these with Bracha’s interface declarations could detect incompatible module compositions before evalModules forces evaluation.