
doi: 10.1145/2818644
When relating formal languages, e.g., in logic or type theory, it is often important to establish representation theorems. These interpret one language in terms of another in a way that preserves semantic properties such as provability or typing. Metalanguages for stating representation theorems can be divided into two groups: First, computational languages are very expressive (usually Turing-complete), but verifying the representation theorems is very difficult (often prohibitively so); second, declarative languages are restricted to certain classes of representation theorems (often based on theory morphisms), for which correctness is decidable. Neither is satisfactory, and this article contributes to the investigation of the trade-off between these two methods. Concretely, we introduce lax theory morphisms, which combine some of the advantages of each: they are substantially more expressive than conventional theory morphisms, but they share many of the invariants that make theory morphisms easy to work with. Specifically, we introduce lax morphisms between theories of a dependently typed logical framework, but our approach and results carry over to most declarative metalanguages. We demonstrate the usefulness of lax theory morphisms by stating and verifying a type erasure translation from typed to untyped first-order logic. The translation is stated as a single lax theory morphism, and the invariants of the framework guarantee its correctness. This is the first time such a complex translation has be verified in a declarative framework.
Logic in computer science, dependent type theory, logical framework, logical relation, translation, theory morphism, representation theorem
Logic in computer science, dependent type theory, logical framework, logical relation, translation, theory morphism, representation theorem
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
