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.
check that fst (pair v w) →∗ v, calculate as follows: = → → = → → →∗ fst (pair v w) fst ((λf. λs. λb. b f s) v w) fst ((λs. λb. b v s) w) fst (λb. b v w) (λp. p tru) (λb. b v w) (λb. b v w) tru tru v w v by deﬁnition reducing the underlined redex reducing the underlined redex by deﬁnition reducing the underlined redex reducing the underlined redex as before. Church Numerals Representing numbers by lambda-terms is only slightly more intricate than what we have just seen. Deﬁne the Church
Definition [Substitution]: The substitution of a term s for variable number j in a term t, written [j s]t, is deﬁned as follows: [j s]k = [j [j s](λ.t1 ) s](t1 t2 ) = = s if k = j k otherwise λ. [j+1 ↑1 (s)]t1 ([j s]t1 [j s]t2 ) Exercise [ ]: Convert the following uses of substitution to nameless form, assuming the global context is Γ = a,b, and calculate their results using the above deﬁnition. Do the answers correspond to the original deﬁnition of substitution on ordinary terms from
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.
straightforward analyses embodied in most type systems are not capable of proscribing arbitrary undesired program behaviors; they can only guarantee that well-typed programs are free from certain kinds of misbehavior. For example, most type systems can check statically that the arguments to primitive arithmetic operations are always numbers, that the receiver object in a method invocation always provides the requested method, etc., but not that the second argument to the division operation is
of tags of the variant type T exn ). This leaves no room for programmers to declare application-speciﬁc exceptions. 4. The same idea can be reﬁned to leave room for user-deﬁned exceptions by taking Texn to be an extensible variant type. ML adopts this idea, providing a single extensible variant type called exn. 1 The ML declaration exception l of T can be understood, in the present setting, as “make sure that l is diﬀerent from any tag already present in the variant type T exn ,2 and from now on