Programming Language Pragmatics
Third Edition

Contents

   Located on the companion CD
   New or heavily rewritten for the third 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	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
		A	Programming Languages Mentioned
		B	Language Design and Language Implementation
		C	Numbered Examples
		Bibliography
		Index