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

A summary of the paper and how gen uses 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.

How gen uses this

gen-algebra (lib/rec.nix)

The most direct implementation. gen-algebra’s record algebra realises Bracha’s constructs over labelled records.

• record.combine { left; right; } is the base combination operator ⊕. It is left-biased: left’s values shadow right’s. This is Section 2.1’s record combination.

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

• record.mixinBeta prefix suffix is Beta-direction inheritance with inner empty: the prefix (parent) has priority and the suffix is subordinate. This is the inverted formula from Section 2.2.

• record.compose m1 m2 is the mixin composition operator ⋆, fun(i) m1(m2(i) + i) + m2(i) from Section 4. It returns a new mixin, a function from the inner parameter to a record, so compositions chain and stay associative.

• Scoped labels. The shadow-stack representation of records comes from Leijen 2005. combine on records with duplicate labels follows Bracha’s left bias, and the stack keeps the shadowed value so restrict can expose it again, which is Leijen’s contribution.

gen-schema (lib/mixin.nix)

gen-schema lifts Bracha’s algebra to kind definitions.

• mkMixin { requires ? [ ]; provides ? [ ]; } define creates a first-class mixin with an explicit interface: the options come first, as one closed set, and define last. requires lists the labels the mixin expects on its parent, as a partial mixin references undefined fields. provides lists the labels it contributes. define receives the parent record and returns new fields, which is Bracha’s parametric delta.

• composeMixins [ m1 m2 m3 ] composes a chain with record.compose. It tracks requires and provides across the chain, so an earlier mixin’s provides satisfies a later mixin’s requires. Bracha’s Modula-3 sketch leaves this compatibility to static typing.

• beta mixin marks a mixin for Beta-direction application. composeMixins then gives priority to what came before it, the parent or prefix side. This is the direction switch of Section 2.3 on the same composition machinery.

• applyMixin applies a mixin to one kind’s record. It checks the requires list against the record, respects the mixin’s direction and returns the extended record. This is where a partial mixin becomes part of a complete kind definition.

• Kind inheritance with inherits. A kind definition can declare inherits = [ "user" ], and evalSchema resolves each parent by name in a strictly earlier pass and imports the parent’s module into the child. The module system’s merge composes them. Naming the parent is Bracha’s explicit ordering: the composition chain is stated, never discovered from the tree being declared.

Schema extension in a framework

In a framework built on gen, independent modules contribute fragments to one kind’s schema, such as a host kind. Each fragment is a Bracha delta, and the module system’s deferred-module merge is the composition operator. Because that composition is associative, the order in which fragments arrive does not change the merged kind, apart from explicit priorities such as mkForce and mkDefault.

Appendix: Follow-up Work

Unexploited Ideas

Commutativity under commutative combination (Section 4). If the base combination operator is commutative as well as associative, mixin composition is commutative too. gen-algebra and gen-schema do not use this. Where merge order does not matter (set union for tags, commutative monoid aggregation), enforcing commutativity would allow unordered composition with guaranteed determinism. composeMixins is order-dependent even when the underlying merge is commutative.

Complete and partial mixins (Section 4). The paper separates complete mixins (instantiable) from partial ones (composition-only). mkMixin does not track the distinction, and every mixin is partial until applied to a kind. A completeness check could catch a mixin that is never composed into a complete kind, at schema definition time instead of at instance creation.

The Modula-3 super clause as an interface declaration (Section 5.3). The super clause declares the expected interface of overridden methods, so a mixin can be type-checked before composition. gen-schema’s requires checks field presence only. The paper’s approach checks signatures and would catch type mismatches between a mixin’s expectations and its parent.

Mixin procedures (Section 5.3.1). The paper’s mixin procedure form tags procedures that reference super so they can only be invoked as methods, hiding a mixin instance’s overridden methods from outside code. gen-schema does not enforce this. A mixin’s define can return any attrset, and outside code can reach shadowed fields through record.restrict.

Potential New Libraries or Features

record.composeCommutative in gen-algebra. A variant of record.compose that checks commutativity of the base merge per label and fails when composition order would change the result.

A mixin completeness check in gen-schema. A predicate that checks whether a mixin or composed chain defines every field it references and does not use its parent parameter, by following requires across the chain. A kind with unsatisfied requirements could warn when instances are created.

Typed requires in gen-schema. Extend mkMixin’s requires from field names to name and type pairs, so applyMixin checks type compatibility against the kind’s option declarations as well as presence.

Mixin-aware binding in gen-bind. gen-bind injects values into NixOS modules and layers binding sets with composeWith. A binding mixin would be a function from the previous bindings to extended bindings, with super access to the earlier layer, which states composeWith as mixin composition. gen-bind’s bind-wins and system-wins merge strategies correspond to Smalltalk and Beta direction.

Research Directions

Mixin composition in attribute grammars. gen-scope evaluates demand-driven attributes over scope graphs, and attribute definitions from different aspects are merged by the consumer before evaluation. Treating attribute composition as mixin composition, where each aspect contributes a delta over the attribute set with super access to the previous definitions, would give principled resolution of attribute name collisions. Associativity would guarantee that aspect order within a priority tier does not affect evaluation.

Scope-graph linearisation. Bracha replaces linearisation with explicit ordering. A scope graph already orders declarations through resolution specificity (D < I < P). Whether that order satisfies Bracha’s associativity requirements is open. If it does, it gives an automatic linearisation that respects encapsulation, and it is local, since each node resolves independently, where CLOS linearisation is global.

Typed composition of NixOS modules. The NixOS module system merges untyped definitions and checks types at evaluation time. Bracha’s typing rules for mixins suggest validating module compositions at definition time. gen-schema’s refinements (after Findler 2002) and gen-types’ validators provide the predicates. Combined with Bracha’s interface declarations they could detect incompatible module compositions before evalModules forces them.