Covering All Bases: Design and implementation of case analysis for contextual objects

Unpublished manuscript

Brigitte Pientka and Joshua Dunfield

Abstract

We consider the question: Does a set of patterns cover all objects of a given type? This is straightforward in the simply-typed setting, but undecidable in the presence of dependent types. We discuss the question in the setting of Beluga, a dependently-typed programming and reasoning environment which supports programming with contextual objects and contexts. We describe the design and implementation of a coverage algorithm for Beluga programs and provide an in-depth comparison to closely related systems such as Twelf and Delphin. Our experience with coverage checking Beluga programs shows that many problems and difficulties are avoided. Beluga's coverage algorithm has been used on a wide range of examples, from mechanizing the meta-theory of programming languages from Pierce's textbook Types and Programming Languages to the examples from the Twelf repository.

Reader’s guide

The implementation described in this paper is based on the coverage-checking rules given in our LFMTP '08 paper.

Draft of October 2010

BibTeX entry

  @Unpublished{PientkaDunfield10:coverage,
    author =    {Brigitte Pientka and Joshua Dunfield},
    title =     {Covering All Bases: Design and implementation of case analysis for contextual objects},
    month =     oct,
    year =      {2010},
    note =      {\url{http://www.cs.cmu.edu/~joshuad/papers/case-hoas-2010/}}
  }
  

all papers * related papers
Joshua Dunfield