with leftovers: a mechanisation in Agda
From MaRDI portal
Publication:2117018
Logic in computer science (03B70) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Specification and verification (program logics, model checking, etc.) (68Q60) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Formalization of mathematics in connection with theorem provers (68V20)
Abstract: Linear type systems need to keep track of how programs use their resources. The standard approach is to use context splits specifying how resources are (disjointly) split across subterms. In this approach, context splits redundantly echo information which is already present within subterms. An alternative approach is to use leftover typing, where in addition to the usual (input) usage context, typing judgments have also an output usage context: the leftovers. In this approach, the leftovers of one typing derivation are fed as input to the next, threading through linear resources while avoiding context splits. We use leftover typing to define a type system for a resource-aware {pi}-calculus, a process algebra used to model concurrent systems. Our type system is parametrised over a set of usage algebras that are general enough to encompass shared types (free to reuse and discard), graded types (use exactly n number of times) and linear types (use exactly once). Linear types are important in the {pi}-calculus: they ensure privacy and safety of communication and avoid race conditions, while graded and shared types allow for more flexible programming. We provide a framing theorem for our type system, generalise the weakening and strengthening theorems to include linear types, and prove subject reduction. Our formalisation is fully mechanised in about 1850 lines of Agda.
Recommendations
Cites work
- -calculus in (Co)inductive-type theory
- \textsc{Lincx}: a linear logical framework with first-class contexts
- A calculus of mobile processes. I
- A Coq library for verification of concurrent programs
- A linear logical framework
- An extensible approach to session polymorphism
- Formalising the π-Calculus Using Nominal Logic
- scientific article; zbMATH DE number 1296290 (Why is no real title available?)
- scientific article; zbMATH DE number 1950451 (Why is no real title available?)
- scientific article; zbMATH DE number 1759486 (Why is no real title available?)
- scientific article; zbMATH DE number 1863387 (Why is no real title available?)
- scientific article; zbMATH DE number 969070 (Why is no real title available?)
- scientific article; zbMATH DE number 3400430 (Why is no real title available?)
- I got plenty o' nuttin'
- Inductive families
- Iris: monoids and invariants as an orthogonal basis for concurrent reasoning
- Lilac: a functional programming language based on linear logic
- Linear type theory for asynchronous session types
- Logical relations for fine-grained concurrency
- Session types revisited
- Syntax and semantics of quantitative type theory
- The -calculus: A theory of mobile processes
- Type systems for concurrent programs.
- Typing with Leftovers - A mechanization of Intuitionistic Multiplicative-Additive Linear Logic
Cited in
(2)
This page was built for publication: \( \pi\) with leftovers: a mechanisation in Agda
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2117018)
