Write a Blog >>
ICFP 2016
Sun 18 - Sat 24 September 2016 Nara, Japan
Wed 21 Sep 2016 10:35 - 11:00 at Noh Theater - Session 9 Chair(s): Sam Lindley

Generalized Algebraic Dataypes, or simply GADTs, can encode non-trivial properties in the types of the constructors. Once such properties are encoded in a datatype, however, all code manipulating that datatype must provide proof that it maintains these properties in order to typecheck. In this paper, we take a step towards gradualizing these obligations. We introduce a tool, Ghostbuster, that produces simplified versions of GADTs which elide selected type parameters, thereby weakening the guarantees of the simplified datatype in exchange for reducing the obligations necessary to manipulate it. Like ornaments, these simplified datatypes preserve the recursive structure of the original, but unlike ornaments we focus on information-preserving bidirectional transformations. Ghostbuster generates type-safe conversion functions between the original and simplified datatypes, which we prove are the identity function when composed. We evaluate a prototype tool for Haskell against thousands of GADTs found on the Hackage package database, generating simpler Haskell'98 datatypes and round-trip conversion functions between the two.

Wed 21 Sep

icfp-2016-papers
10:35 - 12:15: Research Papers - Session 9 at Noh Theater
Chair(s): Sam LindleyUniversity of Edinburgh, UK
icfp-2016-papers10:35 - 11:00
Talk
Trevor L. McDonellIndiana University, USA, Timothy A. K. ZakianOxford University, UK, Matteo CiminiIndiana University, USA, Ryan R. NewtonIndiana University, USA
DOI
icfp-2016-papers11:00 - 11:25
Talk
David ThibodeauMcGill University, Canada, Andrew CaveMcGill University, Canada, Brigitte PientkaMcGill University, Canada
DOI
icfp-2016-papers11:25 - 11:50
Talk
Bruno C. d. S. OliveiraUniversity of Hong Kong, China, Zhiyuan ShiUniversity of Hong Kong, China, João AlpuimUniversity of Hong Kong, China
DOI
icfp-2016-papers11:50 - 12:15
Talk
Giuseppe CastagnaParis Diderot University & CNRS, Tommaso PetruccianiUniversity of Genoa, France, Kim NguyễnUniversity of Paris-Sud, France
DOI