A framework for substructural type systems

Wood, James and Atkey, Robert; (2022) A framework for substructural type systems. In: ESOP 2022 Proceedings. Lecture Notes in Computer Science . Springer, DEU.

[thumbnail of Wood-Atkey-ESOP-2022-A-framework-for-substructural-type-systems]
Preview
 Text. Filename: Wood_Atkey_ESOP_2022_A_framework_for_substructural_type_systems.pdf
Accepted Author Manuscript
License: Strathprints license 1.0
Download (875kB)| Preview

Abstract

Mechanisation of programming language research is of growing interest, and the act of mechanising type systems and their metatheory is generally becoming easier as new techniques are invented. However, state-of-the-art techniques mostly rely on structurality of the type system --- that weakening, contraction, and exchange are admissible and variables can be used unrestrictedly once assumed. Linear logic, and many related subsequent systems, provide motivations for breaking some of these assumptions. We present a framework for mechanising the metatheory of certain substructural type systems, in a style resembling mechanised metatheory of structural type systems. The framework covers a wide range of simply typed syntaxes with semiring usage annotations, via a metasyntax of typing rules. The metasyntax for the premises of a typing rule is related to bunched logic, featuring both sharing and separating conjunction, roughly corresponding to the additive and multiplicative features of linear logic. We use the uniformity of syntaxes to derive type system-generic renaming, substitution, and a form of linearity checking.

ORCID iDs

Wood, James and Atkey, Robert ORCID logoORCID: https://orcid.org/0000-0002-4414-5047;
CORE (COnnecting REpositories)