Programming Language Pragmatics

5th Edition - January 9, 2025
Authors: Michael Scott, Jonathan Aldrich
Language: English
Paperback ISBN:
9 7 8 - 0 - 3 2 3 - 9 9 9 6 6 - 3
eBook ISBN:
9 7 8 - 0 - 3 2 3 - 9 8 4 2 3 - 2

Programming Language Pragmatics is the most comprehensive programming language textbook available today, with nearly 1000 pages of content in the book, plus hundreds more pages… Read more

Purchase options

ROBOTICS & AUTOMATION

Empowering Progress

Up to 25% off Essentials Robotics and Automation titles

Explore now

Image with Robotics & Automation book covers

Institutional subscription on ScienceDirect

Request a sales quote

Resources

Textbook support for instructors(opens in new tab/window)

Programming Language Pragmatics is the most comprehensive programming language textbook available today, with nearly 1000 pages of content in the book, plus hundreds more pages of reference materials and ancillaries online. Michael Scott takes theperspective that language design and language implementation are tightly interconnected, and that neither can be fully understood in isolation. In an approachable, readable style, he discusses more than 50 languages in the context of understanding how code isinterpreted or compiled, providing an organizational framework for learning new languages, regardless of platform. This edition has been thoroughly updated to cover the most recent developments in programming language design and provides both a solid understanding of the most important issues driving software development today

Title of Book
Cover image
Title page
Table of Contents
Copyright
Dedication
About the Authors
Preface
Part I: Foundations
Introduction
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
1.7. Summary and Concluding Remarks
1.8. Exercises
1.9. Explorations
1.10. Bibliographic Notes
2: Programming Language Syntax
2.1. Specifying Syntax: Regular Expressions and Context-Free Grammars
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. Recovering from Syntax Errors
2.4. Theoretical Foundations
2.5. Summary and Concluding Remarks
2.6. Exercises
2.7. Explorations
2.8. Bibliographic Notes
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.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.9. Summary and Concluding Remarks
3.10. Exercises
3.11. Explorations
3.12. Bibliographic Notes
4: Program Semantics
4.1. Abstract Syntax Trees
4.2. Constructing ASTs with Action Routines
4.3. Dynamic Semantics
4.3.1. Dynamic Semantics for Variables and Statements
4.3.2. Interpreting Dynamic Semantics
4.4. Static Semantics and Semantic Analysis
4.4.1. Name Binding and Type Checking
4.4.2. Implementing Type Checking
4.4.3. Specifying Transformations
4.5. Semantic Properties of Languages: Soundness
4.6. Attribute Grammars
4.7. Summary and Concluding Remarks
4.8. Exercises
4.9. Explorations
4.10. Bibliographic Notes
5: Target Machine Architecture
Part II: Core Issues in Language Design
Introduction
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. Logically Controlled Loops
6.6. Recursion
6.6.1. Iteration and Recursion
6.6.2. Applicative- and Normal-Order Evaluation
6.7. Nondeterminacy
6.8. Summary and Concluding Remarks
6.9. Exercises
6.10. Explorations
6.11. Bibliographic Notes
7: Type Systems
7.1. Overview
7.1.1. The Meaning of “Type”
7.1.2. Subtyping
7.1.3. Polymorphism
7.1.4. Orthogonality
7.1.5. Classification of Types
7.2. Type Checking
7.2.1. Type Equivalence
7.2.2. Subtyping and Type Compatibility
7.2.3. Local Type Inference
7.3. Generic Subroutines and Classes
7.3.1. Checking Generic Types
7.3.2. Implementation Options
7.3.3. Generic Parameter Constraints
7.3.4. Implicit Instantiation
7.3.5. Generics in C++, Java, and C#
7.4. Implicit Parametric Polymorphism in ML
7.4.1. Hindley–Milner Type Inference
7.4.2. Bounded Polymorphism in Haskell
7.4.3. Polymorphism through Dynamic Typing
7.5. Equality Testing and Assignment
7.6. Summary and Concluding Remarks
7.7. Exercises
7.8. Explorations
7.9. Bibliographic Notes
8: Composite Types
8.1. Records (Structures)
8.1.1. Syntax and Operations
8.1.2. Record Semantics
8.1.3. Memory Layout
8.1.4. Unions (Variant Records, Datatypes)
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. Semantics of Pointers and Recursive Data Structures
8.5.3. Dangling References
8.5.4. Garbage Collection
8.5.5. Memory Management in Rust
8.6. Lists
8.7. Files and Input/Output
8.8. Summary and Concluding Remarks
8.9. Exercises
8.10. Explorations
8.11. Bibliographic Notes
9: Subroutines and Control Abstraction
9.1. Review of Stack Layout
9.2. Calling Sequences
9.2.1. Displays
9.2.2. Stack 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
9.7. Asynchronous Programming
9.7.1. Callbacks, Promises, and await in JavaScript
9.7.2. C# Tasks
9.8. Summary and Concluding Remarks
9.9. Exercises
9.10. Explorations
9.11. Bibliographic Notes
Part III: Programming Models and Paradigms
Introduction
10: 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. 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 Methods and Abstract Classes
10.4.2. Member Lookup
10.4.3. Object Closures
10.5. Interface Inheritance: Traits and Mix-ins
10.5.1. Implementation: In-line Caching
10.5.2. Extensions
10.6. True Multiple Inheritance
10.7. Object-Oriented Programming Revisited
10.7.1. The Object Model of Smalltalk
10.8. Summary and Concluding Remarks
10.9. Exercises
10.10. Explorations
10.11. Bibliographic Notes
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.8. Functional Programming in Perspective
11.9. Summary and Concluding Remarks
11.10. Exercises
11.11. Explorations
11.12. Bibliographic Notes
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.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
12.5. Summary and Concluding Remarks
12.6. Exercises
12.7. Explorations
12.8. Bibliographic Notes
13: Concurrency
13.1. Background and Motivation
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 and Mutex Locks
13.4. Language-Level Constructs
13.4.1. Scoped Locks
13.4.2. Monitors
13.4.3. Conditional Critical Regions
13.4.4. Synchronization in Java
13.4.5. Transactional Memory
13.4.6. Implicit Synchronization
13.5. Message Passing
13.6. Summary and Concluding Remarks
13.7. Exercises
13.8. Explorations
13.9. Bibliographic Notes
14: Scripting
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, Statistics, and Data Analytics
14.2.4. “Glue” Languages and General-Purpose Scripting
14.2.5. Extension Languages
14.3. Scripting the World Wide Web
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
14.5. Summary and Concluding Remarks
14.6. Exercises
14.7. Explorations
14.8. Bibliographic Notes
Part IV: A Closer Look at Implementation
Introduction
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. GCC and LLVM
15.2.2. Stack-Based Intermediate Forms
15.2.3. WebAssembly
15.3. Code Generation
15.3.1. An Inference Rule 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.8. Summary and Concluding Remarks
15.9. Exercises
15.10. Explorations
15.11. Bibliographic Notes
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
16.4. Summary and Concluding Remarks
16.5. Exercises
16.6. Explorations
16.7. Bibliographic Notes
17: Code Improvement
A: Programming Languages Mentioned
B: Language Design and Language Implementation
C: Numbered Examples
Bibliography
Index
Contents
Supplement
2. Programming Language Syntax
2.3.5. Recovering from Syntax Errors
2.4. Theoretical Foundations
2.4.1. Finite Automata
2.4.2. Push-Down Automata
2.4.3. Grammar and Language Classes
2.6. Exercises
2.7. Explorations
3. Names, Scopes, and Bindings
3.4. Implementing Scope
3.8. Separate Compilation
3.10. Exercises
3.11. Explorations
4. Program Semantics
4.6. Attribute Grammars
4.8. Exercises
4.9. Explorations
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
5.6. Summary and Concluding Remarks
5.7. Exercises
5.8. Explorations
5.9. Bibliographic Notes
6. Control Flow
6.7. Nondeterminacy
6.9. Exercises
6.10. Explorations
7. Type Systems
7.3.5. Generics in C++, Java, and C#
7.7. Exercises
7.8. Explorations
8. Composite Types
8.1.4. Unions (Variant Records, Datatypes)
8.5.3. Dangling References
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
8.9. Exercises
8.10. Explorations
9. Subroutines and Control Abstraction
9.2.1. Displays
9.2.2. Stack Case Studies: LLVM on Arm; gcc on x86
9.2.3. Register Windows
9.3.2. Call by Name
9.5.3. Implementation of Iterators
9.5.4. Discrete Event Simulation
9.9. Exercises
9.10. Explorations
10. Object Orientation
10.6. True Multiple Inheritance
10.9. Exercises
10.10. Explorations
11. Functional Languages
11.7. Theoretical Foundations
11.10. Exercises
11.11. Explorations
12. Logic Languages
12.3. Theoretical Foundations
12.6. Exercises
12.7. Explorations
13. Concurrency
13.5. Message Passing
13.7. Exercises
13.8. Explorations
14. Scripting
14.3. Scripting the World Wide Web
14.6. Exercises
14.7. Explorations
15. Building a Runnable Program
15.2.1. GCC and LLVM
15.7. Dynamic Linking
15.7.1. Position-Independent Code
15.7.2. Fully Dynamic (Lazy) Linking
15.9. Exercises
15.10. Explorations
16. Run-Time Program Management
16.1.2. The Common Language Infrastructure
16.5. Exercises
16.6. Explorations
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
17.9. Summary and Concluding Remarks
17.10. Exercises
17.11. Explorations
17.12. Bibliographic Notes

Life Sciences

Physical Sciences & Engineering

Social Sciences & Humanities

Health

Programming Language Pragmatics

Purchase options

Empowering Progress

Institutional subscription on ScienceDirect

Resources

Michael Scott

Jonathan Aldrich