Programming Lenguages: Concepts and Constructs, Second Edition retains the "character" of the original, emphasizing concepts and how they work together. This classic book has been thoroughly revised to provide readable coverage of imperative programming in Ianguages like Pascal and C flows smoothly into object-oriented programming in C++ and Smalltalk. The charm of fanctional languages in illustrated by programs in Standard ML and the Scheme dialect of Lisp. Logic programming is introduced using Prolog.
This book is designed for junior/senior level courses on programming languages. A minimal pre-requisite is an introductory programming course.With supplementary readings, the book can also be used for graduate courses.
What's New in this Edition
Changes on the language scene and feedback bom the use of the book have prompted a thorough revision. hTstructors liked the emphasis on concepts,but asked that the concepts be illushated using fewer languages. Meanwhile,Modula-2 has faded, and C++ has taken off as a language for production prpgramming. Candidates for functional languages now include Standard ML,Haskell, and Miranda.
The new edition has 15 chapters, three more than the first edition. The role of the three new chapters is as follows:
· Data types like arrays, records, and pointers have a new chapter.
· Functional programming is introduced using ML in a new chapter.
· Language summaries appear in a final chapter.
Language description and syntax are now treated early, in Chapter 2.
Organization of this Book
The emphasis is on concepls and how they work together, rather than on language features. Related concepts are therefore covered together, to allow meaningful examples and programming exercises along the way. Tust enough of a language is introduced, as needed, for the examples and exercises. Language summaries appear in Chapter 15.
Pan I: Introduction
Chapter I traces the role and development of programming languages. It introduces the programming paradigms in this book. They include imperative, object-oriented, functional, and logic programming.
Syntax description is treated in Chapter 2, so it can be applied in the rest of the book. The examples in the chapter deal with expressions, since methods for describing the syntax of expressions carry over to the rest of a language.
Part II: Imperative Programming
The imperative family is treated in Chapters 3-5. The term "imperative"comes from command or action: the computation model is that of a sequence of actions on an underlying machine.
Chapter 3 deals with control now. Structu,ecl constructs like while statements organize the aow of control so that the unit of programming is a structured statement, instead of an individual assignment. Students in a course that emphasizes imperative programming are usually familiar with Pascal, so this chapter goes beyond assignments and structured statements to consider programming with invariants. The examples deal with basic values, like integers, and arrays.
Chapter 4 deals with data in imperative languages. Data representation facilities such as arrays, records, and pointers, have been stable since Pascal and C appeared. The treatment of these facilities anticipates their use to represent obiects in Chapters 6 and 7.
Chapter 5 rounds out the discussion of the core of imperative languages,embodied in a language like Pascal or C. Among the topics are the distinction between the source text of a procedure and its activations, parameter passing,scope rules, and storage allocation.
This book illustrates imperative programming using Pascal, where possible. Pascal suffices as a vehicle for Chapters 3-5. C is an alternative.
Part III: Oblect.Oriented Programming
As programs get larger, the natural unit of programming is a grouping of da}a and operations. The progression of concepts for SLICh groupings can be described in terms of modu!es, user-defined types (for example, stacks), and classes (as in ob}ect-oriented programming).
Chapter 6 begins with of programming with procedures, modules, and classes. These constructs serve distinct needs and can be used in combination with each other: procedures are needed to implement operalions in a module or class; modules can be used to statically partition the source text of a program with classes. Some versions of Pascal suppoTt modules; they can be used for the first half of Chapter 6 as well. C++, an extension of C, is introduced in Chapter 6.
The model of computation in Chapter 7 is that of independent objects.The objects interact by sending messages to each other. The first third of the chapter introduces object-oriented programming in general, using a running example that has similar implementations in C++ and Smalltalk. The rest of the chapter has independent coverage of C++ and Smalltalk, so either one can be used to explore obiect-oriented programming. Based on feedback from instructors, this edition'covers C++ before Smalltalk, inverting the order in the previous edition. Obiect-oriented programmlng is illustrated using both C++and Smantalk, since the two represent different approaches.
AII of the concepts in Chapters 3-7 can be illustrated using C++. Students can be introduced directly to C++, with(}ut going through C.
Part IV: Functional Programming
Functional programming is worth studying as a programming style in its own right; as a setting for studying concepts sach as types; and as a technique tor language description. The emphasis in Chapter 8 is on concepts, in Chapters 9 and IO on programming style, and in Chapter 13 on language description.
The computational model is based on an expression interpreter; an expression consists of a functlon applied to subexpressions.The emphasis in Chapter 8 is on concepts. The simplicity of functional languages makes them convenlent for introducing concepts such as values,types, names, and functions. The simplicity results from the emphasis on expressions and values, independent of the underlying machine. The chapter treads ground common to functional languages, using ML as the working language.
The fundamental difference between ML and Lisp is that ML is typed; the inauence of types permeates the language. Chapter 9 uses ML to illustrate the use of functions and datatypes. As first-class citizens, functions have the same status as any other values in functional programming. This first-class status permits the creation of powerful operations on collections of data.
Functional programming originated with Lisp. Programs and data are both represented by lists in Lisp; the name is a contraction of "List Processor."The uniform use of lists makes Lisp eminently extensible. Chapter 10 explores the use of lists, using the Scheme dialect of Lisp.
See also Chapter 13, which contains an interpreter for a small subset of Scheme, and Chapter 14, which covers the lambda calculus.
Pan V: Other Paradigms
Logic programming goes hand in hand with Prolog, in Chapter Il. Logic progra-mnting deals with relations rather than functions. Where it fits, programs;re conci"se, consisting of facts and rules. The languages uses the facts and rules to deduce responses to queries.
Connlnent programming is illustrated using Ada, in Chapter 12. An alternative approach would have been to cover concurrent programmlng arter object-orienthh programmiog. Processn can be formed by giving each 0biect its own thread of computation. The present organization puts tunctional propammlng before concurrent programming.
Part VI:Language Description
The methods for language description in Chapter 13 are aimed at specialists.The methods range from attributes used for language translation,to logical rules for used type inference, to interpreters nsed for clarifying subtle language questions.
A language can be described by writing a definitional interpreter for it, socalled because its purpose is to define the interpreted language; efficiency is not a concem. McCadhy's & original definitional interpreter for Lisp in Lisp remains imponant for language description, so language description is illus trated using the Scheme dialect of Lisp. Chapter 13 develops an interpreter for a small subset of Scheme.
The lambda calculus is Ihe intellectual ancestor of functional languages.The small syntax of the lambda calculus has also led to its use as a vehicle'for studying languages. Variants of the lamMa calculus are inhoduced in Chapter 14. The chapter progresses from the pure untyped lambda calculus "to typed lambda calculi.
Chapler 15 contains brief summaries of the languages in this book.
Acknowledgments
From the First Edition A graduate seminar at Rutgers University gave me both the opporhlnity and the incentive to collect material on programming languages. I'd like to thank Alex Borgida, Martin Carroll, Fritz Henglein, Naftaly Minsky, Bob Paige. And Barbara Rytler for keeping the seminar lively.
An undergraduate course at Harvard University used an early draft of this book. Written comments by the students in the course were very helpful.
The organization of this book has benefited greatly from the comments and especially the criticism of the then anonymous reviewers contacted by Addison-Wesley. They are Tom Cheatham. Harvard University, John Crenshaw, Westem Kentucky University. Paul Hilfinger, University of California, Berkeley, Bamy Kurtz, New Mexico State University, Robert Noonan, College of William and Mary, Ron Olsson, University of California, Davis, William Pervin, University of Texas at Dallas, Paul Reynolds, University of Virginia,David Schmidt, Kansas State University, and Laurie Werth, University of Texas at Austin.
For all their technical help, I am grateful to AI Aho, Jon Bentley, Gerard Berry, Eric Cooper, Bruce Duba, Tom Ouncan, Rich Orechsler, Peggy Ellis,Charlie Fischer, Dan Friedman, Georges Gonthier, Bob Harper, Mike Hanison. Bruce Hillyer, Brian Kernighan, Kim King, Chandra Kintala, Dave MacQueet, Dianne Maki, Doug Mcllroy, John Mitchell, Mike O'Donnell, Dennis Ritchie, Bjarne Stroustrup, Chris Van Wyk, and Carl Woolf.
This book on Frogramming languages was produced with the help of a number of little languages. The diagrams were drawn using Brian Rich Drechsler. The tables were laid out using Mike Lesk's Tbl program. Eqn,Lorinda Chemy and Brian Kemighan's language for typesetting mathematics,handled the pseudo-code as well. The Troff program was originally wriffen by the late Joe Ossanna and is kept vital by Brian Kemighan. Page layout would have suffered without a new Troff macro package and post-processor by Brian Kemighan and Chris Van Wyk. The indexing programs were supplied by Jon Bentley and Bdan Kernighan. Cross references were managed usiog scripts wrifien with the help of AI Aho for managing the text of the"dragon" book.
Finally, I'd like to thank Bell Labs for its support. I have learnt more from my colleagues here than they might suspect. Whenever a question occurred,someone in the building always seemed to have Ihe answer.
I really appreciate the comments I have received on the tirst edition. The experience of insauctors and the bank opinions of reviewers have guided the revision.
Debbie Lafferty of Addison-Wesley has been the voice on the phone through the months, coordioating reviews and credits, and generally keeping the proiect on hack. I now know that the reviewers ioclude Bill Appelbe,Michael Barnett, Manuel E. Bermudez, Ray Ford, Aditya P. Mathur, L. A.Oldroyd, and Hamilton Richards - thanks.
For technical help and discussions, I am grateful to Jon Bentley, Lorinda Cherry, Brian Kernighan, Dave MacQueen, Jon Riecke, Bjarne Stroustrup, and Rich Wolf. My colleagues at Bell Labs have been greatly supportive.
A lot has happened while I have been immersed in the Book, including a death, a birth, a move, a fire. Dianne Maki has helped me navigate through it all.
The widespread use of programming languages began with the arrival of Fortran in 1957. It allowed scientists and engineers to write formulas using traditional symbols from mathematics -the use of + for addition dates back to the fifteenth century and the use of * for multiplication dates back to the seventeenth century. Such notations were therefore a natural staning point for the design of programming languages.
The formula b2 - 4acwas written in Fortran as the expressionB**2 - 4.O*A*C
Fortran takes its name from Formula Translation; readable formulas were translated into machine instructions for the IBM 704.Besides describing a result, a formula or expression x+y*z can be treated as an algorithm for computing the result. The algorithm is to multiply ywith z and add the result to x. An expression can therefore be translated into machine instmctions for evaluating the expression .Hundreds of programming languages have since been designed and implemented. Related programming languages are grouped into families; members of a family differ in taste more than substance. Having learned one member, it is easier to learn another,since concepts from one member carry over to other members of family.
Chapter 1 begins with the need for programming languages and goes on to introduce four approaches to programming: imperative functional, object-oriented, and logic programming. These approaches are explored in the rest of this book.Chapter 2 deals with language description. It introduces grammars, which are a notation for describing the syntax of programming languages.
(美)Ravi Sethi：Ravi Sethi: 自1976年起一直在新泽西州Murray Hill的AT&T贝尔实验室工作，是贝尔实验室计算科学研究中心的主任。他曾在宾夕法尼亚州立大学和亚利桑那大学担任教授，并曾在普林斯顿大学和Rutgers大学任教。他是著名的“龙书”（《编译器：原理和工具》）的作者之一，还写过许多文章。他的书已经被译为多种文字在世界范围流传。
1 INTRODUCTION
1 The Role of Programming Languages
1.1 Toward Higher-Level Languages
1.2 Problems of Scale
1.3 Programming Paradigms
1.4 Language Implementation: Bridging the Gap
EXERCISES
BIBLIOGRAPHIC NOTES
2 Language Description: Syntactic Structure
2.1 Expression Notations
2.2 Abstract Syntax Trees
2.5 Lexical Syntax
2.4 Context-Free Grammars
2.5 Grammars for Expressions
2.6 Variants of Grammars
EXERCISES
BIBLIOGRAPHIG NOTES
II IMPERATIVE PROGRAMMING
3 Statements: Structured Programming
3.1 The Need for Structured Programming
3.2 Syntax-Directed Control Flow
3.3 Design Considerations: Syntax
3.4 Handling Special Cases in Loops
S.5 Programming with Invariants
3.6 Proof Rules for Panial Correctness
3.7 Control flow in C
EXERCISES
BIBLIOGRAPHIC NOTES
4 Types: Data Representation
4.1 The Role of Types
4.2 Basic Types
4.3 Arrays: Sequences of Elements
4.4 Records: Named Fields
4.5 Unions and Variant Records
4.6 Sets
4.7 Pointers: ERiciency and Dynamic Allocation
4.e Two String Tables
4.9 Types and Error Checking
EXERCISES
BIBLIOGRAPHIC NOTES
5 Procedure Activations
5.1 Introduction to Procedures
5.2 Parameter-Passing Methods
5.3 Scope Rules for Names
5.4 Nested Scopes in the Source Text
5.5 Activation Records
5.8 Lexical Scope: Procedures as in C
5.7 Lexical Scope: Nested Procedures and Pascal
EXERCISES
BIBLIOGRAPHIC NOTES
III OBJECT-ORIENTED PROGRAMMING
6 Groupings of Data and Operations
6.1 Constructs for Program Structuring
6.2 Information Hiding
6.3 Program Design with Modules
6.4 Modules and Defined Types
6.5 Class Declarations in C++
6.6 Dynamic Allocation in C++
6.7 Templates: Parameterized Types
6.8 Implementation of Objects in C++
EXERCISES
BIBLIOGRAPHIC NOTES
7 Object-Oriented Programming
7.1 What is an Object
7.2 Object-Oriented Thinking
7.3 inheritance
7.4 Object-Oriented Programming in C++
7.5 An Extended C++ Example
7.6 Derived Classes and Information Hiding
7.7 Objects in Smalltalk
7.8 Smalltalk Objects have a Seff
EXERCISES
BIBLIOGRAPHIC NOTES
IV FUNCTIONAL PROGRAMMING
8 Elements of Functional Programming
8.1 A Little Language of Expressions
8.2 Types: Values and Operations
B.3 Function Declarations
8.4 Approaches to Expression Evaluation
8.5 Lexical Scope
B.6 Type Checking
EXERGISES
BIBLIOGRAPHIC NOTES
9 Functional Programming in a Typed Language
9.1 Exploring a List
9.2 Function Declaration by Cases
9.3 Functions as First-Class Values
9.4 ML: ImplicitTypes
9.5 DataTypes
9.6 Exception Handling in ML
9.7 Little Quilt in Standard ML
EXERCISES
BIBLIOGRAPHIC NOTES
10 Functional Programming with Lists
10.1 Scheme, a Dialect of Lisp
10.2 The Structure of Lists
10.3 List Manipulation
10.4 A Motivating Example: DiHerentiation
10.5 Simplification of Expressions
10.6 Storage Allocation for Lists
EXERCISES
BIBLIOGRAPHIC NOTES
V OTHER PARADIGMS
11 Logic Programming
11.1 Computing with Relations
11.2 Introduction to Proiog
11.3 Data Structures in Prolog
11.4 Programming Techniques
11.5 Control in Prolog
11.e Cuts
EXERCISES
BIBLIOGRAPHIC NOTES
12 An Introduction to Concurrent Programming
12.1 Parallelism in Hardware
12.2 Streams: Implicit Synchronization
12.3 Concurrency as Interleaving
12.4 Liveness Propenies
12.5 Safe Access to Shared Data
12.6 Concurrency in Ada
12.7 Synchronized Access to Shared Variables
EXERCISES
BIBLIOGRAPHIC NOTES
VI LANGUAGE DESCRIPTION
13 Semantic Methods
13.1 Synthesized Attributes
13.2 Attribute Grammars
13.3 Natural Semantics
13.4 Denotational Semantics
13.5 A Calculator in Scheme
13.6 Lexically Scoped Lambda Expressions
13.7 An Interpreter
13.8 An Extension: Recursive Functions
EXERCISES
BIBLIOGRAPHIC NOTES
14 Static Types and the Lambda Calculus
14.1 Equality of Pure Lambda Terms
14.2 Substitution Revisited
14.3 Computation with Pure Lambda Terms
14.4 Programming Constructs as Lambda-Terms
14.5 The Typed Lambda Calculus
14.6 Polymorphic Types
EXERCISES
BIBLIOGRAPHIC NOTES
15 A Look at Some Languages
15.1 Pascal: A Teaching Language
15.2 C: Systems Programming
15.3 C++: A Range of Programming Styles
15.4 Smalltalk, the Language
15.5 Standard ML
15.6 Scheme, a Dialect of Lisp
15.7 Prolog
Bibliography
Credits
Index
