Description
Book SynopsisMichel Charpentier is an associate professor with the Computer Science department at the University of New Hampshire (UNH). His interests over the years have ranged from distributed systems to formal verification and mobile sensor networks. He has been with UNH since 1999 and currently teaches courses in programming languages, concurrency, formal verification, and model-checking.
Table of ContentsForeword by Cay Horstmann xxiii
Preface xxv
Acknowledgments xxxv
About the Author xxxvii
Part I. Functional Programming 1
Chapter 1: Concepts of Functional Programming 3
1.1 What Is Functional Programming? 3
1.2 Functions 4
1.3 From Functions to Functional Programming Concepts 6
1.4 Summary 7
Chapter 2: Functions in Programming Languages 9
2.1 Defining Functions 9
2.2 Composing Functions 10
2.3 Functions Defined as Methods 12
2.4 Operators Defined as Methods 12
2.5 Extension Methods 13
2.6 Local Functions 14
2.7 Repeated Arguments 15
2.8 Optional Arguments 16
2.9 Named Arguments 16
2.10 Type Parameters 17
2.11 Summary 19
Chapter 3: Immutability 21
3.1 Pure and Impure Functions 21
3.2 Actions 23
3.3 Expressions Versus Statements 25
3.4 Functional Variables 26
3.5 Immutable Objects 28
3.6 Implementation of Mutable State 29
3.7 Functional Lists 31
3.8 Hybrid Designs 32
3.9 Updating Collections of Mutable/Immutable Objects 35
3.10 Summary 36
Chapter 4: Case Study: Active–Passive Sets 39
4.1 Object-Oriented Design 39
4.2 Functional Values 41
4.3 Functional Objects 43
4.4 Summary 44
Chapter 5: Pattern Matching and Algebraic Data Types 47
5.1 Functional Switch 47
5.2 Tuples 48
5.3 Options 50
5.4 Revisiting Functional Lists 51
5.5 Trees 53
5.6 Illustration: List Zipper 56
5.7 Extractors 59
5.8 Summary 60
Chapter 6: Recursive Programming 63
6.1 The Need for Recursion 63
6.2 Recursive Algorithms 65
6.3 Key Principles of Recursive Algorithms 67
6.4 Recursive Structures 69
6.5 Tail Recursion 71
6.6 Examples of Tail Recursive Functions 73
6.7 Summary 77
Chapter 7: Recursion on Lists 79
7.1 Recursive Algorithms as Equalities 79
7.2 Traversing Lists 80
7.3 Returning Lists 82
7.4 Building Lists from the Execution Stack 84
7.5 Recursion on Multiple/Nested Lists 85
7.6 Recursion on Sublists Other Than the Tail 88
7.7 Building Lists in Reverse Order 90
7.8 Illustration: Sorting 92
7.9 Building Lists Efficiently 94
7.10 Summary 96
Chapter 8: Case Study: Binary Search Trees 99
8.1 Binary Search Trees 99
8.2 Sets of Integers as Binary Search Trees 100
8.3 Implementation Without Rebalancing 102
8.4 Self-Balancing Trees 107
8.5 Summary 113
Chapter 9: Higher-Order Functions 115
9.1 Functions as Values 115
9.2 Currying 118
9.3 Function Literals 120
9.4 Functions Versus Methods 123
9.5 Single-Abstract-Method Interfaces 124
9.6 Partial Application 125
9.7 Closures 130
9.8 Inversion of Control 133
9.9 Summary 133
Chapter 10: Standard Higher-Order Functions 137
10.1 Functions with Predicate Arguments 137
10.2 map and foreach 140
10.3 atMap 141
10.4 fold and reduce 146
10.5 iterate, tabulate, and unfold 148
10.6 sortWith, sortBy, maxBy, and minBy 149
10.7 groupBy and groupMap 150
10.8 Implementing Standard Higher-Order Functions 152
10.9 foreach, map, atMap, and for-Comprehensions 152
10.10 Summary 155
Chapter 11: Case Study: File Systems as Trees 157
11.1 Design Overview 157
11.2 A Node-Searching Helper Function 158
11.3 String Representation 158
11.4 Building Trees 160
11.5 Querying 164
11.6 Navigation 168
11.7 Tree Zipper 169
11.8 Summary 172
Chapter 12: Lazy Evaluation 173
12.1 Delayed Evaluation of Arguments 173
12.2 By-Name Arguments 174
12.3 Control Abstraction 176
12.4 Internal Domain-Specifc Languages 179
12.5 Streams as Lazily Evaluated Lists 180
12.6 Streams as Pipelines 182
12.7 Streams as Infinite Data Structures 184
12.8 Iterators 184
12.9 Lists, Streams, Iterators, and Views 187
12.10 Delayed Evaluation of Fields and Local Variables 190
12.11 Illustration: Subset-Sum 191
12.12 Summary 193
Chapter 13: Handling Failures 195
13.1 Exceptions and Special Values 195
13.2 Using Option 197
13.3 Using Try 198
13.4 Using Either 199
13.5 Higher-Order Functions and Pipelines 201
13.6 Summary 204
Chapter 14: Case Study: Trampolines 205
14.1 Tail-Call Optimization 205
14.2 Trampolines for Tail-Calls 206
14.3 Tail-Call Optimization in Java 207
14.4 Dealing with Non-Tail-Calls 209
14.5 Summary 213
A Brief Interlude 215
Chapter 15: Types (and Related Concepts) 217
15.1 Typing Strategies 217
15.2 Types as Sets 222
15.3 Types as Services 223
15.4 Abstract Data Types 224
15.5 Type Inference 225
15.6 Subtypes 229
15.7 Polymorphism 232
15.8 Type Variance 235
15.9 Type Bounds 241
15.10 Type Classes 245
15.11 Summary 250
Part II. Concurrent Programming 253
Chapter 16: Concepts of Concurrent Programming 255
16.1 Non-sequential Programs 255
16.2 Concurrent Programming Concepts 258
16.3 Summary 259
Chapter 17: Threads and Nondeterminism 261
17.1 Threads of Execution 261
17.2 Creating Threads Using Lambda Expressions 263
17.3 Nondeterministic Behavior of Multithreaded Programs 263
17.4 Thread Termination 264
17.5 Testing and Debugging Multithreaded Programs 266
17.6 Summary 268
Chapter 18: Atomicity and Locking 271
18.1 Atomicity 271
18.2 Non-atomic Operations 273
18.3 Atomic Operations and Non-atomic Composition 274
18.4 Locking 278
18.5 Intrinsic Locks 279
18.6 Choosing Locking Targets 281
18.7 Summary 283
Chapter 19: Thread-Safe Objects 285
19.1 Immutable Objects 285
19.2 Encapsulating Synchronization Policies 286
19.3 Avoiding Reference Escape 288
19.4 Public and Private Locks 289
19.5 Leveraging Immutable Types 290
19.6 Thread-Safety 293
19.7 Summary 295
Chapter 20: Case Study: Thread-Safe Queue 297
20.1 Queues as Pairs of Lists 297
20.2 Single Public Lock Implementation 298
20.3 Single Private Lock Implementation 301
20.4 Applying Lock Splitting 303
20.5 Summary 305
Chapter 21: Thread Pools 307
21.1 Fire-and-Forget Asynchronous Execution 307
21.2 Illustration: Parallel Server 309
21.3 Different Types of Thread Pools 312
21.4 Parallel Collections 314
21.5 Summary 318
Chapter 22: Synchronization 321
22.1 Illustration of the Need for Synchronization 321
22.2 Synchronizers 324
22.3 Deadlocks 325
22.4 Debugging Deadlocks with Thread Dumps 328
22.5 The Java Memory Model 330
22.6 Summary 335
Chapter 23: Common Synchronizers 337
23.1 Locks 337
23.2 Latches and Barriers 339
23.3 Semaphores 341
23.4 Conditions 343
23.5 Blocking Queues 349
23.6 Summary 353
Chapter 24: Case Study: Parallel Execution 355
24.1 Sequential Reference Implementation 355
24.2 One New Thread per Task 356
24.3 Bounded Number of Threads 357
24.4 Dedicated Thread Pool 359
24.5 Shared Thread Pool 360
24.6 Bounded Thread Pool 361
24.7 Parallel Collections 362
24.8 Asynchronous Task Submission Using Conditions 362
24.9 Two-Semaphore Implementation 367
24.10 Summary 368
Chapter 25: Futures and Promises 369
25.1 Functional Tasks 369
25.2 Futures as Synchronizers 371
25.3 Timeouts, Failures, and Cancellation 374
25.4 Future Variants 375
25.5 Promises 375
25.6 Illustration: Thread-Safe Caching 377
25.7 Summary 379
Chapter 26: Functional-Concurrent Programming 381
26.1 Correctness and Performance Issues with Blocking 381
26.2 Callbacks 384
26.3 Higher-Order Functions on Futures 385
26.4 Function atMap on Futures 388
26.5 Illustration: Parallel Server Revisited 390
26.6 Functional-Concurrent Programming Patterns 393
26.7 Summary 397
Chapter 27: Minimizing Thread Blocking 399
27.1 Atomic Operations 399
27.2 Lock-Free Data Structures 402
27.3 Fork/Join Pools 405
27.4 Asynchronous Programming 406
27.5 Actors 407
27.6 Reactive Streams 411
27.7 Non-blocking Synchronization 412
27.8 Summary 414
Chapter 28: Case Study: Parallel Strategies 417
28.1 Problem Definition 417
28.2 Sequential Implementation with Timeout 419
28.3 Parallel Implementation Using invokeAny 420
28.4 Parallel Implementation Using CompletionService 421
28.5 Asynchronous Implementation with Scala Futures 422
28.6 Asynchronous Implementation with CompletableFuture 426
28.7 Caching Results from Strategies 427
28.8 Summary 431
Appendix A. Features of Java and Kotlin 433
A.1 Functions in Java and Kotlin 433
A.2 Immutability 436
A.3 Pattern Matching and Algebraic Data Types 437
A.4 Recursive Programming 439
A.5 Higher-Order Functions 440
A.6 Lazy Evaluation 446
A.7 Handling Failures 449
A.8 Types 451
A.9 Threads 453
A.10 Atomicity and Locking 454
A.11 Thread-Safe Objects 455
A.12 Thread Pools 457
A.13 Synchronization 459
A.14 Futures and Functional-Concurrent Programming 460
A.15 Minimizing Thread Blocking 461
Glossary 463
Index 465
