A course in computer programming provides the typical student’s first exposure to the field of computer science. Most students in such a course will have used computers all their lives, for email, games, web browsing, word processing, instant messaging, and a host of other tasks, but it is not until they write their first programs that they begin to appreciate how applications work. After gaining a certain level of facility as programmers (presumably with the help of a good course in data structures and algorithms), the natural next step is to wonder how programming languages work. This book provides an explanation. It aims, quite simply, to be the most comprehensive and accurate languages text available, in a style that is engaging and accessible to the typical undergraduate. This aim reflects my conviction that students will understand more, and enjoy the material more, if we explain what is really going on.
In the conventional “systems” curriculum, the material beyond data structures (and possibly computer organization) tends to be compartmentalized into a host of separate subjects, including programming languages, compiler construction, computer architecture, operating systems, networks, parallel and distributed computing, database management systems, and possibly software engineering, object-oriented design, graphics, or user interface systems. One problem with this compartmentalization is that the list of subjects keeps growing, but the number of semesters in a Bachelor’s program does not. More important, perhaps, many of the most interesting discoveries in computer science occur at the boundaries between subjects. The RISC revolution, for example, forged an alliance between computer architecture and compiler construction that has endured for 20 years. More recently, renewed interest in virtual machines has blurred the boundary between the operating system kernel and the language run-time system. The spread of Java and .NET has similarly blurred the boundary between the compiler and the run-time system. Programs are now routinely embedded in web pages, spreadsheets, and user interfaces.
Increasingly, both educators and practitioners are recognizing the need to emphasize these sorts of interactions. Within higher education in particular there is a growing trend toward integration in the core curriculum. Rather than give the typical student an in-depth look at two or three narrow subjects, leaving holes in all the others, many schools have revised the programming languages and operating systems courses to cover a wider range of topics, with follow-on electives in various specializations. This trend is very much in keeping with the findings of the ACM/IEEE-CS Computing Curricula 2001 task force, which emphasize the growth of the field, the increasing need for breadth, the importance of flexibility in curricular design, and the overriding goal of graduating students who “have a system-level perspective, appreciate the interplay between theory and practice, are familiar with common themes, and can adapt over time as the field evolves” [Sec. 11.1, adapted].
The first edition of Programming Language Pragmatics (PLP-1e) had the good fortune of riding this curricular trend. The second edition continues and strengthens the emphasis on integrated learning while retaining a central focus on programming language design.
At its core, PLP is a book about how programming languages work. Rather than enumerate the details of many different languages, it focuses on concepts that underlie all the languages the student is likely to encounter, illustrating those concepts with a variety of concrete examples, and exploring the tradeoffs that explain why different languages were designed in different ways. Similarly, rather than explain how to build a compiler or interpreter (a task few programmers will undertake in its entirety), PLP focuses on what a compiler does to an input program, and why. Language design and implementation are thus explored together, with an emphasis on the ways in which they interact.
There were four main goals for the second edition:
Item (2) reflects such key developments as the finalized C99 standard and the appearance of Java 5 and C# (version 2.0). Chapter 6 (Control Flow) now covers boxing, unboxing, and the latest iterator constructs. Chapter 8 (Subroutines) covers Java and C# generics. Chapter 12 (Concurrency) covers the Java 5 concurrency library (JSR 166). References to C# have been added where appropriate throughout. In keeping with changes in the microprocessor market, the ubiquitous Intel/AMD x86 has replaced the Motorola 68000 in the case studies of Chapters 5 (Architecture) and 8 (Subroutines). The MIPS case study in Chapter 8 has been updated to 64-bit mode. References to technological constants and trends have also been updated. In several places I have rewritten examples to use languages with which students are more likely to be familiar; this process will undoubtedly continue in future editions.
Many sections have been heavily rewritten to make them clearer or more accurate. These include coverage of finite automaton creation (2.2.1); declaration order (3.3.3); modules (3.3.4); aliases and overloading (3.6.1 and 3.6.2); polymorphism and generics (3.6.3, 7.1.2, 8.4, and 9.4.4); separate compilation (3.7); continuations, exceptions, and multilevel returns (6.2.1, 6.2.2, and 8.5); calling sequences (8.2); and most of Chapter 5.
Item (3) reflects Morgan Kaufmann’s commitment to making definitive texts available at a reasonable cost. PLP-1e was larger and more comprehensive than competing texts, but sold for less. This second edition keeps a handle on cost (and also reduces bulk) with high quality paperback construction.
Finally, item (4) encompasses a large number of presentational changes. Some of these are relatively small. There are more frequent section headings, for example, and more historical anecdotes. More significantly, the book has been organized into four major parts:
To minimize the physical size of the text, make way for new material, and allow students to focus on the fundamentals when browsing, approximately 250 pages of more advanced or peripheral material has been moved to a companion CD. For the most part (though not exclusively) this material comprises the sections that were identified as advanced or optional in PLP-1e.
The most significant single move is the entire chapter on code improvement (15). The rest of the moved material consists of scattered, shorter sections. Each such section is represented in the text by a brief introduction to the subject and an “In More Depth” paragraph that summarizes the elided material.
Note that the placement of material on the CD does not constitute a judgment about its technical importance. It simply reflects the fact that there is more material worth covering than will fit in a single volume or a single course. My intent is to retain in the printed text the material that is likely to be covered in the largest number of courses.
Also contained on the CD are compilable copies of all significant code fragments found in the text (in 25 different languages), an extensive search facility, and pointers to on-line resources.
PLP-1e placed a heavy emphasis on the ways in which language design constrains implementation options, and the ways in which anticipated implementations have influenced language design. PLP-2e uses more than 120 sidebars to make these connections more explicit. A more detailed introduction to these sidebars appears on page 7 (Chapter 1). A numbered list appears in Appendix B.
Examples in PLP-2e are intimately woven into the flow of the presentation. To make it easier to find specific examples, to remember their content, and to refer to them in other contexts, a number and a title for each is now displayed in a marginal note. There are nearly 900 such examples across the main text and the CD. A detailed list appears in Appendix C.
PLP-1e contained a total of 385 review questions and 312 exercises, located at the ends of chapters. Review questions in the second edition have been moved to the ends of sections, closer to the material they cover, to make it easier to tell when one has grasped the central concepts. The total number of such questions has nearly doubled.
The problems remaining at the ends of chapters have now been divided into Exercises and Explorations. The former are intended to be more-or-less straightforward, though more challenging than the per-section review questions; they should be suitable for homework or brief projects. The exploration questions are more open-ended, requiring web or library research, substantial time commitment, or the development of subjective opinion. The total number of questions has increased from a little over 300 in PLP-1e to over 500 in the current edition. Solutions to the exercises (but not the explorations) are available to registered instructors from a password-protected web site.
Programming Language Pragmatics covers almost all of the material in the PL “knowledge units” of the Computing Curricula 2001 report . The book is an ideal fit for the CS 341 model course (Programming Language Design), and can also be used for CS 340 (Compiler Construction) or CS 343 (Programming Paradigms). It contains a significant fraction of the content of CS 344 (Functional Programming) and CS 346 (Scripting Languages).
Figure 1 illustrates several possible paths through the text. Darker shaded regions indicate supplemental “In More Depth” sections on the PLP CD. Section numbers are shown for breaks that do not correspond to supplemental material.
Figure 1: Paths through the text.
For self-study, or for a full-year course (track F in Figure 1), I recommend working through the book from start to finish, turning to the PLP CD as each “In More Depth” section is encountered. The one-semester course at the University of Rochester (track R), for which the text was originally developed, also covers most of the book, but leaves out most of the CD sections, as well as bottom-up parsing (2.3.3), message passing (12.4), web scripting (13.3), and most of Chapter 14 (Building a Runnable Program).
Some chapters (2, 4, 5, 14, 15) have a heavier emphasis than others on implementation issues. These can be reordered to a certain extent with respect to the more design-oriented chapters, but it is important that chapter 5 or its equivalent be covered before chapters 6 through 9. Many students will already be familiar with some of the material in chapter 5, most likely from a course on computer organization. In this case the chapter may simply be skimmed for review. Some students may also be familiar with some of the material in chapter 2, perhaps from a course on automata theory. Much of this chapter can then be read quickly as well, pausing perhaps to dwell on such practical issues as recovery from syntax errors, or the ways in which a scanner differs from a classical finite automaton.
A traditional programming languages course (track P in Figure 1) might leave out all of scanning and parsing, plus all of Chapters 4 and 5. It would also de-emphasize the more implementation-oriented material throughout. In place of these it could add such design-oriented CD sections as the ML type system (7.2.4), multiple inheritance (9.5), Smalltalk (9.6.1), lambda calculus (10.6), and predicate calculus (11.3).
PLP has also been used at some schools for an introductory compiler course (track C in Figure 1). The typical syllabus leaves out most of Part III (Chapters 10 through 13), and de-emphasizes the more design-oriented material throughout. In place of these it includes all of scanning and parsing, Chapters 14 and 15, and a slightly different mix of other CD sections.
For a school on the quarter system, an appealing option is to offer an introductory one-quarter course and two optional follow-on courses (track Q in Figure 1). The introductory quarter might cover the main (non-CD) sections of Chapters 1, 3, 6, and 7, plus the first halves of Chapters 2 and 8. A language-oriented follow-on quarter might cover the rest of Chapter 8, all of Part III, CD sections from Chapters 6 through 8, and possibly supplemental material on formal semantics, type systems, or other related topics. A compiler-oriented follow-on quarter might cover the rest of Chapter 2; Chapters 4–5 and 14–15, CD sections from Chapters 3 and 8–9, and possibly supplemental material on automatic code generation, aggressive code improvement, programming tools, and so on.
Whatever the path through the text, I assume that the typical reader has already acquired significant experience with at least one imperative language. Exactly which language it is shouldn’t matter. Examples are drawn from a wide variety of languages, but always with enough comments and other discussion that readers without prior experience should be able to understand easily. Single-paragraph introductions to some 50 different languages appear in Appendix A. Algorithms, when needed, are presented in an informal pseudocode that should be self-explanatory. Real programming language code is set in "typewriter" font. Pseudocode is set in a san-serif font.
In addition to supplemental sections of the text, the PLP CD contains a variety of other resources, including
Additional resources are available at Morgan Kaufmann's website (you may wish to check back from time to time). For instructors who have adopted the text, a password-protected page provides access to
In preparing the second edition I have been blessed with the generous assistance of a very large number of people. Many provided errata or other feedback on the first edition, among them Anthony Adachi, Manuel E. Bermudez, John Boyland, Brian Cumming, Stephen A. Edward, Michael J. Eulenstein, Tayssir John Gabbour, Tommaso Galleri, Andrey Garbanzo, Eileen Head, David Hoffman, Paul Ilardi, Lucian Ilie, Rahul Jain, Eric Joanis, Alan Kaplan, Les Lander, Jim Larus, Hui Li, Jingke Li, Esteban Meneses, Evangelos Milios, Eduardo Pinheiro, Barbara Ryder, Nick Stuifbergen, Raymond Toal, Andrew Tolmach, Jens Troeger, and Robbert van Renesse. Zongyan Qiu prepared the Chinese translation, and found several bugs in the process. Simon Fillat maintained the Morgan Kaufmann website. I also remain indebted to the many other people, acknowledged in the first edition, who helped in that earlier endeavor, and to the reviewers, adopters, and readers who made it a success. Their contributions continue to be reflected in the current edition.
Work on the second edition began in earnest with a “focus group” at SIGCSE ’02; my thanks to Denise Penrose, Emilia Thiuri, and the rest of the team at Morgan Kaufmann for organizing that event, to the approximately two dozen attendees who shared their thoughts on content and pedagogy, and to the many other individuals who reviewed two subsequent revision plans.
A draft of the second edition was class tested in the fall of 2004 at 8 different universities. I am grateful to Gerald Baumgartner (Louisiana State University), William Calhoun (Bloomsburg University), Betty Cheng (Michigan State University), Jingke Li (Portland State University), Beverly Sanders (University of Florida), Darko Stefanovic (University of New Mexico), Raymond Toal (Loyola Marymount University), Robert van Engelen (Florida State University), and all their students for a mountain of suggestions, reactions, bug fixes, and other feedback. Prof. van Engelen provided several excellent end-of-chapter exercises.
External reviewers for the second edition also provided a wealth of useful suggestions; my thanks to Richard J. Botting (California State University, San Bernardino), Kamal Dahbur (DePaul University), Stephen A. Edwards (Columbia University), Eileen Head (Binghamton University), Li Liao (University of Delaware), Christopher Vickery (Queens College, City University of New York), Garrett Wollman (MIT), Neng-Fa Zhou (Brooklyn College, City University of New York), and Cynthia Brown Zickos (University of Mississippi). Garrett Wollman’s technical review of Chapter 13 was particularly helpful, as were his earlier comments on a variety of topics in the first edition. Sadly, time has not permitted me to do justice to everyone’s suggestions. I have incorporated as much as I could, and have carefully saved the rest for guidance on the third edition. Problems that remain in the current edition are entirely my own.
PLP-2e was also class tested at the University of Rochester in the fall of 2004. I am grateful to all my students, and to John Heidkamp, David Lu, and Dan Mullowney in particular, for their enthusiasm and suggestions. Mike Spear provided several helpful pointers on web technology for Chapter 13. Over the previous several years, my colleagues Chen Ding and Sandhya Dwarkadas taught from the first edition several times, and had many helpful suggestions. Chen’s feedback on Chapter 15, (assisted by Yutao Zhong) was particularly valuable. My thanks as well to the rest of my colleagues, to department chair Mitsunori Ogihara, and to the department’s administrative, secretarial, and technical staff for providing such a supportive and productive work environment.
As they were on the first edition, the staff at Morgan Kaufmann have been a genuine pleasure to work with, on both a professional and a personal level. My thanks in particular to Denise Penrose, publisher; Nate McFadden, editor; Carl Soares, production editor; Peter Ashenden, CD designer; Brian Grimm, marketing manager; and Valerie Witte, editorial assistant.
Most important, I am indebted to my wife, Kelly, and our daughters, Erin and Shannon, for their patience and support through endless months of writing and revising. Computing is a fine profession, but family is what really matters.
Michael L. Scott