Search papers, labs, and topics across Lattice.
The paper introduces Overlay-Calculus, a novel calculus for declarative programming built on record, definition, and inheritance primitives, analogous to the lambda calculus for functional programming. It demonstrates that Overlay-Calculus trivially embeds the lambda calculus while relying only on naive set theory, leading to inherent commutativity, idempotence, and associativity of constructs, thus circumventing linearization problems in multiple inheritance. The calculus induces a fully abstract semantics of the lazy lambda-calculus with respect to Böhm tree equivalence and exhibits emergent properties such as dissolving the Expression Problem and enabling CPS-agnostic programs.
Forget linearization headaches: a new calculus built on naive set theory makes multiple inheritance commutative, idempotent, and associative by design.
Just as the $\lambda$-calculus uses three primitives (abstraction, application, variable) as the foundation of functional programming, Overlay-Calculus uses three primitives (record, definition, inheritance) as the foundation of declarative programming. It trivially embeds the $\lambda$-calculus, although the entire semantics builds on only naive set theory; as a consequence, all constructs including inheritance are inherently commutative, idempotent, and associative; the linearization problem of multiple inheritance simply does not arise. This induces a fully abstract semantics of the lazy $\lambda$-calculus with respect to B\"ohm tree equivalence. Overlay-Calculus is distilled from the Overlay language, a practical implementation in which we observed further emergent phenomena: the Expression Problem dissolves, programs are CPS-agnostic, records natively encode random-access memory, and self-reference resolves to multiple targets. These properties suggest applications to configuration languages, dependency injection, object-oriented programming, composable effect systems, modular software architectures, file-system-as-compiler, general-purpose programming, and no-code development.
