Functional and Concurrent Programming: Core Concepts and Features

Functional and Concurrent Programming: Core Concepts and Features

by Michel Charpentier
Released December 2022
Publisher(s): Addison-Wesley Professional
ISBN: 9780137466696

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

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 languagesnow 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 languageincluding 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

  1. Cover Page
  2. About This eBook
  3. Halftitle Page
  4. Title Page
  5. Copyright Page
  6. Dedication Page
  7. Contents
  8. List of Listings
  9. List of Figures
  10. Foreword by Cay Horstmann
  11. Preface
    1. Why Scala?
    2. Target Audience
    3. How to Read This Book
  12. Acknowledgments
  13. About the Author
  14. Part I: Functional Programming
    1. Chapter 1. Concepts of Functional Programming
      1. 1.1 What Is Functional Programming?
      2. 1.2 Functions
      3. 1.3 From Functions to Functional Programming Concepts
      4. 1.4 Summary
    2. Chapter 2. Functions in Programming Languages
      1. 2.1 Defining Functions
      2. 2.2 Composing Functions
      3. 2.3 Functions Defined as Methods
      4. 2.4 Operators Defined as Methods
      5. 2.5 Extension Methods
      6. 2.6 Local Functions
      7. 2.7 Repeated Arguments
      8. 2.8 Optional Arguments
      9. 2.9 Named Arguments
      10. 2.10 Type Parameters
      11. 2.11 Summary
    3. Chapter 3. Immutability
      1. 3.1 Pure and Impure Functions
      2. 3.2 Actions
      3. 3.3 Expressions Versus Statements
      4. 3.4 Functional Variables
      5. 3.5 Immutable Objects
      6. 3.6 Implementation of Mutable State
      7. 3.7 Functional Lists
      8. 3.8 Hybrid Designs
      9. 3.9 Updating Collections of Mutable/Immutable Objects
      10. 3.10 Summary
    4. Chapter 4. Case Study: Active–Passive Sets
      1. 4.1 Object-Oriented Design
      2. 4.2 Functional Values
      3. 4.3 Functional Objects
      4. 4.4 Summary
    5. Chapter 5. Pattern Matching and Algebraic Data Types
      1. 5.1 Functional Switch
      2. 5.2 Tuples
      3. 5.3 Options
      4. 5.4 Revisiting Functional Lists
      5. 5.5 Trees
      6. 5.6 Illustration: List Zipper
      7. 5.7 Extractors
      8. 5.8 Summary
    6. Chapter 6. Recursive Programming
      1. 6.1 The Need for Recursion
      2. 6.2 Recursive Algorithms
      3. 6.3 Key Principles of Recursive Algorithms
      4. 6.4 Recursive Structures
      5. 6.5 Tail Recursion
      6. 6.6 Examples of Tail Recursive Functions
      7. 6.7 Summary
    7. Chapter 7. Recursion on Lists
      1. 7.1 Recursive Algorithms as Equalities
      2. 7.2 Traversing Lists
      3. 7.3 Returning Lists
      4. 7.4 Building Lists from the Execution Stack
      5. 7.5 Recursion on Multiple/Nested Lists
      6. 7.6 Recursion on Sublists Other Than the Tail
      7. 7.7 Building Lists in Reverse Order
      8. 7.8 Illustration: Sorting
      9. 7.9 Building Lists Efficiently
      10. 7.10 Summary
    8. Chapter 8. Case Study: Binary Search Trees
      1. 8.1 Binary Search Trees
      2. 8.2 Sets of Integers as Binary Search Trees
      3. 8.3 Implementation Without Rebalancing
      4. 8.4 Self-Balancing Trees
      5. 8.5 Summary
    9. Chapter 9. Higher-Order Functions
      1. 9.1 Functions as Values
      2. 9.2 Currying
      3. 9.3 Function Literals
      4. 9.4 Functions Versus Methods
      5. 9.5 Single-Abstract-Method Interfaces
      6. 9.6 Partial Application
      7. 9.7 Closures
      8. 9.8 Inversion of Control
      9. 9.9 Summary
    10. Chapter 10. Standard Higher-Order Functions
      1. 10.1 Functions with Predicate Arguments
      2. 10.2 map and foreach
      3. 10.3 flatMap
      4. 10.4 fold and reduce
      5. 10.5 iterate, tabulate, and unfold
      6. 10.6 sortWith, sortBy, maxBy, and minBy
      7. 10.7 groupBy and groupMap
      8. 10.8 Implementing Standard Higher-Order Functions
      9. 10.9 foreach, map, flatMap, and for-Comprehensions
      10. 10.10 Summary
    11. Chapter 11. Case Study: File Systems as Trees
      1. 11.1 Design Overview
      2. 11.2 A Node-Searching Helper Function
      3. 11.3 String Representation
      4. 11.4 Building Trees
      5. 11.5 Querying
      6. 11.6 Navigation
      7. 11.7 Tree Zipper
      8. 11.8 Summary
    12. Chapter 12. Lazy Evaluation
      1. 12.1 Delayed Evaluation of Arguments
      2. 12.2 By-Name Arguments
      3. 12.3 Control Abstraction
      4. 12.4 Internal Domain-Specific Languages
      5. 12.5 Streams as Lazily Evaluated Lists
      6. 12.6 Streams as Pipelines
      7. 12.7 Streams as Infinite Data Structures
      8. 12.8 Iterators
      9. 12.9 Lists, Streams, Iterators, and Views
      10. 12.10 Delayed Evaluation of Fields and Local Variables
      11. 12.11 Illustration: Subset-Sum
      12. 12.12 Summary
    13. Chapter 13. Handling Failures
      1. 13.1 Exceptions and Special Values
      2. 13.2 Using Option
      3. 13.3 Using Try
      4. 13.4 Using Either
      5. 13.5 Higher-Order Functions and Pipelines
      6. 13.6 Summary
    14. Chapter 14. Case Study: Trampolines
      1. 14.1 Tail-Call Optimization
      2. 14.2 Trampolines for Tail-Calls
      3. 14.3 Tail-Call Optimization in Java
      4. 14.4 Dealing with Non-Tail-Calls
      5. 14.5 Summary
  15. A Brief Interlude
    1. Chapter 15. Types (and Related Concepts)
      1. 15.1 Typing Strategies
      2. 15.2 Types as Sets
      3. 15.3 Types as Services
      4. 15.4 Abstract Data Types
      5. 15.5 Type Inference
      6. 15.6 Subtypes
      7. 15.7 Polymorphism
      8. 15.8 Type Variance
      9. 15.9 Type Bounds
      10. 15.10 Type Classes
      11. 15.11 Summary
  16. Part II: Concurrent Programming
    1. Chapter 16. Concepts of Concurrent Programming
      1. 16.1 Non-sequential Programs
      2. 16.2 Concurrent Programming Concepts
      3. 16.3 Summary
    2. Chapter 17. Threads and Nondeterminism
      1. 17.1 Threads of Execution
      2. 17.2 Creating Threads Using Lambda Expressions
      3. 17.3 Nondeterminism of Multithreaded Programs
      4. 17.4 Thread Termination
      5. 17.5 Testing and Debugging Multithreaded Programs
      6. 17.6 Summary
    3. Chapter 18. Atomicity and Locking
      1. 18.1 Atomicity
      2. 18.2 Non-atomic Operations
      3. 18.3 Atomic Operations and Non-atomic Composition
      4. 18.4 Locking
      5. 18.5 Intrinsic Locks
      6. 18.6 Choosing Locking Targets
      7. 18.7 Summary
    4. Chapter 19. Thread-Safe Objects
      1. 19.1 Immutable Objects
      2. 19.2 Encapsulating Synchronization Policies
      3. 19.3 Avoiding Reference Escape
      4. 19.4 Public and Private Locks
      5. 19.5 Leveraging Immutable Types
      6. 19.6 Thread-Safety
      7. 19.7 Summary
    5. Chapter 20. Case Study: Thread-Safe Queue
      1. 20.1 Queues as Pairs of Lists
      2. 20.2 Single Public Lock Implementation
      3. 20.3 Single Private Lock Implementation
      4. 20.4 Applying Lock Splitting
      5. 20.5 Summary
    6. Chapter 21. Thread Pools
      1. 21.1 Fire-and-Forget Asynchronous Execution
      2. 21.2 Illustration: Parallel Server
      3. 21.3 Different Types of Thread Pools
      4. 21.4 Parallel Collections
      5. 21.5 Summary
    7. Chapter 22. Synchronization
      1. 22.1 Illustration of the Need for Synchronization
      2. 22.2 Synchronizers
      3. 22.3 Deadlocks
      4. 22.4 Debugging Deadlocks with Thread Dumps
      5. 22.5 The Java Memory Model
      6. 22.6 Summary
    8. Chapter 23. Common Synchronizers
      1. 23.1 Locks
      2. 23.2 Latches and Barriers
      3. 23.3 Semaphores
      4. 23.4 Conditions
      5. 23.5 Blocking Queues
      6. 23.6 Summary
    9. Chapter 24. Case Study: Parallel Execution
      1. 24.1 Sequential Reference Implementation
      2. 24.2 One New Thread per Task
      3. 24.3 Bounded Number of Threads
      4. 24.4 Dedicated Thread Pool
      5. 24.5 Shared Thread Pool
      6. 24.6 Bounded Thread Pool
      7. 24.7 Parallel Collections
      8. 24.8 Asynchronous Task Submission Using Conditions
      9. 24.9 Two-Semaphore Implementation
      10. 24.10 Summary
    10. Chapter 25. Futures and Promises
      1. 25.1 Functional Tasks
      2. 25.2 Futures as Synchronizers
      3. 25.3 Timeouts, Failures, and Cancellation
      4. 25.4 Future Variants
      5. 25.5 Promises
      6. 25.6 Illustration: Thread-Safe Caching
      7. 25.7 Summary
    11. Chapter 26. Functional-Concurrent Programming
      1. 26.1 Correctness and Performance Issues with Blocking
      2. 26.2 Callbacks
      3. 26.3 Higher-Order Functions on Futures
      4. 26.4 Function flatMap on Futures
      5. 26.5 Illustration: Parallel Server Revisited
      6. 26.6 Functional-Concurrent Programming Patterns
      7. 26.7 Summary
    12. Chapter 27. Minimizing Thread Blocking
      1. 27.1 Atomic Operations
      2. 27.2 Lock-Free Data Structures
      3. 27.3 Fork/Join Pools
      4. 27.4 Asynchronous Programming
      5. 27.5 Actors
      6. 27.6 Reactive Streams
      7. 27.7 Non-blocking Synchronization
      8. 27.8 Summary
    13. Chapter 28. Case Study: Parallel Strategies
      1. 28.1 Problem Definition
      2. 28.2 Sequential Implementation with Timeout
      3. 28.3 Parallel Implementation Using invokeAny
      4. 28.4 Parallel Implementation Using CompletionService
      5. 28.5 Asynchronous Implementation with Scala Futures
      6. 28.6 Asynchronous Implementation with CompletableFuture
      7. 28.7 Caching Results from Strategies
      8. 28.8 Summary
  17. Appendix A. Features of Java and Kotlin
    1. A.1 Functions in Java and Kotlin
    2. A.2 Immutability
    3. A.3 Pattern Matching and Algebraic Data Types
    4. A.4 Recursive Programming
    5. A.5 Higher-Order Functions
    6. A.6 Lazy Evaluation
    7. A.7 Handling Failures
    8. A.8 Types
    9. A.9 Threads
    10. A.10 Atomicity and Locking
    11. A.11 Thread-Safe Objects
    12. A.12 Thread Pools
    13. A.13 Synchronization
    14. A.14 Futures and Functional-Concurrent Programming
    15. A.15 Minimizing Thread Blocking
  18. Glossary
  19. Index

Product information

  • Title: Functional and Concurrent Programming: Core Concepts and Features
  • Author(s): Michel Charpentier
  • Release date: December 2022
  • Publisher(s): Addison-Wesley Professional
  • ISBN: 9780137466696