Programming Language Fundamentals A Metalanguage Approach in Elm

Understand the key principles of programming languages

Programming languages are the tools needed to let algorithms run on electronic computers. As they form the linguistic interface between humans and machines, the understanding of programming languages is essential for being able to control machine behavior. Programming Language Fundamentals offers a precise, comprehensive introduction to the principles that are the basis of most programming languages. Explaining both functional programming and logic programming, it presents a broad perspective on programming and constitutes an indispensable introduction to the foundations of programming languages.

Programming Language Fundamentals readers will also find:

• Introduction to Elm as a metalanguage to encourage thinking and experimenting with programming languages in a formal way
• Detailed discussion of topics including abstract syntax, semantics, types, and more
• In-depth explanations of key concepts such as scope and parameter passing

Programming Language Fundamentals is ideal for undergraduate students in computer science, as well as researchers and practitioners working with programming languages who are looking to broaden their understanding of the field.

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

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.