François René Rideau - First Class Implementations: Climbing up the Semantic Tower - λC 2018
Software exists at multiple levels of abstraction, where each more concrete level is an implementation of the more abstract level above, in a semantic tower of compilers and/or interpreters. First-class implementations are a reflection protocol to navigate this tower at runtime: they enable changing the underlying implementation of a computation while it is running.
The key is a generalized notion of safe points that enables observing a computation at a higher-level than that at which it runs, and therefore enables climbing up the semantic tower, whereas at runtime most existing systems only ever allow you to go further down. The protocol I will describe was obtained by extracting the computational content of a formal specification for implementations and some of their properties. This approach reconciles two heretofore mutually exclusive fields: Semantics and Runtime Reflection.
My formalism makes some trivial use of category theory, though with partial rather than total functors. I'll leave it to experts to figure out the implications, though I'll suggest that implementation is the opposite of abstract interpretation, whereas natural transformations are opposite to code instrumentation.
I will explain how this theory opens a systematic approach to universally implementing a lot of currently prohibitively expensive ad hoc techniques, from code migration to time travel debugging to orthogonal persistence. I will discuss the price we pay to use first-class implementations as well as the benefits they bring, and I will explore new kinds of software architecture enabled by this new approach.