PLP 4e cover

Programming Language Pragmatics
Fourth Edition

Contents

   Located on the companion web site
   New or heavily updated for the fourth edition

Foreword
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  Writing an LL(1) Grammar
2.3.3  Table-Driven Top-Down Parsing
2.3.4  Bottom-Up Parsing
2.3.5  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.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.6.4  Lambda Expressions
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  Tree Grammars and Syntax Tree Decoration
 
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 (ISA)
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 ARM
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  Type Systems
7.1  Overview
7.1.1  The Meaning of “Type”
7.1.2  Polymorphism
7.1.3  Orthogonality
7.1.4  Classification of Types
7.2  Type Checking
7.2.1  Type Equivalence
7.2.2  Type Compatibility
7.2.3  Type Inference
7.2.4  Type Checking in ML
7.3  Parametric Polymorphism
7.3.1  Generic Subroutines and Classes
7.3.2  Generics in C++, Java, and C#
7.4  Equality Testing and Assignment
 
8  Composite Types
8.1  Records (Structures)
8.1.1  Syntax and Operations
8.1.2  Memory Layout and Its Impact
8.1.3  Variant Records (Unions)
8.2  Arrays
8.2.1  Syntax and Operations
8.2.2  Dimensions, Bounds, and Allocation
8.2.3  Memory Layout
8.3  Strings
8.4  Sets
8.5  Pointers and Recursive Types
8.5.1  Syntax and Operations
8.5.2  Dangling References
8.5.3  Garbage Collection
8.6  Lists
8.7  Files and Input/Output
8.7.1  Interactive I/O
8.7.2  File-Based I/O
8.7.3  Text I/O
 
9  Subroutines and Control Abstraction
9.1  Review of Stack Layout
9.2  Calling Sequences
9.2.1  Displays
9.2.2  Case Studies: LLVM on ARM; gcc on x86
9.2.3  Register Windows
9.2.4  In-Line Expansion
9.3  Parameter Passing
9.3.1  Parameter Modes
9.3.2  Call by Name
9.3.3  Special Purpose Parameters
9.3.4  Function Returns
9.4  Exception Handling
9.4.1  Defining Exceptions
9.4.2  Exception Propagation
9.4.3  Implementation of Exceptions
9.5  Coroutines
9.5.1  Stack Allocation
9.5.2  Transfer
9.5.3  Implementation of Iterators
9.5.4  Discrete Event Simulation
9.6  Events
9.6.1  Sequential Handlers
9.6.2  Thread-Based Handlers
 
10  Data Abstraction and Object Orientation
10.1  Object-Oriented Programming
10.1.1  Classes and Generics
10.2  Encapsulation and Inheritance
10.2.1  Modules
10.2.2  Classes
10.2.3  Nesting (Inner Classes)
10.2.4  Type Extensions
10.2.5  Extending without Inheritance
10.3  Initialization and Finalization
10.3.1  Choosing a Constructor
10.3.2  References and Values
10.3.3  Execution Order
10.3.4  Garbage Collection
10.4  Dynamic Method Binding
10.4.1  Virtual and Nonvirtual Methods
10.4.2  Abstract Classes
10.4.3  Member Lookup
10.4.4  Object Closures
10.5  Mix-in Inheritance
10.5.1  Implementation
10.5.2  Extensions
10.6  True Multiple Inheritance
10.6.1  Semantic Ambiguities
10.6.2  Replicated Inheritance
10.6.3  Shared Inheritance
10.7  Object-Oriented Programming Revisited
10.7.1  The Object Model of Smalltalk

  Part III: Alternative Programming Models

11  Functional Languages
11.1  Historical Origins
11.2  Functional Programming Concepts
11.3  A Bit of Scheme
11.3.1  Bindings
11.3.2  Lists and Numbers
11.3.3  Equality Testing and Searching
11.3.4  Control Flow and Assignment
11.3.5  Programs as Lists
11.3.6  Extended Example: DFA Simulation in Scheme
11.4  A Bit of OCaml
11.4.1  Equality and Ordering
11.4.2  Bindings and Lambda Expressions
11.4.3  Type Constructors
11.4.4  Pattern Matching
11.4.5  Control Flow and Side Effects
11.4.6  Extended Example: DFA Simulation in OCaml
11.5  Evaluation Order Revisited
11.5.1  Strictness and Lazy Evaluation
11.5.2  I/O: Streams and Monads
11.6  Higher-Order Functions
11.7  Theoretical Foundations
11.7.1  Lambda Calculus
11.7.2  Control Flow
11.7.3  Structures
11.8  Functional Programming in Perspective
 
12  Logic Languages
12.1  Logic Programming Concepts
12.2  Prolog
12.2.1  Resolution and Unification
12.2.2  Lists
12.2.3  Arithmetic
12.2.4  Search/Execution Order
12.2.5  Extended Example: Tic-Tac-Toe
12.2.6  Imperative Control Flow
12.2.7  Database Manipulation
12.3  Theoretical Foundations
12.3.1  Clausal Form
12.3.2  Limitations
12.3.3  Skolemization
12.4  Logic Programming in Perspective
12.4.1  Parts of Logic Not Covered
12.4.2  Execution Order
12.4.3  Negation and the “Closed World” Assumption
 
13  Concurrency
13.1  Background and Motivation
13.1.1  The Case for Multithreaded Programs
13.1.2  Multiprocessor Architecture
13.2  Concurrent Programming Fundamentals
13.2.1  Communication and Synchronization
13.2.2  Languages and Libraries
13.2.3  Thread Creation Syntax
13.2.4  Implementation of Threads
13.3  Implementing Synchronization
13.3.1  Busy-Wait Synchronization
13.3.2  Nonblocking Algorithms
13.3.3  Memory Consistency
13.3.4  Scheduler Implementation
13.3.5  Semaphores
13.4  Language-Level Constructs
13.4.1  Monitors
13.4.2  Conditional Critical Regions
13.4.3  Synchronization in Java
13.4.4  Transactional Memory
13.4.5  Implicit Synchronization
13.5  Message Passing
13.5.1  Naming Communication Partners
13.5.2  Sending
13.5.3  Receiving
13.5.4  Remote Procedure Call
 
14  Scripting Languages
14.1  What Is a Scripting Language?
14.1.1  Common Characteristics
14.2  Problem Domains
14.2.1  Shell (Command) Languages
14.2.2  Text Processing and Report Generation
14.2.3  Mathematics and Statistics
14.2.4  “Glue” Languages and General Purpose Scripting
14.2.5  Extension Languages
14.3  Scripting the World Wide Web
14.3.1  CGI Scripts
14.3.2  Embedded Server-Side Scripts
14.3.3  Client-Side Scripts
14.3.4  Java Applets and Other Embedded Elements
14.3.5  XSLT
14.4  Innovative Features
14.4.1  Names and Scopes
14.4.2  String and Pattern Manipulation
14.4.3  Data Types
14.4.4  Object Orientation

  Part IV: A Closer Look at Implementation

15  Building a Runnable Program
15.1  Back-End Compiler Structure
15.1.1  A Plausible Set of Phases
15.1.2  Phases and Passes
15.2  Intermediate Forms
15.2.1  GIMPLE and RTL
15.2.2  Stack-Based Intermediate Forms
15.3  Code Generation
15.3.1  An Attribute Grammar Example
15.3.2  Register Allocation
15.4  Address Space Organization
15.5  Assembly
15.5.1  Emitting Instructions
15.5.2  Assigning Addresses to Names
15.6  Linking
15.6.1  Relocation and Name Resolution
15.6.2  Type Checking
15.7  Dynamic Linking
15.7.1  Position-Independent Code
15.7.2  Fully Dynamic (Lazy) Linking
 
16  Run-time Program Management
16.1  Virtual Machines
16.1.1  The Java Virtual Machine
16.1.2  The Common Language Infrastructure
16.2  Late Binding of Machine Code
16.2.1  Just-in-Time and Dynamic Compilation
16.2.2  Binary Translation
16.2.3  Binary Rewriting
16.2.4  Mobile Code and Sandboxing
16.3  Inspection/Introspection
16.3.1  Reflection
16.3.2  Symbolic Debugging
16.3.3  Performance Analysis
 
17  Code Improvement
17.1  Phases of Code Improvement
17.2  Peephole Optimization
17.3  Redundancy Elimination in Basic Blocks
17.3.1  A Running Example
17.3.2  Value Numbering
17.4  Global Redundancy and Data Flow Analysis
17.4.1  SSA Form and Global Value Numbering
17.4.2  Global Common Subexpression Elimination
17.5  Loop Improvement I
17.5.1  Loop Invariants
17.5.2  Induction Variables
17.6  Instruction Scheduling
17.7  Loop Improvement II
17.7.1  Loop Unrolling and Software Pipelining
17.7.2  Loop Reordering
17.8  Register Allocation
 
AProgramming Languages Mentioned
BLanguage Design and Language Implementation
CNumbered Examples
 
Bibliography
Index