This book is an introduction to the broad field of programming languages. It combines a general presentation of principles with considerable detail about many modern languages, including some of the newest functional and object-oriented languages. Unlike many introductory texts, it also contains significant material on implementation issues, the theoretical foundations of programming languages, and a large number of exercises, many of which have detailed answers in an appendix. All of these features make this text a useful bridge to compiler courses, and to the theoretical study of programming languages. However, it is specifically designed for use as a text in an advanced undergraduate programming languages survey course that covers most of the Programming Languages Requirements specified in the 1991 ACM/IEEE-CS Joint Curriculum Task Force Report, and the CS8 course of the 1978 ACM Curriculum.
Rather than focusing on a particular programming language, I use examples from the most widely known imperative languages, including Pascal, C, Modula-2, Ada, and FORTRAN. Also featured are some of the less widely known languages representing other language paradigms, such as Scheme, ML, Miranda, C++, Eiffel, Smalltalk, and Prolog. Readers are not expected to know any one particular language. However, experience with at least one language is necessary. A certain degree of ``computational sophistication,'' such as that provided by a course in data structures and a discrete mathematics course, is also expected.
In most cases each chapter is largely independent of the others, without artificially restricting the material in each. Cross references in the text allow the reader or instructor to fill in any gaps that might arise even if a particular chapter or section is skipped.
Chapter 1 is a survey of the concepts studied in later chapters, and introduces the different language paradigms with simple examples in typical languages.
Chapters 2 and 3 provide overviews of the history of programming languages and language design principles, respectively. Chapter 3 could well serve as a culminating chapter for the book, but I find it arouses interest in later topics when covered here.
Chapter 4 treats syntax in some detail, including the use of BNF, EBNF, and syntax diagrams. A brief section views recursive definitions (like BNF) as set equations to be solved, a view that recurs periodically throughout the text. One section is devoted to recursive-descent parsing and the use of parsing tools.
Chapters 5, 6, and 7 cover the central semantic issues of programming languages: declaration, allocation, evaluation; the symbol table and runtime environment as semantic functions; data types and type checking; and procedure activation and parameter passing. A final section in Chapter 7 is on exception handling.
Chapter 8 gives an overview of abstract data types, including language mechanisms and equational, or algebraic, specification. It also includes a section on separate compilation, and leads into the next chapter (on object-oriented programming) by discussing the limitations of abstract data type mechanisms.
Chapters 9, 10, and 11 address language paradigms, beginning with the object-oriented paradigm in Chapter 9. I use Simula67 to introduce the concepts in this chapter, which provides a gentle introduction using Algol-like syntax. Individual sections feature C++, Eiffel, and Smalltalk. Chapter 10 deals with the functional paradigm. One section covers the Scheme language in some detail, and there are additional sections on ML and Miranda. This chapter also includes introductions to the lambda calculus, the theory of recursive function definitions, and dynamic memory management. Chapter 11 is on logic programming, with an extended section on Prolog. One section is also devoted to equational languages such as OBJ.
Chapter 12 introduces the three principal methods of formal semantics: operational, denotational, and axiomatic. This is unique among introductory texts in that it gives enough detail to provide a real flavor for the methods.
Chapter 13 treats the major ways parallelism has been introduced into programming languages: coroutines, semaphores, monitors, and message passing, with examples from Modula-2, Ada, CSP, and Concurrent Pascal. A final section surveys recent efforts to introduce parallelism into LISP and Prolog.
I successfully class-tested this text over a five-year period in my CS 152 classes at San Jose State University. This course is taken by upper division computer science majors and graduate students. I have taught the course using two completely different organizations, which could loosely be called the ``principles'' approach and the ``paradigm'' approach. Two suggested organizations of these approaches in a semester-long course are as follows:
The ``principles'' approach: Chapters 1, 4, 5, 6, 7, and 8. If there is extra time, Chapters 2 and 3.
The ``paradigm'' approach: Chapters 1, 9, 10, 11, and 13 (not necessarily in that order). If there is extra time, Chapters 2 and 3, or selected topics from Chapters 5, 7, and 8.
In a two-semester or two-quarter sequence it should be possible to cover most of the book.
A large number of exercises are at the end of each chapter, with selected answers in an appendix. Many of these are programming exercises (none extremely long) in languages discussed in the text. Conceptual exercises range from the short-answer type that test understanding of the material to longer essay-style exercises and challenging ``thought'' questions. A few moments' reflection should give the reader adequate insight into the potential difficulty of a particular exercise. Further knowledge can be gained by reading the answers, which I treat as an extension of the text and sometimes provide additional information beyond that required to solve the problem. Occasionally the answer to an exercise on a particular language requires the reader to consult a language reference manual or have knowledge of the language not specifically covered in the text.
One vexing issue in teaching a programming languages course is what specific languages to use for the programming exercises (which I consider essential in a programming languages course). Each instructor has his or her own favorite languages, and a text should not require the use of one language over another. This book lends itself to use with a broad mix of actual languages for programming projects.
ACKNOWLEDGMENTS
I would like to thank the many students in my CS 152 sections at San Jose State University for their direct and indirect contributions to this book. I also want to thank three of my colleagues at San Jose State, Michael Beeson, Cay Horstmann, and Vinh Phat, who read and commented on individual chapters. In addition, I thank my editors at PWS-KENT for their encouragement and assistance, particularly Tom Robbins and Patty Adams. A special thanks is owed to Marjorie Schlaiker, who first convinced me I should write this book. Finally, I thank my wife Margreth for her understanding, patience, and prodding during the long hours of work.
The following reviewers contributed useful suggestions: Ray Fanselau, American River College; Larry Irwin, Ohio University; Zane C. Motteler, California Polytechnic State University; Tony P. Ng, University of Illinois-Urbana; Rick Ruth, Shippensburg University; Ryan Stansifer, University of North Texas.
A quote from the preface to the Concise Oxford Dictionary edited by Henry W. Fowler impressed me many years ago:
``A dictionary-maker, unless he is a monster of omniscience, must deal with a great many matters of which he has no firsthand knowledge. That he has been guilty of errors and omissions in some of these he will learn soon after publication, sometimes with gratitude to his enlightener, sometimes otherwise.''
I have tried to make this book as error-free as possible by testing most of the code myself. In a few cases, where language translators were not directly available to me, I relied on others, or my own reading of language manuals or research papers. I would be grateful to all readers willing to supply me with corrections of any errors that may have gone undetected.
K.C.L.