Functors are type refinement systems

Paul André Melliès, Noam Zeilberger

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

The standard reading of type theory through the lens of category theory is based on the idea of viewing a type system as a category of well-typed terms.We propose a basic revision of this reading: Rather than interpreting type systems as categories, we describe them as functors from a category of typing derivations to a category of underlying terms. Then, turning this around, we explain how in fact any functor gives rise to a generalized type system, with an abstract notion of typing judgment, typing derivations and typing rules. This leads to a purely categorical reformulation of various natural classes of type systems as natural classes of functors. The main purpose of this paper is to describe the general framework (which can also be seen as providing a categorical analysis of refinement types), and to present a few applications. As a larger case study, we revisit Reynolds' paper on "The Meaning of Types" (2000), showing how the paper's main results may be reconstructed along these lines.

Original languageEnglish
Title of host publicationPOPL 2015 - Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages
PublisherAssociation for Computing Machinery
Pages3-16
Number of pages14
ISBN (Electronic)9781450333009
DOIs
Publication statusPublished - 14 Jan 2015
Externally publishedYes
Event42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2015 - Mumbai, India
Duration: 12 Jan 201518 Jan 2015

Publication series

NameConference Record of the Annual ACM Symposium on Principles of Programming Languages
Volume2015-January
ISSN (Print)0730-8566

Conference

Conference42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2015
Country/TerritoryIndia
CityMumbai
Period12/01/1518/01/15

Keywords

  • Category theory
  • Refinement types
  • Type theory

Fingerprint

Dive into the research topics of 'Functors are type refinement systems'. Together they form a unique fingerprint.

Cite this