Gradually structured data

Stefan Malewski, Michael Greenberg, Éric Tanter

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

Dynamically-typed languages offer easy interaction with ad hoc data such as JSON and S-expressions; statically-typed languages offer powerful tools for working with structured data, notably algebraic datatypes, which are a core feature of typed languages both functional and otherwise. Gradual typing aims to reconcile dynamic and static typing smoothly. The gradual typing literature has extensively focused on the computational aspect of types, such as type safety, effects, noninterference, or parametricity, but the application of graduality to data structuring mechanisms has been much less explored. While row polymorphism and set-theoretic types have been studied in the context of gradual typing, algebraic datatypes in particular have not, which is surprising considering their wide use in practice. We develop, formalize, and prototype a novel approach to gradually structured data with algebraic datatypes. Gradually structured data bridges the gap between traditional algebraic datatypes and flexible data management mechanisms such as tagged data in dynamic languages, or polymorphic variants in OCaml. We illustrate the key ideas of gradual algebraic datatypes through the evolution of a small server application from dynamic to progressively more static checking, formalize a core functional language with gradually structured data, and establish its metatheory, including the gradual guarantees.

Original languageEnglish
Article number126
JournalProceedings of the ACM on Programming Languages
Volume5
Issue numberOOPSLA
DOIs
StatePublished - Oct 2021

Keywords

  • algebraic datatypes
  • gradual typing
  • semi-structured data

Fingerprint

Dive into the research topics of 'Gradually structured data'. Together they form a unique fingerprint.

Cite this