Online version of “Introduction to the Theory of Programming Languages”
A full, free online version of
Introduction to the Theory of Programming Languages,
2nd printing (1991)
Copyright notice: The text is not in the public domain. It is copyrighted material, made available free of charge on the Web for the convenience of readers, with the permission of the original publisher (Prentice Hall, now Pearson Education, Inc.). You are not permitted to copy it or redistribute it. Please refer others to the present version at bertrandmeyer.com/ITPL.
The text (3.3 MB) is available here for download.
(Please do not bookmark or share the above download link as it may change, but use the present page: https:/bertrandmeyer.com/ITPL.)
The book is a survey of methods for specifying programming languages, both syntax (focusing on abstract syntax) and various semantic approaches: operational semantics, translational semantics, denotational semantics and axiomatic semantics, as well as their complementarity. There are 10 chapters; here is the table of contents (xvi + 448 pages):
- Preface
- Basic concepts
- Mathematical background.
- Syntax (introduces formal techniques for describing syntax, included a simplified BNF).
- Semantics: the main approaches (overview of the techniques described in detail in the following chapters).
- Lambda calculus.
- Denotational semantics: fundamentals.
- Denotational semantics: language features (covers denotational-style specifications of records, arrays, input/output etc.).
- The mathematics of recursion (talks in particular about iterative methods and fixpoints, and the bottom-up interpretation of recursion, based on work by Gérard Berry).
- Axiomatic semantics (an extensive — 98-page — presentation of Hoare-style language and program specification, also including Dijkstra’s weakest-precondition calculus and techniques of correctness by construction).
- Complementary semantic definitions (establishing a clear relationship between different specifications, particular axiomatic and denotational).
- Bibliography
The text is from the second corrected printing, 1991, with additional corrections of errata reported after that publication.
The presentation uses a simple example language called Graal (for “Great Relief After Ada Lessons”). (You will also find, for specific examples, the language Lullaby, Little-Used Lilliputian Language Appropriate for Beginners and the Young, and Oulala, Outrageously Useless Lilliputian Assembly Language for Analphabets.)
This is a 3-decade-old text, and would be written differently today, but I believe it retains interest as an introduction to program semantics and formal methods.