A Calculus of Inheritance

Abstract

Just as the $λ$-calculus is a pure functional programming language built from three primitives (abstraction, application, variable), we present inheritance-calculus, a pure declarative programming language built from three primitives (mixin, definition, reference). We introduce multi-target $\mathtt{this}$ to solve the problem that inheritance conflicts with modularity, and thereby unify object-oriented and configuration constructs: modules, classes, objects, methods, fields, and locals become a single mixin abstraction, and inheritance becomes simply set union, the deep merge of configuration languages. Consequently, composition is commutative, idempotent, and associative, structurally eliminating the multiple-inheritance linearization problem; the inheritance relation has substitutability; every path of every program can be inherited and extended; every subtree can be split into parts that, inherited together, behave as the whole; and programs have no side effects and cover every input. We call these properties modularity by construction. The calculus has no functions, yet it macro-expresses the lazy $λ$-calculus and is more macro-expressive than it in Felleisen's sense. Its semantics is first-order, denotational, and evaluated by tabling, even for cyclic inheritance hierarchies. Inheritance-calculus is distilled from MIXINv2, an implementation in which the same code acts as different function colors and ordinary arithmetic agrees with the relational semantics of logic programming.