Split Decisions: Explicit Contexts for Substructural Languages
Open Access
- 10 January 2025
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 257-271
Abstract
A central challenge in mechanizing the meta-theory of substructural languages is modeling contexts. Although various ad hoc approaches to this problem exist, we lack a set of good practices and a simple infrastructure that can be leveraged for mechanizing a wide range of substructural systems. In this work, we describe Contexts as Resource Vectors (CARVe), a general syntactic infrastructure for managing substructural contexts, where elements are annotated with tags from a resource algebra denoting their availability. Assumptions persist as contexts are manipulated since we model resource consumption by changing their tags. We may thus define relations between substructural contexts via simultaneous substitutions without the need to split them. Moreover, we establish a series of algebraic properties about context operations that are typically required to carry out proofs in practice. CARVe is implemented in the proof assistant Beluga. To illustrate best practices for using our infrastructure, we give a detailed reformulation of the linear sequent calculus and bidirectional linear λ-calculus in terms of CARVe’s context operations and prove their equivalence using the aforementioned algebraic properties. In addition, we apply CARVe to mechanize a diverse set of systems, from the affine λ-calculus to the session-typed process calculus CP, giving us confidence that CARVe is sufficiently general to mechanize a broad range of substructural systems.Keywords
Funding Information
- This work was funded by the Natural Sciences and Engineering Research Council of Canada and the Fonds de recherche du Quebec --- Nature et technologies. ()
This publication has 50 references indexed in Scilit:
- The Concurrent Calculi Formalisation Benchmark2024
- A Framework for Substructural Type Systems2022
- $\pi $ with Leftovers: A Mechanisation in Agda2021
- EMTST: Engineering the Meta-theory of Session Types2020
- I Got Plenty o’ Nuttin’2016
- A Fresh Look at Separation Algebras and Share Accounting2009
- Celf – A Logical Framework for Deductive and Concurrent Systems (System Description)2008
- A Linear Logical FrameworkInformation and Computation, 2002
- A Framework for the Formalisation of Pi Calculus Type Systems in Isabelle/HOL2001
- Logic Programming in a Fragment of Intuitionistic Linear LogicInformation and Computation, 1994