On the Semantics of “Data Type”

Abstract

This paper considers the general problem of specifying the meaning of programming languages that include “data type definition facilities.” The fundamental question posed in attempting to define such languages is: “what meaning should be given to a data type definition,” or more simply, “what does data type mean?” In this paper we describe a new approach to defining the meaning of data types, treating data types as values, and give its application to the definition of a typed lambda calculus extension. We also prove a theorem stating that our lambda calculus definition is “strongly typed.”