Multimodal Dependent Type Theory

Daniel Gratzer, G. A. Kavvos, Andreas Nuyts, Lars Birkedal

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

49 Downloads (Pure)

Abstract

We introduce MTT, a dependent type theory which supports multiple modalities. MTT is parametrized by a mode theory which specifies a collection of modes, modalities, and transformations between them. We show that different choices of mode theory allow us to use the same type theory to compute and reason in many modal situations, including guarded recursion, axiomatic cohesion, and parametric quantification. We reproduce examples from prior work in guarded recursion and axiomatic cohesion--demonstrating that MTT constitutes a simple and usable syntax whose instantiations intuitively correspond to previous handcrafted modal type theories. In some cases, instantiating MTT to a particular situation unearths a previously unknown type theory that improves upon prior systems. Finally, we investigate the metatheory of MTT. We prove the consistency of MTT and establish canonicity through an extension of recent type-theoretic gluing techniques. These results hold irrespective of the choice of mode theory, and thus apply to a wide variety of modal situations.

Original languageEnglish
Title of host publicationLICS '20
Subtitle of host publicationProceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science
Place of PublicationNew York, NY, USA
PublisherAssociation for Computing Machinery (ACM)
Pages492-506
Number of pages15
ISBN (Print)9781450371049
DOIs
Publication statusPublished - 8 Jul 2020
EventThirty-Fifth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2020) - Saarland Informatics Campus, Saarbrücken, Germany
Duration: 8 Jul 202011 Jul 2020
Conference number: 2020
https://lics.siglog.org/lics20/

Conference

ConferenceThirty-Fifth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2020)
Abbreviated titleLICS
CountryGermany
CitySaarbrücken
Period8/07/2011/07/20
Internet address

Structured keywords

  • Programming Languages

Keywords

  • modal types
  • dependent types
  • type theory
  • modal type theory
  • guarded recursion
  • categorical semantics

Fingerprint Dive into the research topics of 'Multimodal Dependent Type Theory'. Together they form a unique fingerprint.

Cite this