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
		A	Programming Languages Mentioned
		B	Language Design and Language Implementation
		C	Numbered Examples
		Bibliography
		Index