本书介绍了程序设计语言的一般概念，包括程序设计语言的语法和语义，涉及命令式语言、面向对象语言、函数式语言、逻辑式语言和并行语言等多种范例，分析了各种语言的设计原理和内在机制，讨论了语言的理论基础和实现时必须考虑的问题。\r\n\r\n 本书可用于计算机及其相关专业学生的双语教材，软件与理论专业研究生相关课程的参考书，也可供计算机专业人员参考。\r\n
\r\n
1 Introduction 1 \r\n\r\n 1.1 What Is a Programming Language? 2 \r\n\r\n 1.2 Abstractions in Programming Languages 5 \r\n\r\n 1.3 Computational Patadigms 13 \r\n\r\n 1.4 Language Definition 20 \r\n\r\n 1.5 Language Translation 22 \r\n\r\n 1.6 Language Design 29 \r\n\r\n Exercises 30 \r\n\r\n Notes and References 33 \r\n\r\n 2 History 34 \r\n\r\n 2.1 Early History: The First Programmer 35 \r\n\r\n 2.2 The 1950s: The First Programming Languages 37 \r\n\r\n 2.3 The 1960s: An Explosion in Programming Languages 39 \r\n\r\n 2.4 The 1970s, Simplicity, Abstraction, Study 42 \r\n\r\n 2.5 The 1980s: New Directions and the Rise \r\n\r\n of Object-Orientation 43 \r\n\r\n 2.6 The 1990s: Consolidation, the Internet, Libraries, \r\n\r\n and Scripting 46 \r\n\r\n 2.7 The Future 49 \r\n\r\n Exercises 50 \r\n\r\n Notes and References 53 \r\n\r\n 3 Language Design Principles 55 \r\n\r\n 3.1 History and Design Criteria 57 \r\n\r\n 3.2 Efficiency 59 \r\n\r\n 3.3 Regularity 60 \r\n\r\n 3.4 Further Language Design Principles 63 \r\n\r\n 3.5 C++: A Case Study in Language Design 68 \r\n\r\n Exercises 72 \r\n\r\n Notes and References 76 \r\n\r\n 4 Syntax 77 \r\n\r\n 4.1 Lexical Structure of Programming Languages 78 \r\n\r\n 4.2 Context-Free Grammars and BNFs 83 \r\n\r\n 4.3 Parse Trees and Abstract Syntax Trees 89 \r\n\r\n 4.4 Ambiguity, Associativity, and Precedence 92 \r\n\r\n 4.5 EBNFs and Syntax Diagrams 97 \r\n\r\n 4.6 Parsing Techniques and Tools 101 \r\n\r\n 4.7 Lexics versus Syntax versus Semantics 113 \r\n\r\n Exercises 115 \r\n\r\n Notes and References 123 \r\n\r\n 5 Basic Semantice 125 \r\n\r\n 5.1 Attributes, Binding, and Semantic Functions 126 \r\n\r\n 5.2 Declarations, Blocks, and Scope 130 \r\n\r\n 5.3 The Symbol Table 139 \r\n\r\n 5.4 Name Resolution and Overloading 152 \r\n\r\n 5.5 Allocation, Lifetimes, and the Environment 159 \r\n\r\n 5.6 Variables and Constants 167 \r\n\r\n 5.7 Aliases, Dangling References, and Garbage 174 \r\n\r\n Exercises 180 \r\n\r\n Notes and References 187 \r\n\r\n 6 Data Types 189 \r\n\r\n 6.1 Data Types and Type Information 192 \r\n\r\n 6.2 Simple Types 197 \r\n\r\n 6.3 Type Constructors 200 \r\n\r\n 6.4 Type Nomenclature in Sample Languages 215 \r\n\r\n 6.5 Type Equivalence 218 \r\n\r\n 6.6 Type Checking 225 \r\n\r\n 6.7 Type Conversion 231 \r\n\r\n 6.8 Polymorphic Type Checking 235 \r\n\r\n 6.9 Explicit Polymorphism 244 \r\n\r\n Exercises 250 \r\n\r\n Notes and References 258 \r\n\r\n 7 Control I-Expressions and Statements 260 \r\n\r\n 7.1 Expressions 262 \r\n\r\n 7.2 Conditional Statements and Guards 270 \r\n\r\n 7.3 Loops and Variation on WHILE 276 \r\n\r\n 7.4 The GOTO Controversy 280 \r\n\r\n 7.5 Exception Handling 282 \r\n\r\n Exercises 299 \r\n\r\n Notes and References 307 \r\n\r\n 8 Control II-Procedures and Environments 309 \r\n\r\n 8.1 Procedure Definition and Activation 311 \r\n\r\n 8.2 Procedure Semantics 313 \r\n\r\n 8.3 Parameter Passing Mechanisms 317 \r\n\r\n 8.4 Procedure Environments, Activations, and Allocation 325 \r\n\r\n 8.5 Dynamic Memory Management 340 \r\n\r\n 8.6 Exception Handling and Environments 344 \r\n\r\n Exercises 346 \r\n\r\n Notes and References 355 \r\n\r\n 9 Abstract Data Types and Modules 356 \r\n\r\n 9.1 The Algebraic Specification of Abstract Data Types 359 \r\n\r\n 9.2 Abstract Data Type Mechanisms and Modules 364 \r\n\r\n 6.3 Type Constructors 200 \r\n\r\n 6.4 Type Nomenclature in Sample Languages 215 \r\n\r\n 6.5 Type Equivalence 218 \r\n\r\n 6.6 Type Checking 225 \r\n\r\n 6.7 Type Conversion 231 \r\n\r\n 6.8 Polymorphic Type Checking 235 \r\n\r\n 6.9 Explicit Polymorphism 244 \r\n\r\n Exercises 250 \r\n\r\n Notes and References 258 \r\n\r\n 7 Control I-Expressions and Statenlents 260 \r\n\r\n 7.1 Expressions 262 \r\n\r\n 7.2 Conditional Statements and Guards 270 \r\n\r\n 7.3 Loops and Variation on WHILE 276 \r\n\r\n 7.4 The GOTO Controversy 280 \r\n\r\n 7.5 Exception Handling 282 \r\n\r\n Exercises 299 \r\n\r\n Notes and References 307 \r\n\r\n 8 Control II-Procedures and Environments 309 \r\n\r\n 8.1 Procedure Definition and Activation 311 \r\n\r\n 8.2 Procedure Semantics 313 \r\n\r\n 8.3 Parameter Passing Mechanisms 317 \r\n\r\n 8.4 Procedure Environments, Activations, and Allocation 325 \r\n\r\n 8.5 Dynamic Memory Management 340 \r\n\r\n 8.6 Exception Handling and Environmenn 344 \r\n\r\n Exercises 346 \r\n\r\n Notes and References 355 \r\n\r\n 9 Abstract Data Types and Modules 356 \r\n\r\n 9.1 The Algebraic Specification of Abstract Data Types 359 \r\n\r\n 9.2 Abstract Data Type Mechanisms and Modules 364 \r\n\r\n 9.3 Separate Compilation in C, C++ Namespaces \r\n\r\n and Java Packages 368 \r\n\r\n 9.4 Ada Packages 375 \r\n\r\n 9.5 Modules in ML 381 \r\n\r\n 9.6 Modules in Earlier Languages 385 \r\n\r\n 9.7 Problems with Abstract Data Type Mechanisms 390 \r\n\r\n 9.8 The Mathematics of Abstract Data Types 398 \r\n\r\n Exercises 402 \r\n\r\n Notes and References 407 \r\n\r\n 10 Object-Oriented Programming 409 \r\n\r\n 10.1 Software Reuse and Independence 410 \r\n\r\n 10.2 Java: Objects, Classes, and Methods 413 \r\n\r\n 10.3 Inheritance 419 \r\n\r\n 10.4 Dynamic Binding 431 \r\n\r\n 10.5 C++ 434 \r\n\r\n 10.6 Smalltalk 446 \r\n\r\n 10.7 Design Issues in Object-Oriented Languages 452 \r\n\r\n 10.8 Implementation Issues in Object-Oriented Languages 456 \r\n\r\n Exercises 462 \r\n\r\n Notes and References 470 \r\n\r\n 11 Functional Programming 471 \r\n\r\n 11.1 Programs as Functions 473 \r\n\r\n 11.2 Functional Programming in an Impertive Language 476 \r\n\r\n 11.3 Scheme: A Dialect of LISP 481 \r\n\r\n 11.4 ML: Functional Programming with Static Typing 494 \r\n\r\n 11.5 Delayed Evaluation 507 \r\n\r\n 11.6 Haskell-A Fully-Curried Lazy Language with Overloading 512 \r\n\r\n 11.7 The Mathematic of Functional Programming I: \r\n\r\n Recursive Functions 520 \r\n\r\n 11.8 The Mathematics of Functional Programming II: \r\n\r\n Lambda Calculus 524 \r\n\r\n Exercises 529 \r\n\r\n Notes and References 537 \r\n\r\n l2 Logic Programming 539 \r\n\r\n 12.1 Logic and Logic Programs 541 \r\n\r\n 12.2 Hom Clauses 545 \r\n\r\n 12.3 Resolution and Unification 548 \r\n\r\n 12.4 The Language Prolog 552 \r\n\r\n 12.5 Problems with Logic Programming 563 \r\n\r\n 12.6 Extending Logic Programming: Constraint Logic Programming \r\n\r\n and Equational Systems 568 \r\n\r\n Exercises 572 \r\n\r\n Notes and References 577 \r\n\r\n 13 Formal Semantics 579 \r\n\r\n 13.1 A Sample Small Language 581 \r\n\r\n 13.2 Operational Semantics 585 \r\n\r\n 13.3 Denotational Semantics 595 \r\n\r\n 13.4 Axiomatic Semantics 604 \r\n\r\n 13.5 Proofs of Program Correctness 611 \r\n\r\n Exercises 614 \r\n\r\n Notes and References 619 \r\n\r\n 14 Parollel Programming 620 \r\n\r\n 14.1 Introduction to Parallel Processing 622 \r\n\r\n 14.2 Parallel Processing and Programming Languages 626 \r\n\r\n 14.3 Threads 634 \r\n\r\n 14.4 Semaphores 643 \r\n\r\n 14.5 Monitors 648 \r\n\r\n 14.6 Message Passing 654 \r\n\r\n 14.7 Parallelism in Non-Imperative Languages 660 \r\n\r\n Exercises 665 \r\n\r\n Notes and References 671 \r\n\r\n Bibliography 673 \r\n\r\n Index 685 \r\n
\r\n
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 contains significant material on implementation issues, the theoretical foundations of programming languages, and a large number of exercises.
All of these features make this text a useful bridge to compiler courses and to the theoretical study of programming languages. However, it is a text specifically designed for an advanced undergraduate programming languages survey course that covers most of the progamming languages requirements specified in the 2001 ACM/IEEE-CS Joint Curriculum Task Force Report, and the CS8 coure of the 1978 ACM Curriculum.
My-goals in preparing this new edition are to bring the language-specific material in line with the changes in the popularity and use of programming languages since the publication of the first edition in 1993, to improve and expand the coverage in certain areas, and to improve the presentation and usefulness of the examples and exercises, while retaining as much of the original text and organitization as possible.
Students are not expected to know any one particular Ianguage.
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. Major languages used in this edition include C, C+ +, Java, Ada, ML, Haskell, Scheme, and Prolog; many other languages are discussed more briefly.
In most cases, each chapter largely is independent of the others without artificially restricting the material in each. Cross references in the text allow the student or instructor to fill in any gaps that might ariae even if a particular chapter or section is skipped.
Chapter l surverys the concepts studied in later chapters, and introduces the different language paradigms with simple examples in typical languages.
Chapters 2 and 3 provide overiews of the history of programming languages and language deslgn principles, respectively. Chapter 3 could serve well 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 recurive definitions (like BNF) as set equations to be solved, a view that recure periodically throughout the text. One section is devoted to recursive-descent parsing and the use of parsing tools.
Chapters 5, 6, 7, and 8 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; procedure activation and parameter passing; and exceptions and exception handling.
Chapter 9 gives an overview of modules and abstract, data types,
including language mechanisms and equational, or algebraic, specification.
Chapters 10, 11, 12, and 13 address language paradigms, beginning
with the object-oriented paradigms in Chapter 10. I use Java to introduce the concepts in this chapter. Individual sections feature C++ and Smalltalk. Chapter 11 deals with the functional paradigm. Each of the languages Scheme, ML, and Haskell are covered in some detail. This
chapter also introduces the lambda calculus and the theory of recurive function definitions. Chapter 12, on logic programming, offers an extended section on Prolog, and devotes one section to equational languages such as OBJ.
Chapter 13 introduces the three principal methods of formal semantics: operational, denotational, and axiomatic. This is somewhat unique among introductory texts in that it gives enough detail to provide a real flavor for the methods.
Chapter 14 treats the major ways parallelism has been introduced into programming languages: corouatines, threads, semaphores, monitors, and message passing, with examples primarily from Java and Ada. Its final section surveys recent efforts to introduce parallelism into LISP and Prolog.
Use as a Text
I have used this text for more than ten years in my CS 152 classes of upper division computer science majors and graduate students at San Jose State University. 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 follow:
The principles approach: Chapters l, 4, 5, 6, 7, 8, and 9. If there is extra time, Chapters 2 and 3.
The parading approach: Chapters 1, 10, 11, 12, 13, and 14 (not necessarily in that order). If there is extra time, Chapters 2 and 3, Or selected topics from the remaining chapters.
In a two-semester or two-quarter sequence it should be possible to cover most of the book.
Selected answers for many of the exercises at the end of each chapter may be found at www.brookscole.com or on the author's Web. site, www.cs.sisu.edu/faculty/louden. Many are programming exercises (none extremely long) in languages discussed in the text. Conceptual exercise range from the short-answer type that test understanding of the material to longer. essay-style exercises and challenging "thought" questions. A few moments' renection should give the reader adequate insight into the potential difficulty of a particular exercise. Further knowledge can be gained by reading the on-line 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.
Throughout the book I have tried to improve the usefulness of the code examples by adding line numbers where appropriate, and by augmenting many examples with main program drivers that allow them to be executed to demonstrate their described behavior. AII such examples, as well as a number of others (in which, for space or other reasons, such extra code was sunpressed), are available through www.brookscole.com or the author's Web site listed above. These Web sites also contain links to free, downloadable translators for all the major languages of the book, many of which I have used to test the examples. Other materials may also be available .
Summary of Changes between
the First and Second Editions
In the first edition, I used examples from the most widely known imperative languages, including C, Pascal, Ada, Modula-2, and FORTRAN, as well as some of the less widely known Ianguages representing other language paradigms, such as Scheme, ML, Miranda , C+ +, Eiffel, SmalItalk, and Prolog. The most extensive change in the current edition is the replacement of Pascal and Modula-2 largely by C, C++, and Java in the examples. Modula-2 has disappeared, except for a "historical" section in Chapter 9, on ADTs; a few examples in Pascal remain. I also use Ada quite a bit, especially for features that are not well represented. in C/C++//Java (e.g., subranges, arrays and slices, name equivalence of data tvpes). Java replaces Simula as the primary example in Chapter 10, On object-oriented programming languages, and I eliminated the section on Eiffel. l devote considerably more space to ML and Haskell in Chapter 11, on functional languages, and I added ML examples liberaIly throughout the book. Finally, I use Java threads as the basic example of concurrency in Chapter 14, on parallel programming languages. Additional significant cnanges are as tollows:
I split off procedures and environments from the rest of the control material, so Chapter 7 now treats control expressions and statements.
and the new Chapter 8 treats control procedures and environments.
l moved expressions from the end of Chapter 5, on basic semantics,
to the beginning of Chapter 7. Because in most cases some implicit
or explicit control is inherent in evaluating expressions, this topic fits well with other control issues.
I include overloading with the symbol table material in Chapter 5,
because it essentially is a symbol table task to disambiguate overloaded identifiers. While this presents a "phase order" problem with chapter 6, or data cypes—the type signature being the primary
attribute used in overload resolution—the amount of data type infor-
mation needed to understand overload resolution is not great, and
the material seems more natural pressented in this way.
I include parametric polymorphism with the discussion of type checking in Chapter 6, in which I also give a more extensive account of
Hindley-Milner polymorphic type checking. Parametric polymophism comes up again in Chapter 9 in discussing Ada packages.
and in Chapter 10 in discussing C++ class templates.
I rewrote Chapter 9 on ADTs and modules to emphasize modules a bit more and changed its title to include modules. This topic is more challenging than most to present concisely, because the design of ADT and module mechanisms differs more widely among common languages than any other teature except, possibly, concurrency mechanisms. Iuse ML and Ada as the major examples here, with some additional material on C++ namespaces and Java packages. I defer the use of classes to represent ADTs and modules to Chapter 10 on object-oriented programming I do not mention the scripting languages, such as Perl, JavaScript, and TCL, extensively in this text (except for a brief section in Chapter 2). While the use of such languages is widespread and increasing. par ticularly for Web applications and saldent interest in them is intese, I still consider them somewhat too special-purpose for this text. However, nothing would prevent the interested instructor from providing examples in these languages of virtually every major language teature.
I also do not cover any "visual" Ianguages or component assembly tools, such as Visual Basic or various JavaBean tools". My view is that these "languages" are better studied in a OUI or sofware engineering course. Similarly, I only mention the various markup languages such as XML, SGML, and HTML, in passing.
Acknowledgntents
I would like to thank all those persons too namerous to mention who, over the years, have emailed me with commets, corrections, and suggestions. l especially thank the reviewers of this edition for their many usetuI suggestions and comments: Leonard M. Faltz of Arizona State university, Tesse Yu of the College of St. Elizabeth, Mike Frazier of Abilene Christian Unniversity, Ariel Ortiz Ramtirez of ITESM Campus Estado de Mexico, Tames J. Ball of Indiana State University, Samuel A. Rebelsky of Grinnell College, and Arthur Fleck of the University of lowa.
I aIso thank Eran Yahav of Tel-Aviv University for reading and commenting on Chapter 14 on concurrency, and Hamilton Kichards of the University of Texas for his comments and suggesttions on survey Chapter l and Chapter 11, on functional programming.
I remain grateful to the many students in my CS 152 sections at San Jose State University for their direct and indirect contributions to this edition and to the previous edition; to my colleagues at San Jose State, Michael Beeson, Cay Hortmann, and Vinh Phat, who fead and commented on individual chapters in the first edition;and to the reviewers of that edition, Ray Fanselau of American River College, Larry lrwin of Ohio University, Zane C. Motteler of California Polytechnic State University, Tony P. Ng of the University of Illinois-Urbana, Rick Ruth of Shippensburg University of Pennsylvania, and Ryan Stansiter of the University of North Texas.
Of course, I alone am responsible for the shortcomings and errors in this book. I am happy to receive reports of errors and any other comments from readers at louden@cs.sjsu.edu.
I particularly thank Kallie Swanson, computer science editor at Brooks/Cole, for her encouragement and patience during the seemingly endless process of revision. A special thank is owed to Marjorie Schlaikier, who first convinced me to write this book.
Finally, l give my thanks and appreciation, as ever, for the patience, support, and love of my wife, Margreth, and my sons, Andrew and Robin. Without you, much of this would never have happened.
第二书店&China-pub战略联盟提供专业服务
第二书店联系方式 010-64348411 webmaster@dearbook.com