PLP 3e cover

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 Creation Syntax
12.2.4  Implementation of Threads
12.3  Implementing Synchronization
12.3.1  Busy-Wait Synchronization
12.3.2  Nonblocking Algorithms
12.3.3  Memory Consistency Models
12.3.4  Scheduler Implementation
12.3.5  Semaphores
12.4  Language-Level Mechanisms
12.4.1  Monitors
12.4.2  Conditional Critical Regions
12.4.3  Synchronization in Java
12.4.4  Transactional Memory
12.4.5  Implicit Synchronization
12.5  Message Passing
12.5.1  Naming Communication Partners
12.5.2  Sending
12.5.3  Receiving
12.5.4  Remote Procedure Call
 
13  Scripting Languages
13.1  What Is a Scripting Language?
13.1.1  Common Characteristics
13.2  Problem Domains
13.2.1  Shell (Command) Languages
13.2.2  Text Processing and Report Generation
13.2.3  Mathematics and Statistics
13.2.4  “Glue” Languages and General Purpose Scripting
13.2.5  Extension Languages
13.3  Scripting the World Wide Web
13.3.1  CGI Scripts
13.3.2  Embedded Server-Side Scripts
13.3.3  Client-Side Scripts
13.3.4  Java Applets
13.3.5  XSLT
13.4  Innovative Features
13.4.1  Names and Scopes
13.4.2  String and Pattern Manipulation
13.4.3  Data Types
13.4.4  Object Orientation

  Part IV: A Closer Look at Implementation

14  Building a Runnable Program
14.1  Back-End Compiler Structure
14.1.1  A Plausible Set of Phases
14.1.2  Phases and Passes
14.2  Intermediate Forms
14.2.1  Diana
14.2.2  The gcc IFs
14.2.3  Stack-Based Intermediate Forms
14.3  Code Generation
14.3.1  An Attribute Grammar Example
14.3.2  Register Allocation
14.4  Address Space Organization
14.5  Assembly
14.5.1  Emitting Instructions
14.5.2  Assigning Addresses to Names
14.6  Linking
14.6.1  Relocation and Name Resolution
14.6.2  Type Checking
14.7  Dynamic Linking
14.7.1  Position-Independent Code
14.7.2  Fully Dynamic (Lazy) Linking
 
15  Run-time Program Management
15.1  Virtual Machines
15.1.1  The Java Virtual Machine
15.1.2  The Common Language Infrastructure
15.2  Late Binding of Machine Code
15.2.1  Just-in-Time and Dynamic Compilation
15.2.2  Binary Translation
15.2.3  Binary Rewriting
15.2.4  Mobile Code and Sandboxing
15.3  Inspection/Introspection
15.3.1  Reflection
15.3.2  Symbolic Debugging
15.3.3  Performance Analysis
 
16  Code Improvement
16.1  Phases of Code Improvement
16.2  Peephole Optimization
16.3  Redundancy Elimination in Basic Blocks
16.3.1  A Running Example
16.3.2  Value Numbering
16.4  Global Redundancy and Data Flow Analysis
16.4.1  SSA Form and Global Value Numbering
16.4.2  Global Common Subexpression Elimination
16.5  Loop Improvement I
16.5.1  Loop Invariants
16.5.2  Induction Variables
16.6  Instruction Scheduling
16.7  Loop Improvement II
16.7.1  Loop Unrolling and Software Pipelining
16.7.2  Loop Reordering
16.8  Register Allocation
 
AProgramming Languages Mentioned
BLanguage Design and Language Implementation
CNumbered Examples
 
Bibliography
Index