Programming Language Pragmatics / Edition 3

by Michael Scott

Overview

Programming Language Pragmatics addresses the fundamental principles at work in the most important contemporary languages, highlights the critical relationship between language design and language implementation, and devotes special attention to issues of importance to the expert programmer. Thanks to its rigorous but accessible teaching style, you’ll emerge better prepared to choose the best language for particular projects, to make more effective use of languages you already know, and to learn new languages quickly and completely.

Features

• Addresses the most recent developments in programming language design, spanning more than forty different languages, including Ada 95, C, C++, Fortran 95, Java, Lisp, Scheme, ML, Modula-3, Pascal, and Prolog.
• Places a special emphasis on implementation issues—how the techniques used by compilers and related tools influence language design, and vice versa.
• Covers advanced topics in language design and implemenation, such as iterators, coroutines, templates (generics), separate compilation, I/O, type inference, and exception handling.
• Reviews language-related topics in assembly-level architecture critical for understanding what a compiler does to a program.
• Offers in-depth coverage of object-oriented programming, including multiple inheritance and dynamic method binding.
• Devotes a special section to static and dynamic linking.
• Includes a comprehensive chapter on concurrency, with detailed coverage of both shared-memory and message-passing languages and libraries.
• Provides an accessible introduction to the formal foundations of compilation (automata theory), functional programming (lambda calculus), and logic programming (predicate calculus).

About the Author
Michael L. Scott is a professor in the University of Rochester's Department of Computer Science, which he chaired from 1996 to 1999. He is the designer of the Lynx distributed programming language and a co-designer of the Charlotte and Psyche parallel operating systems, the Bridge parallel file system, the Cashmere distributed shared memory system, and the MCS mutual exclusion lock. He received his Ph.D. from the University of Wisconsin-Madison in 1985.

Product Details

ISBN-13:	2900123745148
Publication date:	03/23/2009
Pages:	944
Product dimensions:	6.00(w) x 1.25(h) x 9.00(d)

About the Author

Michael L. Scott is a professor and past Chair of the Computer Science Department at the University of Rochester. He is best known for work on synchronization and concurrent data structures: algorithms from his group appear in a wide variety of commercial and open-source systems. A Fellow of the ACM and the IEEE, he shared the 2006 Dijkstra Prize in Distributed Computing. In 2001 he received the University's Robert and Pamela Goergen Award for Distinguished Achievement and Artistry in Undergraduate Teaching.

Table of Contents

What People are Saying About This

From the Publisher

The classic comprehensive programming language text that combines language design and language implementation, thoroughly updated to cover the most recent developments in programming language design

From the B&N Reads Blog

Page 1 of

Related Subjects

Computers

Computer Programming

Software Engineering

General Software Engineering

Software Development * Programming

Computers

Computer Programming

Software Engineering

General Software Engineering

Software Development * Programming

Editorial Reviews

This textbook for a programming languages course focuses on concepts that underlie all of the languages normally encountered, illustrating those concepts with examples from various languages. Language design and implementation are explored together, with an emphasis on the ways in which they interact. Annotation c. Book News, Inc., Portland, OR (booknews.com)

Booknews

"This book is a key resource for any computer science student and is certainly faithful to its title - Programming Language Pragmatics…. The updated third edition of this popular book delivers the key concepts of programming languages and their implementation in a concise and intuitive way, illustrated with clear explanations and examples…. In addition to the coverage of traditional language topics, Scott’s book delves into the sometimes obscure, but essential, details of programming artifacts. The descriptions of language theory, along with concrete implementations of how to realise them, are invariably presented in a language-agnostic fashion. And therein lies the strength of this book: whilst the main examples have been updated (with C and Intel x86 replacing Pascal and MIPS), it provides an organisational framework for learning new languages, irrespective of the paradigm…. Programming Language Pragmatics provides a more accessible introduction to many of the key topics than the classic Compilers: Principles, Techniques and Tools by Aho et al. (a.k.a. the ‘Dragon Book’) and provides a deep appreciation of the design and implementation issues of modern languages…. The material is aimed at an undergraduate computer science level, but is also suitable for self-study. Topics are often independent of previously presented material, making it easier to pick and choose areas for study. This is also supported by additional in-depth material and advanced discussion topics on the companion CD…. In summary, this new edition provides both students and professionals alike a solid understanding of the most important issues driving software development today - an essential purchase for any serious programmer or computer scientist!" —BCS.com

From the Publisher

Customer Reviews

	About the Author	ii
	Preface	xvii
Chapter 1	Introduction	1
1.1	The Art of Language Design	3
1.2	The Programming Language Spectrum	5
1.3	Why Study Programming Languages?	7
1.4	Compilation and Interpretation	9
1.5	Programming Environments	14
1.6	An Overview of Compilation	15
1.6.1	Lexical and Syntax Analysis	16
1.6.2	Semantic Analysis and Intermediate Code Generation	18
1.6.3	Target Code Generation	22
1.6.4	Code Improvement	24
1.7	Summary and Concluding Remarks	24
1.8	Review Questions	25
1.9	Exercises	26
1.10	Bibliographic Notes	28
Chapter 2	Programming Language Syntax	31
2.1	Specifying Syntax: Regular Expressions and Context-Free Grammars	32
2.1.1	Tokens and Regular Expressions	33
2.1.2	Context-Free Grammars	34
2.1.3	Derivations and Parse Trees	36
2.2	Recognizing Syntax: Scanners and Parsers	39
2.2.1	Scanning	40
2.2.2	Top-Down and Bottom-Up Parsing	48
2.2.3	Recursive Descent	51
2.2.4	Syntax Errors	57
2.2.5	Table-Driven Top-Down Parsing	62
2.2.6	Bottom-Up Parsing	75
2.3	Theoretical Foundations	87
2.3.1	Finite Automata	88
2.3.2	Push-Down Automata	92
2.3.3	Grammar and Language Classes	93
2.4	Summary and Concluding Remarks	94
2.5	Review Questions	97
2.6	Exercises	98
2.7	Bibliographic Notes	102
Chapter 3	Names, Scopes, and Bindings	105
3.1	The Notion of Binding Time	106
3.2	Object Lifetime and Storage Management	108
3.2.1	Stack-Based Allocation	111
3.2.2	Heap-Based Allocation	113
3.2.3	Garbage Collection	114
3.3	Scope Rules	115
3.3.1	Static Scope	116
3.3.2	Dynamic Scope	129
3.3.3	Symbol Tables	132
3.3.4	Association Lists and Central Reference Tables	137
3.4	The Binding of Referencing Environments	139
3.4.1	Subroutine Closures	141
3.4.2	First- and Second-Class Subroutines	143
3.5	Overloading and Related Concepts	144
3.6	Naming-Related Pitfalls in Language Design	149
3.6.1	Scope Rules	149
3.6.2	Separate Compilation	151
3.7	Summary and Concluding Remarks	155
3.8	Review Questions	157
3.9	Exercises	158
3.10	Bibliographic Notes	162
Chapter 4	Semantic Analysis	165
4.1	The Role of the Semantic Analyzer	166
4.2	Attribute Grammars	168
4.3	Attribute Flow	170
4.4	Action Routines	179
4.5	Space Management for Attributes	180
4.5.1	Bottom-Up Evaluation	181
4.5.2	Top-Down Evaluation	186
4.6	Annotating a Syntax Tree	191
4.7	Summary and Concluding Remarks	197
4.8	Review Questions	198
4.9	Exercises	199
4.10	Bibliographic Notes	202
Chapter 5	Assembly-Level Computer Architecture	203
5.1	Workstation Macro-Architecture	204
5.2	The Memory Hierarchy	207
5.3	Data Representation	209
5.3.1	Integer Arithmetic	211
5.3.2	Floating-Point Arithmetic	212
5.4	Instruction Set Architecture	214
5.4.1	Addressing Modes	215
5.4.2	Conditional Branches	217
5.5	The Evolution of Processor Architecture	218
5.5.1	Two Example Architectures: The 680x0 and MIPS	220
5.5.2	Pseudoassembler Notation	225
5.6	Compiling for Modern Processors	227
5.6.1	Keeping the Pipeline Full	227
5.6.2	Register Allocation	234
5.7	Summary and Concluding Remarks	242
5.8	Review Questions	243
5.9	Exercises	244
5.10	Bibliographic Notes	247
Chapter 6	Control Flow	249
6.1	Expression Evaluation	250
6.1.1	Precedence and Associativity	251
6.1.2	Assignments	254
6.1.3	Ordering Within Expressions	262
6.1.4	Short-Circuit Evaluation	265
6.2	Structured and Unstructured Flow	267
6.3	Sequencing	270
6.4	Selection	271
6.4.1	Short-Circuited Conditions	272
6.4.2	Case/Switch Statements	275
6.5	Iteration	280
6.5.1	Enumeration-Controlled Loops	280
6.5.2	Combination Loops	286
6.5.3	Iterators	287
6.5.4	Logically Controlled Loops	294
6.6	Recursion	297
6.6.1	Iteration and Recursion	297
6.6.2	Applicative- and Normal-Order Evaluation	301
6.7	Nondeterminacy	303
6.8	Summary and Concluding Remarks	308
6.9	Review Questions	310
6.10	Exercises	311
6.11	Bibliographic Notes	316
Chapter 7	Data Types	319
7.1	Type Systems	320
7.1.1	The Definition of Types	322
7.1.2	The Classification of Types	323
7.2	Type Checking	330
7.2.1	Type Equivalence	330
7.2.2	Type Conversion and Casts	334
7.2.3	Type Compatibility and Coercion	337
7.2.4	Type Inference	341
7.2.5	The ML Type System	344
7.3	Records (Structures) and Variants (Unions)	351
7.3.1	Syntax and Operations	351
7.3.2	Memory Layout and Its Impact	353
7.3.3	With Statements	355
7.3.4	Variant Records	358
7.4	Arrays	365
7.4.1	Syntax and Operations	365
7.4.2	Dimensions, Bounds, and Allocation	369
7.4.3	Memory Layout	373
7.5	Strings	379
7.6	Sets	381
7.7	Pointers and Recursive Types	382
7.7.1	Syntax and Operations	383
7.7.2	Dangling References	391
7.7.3	Garbage Collection	395
7.8	Lists	401
7.9	Files and Input/Output	403
7.9.1	Interactive I/O	404
7.9.2	File-Based I/O	405
7.9.3	Text I/O	407
7.10	Equality Testing and Assignment	414
7.11	Summary and Concluding Remarks	416
7.12	Review Questions	418
7.13	Exercises	420
7.14	Bibliographic Notes	425
Chapter 8	Subroutines and Control Abstraction	427
8.1	Review of Stack Layout	428
8.2	Calling Sequences	431
8.2.1	Case Study: C on the MIPS	434
8.2.2	Case Study: Pascal on the 680x0	437
8.2.3	In-Line Expansion	441
8.3	Parameter Passing	442
8.3.1	Parameter Modes	443
8.3.2	Special-Purpose Parameters	453
8.3.3	Function Returns	457
8.4	Generic Subroutines and Modules	459
8.5	Exception Handling	464
8.5.1	Definition of Exceptions	466
8.5.2	Exception Propagation	468
8.5.3	Example: Phrase-Level Recovery in a Recursive Descent Parser	470
8.5.4	Implementation of Exceptions	471
8.6	Coroutines	474
8.6.1	Stack Allocation	476
8.6.2	Transfer	478
8.6.3	Iterators	479
8.6.4	Example: Discrete Event Simulation	480
8.7	Summary and Concluding Remarks	484
8.8	Review Questions	485
8.9	Exercises	486
8.10	Bibliographic Notes	489
Chapter 9	Building a Runnable Program	491
9.1	Back-End Compiler Structure	491
9.1.1	An Example	492
9.1.2	Phases and Passes	496
9.2	Intermediate Forms	496
9.2.1	Diana	498
9.2.2	GNU RTL	499
9.3	Code Generation	503
9.3.1	An Attribute Grammar Example	504
9.3.2	Register Allocation	504
9.4	Address Space Organization	507
9.5	Assembly	510
9.5.1	Emitting Instructions	511
9.5.2	Assigning Addresses to Names	514
9.6	Linking	515
9.6.1	Relocation and Name Resolution	515
9.6.2	Type Checking	516
9.7	Dynamic Linking	518
9.7.1	Position-Independent Code	519
9.7.2	Fully Dynamic (Lazy) Linking	521
9.8	Summary and Concluding Remarks	522
9.9	Review Questions	523
9.10	Exercises	524
9.11	Bibliographic Notes	527
Chapter 10	Data Abstraction and Object Orientation	529
10.1	Object-Oriented Programming	530
10.2	Encapsulation and Inheritance	539
10.2.1	Modules	539
10.2.2	Classes	542
10.2.3	Type Extensions	544
10.3	Intitialization and Finalization	546
10.3.1	Choosing a Constructor	547
10.3.2	References and Values	550
10.3.3	Execution Order	551
10.3.4	Garbage Collection	553
10.4	Dynamic Method Binding	554
10.4.1	Virtual and Nonvirtual Methods	555
10.4.2	Abstract Classes	557
10.4.3	Member Lookup	557
10.4.4	Related Concepts	561
10.5	Multiple Inheritance	564
10.5.1	Semantic Ambiguities	568
10.5.2	Replicated Inheritance	570
10.5.3	Shared Inheritance	572
10.5.4	Mix-In Inheritance	573
10.6	Object-Oriented Programming Revisited	574
10.6.1	The Object Model of Smalltalk	577
10.7	Summary and Concluding Remarks	580
10.8	Review Questions	582
10.9	Exercises	583
10.10	Bibliographic Notes	586
Chapter 11	Nonimperative Programming Models: Functional and Logic Languages	589
11.1	Historical Origins	590
11.2	Functional Programming	592
11.2.1	A Review/Overview of Scheme	594
11.2.2	Evaluation Order Revisited	604
11.2.3	Higher-Order Functions	609
11.2.4	Theoretical Foundations	612
11.2.5	Functional Programming in Perspective	622
11.3	Logic Programming	624
11.3.1	Prolog	625
11.3.2	Theoretical Foundations	641
11.3.3	Logic Programming in Perspective	646
11.4	Summary and Concluding Remarks	648
11.5	Review Questions	650
11.6	Exercises	651
11.7	Bibliographic Notes	657
Chapter 12	Concurrency	659
12.1	Background and Motivation	660
12.1.1	A Little History	660
12.1.2	The Case for Multithreaded Programs	663
12.1.3	Multiprocessor Architecture	667
12.2	Concurrent Programming Fundamentals	670
12.2.1	Communication and Synchronization	671
12.2.2	Languages and Libraries	672
12.2.3	Thread Creation Syntax	673
12.2.4	Implementation of Threads	682
12.3	Shared Memory	687
12.3.1	Busy-Wait Synchronization	688
12.3.2	Scheduler Implementation	692
12.3.3	Scheduler-Based Synchronization	694
12.3.4	Implicit Synchronization	703
12.4	Message Passing	706
12.4.1	Naming Communication Partners	706
12.4.2	Sending	710
12.4.3	Receiving	714
12.4.4	Remote Procedure Call	719
12.5	Summary and Concluding Remarks	722
12.6	Review Questions	724
12.7	Exercises	725
12.8	Bibliographic Notes	730
Chapter 13	Code Improvement	733
13.1	Phases of Code Improvement	735
13.2	Peephole Optimization	737
13.3	Redundancy Elimination in Basic Blocks	740
13.4	Global Redundancy and Data Flow Analysis	745
13.4.1	Static Single Assignment Form and Global Value Numbering	746