Types and Programming Languages (MIT Press)
Benjamin C. Pierce
Format: PDF / Kindle (mobi) / ePub
A type system is a syntactic method for automatically checking the absence of certain erroneous behaviors by classifying program phrases according to the kinds of values they compute. The study of type systems -- and of programming languages from a type-theoretic perspective -- has important applications in software engineering, language design, high-performance compilers, and security.
This text provides a comprehensive introduction both to type systems in computer science and to the basic theory of programming languages. The approach is pragmatic and operational; each new concept is motivated by programming examples and the more theoretical sections are driven by the needs of implementations. Each chapter is accompanied by numerous exercises and solutions, as well as a running implementation, available via the Web. Dependencies between chapters are explicitly identified, allowing readers to choose a variety of paths through the material.
The core topics include the untyped lambda-calculus, simple type systems, type reconstruction, universal and existential polymorphism, subtyping, bounded quantification, recursive types, kinds, and type operators. Extended case studies develop a variety of approaches to modeling the features of object-oriented languages.
By a step of renaming to restore the invariant. 3. We can devise some “canonical” representation of variables and terms that does not require renaming. The system studied in this chapter is the pure untyped lambda-calculus, λ (Figure 5-3). The associated OCaml implementation is fulluntyped. 76 6 Nameless Representation of Terms 4. We can avoid substitution altogether by introducing mechanisms such as explicit substitutions (Abadi, Cardelli, Curien, and Lévy, 1991a). 5. We can avoid variables.
T3 must both evaluate to values of the same type. The two uses of the single metavariable T express the constraint that the result of the if is the type of the then- and else- branches, and that this may be any type (either Nat or Bool or, when we get to calculi with more interesting sets of types, any other type). The rules for numbers in Figure 8-2 have a similar form. T-Zero gives the type Nat to the constant 0. T-Succ gives a term of the form succ t1 the type Nat, as long as t1 has type Nat.
T2 t1 → t1 inr t1 as T2 Γ New typing rules Γ t1 : T1 Γ inl t1 as T1 +T2 : T1 +T2 Γ inr t1 as T1 +T2 : T1 +T2 Γ (E-Inr) → inr t1 as T2 t1 : T2 t:T (T-Inl) (T-Inr) Figure 11-10: Sums (with unique typing) 3. We can demand that the programmer provide an explicit annotation to indicate which type T2 is intended. This alternative is the simplest—and it is not actually as impractical as it might at ﬁrst appear, since, in full-scale language designs, these explicit annotations can often.
Is some term t and store µ with t | µ → t | µ . Proof: Straightforward induction on typing derivations, following the pattern of 9.3.5. (The canonical forms lemma, 9.3.4, needs two additional cases stating that all values of type Ref T are locations and similarly for Unit.) 13.5.8 Exercise [Recommended, ]: Is the evaluation relation in this chapter normalizing on well-typed terms? If so, prove it. If not, write a well-typed factorial function in the present calculus (extended with numbers and.
To guarantee the integrity of these abstractions and of higher-level abstractions introduced by the programmer using the deﬁnitional facilities of the language. For example, a language may provide arrays, with access and update operations, as an abstraction of the underlying memory. A programmer using this language then expects that an array can be changed only by using the update operation on it explicitly—and not, for example, by writing past the end of some other data structure. Similarly, one.