Back to search

University of Strathclyde

A cosmology of datatypes : reusability and dependent types

Abstract

dc:description.abstract

This dissertation defends the idea of a closed dependent type theory whose inductive types are encoded in a universe. Each inductive definition arises by interpreting its description - itself a firstclass citizen in the type theory. Datatype-generic programming thus becomes ordinary programming. This approach is illustrated by several generic programs. We then introduce an elaboration of inductive definitions down to the universe of datatypes. By elaborating an inductive definition - a syntactic artefact - to its code - its type theoretic denotation - we obtain an internalised account of inductive types inside type theory. This is a small step toward bootstrapping, i.e. implementing the inductive fragment in the type theory itself. Building upon this universe of datatypes, ornaments let us treat datatypes as the combination of a structure and a logic: they relate datatypes through their common structure. We set out to rationalise this calculus of structures. We study a categorical model of ornaments, based on Cartesian morphisms of containers. We also illustrate the adequacy of our model by recasting the standard idioms into the categorical mould, and by translating the discovered categorical structures into type theoretic artefacts. Nonetheless, the extreme accuracy of these finely indexed datatypes is a curse for code reuse. Similar functions must be duplicated across similarly structured - but logically incompatible - indexed datatypes. We shall see how code reuse can be achieved by ornamenting functions. We thus capture the relationship between functions such as the addition of natural numbers and the concatenation of lists. We also demonstrate how the implementation of the former informs the implementation of the latter.

Degree

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

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Dagand, Pierre-E?variste

Rights

Identifiers

dc:identifier.*
Identifier
uk.bl.ethos.605921
T13637

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

Dagand, Pierre-E?variste. A cosmology of datatypes : reusability and dependent types. doctoral-pg thesis, University of Strathclyde, 2013. https://stax.strath.ac.uk/concern/theses/k930bx12m