PLP 2e cover

Programming Language Pragmatics
Second Edition

Contents

   Located on the companion CD
   New or heavily rewritten for the second 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  Significant Comments
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  Stack-Based Allocation
3.2.2  Heap-Based Allocation
3.2.3  Garbage Collection
3.3  Scope Rules
3.3.1  Static Scope
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 Scope
3.4  Implementing Scope
3.4.1  Symbol Tables
3.4.2  Association Lists and Central Reference Tables
3.5  The Binding of Referencing Environments
3.5.1  Subroutine Closures
3.5.2  First- and Second-Class Subroutines
3.6  Binding Within a Scope
3.6.1  Aliases
3.6.2  Overloading
3.6.3  Polymorphism and Related Concepts
3.7  Separate Compilation
3.7.1  Separate Compilation in C
3.7.2  Packages and Automatic Header Inference
3.7.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  Computer 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  Two Example Architectures: The x86 and MIPS
5.4.5  Pseudo-Assembly Notation
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.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 Definition of Types
7.1.4  The 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
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  Example: Phrase-Level Recovery in a Recursive Descent Parser
8.5.4  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
 
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  Type Extensions
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  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  A Little History
12.1.2  The Case for Multithreaded Programs
12.1.3  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  Shared Memory
12.3.1  Busy-Wait Synchronization
12.3.2  Scheduler Implementation
12.3.3  Semaphores
12.3.4  Monitors
12.3.5  Conditional Critical Regions
12.3.6  Implicit Synchronization
12.4  Message Passing
12.4.1  Naming Communication Partners
12.4.2  Sending
12.4.3  Receiving
12.4.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  GNU RTL
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  Code Improvement
15.1  Phases of Code Improvement
15.2  Peephole Optimization
15.3  Redundancy Elimination in Basic Blocks
15.3.1  A Running Example
15.3.2  Value Numbering
15.4  Global Redundancy and Data Flow Analysis
15.4.1  SSA Form and Global Value Numbering
15.4.2  Global Common Subexpression Elimination
15.5  Loop Improvement I
15.5.1  Loop Invariants
15.5.2  Induction Variables
15.6  Instruction Scheduling
15.7  Loop Improvement II
15.7.1  Loop Unrolling and Software Pipelining
15.7.2  Loop Reordering
15.8  Register Allocation
 
AProgramming Languages Mentioned
BLanguage Design and Language Implementation
CNumbered Examples
 
Bibliography
Index


Back to the book home page
Last Change: 23 February 2009 / Michael Scott's email address