Theories of Programming Languages

A book by John C. Reynolds, published by Cambridge University Press (U.S., Britain).
hardback, Fall 1998 500+xii pages ISBN: 9780521594141 (old ISBN: 0-521-59414-6) (U.S., Britain).
paperback, Spring 2009 500+xii pages ISBN: 9780521106979 (U.S., Britain).

(There is only one edition of the book; the hardback and paperback versions are textually identical.)

This textbook is a broad but rigorous survey of the theoretical basis for the design, definition, and implementation of programming languages, and of systems for specifying and proving program behavior. Both imperative and functional programming are covered, as well as the ways of integrating these aspects into more general anguages. Recognizing a unity of technique beneath the diversity of research in programming languages, the author presents an integrated treatment of the basic principles of the subject. He identifies the relatively small number of concepts, such as compositional semantics, binding structure, domains, transition systems, and inference rules, that serve as the foundation of the field.

The basic concepts and their properties are described with mathematical rigor, but the mathematical development is balanced by numerous examples of applications, particularly of program specification and proof, concurrent programming, functional programming (including the use of continuations and lazy evaluation), and type systems (including subtyping, polymorphism, and modularization).

Assuming only knowledge of elementary programming and mathematics, this text is perfect for advanced undergraduate and beginning graduate courses in programming language theory, and also will appeal to researchers and professionals in desinging or implementing computer languages.

Contents

  1. Predicate Logic
  2. The Simple Imperative Language
  3. Program Specifications and Their Proofs
  4. Arrays
  5. Failure, Input-Output, and Continuations
  6. Transition Semantics
  7. Nondeterminism and Guarded Commands
  8. Shared-Variable Concurrency
  9. Communicating Sequential Processes
  10. The Lambda Calculus
  11. An Eager Functional Language
  12. Continuations in a Functional Language
  13. Iswim-like Languages
  14. A Normal-Order Language
  15. The Simple Type System
  16. Subtypes and Intersection Types
  17. Polymorphism
  18. Module Specification
  19. Algol-like Languages
  20. Appendix: Mathematical Background

Additional Information

John.Reynolds@cs.cmu.edu (home page)
last updated October 6, 2009