Universes for generic programs and proofs in dependent type theory
Marcin Benke, Peter Dybjer, Patrik Jansson · 2003
We show how to write generic programs and proofs in MartinL of type theory. To this end we consider several extensions of MartinL of's logical framework for dependent types. Each extension has a universe of codes (signatures) for inductively de ned sets with generic formation, introduction, elimination, and equality rules. These extensions are modeled on Dybjer and Setzer's nitely axiomatized theories of inductive-recursive de nitions, which also have universes of codes for sets, and generic formation, introduction, elimination, and equality rules. Here we consider several smaller universes of interest for generic programming and universal algebra. We formalize one-sorted and many-sorted term algebras, as well as iterated, generalized, parameterized, and indexed inductive de nitions. We also show how to extend the techniques of generic programming to these universes. Furthermore, we give generic proofs of reexivity and substitutivity of a generic equality test. Most of the definitions in the paper have been implemented using the proof assistant Alfa for dependent type theory.