Functional and Concurrent Programming: Core Concepts and Features

Leverage Modern Language Constructs to Write High-Quality Code Faster The functional and concurrent programming language features supported by modern languages can be challenging, even for experienced developers. These features may appear intimidating to OOP programmers because of a misunderstanding of how they work. Programmers first need to become familiar with the abstract concepts that underlie these powerful features. In Functional and Concurrent Programming, Michel Charpentier introduces a core set of programming language constructs that will help you be productive in a variety of programming languages—now and in the future. Charpentier illustrates key concepts with numerous small, focused code examples, written in Scala, and with case studies that provide a thorough grounding in functional and concurrent programming skills. These skills will carry from language to language—including the most recent incarnations of Java. Using these features will enable developers and programmers to write high-quality code that is easier to understand, debug, optimize, and evolve. Key topics covered include: Recursion and tail recursion Pattern matching and algebraic datatypes Persistent structures and immutability Higher-order functions and lambda expressions Lazy evaluation and streams Threads and thread pools Atomicity and locking Synchronization and thread-safe objects Lock-free, non-blocking patterns Futures, promises, and functional-concurrent programming As a bonus, the book includes a discussion of common typing strategies used in modern programming languages, including type inference, subtyping, polymorphism, type classes, type bounds, and type variance. Most of the code examples are in Scala, which includes many of the standard features of functional and concurrent programming; however, no prior knowledge of Scala is assumed. You should be familiar with concepts such as classes, methods, objects, types, variables, loops, and conditionals and have enough programming experience to not be distracted by simple matters of syntax.

Table of Contents:
Foreword 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

About the Author :
Michel 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.