Data, syntax and semantics are among the Big Ideas of Computer Science. The concepts are extremely general and can be found throughout Computer Science and its applications. Wherever there are languages for specifying, designing, programming or reasoning, one finds data, syntax and semantics.
A programming language is simply a notation for expressing algorithms and performing computations with the help of machines. There are many different designs for programming languages, tailored to the computational needs of many different types of users. Programming languages are a primary object of study in Computer Science, influencing most of the subject and its applications.
This book is an introduction to the mathematical theory of programming languages. It is intended to provide a first course, one that is suitable for all university students of Computer Science to take early in their education; for example, at the beginning of their second year, or, possibly, in the second half of their first year. The background knowledge needed is a first course in imperative programming and in elementary set theory and logic. The theory will help develop their scientific maturity by asking simple and sometimes deep questions, and by weaning them off examples and giving them a taste for general ideas, principles and techniques, precisely expressed. We have picked a small number of topics, and attempted to make the book self-contained and relevant.
The book contains much basic mathematical material on data, syntax and semantics. There are some seemingly advanced features and contemporary topics that may not be common in the elementary text-book literature: data types and their algebraic theory, real numbers, interface definition languages, algebraic models of abstract syntax, use of algebraic operational semantics, connections with computability theory, virtual machines and compiler correctness. Where our material is standard (e.g., grammars), we have tried to include new and interesting examples and case studies (e.g., internet addressing).
The book is also intended to provide a strong foundation for the further study of the theory of programming languages, and related subjects in algebra and logic, such as: algebraic specification; initial algebra semantics; term rewriting; process algebra; computability and definability theory; program correctness logic; $$\lambda$$-calculus and type theory; domains and fixed point theory etc. There are a number of books available for these later stages, and the literature is discussed in a final chapter on further reading.
The book is based on the lectures of J V Tucker (JVT) to undergraduates at the University of Leeds and primarily at the University of Wales Swansea. In particular, it has developed from the notes for a compulsory second year course on the theory of programming languages, established at Swansea in 1989. These notes began their journey from ring binder to book-shop in 1993, when Chris Tofts taught the course in JVT's stead, and provided the students with a typescript of the lecture notes. Subsequently, as JVT continued to teach the course, Karen Stephenson (KS) maintained and improved the notes, and assisted greatly in the seemingly endless process of revision and improvement. She also contributed topics and conducted a number of successful experiments on algebraic methods with the students. KS became a coauthor of the book in 2000. Together, we revised radically the text and added new chapters on regular languages, virtual machines and compiler correctness.
JVT's interest and views on the theory of programming languages owe much to J W de Bakker, J A Bergstra and J I Zucker. Ideas for this book have been influenced by continuous conversations and collaborations starting at the Mathematical Centre (now CWI), Amsterdam in 1979. However, its final contents and shape has been determined by our own discussions and our work with several generations of undergraduate students.
We would like to thank the following colleagues at Swansea: Dafydd Rees, Chen Min, Jens Blanck, Andy Gimblett, Neal Harman, Chris Whyley, Oliver Kullmann, Peter Mosses, …for their reading of selected chapters, suggestions and advice. A special debt is owed to Markus Roggenbach for a reflective and thorough reading of the text. We are grateful to the following students who formed a reading group and gave useful criticism of earlier drafts of the text: Carl Gilbert, Kevin Hicks, Rachel Holbeche, Tim Hutchison, Richard Knuszka, Paul Marden, Ivan Phillips and Stephan Reiff. We are grateful to Hasib Kabir Chowdhury who, as a student, read a later version of the manuscript and made many suggestions.
Our colleagues and students have made Swansea a warm and inspiring environment in which to educate young people in Computer Science.
The ambiguities and errors that remain in the book are solely our responsibility.
J V Tucker
Perriswood, Gower, 2003
K Stephenson
Malvern, 2003