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

Back to the book home page

Last Change: 23 February 2009 /