Bidirectional Elaboration of Dependently Typed Programs

• Main Authors: Francisco Ferreira, Brigitte Pientka
• Other Authors: The Pennsylvania State University CiteSeerX Archives
• Format: Text
• Language: English
• Subjects: type reconstruction; Beluga; Beluga*
• Online Access: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.672.6554; http://www.cs.mcgill.ca/%7Ebpientka/papers/reconstruction-long.pdf

Dependently typed programming languages allow programmers to express a rich set of invariants and verify them statically via type checking. To make programming with dependent types practical, dependently typed systems provide a compact language for pro-grammers where one can omit some arguments, called implicit, which can be inferred. This source language is then usually elab-orated into a core language where type checking and fundamen-tal properties such as normalization are well understood. Unfor-tunately, this elaboration is rarely specified and in general is ill-understood. This makes it not only difficult for programmers to un-derstand why a given program fails to type check, but also is one of the reasons that implementing dependently typed programming systems remains a black art known only to a few. In this paper, we specify the design of a source language for a dependently typed programming language where we separate the language of programs from the language of types and terms occur-ring in types. We then give a bi-directional elaboration algorithm to translate source terms where implicit arguments can be omitted to a fully explicit core language and prove soundness of our elabora-tion. Our framework provides post-hoc explanation for elaboration found in the programming and proof environment, Beluga. Categories and Subject Descriptors CR-number [subcategory]: third-level