Types and Programming Languages (MIT Press)

Types and Programming Languages (MIT Press)

Benjamin C. Pierce

Language: English

Pages: 645

ISBN: 0262162091

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.

Principles of Transaction Processing for the Systems Professional (1st Edition)

Data Science at the Command Line: Facing the Future with Time-Tested Tools

A Practical Guide to Web App Success

The Handbook of Brain Theory and Neural Networks (2nd Edition)

















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 definition reducing the underlined redex reducing the underlined redex by definition 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. Define the Church

Definition [Substitution]: The substitution of a term s for variable number j in a term t, written [j s]t, is defined 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 definition. Do the answers correspond to the original definition 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-specific exceptions. 4. The same idea can be refined to leave room for user-defined 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 different from any tag already present in the variant type T exn ,2 and from now on

Download sample