Programming Language Fundamentals

Preface vii

About the Companion Website xi

1 Introduction 1

1.1 The Role of Programming Languages in Computer Science 2

1.2 Why Study Programming Language Fundamentals? 4

1.3 What Are the Fundamentals of Programming Languages? 5

1.4 How to Study the Fundamentals of Programming Languages? 8

1.5 About Programming Paradigms 9

2 Functional Programming with Elm 13

2.1 Getting Started 14

2.2 Expressions, Values, and Their Types 18

2.2.1 Naming Values and Expressions 19

2.2.2 Tracing Evaluations 20

2.2.3 Tuples 25

2.3 Functions 26

2.3.1 Function Application 26

2.3.2 Currying and Partial Function Application 27

2.3.3 Function Definitions 29

2.4 Iteration and Recursion 30

2.5 Lists and Pattern Matching 34

2.6 Data Types 40

2.7 Higher-Order Functions 44

3 Syntax 49

3.1 Context-Free Grammars 50

3.2 Parse Trees 54

3.3 Abstract Syntax 56

3.4 Abstract Syntax Idioms 62

3.4.1 Factoring 63

3.4.2 Replacing Grammar Recursion by Lists 65

3.4.3 Grouping Associative Operations Using Lists 68

3.4.4 Representing Optional Syntax Elements 70

4 Denotational Semantics 73

4.1 Defining Semantics in Three Steps 76

4.2 Systematic Construction of Semantic Domains 80

4.2.1 Error Domains 82

4.2.2 Product Domains 86

4.2.3 Union Domains 87

4.2.4 Domains for Modeling Stateful Computation 89

5 Types 97

5.1 Inference Rules 98

5.2 Type Systems 102

5.2.1 The Language of Types 102

5.2.2 Typing Rules 105

5.3 Type Checking 109

5.4 Type Safety 115

5.5 Static and Dynamic Typing 117

6 Scope 123

6.1 The Landscape of Programs: Blocks and Scope 124

6.2 The Runtime Stack 130

6.3 Static vs. Dynamic Scoping 134

7 Parameter Passing 139

7.1 Call-by-Value 141

7.2 Call-by-Reference 144

7.3 Call-by-Value-Result 146

7.4 Call-by-Name 148

7.5 Call-by-Need 150

7.6 Summary 152

8 Logic Programming with Prolog 153

8.1 Getting Started 154

8.2 Predicates and Goals 157

8.2.1 Predicates 158

8.2.2 Goals 159

8.2.3 Repeated Variables (aka Non-linear Patterns) 161

8.2.4 Conjunction 162

8.2.5 Expressing Joins 163

8.2.6 A Simple Operational Evaluation Model for Prolog 165

8.3 Rules 166

8.4 Recursion 171

8.4.1 Trees as Computation Traces 172

8.4.2 Left Recursion 173

8.5 Prolog’s Search Mechanism 174

8.5.1 Unification 175

8.5.2 Scan, Expand, and Backtrack 177

8.6 Structures 179

8.7 Lists 186

8.8 Numbers and Arithmetic 193

8.9 The Cut 195

8.10 Negation 196

Index 203