Skip to main content
Kent Academic Repository

Linearity and uniqueness: An Entente Cordiale

Marshall, Daniel, Vollmer, Michael, Orchard, Dominic (2022) Linearity and uniqueness: An Entente Cordiale. In: Lecture Notes in Computer Science. Programming Languages and Systems: European Symposium on Programming (ESOP). Lecture Notes in Computer Science , 13240. pp. 346-375. Springer ISBN 978-3-030-99336-8. E-ISBN 978-3-030-99336-8. (doi:10.1007/978-3-030-99336-8_13) (KAR id:98024)

Abstract

Substructural type systems are growing in popularity because they allow for a resourceful interpretation of data which can be used to rule out various software bugs. Indeed, substructurality is finally taking hold in modern programming; Haskell now has linear types roughly based on Girard’s linear logic but integrated via graded function arrows, Clean has uniqueness types designed to ensure that values have at most a single reference to them, and Rust has an intricate ownership system for guaranteeing memory safety. But despite this broad range of resourceful type systems, there is comparatively little understanding of their relative strengths and weaknesses or whether their underlying frameworks can be unified. There is often confusion about whether linearity and uniqueness are essentially the same, or are instead ‘dual’ to one another, or somewhere in between. This paper formalises the relationship between these two well-studied but rarely contrasted ideas, building on two distinct bodies of literature, showing that it is possible and advantageous to have both linear and unique types in the same type system. We study the guarantees of the resulting system and provide a practical implementation in the graded modal setting of the Granule language, adding a third kind of modality alongside coeffect and effect modalities. We then demonstrate via a benchmark that our implementation benefits from expected efficiency gains enabled by adding uniqueness to a language that already has a linear basis.

Item Type: Conference or workshop item (Proceeding)
DOI/Identification number: 10.1007/978-3-030-99336-8_13
Uncontrolled keywords: linear types; uniqueness types; substructural logic
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Funders: Engineering and Physical Sciences Research Council (https://ror.org/0439y7842)
Depositing User: Dominic Orchard
Date Deposited: 15 Nov 2022 15:53 UTC
Last Modified: 26 Jun 2024 02:51 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/98024 (The current URI for this page, for reference purposes)

University of Kent Author Information

  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.