Real World OCaml: Functional Programming for the Masses

Cover
Half-title
Title page
Copyright information
Dedication
Contents
1
Prologue
1.1
Why OCaml?
1.1.1
A Brief History
1.1.2
The Base Standard Library
1.1.3
The OCaml Platform
1.2
About This Book
1.2.1
What to Expect
1.2.2
Installation Instructions
1.2.3
Code Examples
1.3
Contributors
Part I Language Concepts
2
A Guided Tour
2.1
OCaml as a Calculator
2.2
Functions and Type Inference
2.2.1
Type Inference
2.2.2
Inferring Generic Types
2.3
Tuples, Lists, Options, and Pattern Matching
2.3.1
Tuples
2.3.2
Lists
2.3.3
Options
2.4
Records and Variants
2.5
Imperative Programming
2.5.1
Arrays
2.5.2
Mutable Record Fields
2.5.3
Refs
2.5.4
For and While Loops
2.6
A Complete Program
2.6.1
Compiling and Running
2.7
Where to Go from Here
3
Variables and Functions
3.1
Variables
3.1.1
Pattern Matching and Let
3.2
Functions
3.2.1
Anonymous Functions
3.2.2
Multiargument Functions
3.2.3
Recursive Functions
3.2.4
Prefix and Infix Operators
3.2.5
Declaring Functions with function
3.2.6
Labeled Arguments
3.2.7
Optional Arguments
4
Lists and Patterns
4.1
List Basics
4.2
Using Patterns to Extract Data from a List
4.3
Limitations (and Blessings) of Pattern Matching
4.3.1
Performance
4.3.2
Detecting Errors
4.4
Using the List Module Effectively
4.4.1
More Useful List Functions
4.5
Tail Recursion
4.6
Terser and Faster Patterns
5
Files, Modules, and Programs
5.1
Single-File Programs
5.2
Multifile Programs and Modules
5.3
Signatures and Abstract Types
5.4
Concrete Types in Signatures
5.5
Nested Modules
5.6
Opening Modules
5.6.1
Open Modules Rarely
5.6.2
Prefer Local Opens
5.6.3
Using Module Shortcuts Instead
5.7
Including Modules
5.8
Common Errors with Modules
5.8.1
Type Mismatches
5.8.2
Missing Definitions
5.8.3
Type Definition Mismatches
5.8.4
Cyclic Dependencies
5.9
Designing with Modules
5.9.1
Expose Concrete Types Rarely
5.9.2
Design for the Call Site
5.9.3
Create Uniform Interfaces
5.9.4
Interfaces Before Implementations
6
Records
6.1
Patterns and Exhaustiveness
6.2
Field Punning
6.3
Reusing Field Names
6.4
Functional Updates
6.5
Mutable Fields
6.6
First-Class Fields
7
Variants
7.1
Catch-All Cases and Refactoring
7.2
Combining Records and Variants
7.2.1
Embedded Records
7.3
Variants and Recursive Data Structures
7.4
Polymorphic Variants
7.4.1
Example: Terminal Colors Redux
7.4.2
When to Use Polymorphic Variants
8
Error Handling
8.1
Error-Aware Return Types
8.1.1
Encoding Errors with Result
8.1.2
Error and Or_error
8.1.3
bind and Other Error Handling Idioms
8.2
Exceptions
8.2.1
Helper Functions for Throwing Exceptions
8.2.2
Exception Handlers
8.2.3
Cleaning Up in the Presence of Exceptions
8.2.4
Catching Specific Exceptions
8.2.5
Backtraces
8.2.6
From Exceptions to Error-Aware Types and Back Again
8.3
Choosing an Error-Handling Strategy
9
Imperative Programming
9.1
Example: Imperative Dictionaries
9.2
Primitive Mutable Data
9.2.1
Array-Like Data
9.2.2
Mutable Record and Object Fields and Ref Cells
9.2.3
Foreign Functions
9.3
For and While Loops
9.4
Example: Doubly Linked Lists
9.4.1
Modifying the List
9.4.2
Iteration Functions
9.5
Laziness and Other Benign Effects
9.5.1
Memoization and Dynamic Programming
9.6
Input and Output
9.6.1
Terminal I/O
9.6.2
Formatted Output with printf
9.6.3
File I/O
9.7
Order of Evaluation
9.8
Side Effects and Weak Polymorphism
9.8.1
The Value Restriction
9.8.2
Partial Application and the Value Restriction
9.8.3
Relaxing the Value Restriction
9.9
Summary
10
GADTs
10.1
A Little Language
10.1.1
Making the Language Type-Safe
10.1.2
Trying to Do Better with Ordinary Variants
10.1.3
GADTs to the Rescue
10.1.4
GADTs, Locally Abstract Types, and Polymorphic Recursion
10.2
When Are GADTs Useful?
10.2.1
Varying Your Return Type
10.2.2
Capturing the Unknown
10.2.3
Abstracting Computational Machines
10.2.4
Narrowing the Possibilities
10.3
Limitations of GADTs
10.3.1
Or-Patterns
10.3.2
Deriving Serializers
11
Functors
11.1
Trivial Example
11.2
A Bigger Example: Computing with Intervals
11.2.1
Making the Functor Abstract
11.2.2
Sharing Constraints
11.2.3
Destructive Substitution
11.2.4
Using Multiple Interfaces
11.3
Extending Modules
12
First-Class Modules
12.1
Working with First-Class Modules
12.1.1
Creating First-Class Modules
12.1.2
Inference and Anonymous Modules
12.1.3
Unpacking First-Class Modules
12.1.4
Functions for Manipulating First-Class Modules
12.1.5
Richer First-Class Modules
12.1.6
Exposing types
12.2
Example: A Query-Handling Framework
12.2.1
Implementing a Query Handler
12.2.2
Dispatching to Multiple Query Handlers
12.2.3
Loading and Unloading Query Handlers
12.3
Living Without First-Class Modules
13
Objects
13.1
OCaml Objects
13.2
Object Polymorphism
13.3
Immutable Objects
13.4
When to Use Objects
13.5
Subtyping
13.5.1
Width Subtyping
13.5.2
Depth Subtyping
13.5.3
Variance
13.5.4
Narrowing
13.5.5
Subtyping Versus Row Polymorphism
14
Classes
14.1
OCaml Classes
14.2
Class Parameters and Polymorphism
14.3
Object Types as Interfaces
14.3.1
Functional Iterators
14.4
Inheritance
14.5
Class Types
14.6
Open Recursion
14.7
Private Methods
14.8
Binary Methods
14.9
Virtual Classes and Methods
14.9.1
Create Some Simple Shapes
14.10
Initializers
14.11
Multiple Inheritance
14.11.1
How Names Are Resolved
14.11.2
Mixins
14.11.3
Displaying the Animated Shapes
Part II Tools and Techniques
15
Maps and Hash Tables
15.1
Maps
15.1.1
Sets
15.1.2
Modules and Comparators
15.1.3
Why Do We Need Comparator Witnesses?
15.1.4
The Polymorphic Comparator
15.1.5
Satisfying Comparator.S with [@@deriving]
15.1.6
Applying [@@deriving] to Maps and Sets
15.1.7
Trees
15.2
Hash Tables
15.2.1
Time Complexity of Hash Tables
15.2.2
Collisions with the Polymorphic Hash Function
15.3
Choosing Between Maps and Hash Tables
16
Command-Line Parsing
16.1
Basic Command-Line Parsing
16.1.1
Defining an Anonymous Argument
16.1.2
Defining Basic Commands
16.1.3
Running Commands
16.1.4
Multi-Argument Commands
16.2
Argument Types
16.2.1
Defining Custom Argument Types
16.2.2
Optional and Default Arguments
16.2.3
Sequences of Arguments
16.3
Adding Labeled Flags
16.4
Grouping Subcommands Together
16.5
Prompting for Interactive Input
16.6
Command-Line Autocompletion with bash
16.6.1
Generating Completion Fragments from Command
16.6.2
Installing the Completion Fragment
16.7
Alternative Command-Line Parsers
17
Concurrent Programming with Async
17.1
Async Basics
17.1.1
Using Let Syntax
17.1.2
Ivars and Upon
17.2
Example: An Echo Server
17.2.1
Improving the Echo Server
17.3
Example: Searching Definitions with DuckDuckGo
17.3.1
URI Handling
17.3.2
Parsing JSON Strings
17.3.3
Executing an HTTP Client Query
17.4
Exception Handling
17.4.1
Monitors
17.4.2
Example: Handling Exceptions with DuckDuckGo
17.5
Timeouts, Cancellation, and Choices
17.6
Working with System Threads
17.6.1
Thread-Safety and Locking
18
Testing
18.1
Inline Tests
18.1.1
More Readable Errors with test_eq
18.1.2
Where Should Tests Go?
18.2
Expect Tests
18.2.1
Basic Mechanics
18.2.2
What Are Expect Tests Good For?
18.2.3
Exploratory Programming
18.2.4
Visualizing Complex Behavior
18.2.5
End-to-End Tests
18.2.6
How to Make a Good Expect Test
18.3
Property Testing with Quickcheck
18.3.1
Handling Complex Types
18.3.2
More Control with Let-Syntax
18.4
Other Testing Tools
18.4.1
Other Tools to Do (Mostly) the Same Things
18.4.2
Fuzzing
19
Handling JSON Data
19.1
JSON Basics
19.2
Parsing JSON with Yojson
19.3
Selecting Values from JSON Structures
19.4
Constructing JSON Values
19.5
Using Nonstandard JSON Extensions
19.6
Automatically Mapping JSON to OCaml Types
19.6.1
ATD Basics
19.6.2
ATD Annotations
19.6.3
Compiling ATD Specifications to OCaml
19.6.4
Example: Querying GitHub Organization Information
20
Parsing with OCamllex and Menhir
20.1
Lexing and Parsing
20.2
Defining a Parser
20.2.1
Describing the Grammar
20.2.2
Parsing Sequences
20.3
Defining a Lexer
20.3.1
OCaml Prelude
20.3.2
Regular Expressions
20.3.3
Lexing Rules
20.3.4
Recursive Rules
20.4
Bringing It All Together
21
Data Serialization with S-Expressions
21.1
Basic Usage
21.1.1
S-Expression Converters for New Types
21.2
The Sexp Format
21.3
Preserving Invariants
21.4
Getting Good Error Messages
21.5
Sexp-Conversion Directives
21.5.1
@sexp.opaque
21.5.2
@sexp.list
21.5.3
@sexp.option
21.5.4
Specifying Defaults
22
The OCaml Platform
22.1
A Hello World OCaml Project
22.1.1
Setting Up an Opam Local Switch
22.1.2
Choosing an OCaml Compiler Version
22.1.3
Structure of an OCaml Project
22.1.4
Defining Module Names
22.1.5
Defining Libraries as Collections of Modules
22.1.6
Writing Test Cases for a Library
22.1.7
Building an Executable Program
22.2
Setting Up an Integrated Development Environment
22.2.1
Using Visual Studio Code
22.2.2
Browsing Interface Documentation
22.2.3
Autoformatting Your Source Code
22.3
Publishing Your Code Online
22.3.1
Defining Opam Packages
22.3.2
Generating Project Metadata from Dune
22.3.3
Setting up Continuous Integration
22.3.4
Other Conventions
22.3.5
Releasing Your Code into the Opam Repository
22.4
Learning More from Real Projects
Part III The Compiler and Runtime System
23
Foreign Function Interface
23.1
Example: A Terminal Interface
23.2
Basic Scalar C Types
23.3
Pointers and Arrays
23.3.1
Allocating Typed Memory for Pointers
23.3.2
Using Views to Map Complex Values
23.4
Structs and Unions
23.4.1
Defining a Structure
23.4.2
Adding Fields to Structures
23.4.3
Incomplete Structure Definitions
23.4.4
Defining Arrays
23.5
Passing Functions to C
23.5.1
Example: A Command-Line Quicksort
23.6
Learning More About C Bindings
23.6.1
Struct Memory Layout
24
Memory Representation of Values
24.1
OCaml Blocks and Values
24.1.1
Distinguishing Integers and Pointers at Runtime
24.2
Blocks and Values
24.2.1
Integers, Characters, and Other Basic Types
24.3
Tuples, Records, and Arrays
24.31
Floating-Point Numbers and Arrays
24.4
Variants and Lists
24.5
Polymorphic Variants
24.6
String Values
24.7
Custom Heap Blocks
24.7.1
Managing External Memory with Bigarray
25
Understanding the Garbage Collector
25.1
Mark and Sweep Garbage Collection
25.2
Generational Garbage Collection
25.3 The
Fast Minor Heap
25.3.1
Allocating on the Minor Heap
25.4
The Long-Lived Major Heap
25..4.1
Allocating on the Major Heap
25.4.2
Memory Allocation Strategies
25.4.3
Marking and Scanning the Heap
25.4.4
Heap Compaction
25.4.5
Intergenerational Pointers
25.5
Attaching Finalizer Functions to Values
26
The Compiler Frontend: Parsing and Type Checking
26.1
An Overview of the Toolchain
26.1.1
Obtaining the Compiler Source Code
26.2
Parsing Source Code
26.2.1
Syntax Errors
26.2.2
Generating Documentation from Interfaces
26.3
Preprocessing with ppx
26.3.1
Extension Attributes
26.3.2
Commonly Used Extension Attributes
26.3.3
Extension Nodes
26.4
Static Type Checking
26.4.1
Displaying Inferred Types from the Compiler
26.4.2
Type Inference
26.4.3
Modules and Separate Compilation
26.4.4
Wrapping Libraries with Module Aliases
26.4.5
Shorter Module Paths in Type Errors
26.5
The Typed Syntax Tree
26.5.1
Examining the Typed Syntax Tree Directly
27
The Compiler Backend: Bytecode and Native code
27.1
The Untyped Lambda Form
27.1.1
Pattern Matching Optimization
27.1.2
Benchmarking Pattern Matching
27.2
Generating Portable Bytecode
27.2.1
Compiling and Linking Bytecode
27.2.2
Executing Bytecode
27.2.3
Embedding OCaml Bytecode in C
27.3
Compiling Fast Native Code
27.3.1
Inspecting Assembly Output
27.3.2
Debugging Native Code Binaries
27.3.3
Profiling Native Code
27.3.4
Embedding Native Code in C
27.4
Summarizing the File Extensions
Index