Programming Language Pragmatics

by Scott, Michael L.

• ISBN13: 9781558604421
• ISBN10: 1558604421
• Format: Hardcover
• Copyright: 1999-10-01
• Publisher: Elsevier Science Ltd

Summary

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.

Author Biography

Michael L. Scott is a professor in the University of Rochester's Department of Computer Science

Table of Contents

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