Programming Language Pragmatics

by Scott

• ISBN13: 9780126339512
• ISBN10: 0126339511
• Edition: 2nd
• Format: Paperback
• Copyright: 2005-11-07
• Publisher: Elsevier Science

Summary

With the rise of virtual machines, scripting languages, mobile code, and graphical user interfaces, the need for an integrated treatment of language design and language implementation has never been greater. Programming Language Pragmatics stresses this sort of integration, while keeping its focus on programming language design. Both students and expert programmers alike will benefit from its comprehensive exploration of the fundamental concepts underlying the most important contemporary languages. Fully updated, this second edition includes a new chapter on scripting languages and covers C99, C# 2.0, and Java 5. Book jacket.

Author Biography

Michael L. Scott is a Professor and past Chair of the Department of Computer Science at the University of Rochester

Table of Contents

Foreword	ix
Preface	xxiii
I FOUNDATIONS	1	(230)
Introduction	3	(34)
The Art of Language Design	5	(3)
The Programming Language Spectrum	8	(3)
Why Study Programming Languages?	11	(2)
Compilation and Interpretation	13	(8)
Programming Environments	21	(1)
An Overview of Compilation	22	(9)
Lexical and Syntax Analysis	23	(2)
Semantic Analysis and Intermediate Code Generation	25	(3)
Target Code Generation	28	(2)
Code Improvement	30	(1)
Summary and Concluding Remarks	31	(1)
Exercises	32	(1)
Explorations	33	(2)
Bibliographic Notes	35	(2)
Programming Language Syntax	37	(66)
Specifying Syntax	38	(8)
Tokens and Regular Expressions	39	(3)
Context-Free Grammars	42	(1)
Derivations and Parse Trees	43	(3)
Scanning	46	(15)
Generating a Finite Automaton	49	(5)
Scanner Code	54	(4)
Table-Driven Scanning	58	(1)
Lexical Errors	58	(2)
Pragmas	60	(1)
Parsing	61	(33)
Recursive Descent	64	(6)
Table-Driven Top-Down Parsing	70	(10)
Bottom-Up Parsing	80	(13)
Syntax Errors CD 1	93	(1)
Theoretical Foundations CD 13	94	(1)
Finite Automata CD 13
Push-Down Automata CD 16
Grammar and Language Classes CD 17
Summary and Concluding Remarks	95	(1)
Exercises	96	(5)
Explorations	101	(1)
Bibliographic Notes	101	(2)
Names, Scopes, and Bindings	103	(58)
The Notion of Binding Time	104	(2)
Object Lifetime and Storage Management	106	(8)
Static Allocation	107	(2)
Stack-Based Allocation	109	(2)
Heap-Based Allocation	111	(2)
Garbage Collection	113	(1)
Scope Rules	114	(22)
Static Scope	115	(2)
Nested Subroutines	117	(2)
Declaration Order	119	(5)
Modules	124	(4)
Module Types and Classes	128	(3)
Dynamic Scope	131	(4)
Implementing Scope CD 23	135	(1)
Symbol Tables CD 23
Association Lists and Central Reference Tables CD 27
The Binding of Referencing Environments	136	(6)
Subroutine Closures	138	(2)
First- and Second-Class Subroutines	140	(2)
Binding Within a Scope	142	(7)
Aliases	142	(1)
Overloading	143	(2)
Polymorphism and Related Concepts	145	(4)
Separate Compilation CD 30	149	(1)
Separate Compilation in C CD 30
Packages and Automatic Header Inference CD 33
Module Hierarchies CD 35
Summary and Concluding Remarks	149	(2)
Exercises	151	(6)
Explorations	157	(1)
Bibliographic Notes	158	(3)
Semantic Analysis	161	(34)
The Role of the Semantic Analyzer	162	(4)
Attribute Grammars	166	(2)
Evaluating Attributes	168	(11)
Action Routines	179	(2)
Space Management for Attributes CD 39	181	(1)
Bottom-Up Evaluation CD 39
Top-Down Evaluation CD 44
Decorating a Syntax Tree	182	(5)
Summary and Concluding Remarks	187	(2)
Exercises	189	(4)
Explorations	193	(1)
Bibliographic Notes	194	(1)
Target Machine Architecture	195	(36)
The Memory Hierarchy	196	(3)
Data Representation	199	(2)
Computer Arithmetic CD 54	199	(2)
Instruction Set Architecture	201	(3)
Addressing Modes	201	(1)
Conditions and Branches	202	(2)
Architecture and Implementation	204	(6)
Microprogramming	205	(1)
Microprocessors	206	(1)
RISC	207	(1)
Two Example Architectures: The x86 and MIPS CD 59	208	(1)
Pseudo-Assembly Notation	209	(1)
Compiling for Modern Processors	210	(11)
Keeping the Pipeline Full	211	(5)
Register Allocation	216	(5)
Summary and Concluding Remarks	221	(2)
Exercises	223	(3)
Explorations	226	(1)
Bibliographic Notes	227	(4)
II CORE ISSUES IN LANGUAGE DESIGN	231	(290)
Control Flow	233	(74)
Expression Evaluation	234	(20)
Precedence and Associativity	236	(2)
Assignments	238	(8)
Initialization	246	(3)
Ordering Within Expressions	249	(3)
Short-Circuit Evaluation	252	(2)
Structured and Unstructured Flow	254	(6)
Structured Alternatives to goto	255	(4)
Continuations	259	(1)
Sequencing	260	(1)
Selection	261	(9)
Short-Circuited Conditions	262	(3)
Case/Switch Statements	265	(5)
Iteration	270	(17)
Enumeration-Controlled Loops	271	(6)
Combination Loops	277	(1)
Iterators	278	(6)
Generators in Icon CD 69	284	(1)
Logically Controlled Loops	284	(3)
Recursion	287	(8)
Iteration and Recursion	287	(4)
Applicative- and Normal-Order Evaluation	291	(4)
Nondeterminacy CD 72	295	(1)
Summary and Concluding Remarks	296	(2)
Exercises	298	(6)
Explorations	304	(1)
Bibliographic Notes	305	(2)
Data Types	307	(100)
Type Systems	308	(13)
Type Checking	309	(1)
Polymorphism	309	(2)
The Definition of Types	311	(1)
The Classification of Types	312	(7)
Orthogonality	319	(2)
Type Checking	321	(15)
Type Equivalence	321	(6)
Type Compatibility	327	(5)
Type Inference	332	(3)
The ML Type System CD 81	335	(1)
Records (Structures) and Variants (Unions)	336	(13)
Syntax and Operations	337	(1)
Memory Layout and Its Impact	338	(3)
With Statements CD 90	341	(1)
Variant Records	341	(8)
Arrays	349	(17)
Syntax and Operations	349	(4)
Dimensions, Bounds, and Allocation	353	(5)
Memory Layout	358	(8)
Strings	366	(1)
Sets	367	(2)
Pointers and Recursive Types	369	(20)
Syntax and Operations	370	(9)
Dangling References	379	(4)
Garbage Collection	383	(6)
Lists	389	(3)
Files and Input/Output CD 93	392	(1)
Interactive I/O CD 93
File-Based I/O CD 94
Text I/O CD 96
Equality Testing and Assignment	393	(2)
Summary and Concluding Remarks	395	(3)
Exercises	398	(6)
Explorations	404	(1)
Bibliographic Notes	405	(2)
Subroutines and Control Abstraction	407	(62)
Review of Stack Layout	408	(2)
Calling Sequences	410	(7)
Displays CD 107	413	(1)
Case Studies: C on the MIPS; Pascal on the x86 CD 111	414	(1)
Register Windows CD 119	414	(1)
In-Line Expansion	415	(2)
Parameter Passing	417	(17)
Parameter Modes	418	(8)
Call by Name CD 122	426	(1)
Special Purpose Parameters	427	(5)
Function Returns	432	(2)
Generic Subroutines and Modules	434	(7)
Implementation Options	435	(2)
Generic Parameter Constraints	437	(3)
Implicit Instantiation	440	(1)
Generics in C++, Java, and C# CD 125	440	(1)
Exception Handling	441	(12)
Defining Exceptions	443	(2)
Exception Propagation	445	(3)
Example: Phrase-Level Recovery in a Recursive Descent Parser	448	(1)
Implementation of Exceptions	449	(4)
Coroutines	453	(6)
Stack Allocation	455	(2)
Transfer	457	(1)
Implementation of Iterators CD 135	458	(1)
Discrete Event Simulation CD 139	458	(1)
Summary and Concluding Remarks	459	(1)
Exercises	460	(6)
Explorations	466	(1)
Bibliographic Notes	467	(2)
Data Abstraction and Object Orientation	469	(52)
Object-Oriented Programming	471	(10)
Encapsulation and Inheritance	481	(8)
Modules	481	(3)
Classes	484	(2)
Type Extensions	486	(3)
Initialization and Finalization	489	(8)
Choosing a Constructor	490	(1)
References and Values	491	(4)
Execution Order	495	(1)
Garbage Collection	496	(1)
Dynamic Method Binding	497	(14)
Virtual and Nonvirtual Methods	500	(1)
Abstract Classes	501	(1)
Member Lookup	502	(3)
Polymorphism	505	(3)
Closures	508	(3)
Multiple Inheritance CD 146	511	(1)
Semantic Ambiguities CD 148
Replicated Inheritance CD 151
Shared Inheritance CD 152
Mix-In Inheritance CD 154
Object-Oriented Programming Revisited	512	(1)
The Object Model of Smalltalk CD 158	513	(1)
Summary and Concluding Remarks	513	(2)
Exercises	515	(2)
Explorations	517	(1)
Bibliographic Notes	518	(3)
III ALTERNATIVE PROGRAMMING MODELS	521	(238)
Functional Languages	523	(36)
Historical Origins	524	(2)
Functional Programming Concepts	526	(2)
A Review/Overview of Scheme	528	(11)
Bindings	530	(1)
Lists and Numbers	531	(1)
Equality Testing and Searching	532	(1)
Control Flow and Assignment	533	(2)
Programs as Lists	535	(2)
Extended Example: DFA Simulation	537	(2)
Evaluation Order Revisited	539	(6)
Strictness and Lazy Evaluation	541	(1)
I/O: Streams and Monads	542	(3)
Higher-Order Functions	545	(4)
Theoretical Foundations CD 166	549	(1)
Lambda Calculus CD 168
Control Flow CD 171
Structures CD 173
Functional Programming in Perspective	549	(3)
Summary and Concluding Remarks	552	(1)
Exercises	552	(5)
Explorations	557	(1)
Bibliographic Notes	558	(1)
Logic Languages	559	(30)
Logic Programming Concepts	560	(1)
Prolog	561	(18)
Resolution and Unification	563	(1)
Lists	564	(1)
Arithmetic	565	(1)
Search/Execution Order	566	(3)
Extended Example: Tic-Tac-Toe	569	(2)
Imperative Control Flow	571	(3)
Database Manipulation	574	(5)
Theoretical Foundations CD 180	579	(1)
Clausal Form CD 181
Limitations CD 182
Skolemization CD 183
Logic Programming in Perspective	579	(4)
Parts of Logic Not Covered	580	(1)
Execution Order	580	(1)
Negation and the ``Closed World'' Assumption	581	(2)
Summary and Concluding Remarks	583	(1)
Exercises	584	(2)
Explorations	586	(1)
Bibliographic Notes	587	(2)
Concurrency	589	(82)
Background and Motivation	590	(11)
A Little History	590	(3)
The Case for Multithreaded Programs	593	(4)
Multiprocessor Architecture	597	(4)
Concurrent Programming Fundamentals	601	(18)
Communication and Synchronization	601	(2)
Languages and Libraries	603	(1)
Thread Creation Syntax	604	(9)
Implementation of Threads	613	(6)
Shared Memory	619	(23)
Busy-Wait Synchronization	620	(3)
Scheduler Implementation	623	(4)
Semaphores	627	(2)
Monitors	629	(5)
Conditional Critical Regions	634	(4)
Implicit Synchronization	638	(4)
Message Passing	642	(18)
Naming Communication Partners	642	(4)
Sending	646	(5)
Receiving	651	(5)
Remote Procedure Call	656	(4)
Summary and Concluding Remarks	660	(2)
Exercises	662	(6)
Explorations	668	(1)
Bibliographic Notes	669	(2)
Scripting Languages	671	(88)
What Is a Scripting Language?	672	(5)
Common Characteristics	674	(3)
Problem Domains	677	(24)
Shell (Command) Languages	677	(7)
Text Processing and Report Generation	684	(5)
Mathematics and Statistics	689	(1)
``Glue'' Languages and General Purpose Scripting	690	(8)
Extension Languages	698	(3)
Scripting the World Wide Web	701	(21)
CGI Scripts	702	(1)
Embedded Server-Side Scripts	703	(5)
Client-Side Scripts	708	(1)
Java Applets	708	(4)
XSLT	712	(10)
Innovative Features	722	(26)
Names and Scopes	723	(5)
String and Pattern Manipulation	728	(8)
Data Types	736	(5)
Object Orientation	741	(7)
Summary and Concluding Remarks	748	(2)
Exercises	750	(5)
Explorations	755	(1)
Bibliographic Notes	756	(3)
IV A CLOSER LOOK AT IMPLEMENTATION	759	(34)
Building a Runnable Program	761	(30)
Back-End Compiler Structure	761	(5)
A Plausible Set of Phases	762	(4)
Phases and Passes	766	(1)
Intermediate Forms CD 189	766	(3)
Diana CD 189
GNU RTL CD 192
Code Generation	769	(6)
An Attribute Grammar Example	769	(3)
Register Allocation	772	(3)
Address Space Organization	775	(1)
Assembly	776	(5)
Emitting Instructions	778	(2)
Assigning Addresses to Names	780	(1)
Linking	781	(3)
Relocation and Name Resolution	782	(1)
Type Checking	783	(1)
Dynamic Linking CD 195	784	(2)
Position-Independent Code CD 195
Fully Dynamic (Lazy) Linking CD 196
Summary and Concluding Remarks	786	(1)
Exercises	787	(2)
Explorations	789	(1)
Bibliographic Notes	790	(1)
Code Improvement CD 202	791	(2)
Phases of Code Improvement CD 204
Peephole Optimization CD 206
Redundancy Elimination in Basic Blocks CD 209
A Running Example CD 210
Value Numbering CD 211
Global Redundancy and Data Flow Analysis CD 217
SSA Form and Global Value Numbering CD 218
Global Common Subexpression Elimination CD 220
Loop Improvement I CD 227
Loop Invariants CD 228
Induction Variables CD 229
Instruction Scheduling CD 232
Loop Improvement II CD 236
Loop Unrolling and Software Pipelining CD 237
Loop Reordering CD 241
Register Allocation CD 248
Summary and Concluding Remarks CD 252
Exercises CD 253
Explorations CD 257
Bibliographic Notes CD 258
Programming Languages Mentioned	793	(10)
Language Design and Language Implementation	803	(4)
Numbered Examples	807	(12)
Bibliography	819	(18)
Index	837