Programming Language Pragmatics

Programming Language Pragmatics
Third Edition
Contents
Located on the companion CD
New or heavily rewritten for the third edition
Forward

Preface

Part I: Foundations
1 Introduction
1.1 The Art of Language Design
1.2 The Programming Language Spectrum
1.3 Why Study Programming Languages?
1.4 Compilation and Interpretation
1.5 Programming Environments
1.6 An Overview of Compilation
1.6.1 Lexical and Syntax Analysis
1.6.2 Semantic Analysis and Intermediate Code Generation
1.6.3 Target Code Generation
1.6.4 Code Improvement

2 Programming Language Syntax
2.1 Specifying Syntax
2.1.1 Tokens and Regular Expressions
2.1.2 Context-Free Grammars
2.1.3 Derivations and Parse Trees
2.2 Scanning
2.2.1 Generating a Finite Automaton
2.2.2 Scanner Code
2.2.3 Table-Driven Scanning
2.2.4 Lexical Errors
2.2.5 Pragmas
2.3 Parsing
2.3.1 Recursive Descent
2.3.2 Table-Driven Top-Down Parsing
2.3.3 Bottom-Up Parsing
2.3.4 Syntax Errors
2.4 Theoretical Foundations
2.4.1 Finite Automata
2.4.2 Push-Down Automata
2.4.3 Grammar and Language Classes

3 Names, Scopes, and Bindings
3.1 The Notion of Binding Time
3.2 Object Lifetime and Storage Management
3.2.1 Static Allocation
3.2.2 Stack-Based Allocation
3.2.3 Heap-Based Allocation
3.2.4 Garbage Collection
3.3 Scope Rules
3.3.1 Static Scoping
3.3.2 Nested Subroutines
3.3.3 Declaration Order
3.3.4 Modules
3.3.5 Module Types and Classes
3.3.6 Dynamic Scoping
3.4 Implementing Scope
3.4.1 Symbol Tables
3.4.2 Association Lists and Central Reference Tables
3.5 The Meaning of Names Within a Scope
3.5.1 Aliases
3.5.2 Overloading
3.5.3 Polymorphism and Related Concepts
3.6 The Binding of Referencing Environments
3.6.1 Subroutine Closures
3.6.2 First-Class Values and Unlimited Extent
3.6.3 Object Closures
3.7 Macro Expansion
3.8 Separate Compilation
3.8.1 Separate Compilation in C
3.8.2 Packages and Automatic Header Inference
3.8.3 Module Hierarchies

4 Semantic Analysis
4.1 The Role of the Semantic Analyzer
4.2 Attribute Grammars
4.3 Evaluating Attributes
4.4 Action Routines
4.5 Space Management for Attributes
4.5.1 Bottom-Up Evaluation
4.5.2 Top-Down Evaluation
4.6 Decorating a Syntax Tree

5 Target Machine Architecture
5.1 The Memory Hierarchy
5.2 Data Representation
5.2.1 Integer Arithmetic
5.2.2 Floating-Point Arithmetic
5.3 Instruction Set Architecture
5.3.1 Addressing Modes
5.3.2 Conditions and Branches
5.4 Architecture and Implementation
5.4.1 Microprogramming
5.4.2 Microprocessors
5.4.3 RISC
5.4.4 Multithreading and Multicore
5.4.5 Two Example Architectures: The x86 and MIPS
5.5 Compiling for Modern Processors
5.5.1 Keeping the Pipeline Full
5.5.2 Register Allocation
Part II: Core Issues in Language Design
6 Control Flow
6.1 Expression Evaluation
6.1.1 Precedence and Associativity
6.1.2 Assignments
6.1.3 Initialization
6.1.4 Ordering Within Expressions
6.1.5 Short-Circuit Evaluation
6.2 Structured and Unstructured Flow
6.2.1 Structured Alternatives to goto
6.2.2 Continuations
6.3 Sequencing
6.4 Selection
6.4.1 Short-Circuited Conditions
6.4.2 Case/Switch Statements
6.5 Iteration
6.5.1 Enumeration-Controlled Loops
6.5.2 Combination Loops
6.5.3 Iterators
6.5.4 Generators in Icon
6.5.5 Logically Controlled Loops
6.6 Recursion
6.6.1 Iteration and Recursion
6.6.2 Applicative- and Normal-Order Evaluation
6.7 Nondeterminacy

7 Data Types
7.1 Type Systems
7.1.1 Type Checking
7.1.2 Polymorphism
7.1.3 The Meaning of “Type”
7.1.4 Classification of Types
7.1.5 Orthogonality
7.2 Type Checking
7.2.1 Type Equivalence
7.2.2 Type Compatibility
7.2.3 Type Inference
7.2.4 The ML Type System
7.3 Records (Structures) and Variants (Unions)
7.3.1 Syntax and Operations
7.3.2 Memory Layout and Its Impact
7.3.3 With Statements
7.3.4 Variant Records (Unions)
7.4 Arrays
7.4.1 Syntax and Operations
7.4.2 Dimensions, Bounds, and Allocation
7.4.3 Memory Layout
7.5 Strings
7.6 Sets
7.7 Pointers and Recursive Types
7.7.1 Syntax and Operations
7.7.2 Dangling References
7.7.3 Garbage Collection
7.8 Lists
7.9 Files and Input/Output
7.9.1 Interactive I/O
7.9.2 File-Based I/O
7.9.3 Text I/O
7.10 Equality Testing and Assignment

8 Subroutines and Control Abstraction
8.1 Review of Stack Layout
8.2 Calling Sequences
8.2.1 Displays
8.2.2 Case Studies: C on the MIPS; Pascal on the x86
8.2.3 Register Windows
8.2.4 In-Line Expansion
8.3 Parameter Passing
8.3.1 Parameter Modes
8.3.2 Call by Name
8.3.3 Special Purpose Parameters
8.3.4 Function Returns
8.4 Generic Subroutines and Modules
8.4.1 Implementation Options
8.4.2 Generic Parameter Constraints
8.4.3 Implicit Instantiation
8.4.4 Generics in C++, Java, and C#
8.5 Exception Handling
8.5.1 Defining Exceptions
8.5.2 Exception Propagation
8.5.3 Implementation of Exceptions
8.6 Coroutines
8.6.1 Stack Allocation
8.6.2 Transfer
8.6.3 Implementation of Iterators
8.6.4 Discrete Event Simulation
8.7 Events
8.7.1 Sequential Handlers
8.7.2 Thread-Based Handlers

9 Data Abstraction and Object Orientation
9.1 Object-Oriented Programming
9.2 Encapsulation and Inheritance
9.2.1 Modules
9.2.2 Classes
9.2.3 Nesting (Inner Classes)
9.2.4 Type Extensions
9.2.5 Extending without Inheritance
9.3 Initialization and Finalization
9.3.1 Choosing a Constructor
9.3.2 References and Values
9.3.3 Execution Order
9.3.4 Garbage Collection
9.4 Dynamic Method Binding
9.4.1 Virtual and Nonvirtual Methods
9.4.2 Abstract Classes
9.4.3 Member Lookup
9.4.4 Polymorphism
9.4.5 Object Closures
9.5 Multiple Inheritance
9.5.1 Semantic Ambiguities
9.5.2 Replicated Inheritance
9.5.3 Shared Inheritance
9.5.4 Mix-In Inheritance
9.6 Object-Oriented Programming Revisited
9.6.1 The Object Model of Smalltalk
Part III: Alternative Programming Models
10 Functional Languages
10.1 Historical Origins
10.2 Functional Programming Concepts
10.3 A Review/Overview of Scheme
10.3.1 Bindings
10.3.2 Lists and Numbers
10.3.3 Equality Testing and Searching
10.3.4 Control Flow and Assignment
10.3.5 Programs as Lists
10.3.6 Extended Example: DFA Simulation
10.4 Evaluation Order Revisited
10.4.1 Strictness and Lazy Evaluation
10.4.2 I/O: Streams and Monads
10.5 Higher-Order Functions
10.6 Theoretical Foundations
10.6.1 Lambda Calculus
10.6.2 Control Flow
10.6.3 Structures
10.7 Functional Programming in Perspective

11 Logic Languages
11.1 Logic Programming Concepts
11.2 Prolog
11.2.1 Resolution and Unification
11.2.2 Lists
11.2.3 Arithmetic
11.2.4 Search/Execution Order
11.2.5 Extended Example: Tic-Tac-Toe
11.2.6 Imperative Control Flow
11.2.7 Database Manipulation
11.3 Theoretical Foundations
11.3.1 Clausal Form
11.3.2 Limitations
11.3.3 Skolemization
11.4 Logic Programming in Perspective
11.4.1 Parts of Logic Not Covered
11.4.2 Execution Order
11.4.3 Negation and the “Closed World” Assumption

12 Concurrency
12.1 Background and Motivation
12.1.1 The Case for Multithreaded Programs
12.1.2 Multiprocessor Architecture
12.2 Concurrent Programming Fundamentals
12.2.1 Communication and Synchronization
12.2.2 Languages and Libraries
12.2.3 Thread.