We present a new approach to proving type soundness for Hindley/Milner-style polymorphic type systems. The keys to our approach are (1) an adaptation of subject reduction theorems from combinatory logic to programming languages, and (2) the use of rewriting techniques for the speci cation of the language semantics. The approach easily extends from polymorphic functional languages to imperative languages that provide references, exceptions, continuations, and similar features. We illustrate the technique with a type soundness theorem for the core of Standard ML, which includes the rst type soundness proof for polymorphic exceptions and continuations. Static type systems for programming languages attempt to prevent the occurrence of type errors during execution. A de nition of type error depends on a speci c language and type system, but always includes the use of a function on arguments for which it is not de ned, and the attempted application of a non-function. A static type system is sound if well-typed programs cannot cause type errors; a programming language with a sound static type system is strongly typed 7]. While it is easy to design a sound type system for an explicitly typed monomorphic language, the formulation of a sound type system for a language based on Hindley/Milnerstyle polymorphism and type inference is delicate 6, 8, 15, 17, 20, 37] . Although the treatment of purely functional languages is relatively well understood in this framework, the incorporation of imperative features such as references and exceptions requires extreme care, and the soundness of such systems is not obvious. A formal proof of soundness is This research was supported in part by the United States Department of Defense under a National Defense Science and Engineering Graduate Fellowship, by NSF grant CCR 89{17022, and by Texas Grant ARP/ATP-91 #003604-014. Syntactic Type Soundness 2 required to lend credibility to the claim that such a system prevents type errors, and may be a crucial tool in the design of the type system. We view a static type system for an implicitly typed language as a lter that selects well-typed programs from a larger universe of untyped programs. A partial function eval : Programs * Answers fwrongg de nes the semantics of untyped programs. The result wrong is returned for programs whose evaluation causes a type error; eval is unde ned for programs whose evaluation does not terminate. Let . e : mean that the type system assigns program e the type , i.e., e is well-typed. The simplest soundness property states that well-typed programs do not yield wrong 20]. De nition (Weak Soundness) If . e : then eval(e) 6 = wrong. While weak soundness establishes that a static type system achieves its primary goal of preventing type errors, it is often possible to demonstrate a stronger property that relates the answer produced to the type of the program. If we view each type as denoting di erent subsets V of the set of all answers V , then strong soundness states that an answer v produced by a terminating program of type is an element of the subset V . De nition (Strong Soundness) If . e : and eval(e) = v then v 2 V . Strong soundness permits an implementation of the language to associate the representation of a value with its type, and thereby omit the representation tags required by dynamically typed languages. Weak soundness follows from strong soundness since wrong is not a member of V for any type . Signi cant e ort has been invested in proving type soundness for Hindley/Milner-style type systems, and their practical realization in the programming language Standard ML 22, 23] . Soundness proofs exist for the functional fragment 20, 36], for extensions including references 6, 17, 35, 37], and for a monomorphic language including rst-class continuations 8]. However, there are several drawbacks to the existing proofs. Proofs of type soundness are sensitive to the precise formulation of the semantics of the language| di erent techniques are required for denotational versus operational formulations of the semantics, and even for di erent languages within the same semantic framework. The proofs for two di erent languages are di cult to reconcile to prove soundness for a language including features of both. The existing techniques are complicated, and the resulting proofs are lengthy and error-prone. For an illustration of the di culties with such proofs, we refer the reader to Tofte's 37] discussion of Damas's 6] faulty proof of a type soundness theorem for a polymorphic language with references. We present a simple approach to the proof of soundness for Hindley/Milner-style polymorphic type systems. Our approach is based on subject reduction, a classical result from combinatory logic 4], and on rewriting as a means to specifying operational semantics 11, 12, 13, 14] . To demonstrate the approach, we develop a proof of soundness for the core 1 of Standard ML, which extends a functional polymorphic language with references and exceptions. We also show soundness for an extension to Standard ML with rst-class continuations. In principle, our approach is uniformly applicable to any language; 1 Mitchell and Harper refer to the functional polymorphic sublanguage as the essence of ML 24]. However, the di culties of typing references and exceptions 6, 17, 35, 37] and the fact that they cannot be expressed by facilities of the functional core 10] indicate that they are equally important. Syntactic Type Soundness 3 in practice, the resulting proofs are lengthy but simple, requiring only ordinary inductive techniques. In the next section, we describe a prototypical functional language with a polymorphic type system, and discuss the various approaches that have previously been used to prove type soundness. Section 3 presents the essence of our approach to proving type soundness; the remaining sections develop illustrative proofs of type soundness for a speci c functional language and various extensions.
The key point for our purposes is that most such systems are closed-world, meaning that they are defined by a fixed set of rules and are proven sound using syntactic techniques REF .
A Syntactic Approach to Type Soundness
Information and Computation
Computer Science Mathematics