Back to search

University of Strathclyde

A framework for semiring-annotated type systems

Abstract

dc:description.abstract

The use of proof assistants as a tool for programming language theorists is becoming ever more practical and widespread. There is a range of satisfactory implementations of simply typed calculi in proof assistants based on dependent type theory. In this thesis, I extend an account of Simply Typed ?-calculus so as to be able to represent and reason about calculi whose variables have restricted usage patterns. Examples of such calculi include a logic with an S4 ?-modality, in which certain variables cannot be used “inside” a box (?); and Linear Logic, in which linear variables have to be used exactly once. While there are existing implementations of some of these calculi in proof assistants, many of these implementations share little with the best presentations of simply typed calculi without variable usage restrictions, and thus end up being poorly understood or suboptimal in facilitating mechanised reasoning. Concretely, the main result of this thesis is a framework for representing and reasoning about a wide range of calculi with restricted variable usage. All of these calculi support novel simultaneous renaming and substitution operations. Furthermore, I provide several other examples of generic and specific programs facilitated by the framework. All of this work is implemented in the proof assistant Agda.

Degree

thesis:*
Name dc:type.qualificationname
phd
Level dc:type.qualificationlevel
doctoral-pg
Grantor dc:publisher.institution
University of Strathclyde
Year dc:date.issued
2024

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Wood, James
Advisor dc:contributor.advisor
  • Atkey Bob
Author Identifier dc:creator.authoridentifier
  • 201754413

Rights

Identifiers

dc:identifier.*
Identifier
T17017

Chain of custody

source
Harvested from
University of Strathclyde
Base URL
stax.strath.ac.uk/catalog/oai
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Wood, James. A framework for semiring-annotated type systems. doctoral-pg thesis, University of Strathclyde, 2024. https://stax.strath.ac.uk/concern/theses/tt44pn44w