A semantic analysis of C++ templates

Abstract. Templates are a powerful but poorly understood feature of the C++ language. Their syntax resembles the parameterized classes of other languages (e.g., of Java). But because C++ supports template spe-cialization, their semantics is quite different from that of parameterized classes. Template specialization provides a Turing-complete sub-language within C++ that executes at compile-time. Programmers put this power to many uses. For example, templates are a popular tool for writing program generators. The C++ Standard defines the semantics of templates using natural lan-guage, so it is prone to misinterpretation. The meta-theoretic properties of C++ templates have not been studied, so the semantics of templates has not been systematically checked for errors. In this paper we present the first formal account of C++ templates including some of the more complex aspects, such as template partial specialization. We validate our semantics by proving type safety and verify the proof with the Isabelle proof assistant. Our formalization reveals two interesting issues in the C++ Standard: the first is a problem with member instantiation and the second concerns the generation of unnecessary template specializations.