A Calculus of Inheritance

Imagine you are building a massive, complex city using only Lego bricks.

In the world of traditional programming (the "Lambda Calculus"), the fundamental building block is a function. Think of a function as a specialized machine: you feed it raw materials (inputs), it runs a specific recipe, and spits out a product. To build complex things, you have to chain these machines together. But there's a catch: if two machines try to claim the same part of the city, or if you need to add a new feature to an existing machine without breaking it, things get messy. You often have to tear down the old machine and rebuild it from scratch.

This paper introduces a new way to build: Inheritance-Calculus.

Instead of machines, the fundamental building block here is a Record (a container of properties). Think of a record not as a machine, but as a transparent box or a layer of a cake.

Here is the core idea, broken down with simple analogies:

1. The Three Magic Tools

Just as traditional programming uses Abstraction, Application, and Variables, this new system uses three simple tools:

Record: A box that holds things (like a folder with files).
Definition: Putting a file inside a box.
Inheritance: Gluing two boxes together.

2. The Superpower: "Deep Merge" (The Cake Analogy)

In most programming languages, if you try to glue two objects together and they both have a file named config.txt, one file overwrites the other. It's like putting a new layer of cake on top of an old one; the old flavor is gone.

In Inheritance-Calculus, gluing is different. It's like deep merging.

Imagine you have a "Base Cake" with a vanilla layer.
You have a "Chocolate Cake" with a chocolate layer.
When you glue them together, you don't lose the vanilla. You get a cake that has both vanilla and chocolate layers, and if they share a "frosting" layer, the frostings mix together perfectly.

This is called Deep Merge. It means you can add new features to an existing system without ever having to delete or rewrite the old code. The new code simply "inherits" and extends the old code.

3. Solving the "Traffic Jam" (The Linearization Problem)

In object-oriented programming (like Java or Scala), if Class A inherits from B, and Class C also inherits from B, and you try to combine A and C, the computer gets confused about who "owns" the shared parts. It has to make a strict list (a "linearization") to decide who wins. This is like a traffic jam where cars are fighting for the right of way.

Inheritance-Calculus eliminates this traffic jam entirely. Because the "gluing" is commutative (order doesn't matter), associative (grouping doesn't matter), and idempotent (gluing the same thing twice doesn't break it), the system just merges everything into one big, happy pile of properties. There is no "winner" or "loser"; everything contributes.

4. The "Ghost in the Machine" (Self-Reference)

Usually, when a program refers to itself (like a function calling itself), it needs a special "magic trick" (a fixed-point combinator) to work.

In this system, self-reference is natural. Imagine a Russian Nesting Doll.

If you have a doll that says "I contain a smaller version of myself," and you glue two of these dolls together, the system doesn't panic. It realizes that "I" actually refers to both the original doll and the new one.
It resolves self-reference to multiple targets simultaneously. It's like a mirror reflecting into another mirror, but instead of an infinite loop that crashes the computer, it just creates a rich, multi-layered reflection that the system can navigate easily.

5. Why This Matters: The "Expression Problem"

There is a famous problem in computer science called the Expression Problem. It asks: How can we add new data types and new operations to a program without breaking existing code or having to rewrite everything?

Old Way: You usually have to choose. You can add new data easily, OR you can add new functions easily, but rarely both without a headache.
Inheritance-Calculus Way: Because of the "Deep Merge" magic, you can add a new file (new data) and a new file (new function) independently. When you glue them together, they automatically talk to each other. It's like adding a new room to a house and a new type of furniture; the furniture just fits into the room automatically because the house is designed to accept anything.

6. The "Color Blindness" of Functions

The paper mentions "Function Color Blindness."

In traditional programming, a function is either "synchronous" (does one thing at a time) or "asynchronous" (does things in the background). Mixing them is hard; you have to rewrite your code to handle the "color."
In this system, the code doesn't care about the color. It just defines a "slot" (a placeholder). Later, someone else can fill that slot with a synchronous version or an asynchronous version. The main code remains unchanged. It's like a universal power outlet that works whether you plug in a lamp or a toaster.

The Big Picture

The author, Bo Yang, is saying: "We don't need complex machines to build complex software. We just need transparent boxes that glue together perfectly."

By treating everything as records that merge deeply, this new "Calculus of Inheritance" makes programming:

More flexible: You can add features anytime without breaking things.
More powerful: It can do everything the old "function-based" systems can do, plus more.
Simpler: It removes the need for complex rules about who owns what, because everything is shared and merged.

It turns programming from a battle of "who wins the conflict" into a collaborative act of "building a bigger, richer structure together."

1. Problem Statement

Modern software engineering relies heavily on declarative and configuration languages (e.g., NixOS modules, Jsonnet, CUE, Dhall) that compose structured data through inheritance or merging. Despite their widespread practical success and high expressiveness (e.g., NixOS can configure entire operating systems), there is no analogous foundational computational model for declarative programming comparable to the $\lambda$ -calculus for functional programming.

Existing computational models fail to capture the unique constraints of configuration languages:

Turing Machines/RAM: Require mutable state.
$\lambda$ -calculus: Requires first-class functions.
Configuration Languages: Are inherently immutable and lack first-class functions, yet appear Turing-complete.

Furthermore, existing object-oriented and mixin-based systems suffer from the Expression Problem (difficulty in extending data types and operations simultaneously) and the linearization problem (ambiguity in method resolution order when multiple inheritance paths exist). Current systems often reject multi-path inheritance or require complex linearization algorithms (like C3) to resolve conflicts.

2. Methodology

The author proposes Inheritance-Calculus, a minimal computational model distilled from the practical implementation MIXINv2. The methodology involves:

Primitives: The calculus is built on three primitives: Record, Definition, and Inheritance. It unifies classes, methods, objects, and properties under a single "record" abstraction.
Deep Merge Semantics: Unlike shallow merging or conflict rejection, inheritance is modeled as a set union of subtrees. This makes composition inherently commutative, idempotent, and associative.
Observational Semantics: Computation is driven by an "observer" querying paths in a lazily constructed tree (a "mixin tree"). The semantics are defined by six mutually recursive, first-order set-theoretic equations:
1. properties: Aggregates labels from the current scope and all supers.
2. supers: Computes the transitive closure of inheritance chains.
3. overrides: Handles deep merging of definitions sharing the same label.
4. bases: Resolves direct inheritance references.
5. resolve: Maps syntactic references to target paths.
6. this: Handles self-reference resolution, allowing a single definition site to resolve to multiple inheritance paths (multi-path resolution).
Fixpoint Theory: The semantics are defined as the Least Fixed Point (lfp) of a monotone immediate consequence operator ( $T_P$ ), ensuring convergence for recursive programs where standard $\beta$ -reduction might diverge.

3. Key Contributions

A. Theoretical Foundations

First-Order Semantics: The calculus provides a first-order, denotational semantics for the lazy $\lambda$ -calculus. It eliminates the need for function spaces, closures, or higher-order strategies in the semantic domain, relying solely on paths and sets of paths.
Expressive Asymmetry: The paper proves that Inheritance-Calculus is strictly more expressive than the lazy $\lambda$ -calculus in Felleisen's sense. While $\lambda$ -terms can be macro-expressed into Inheritance-Calculus (via ANF translation), the reverse is impossible. Inheritance-Calculus allows "open extension," where new observable projections can be added to existing definitions without modification.
Böhm Tree Equivalence: The translation from $\lambda$ -calculus to Inheritance-Calculus preserves Böhm tree equivalence. Notably, some $\lambda$ -terms that diverge under $\beta$ -reduction converge under the lfp( $T_P$ ) semantics of Inheritance-Calculus.

B. Solving the Expression Problem

Immunity to Non-Extensibility: The calculus is structurally immune to the Expression Problem. New operations and data types can be added via separate files (mixins) and composed via inheritance without modifying existing code.
Relational Semantics: The calculus naturally produces the relational semantics of logic programming. Operations on Church-encoded values (tries) automatically distribute over sets, turning arithmetic operations into Cartesian products (e.g., adding $\{1, 2\}$ to $\{3, 4\}$ yields $\{4, 5, 6\}$ ).

C. Practical Implications

Function Color Blindness: The same code can run under different execution models (synchronous vs. asynchronous) because the "color" of the function (effect) is determined at assembly time via inheritance, not at the calculus level.
Multi-Path Self-Reference: The calculus resolves self-references to multiple targets simultaneously, a feature rejected by systems like Scala (DOT calculus) and the NixOS module system, which assume single-valued self-resolution.

4. Results

Implementation: The theory is implemented in MIXINv2 (Python), which includes a test suite covering all examples, including boolean logic, natural number arithmetic, and a web application.
Case Study (Nat Arithmetic): The paper demonstrates that boolean logic and arithmetic can be implemented as separate files and composed without modification. The system handles the "visitor pattern" for equality checking and automatically extends return types (e.g., a Plus operation returns values that also possess Equal properties) without boilerplate.
Datalog Encoding: The paper provides a systematic encoding of Datalog into Inheritance-Calculus, proving that the calculus natively supports recursive query processing and least fixed-point semantics without external engines.
Termination: The evaluation strategy uses tabled evaluation (memoization) to compute the least fixed point, ensuring soundness even in the presence of cyclic dependencies.

5. Significance

Unification of Paradigms: It bridges the gap between functional programming (via $\lambda$ -calculus embedding) and declarative configuration, showing that inheritance is a more fundamental primitive than function application.
Elimination of Linearization: By making inheritance commutative and idempotent, it structurally eliminates the need for complex linearization algorithms (like C3) and conflict resolution strategies found in OOP.
New Computational Model: It establishes a new Turing-complete model that is immutable, function-free, and first-order, filling the "empty cell" in the table of computational models.
Practical Impact: The findings explain why systems like NixOS are so expressive and provide a theoretical basis for building next-generation configuration languages and modular software architectures that are inherently extensible and immune to the Expression Problem.

In conclusion, Inheritance-Calculus reframes inheritance not as a mechanism for code reuse or object hierarchy, but as a fundamental computational primitive capable of expressing logic, arithmetic, and control flow through set-theoretic operations on record trees.