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

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.