Martin Erwig, PhD, is the Stretch Professor of Computer Science in the School of Electrical Engineering and Computer Science at Oregon State University, USA. He is the author of the award-winning book Once Upon an Algorithm: How Stories Explain Computing. He serves as an Editorial Board Member of the Journal of Computer Languages and as an Associate Editor of the Journal of Visual Language and Computing.

• Preface viiAbout the Companion Website xi1 Introduction 11.1 The Role of Programming Languages in Computer Science 21.2 Why Study Programming Language Fundamentals? 41.3 What Are the Fundamentals of Programming Languages? 51.4 How to Study the Fundamentals of Programming Languages? 81.5 About Programming Paradigms 92 Functional Programming with Elm 132.1 Getting Started 142.2 Expressions, Values, and Their Types 182.2.1 Naming Values and Expressions 192.2.2 Tracing Evaluations 202.2.3 Tuples 252.3 Functions 262.3.1 Function Application 262.3.2 Currying and Partial Function Application 272.3.3 Function Definitions 292.4 Iteration and Recursion 302.5 Lists and Pattern Matching 342.6 Data Types 402.7 Higher-Order Functions 443 Syntax 493.1 Context-Free Grammars 503.2 Parse Trees 543.3 Abstract Syntax 563.4 Abstract Syntax Idioms 623.4.1 Factoring 633.4.2 Replacing Grammar Recursion by Lists 653.4.3 Grouping Associative Operations Using Lists 683.4.4 Representing Optional Syntax Elements 704 Denotational Semantics 734.1 Defining Semantics in Three Steps 764.2 Systematic Construction of Semantic Domains 804.2.1 Error Domains 824.2.2 Product Domains 864.2.3 Union Domains 874.2.4 Domains for Modeling Stateful Computation 895 Types 975.1 Inference Rules 985.2 Type Systems 1025.2.1 The Language of Types 1025.2.2 Typing Rules 1055.3 Type Checking 1095.4 Type Safety 1155.5 Static and Dynamic Typing 1176 Scope 1236.1 The Landscape of Programs: Blocks and Scope 1246.2 The Runtime Stack 1306.3 Static vs. Dynamic Scoping 1347 Parameter Passing 1397.1 Call-by-Value 1417.2 Call-by-Reference 1447.3 Call-by-Value-Result 1467.4 Call-by-Name 1487.5 Call-by-Need 1507.6 Summary 1528 Logic Programming with Prolog 1538.1 Getting Started 1548.2 Predicates and Goals 1578.2.1 Predicates 1588.2.2 Goals 1598.2.3 Repeated Variables (aka Non-linear Patterns) 1618.2.4 Conjunction 1628.2.5 Expressing Joins 1638.2.6 A Simple Operational Evaluation Model for Prolog 1658.3 Rules 1668.4 Recursion 1718.4.1 Trees as Computation Traces 1728.4.2 Left Recursion 1738.5 Prolog’s Search Mechanism 1748.5.1 Unification 1758.5.2 Scan, Expand, and Backtrack 1778.6 Structures 1798.7 Lists 1868.8 Numbers and Arithmetic 1938.9 The Cut 1958.10 Negation 196Index 203