Detail View

Functional programming is rooted in lambda calculus, which constitutes the?world's smallest programming language. This well-respected text offers an accessible introduction to functional programming concepts and techniques for students of mathematics and computer science. The treatment is as nontechnical as possible, and it assumes no prior knowledge of mathematics or functional programming. Cogent examples illuminate the central ideas, and numerous exercises appear throughout the text, offering reinforcement of key concepts. All problems feature complete solutions.

Information Provided By: :

CONTENTS
Preface = ⅴ
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 = 38
 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 Strings 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 Composit 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 tree 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' type 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 = 159
 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