Table of Contents
Preface to the Dover Edition iii
Preface v
Chapter 1 Introduction 1
1.1 Names and values in programming 2
1.2 Names and values in imperative and functional languages 2
1.3 Execution order in imperative and functional languages 3
1.4 Repetition in imperative and functional languages 5
1.5 Data structures in functional languages 7
1.6 Functions as values 8
1.7 The origins of functional languages 9
1.8 Computing and the theory of computing 11
1.9 ? calculus 13
Summary 14
Chapter 2 λ calculus 15
2.1 Abstraction 16
2.2 Abstraction in programming languages 19
2.3 Introducing λ calculus 20
2.4 λ expressions 21
2.5 Simple λ functions 23
2.6 Introducing new syntax 30
2.7 Notations for naming functions and reduction 31
2.8 Functions from functions 31
2.9 Argument selection and argument pairing functions 33
2.10 Free and bound variables 33
2.11 Name clashes and α conversion 43
2.12 Simplification through η reduction 44
Summary 45
Exercises 47
Chapter 3 Conditions, booleans and numbers 49
3.1 Truth values and conditional expression 50
3.2 NOT 51
3.3 AND 52
3.4 OR 54
3.5 Natural numbers 55
3.6 Simplified notations 59
Summary 61
Exercises 62
Chapter 4 Recursion and arithmetic 65
4.1 Repetitions, iteration and recursion 66
4.2 Recursion through definitions? 68
4.3 Passing a function to itself 69
4.4 Applicative order reduction 72
4.5 Recursion function 73
4.6 Recursion notation 77
4.7 Arithmetic operations 78
Summary 82
Exercises 84
Chapter 5 Types 87
5.1 Types and programming 88
5.2 Types as objects and operations 89
5.3 Representing typed objects 91
5.4 Errors 92
5.5 Booleans 94
5.6 Typed conditional expression 97
5.7 Numbers and arithmetic 98
5.8 Characters 101
5.9 Repetitive type checking 104
5.10 Static and dynamic type checking 107
5.11 Infix operators 107
5.12 Case definitions and structure matching 108
Summary 111
Exercises 113
Chapter 6 Lists and strings 115
6.1 Lists 116
6.2 List representation 119
6.3 Operations on lists 122
6.4 List notation 124
6.5 Lists and evaluation 127
6.6 Deletion from a list 127
6.7 List comparison 129
6.8 Strings 131
6.9 String comparison 132
6.10 Numeric string to number conversion 134
6.11 Structure matching with lists 139
6.12 Ordered linear lists, insertion and sorting 140
6.13 Indexed linear list access 142
6.14 Mapping functions 146
Summary 150
Exercises 151
Chapter 7 Composite values and trees 153
7.1 Composite values 154
7.2 Processing composite value sequences 155
7.3 Selector functions 157
7.4 Generalized structure matching 160
7.5 Local definitions 164
7.6 Matching composite value results 164
7.7 List inefficiency 167
7.8 Trees 168
7.9 Adding values to ordered binary trees 169
7.10 Binary tree traversal 173
7.11 Binary tree search 174
7.12 Binary trees of composite values 176
7.13 Binary tree efficiency 178
7.14 Curried and uncurried functions 179
7.15 Partial application 181
7.16 Structures, values and functions 183
Summary 183
Exercises 184
Chapter 8 Evaluation 187
8.1 Termination and normal form 188
8.2 Normal order 189
8.3 Applicative order 190
8.4 Consistent applicative order use 191
8.5 Delaying evaluation 193
8.6 Evaluation termination, the halting problem, evaluation equivalence and the Church-Rosser theorems 196
8.7 Infinite objects 197
8.8 Lazy evaluation 199
Summary 204
Exercises 205
Chapter 9 Functional programming in Standard ML 207
9.1 Types 208
9.2 Lists 209
9.3 Tuples 210
9.4 Function types and expressions 211
9.5 Standard functions 212
9.6 Comparison operators 218
9.7 Functions 218
9.8 Making bound variables' types explicit 219
9.9 Definitions 220
9.10 Conditional expressions 221
9.11 Recursion and function definitions 221
9.12 Tuple selection 222
9.13 Pattern matching 223
9.14 Local definitions 225
9.15 Type expressions and abbreviated types 226
9.16 Type variables and polymorphism 227
9.17 New types 230
9.18 Trees 234
9.19 λ calculus in SML 237
9.20 Other features 238
Summary 238
Exercises 238
Chapter 10 Functional programming and LISP 243
10.1 Atoms, numbers and symbols 244
10.2 Forms, expressions and function applications 245
10.3 Logic 245
10.4 Arithmetic and numeric comparison 246
10.5 Lambda functions 248
10.6 Global definitions 250
10.7 Conditional expressions 251
10.8 Quoting 252
10.9 Lists 253
10.10 List selection 255
10.11 Recursion 256
10.12 Local definitions 257
10.13 Binary trees in LISP 257
10.14 Dynamic and lexical scope 259
10.15 Functions as values and arguments 261
10.16 Symbols, quoting and evaluation 263
10.17 λ calculus in LISP 265
10.18 λ calculus and Scheme 266
10.19 Other features 268
Summary 268
Exercises 268
Answers to exercises 273
Bibliography 305
Index 313
