Real World OCaml

• Prologue

  • Why OCaml?

    • A Brief History
    • The Base Standard Library
    • The OCaml Platform

  • About This Book

    • What to Expect
    • Installation Instructions
    • Code Examples

  • Contributors

Part 1: Language Concepts

• 1. A Guided Tour

  • Base and Core

  • OCaml as a Calculator

  • Functions and Type Inference

    • Type Inference
    • Inferring Generic Types
      • Type Errors Versus Exceptions

  • Tuples, Lists, Options, and Pattern Matching

    • Tuples
      • Operators in Base and the Stdlib
    • Lists
      • The List Module
      • Constructing Lists with ::
      • Semicolons Versus Commas
      • List Patterns Using Match
      • Recursive List Functions
    • Options

  • Records and Variants

    • Base and Polymorphic Comparison

  • Imperative Programming

    • Arrays
    • Mutable Record Fields
    • Refs
      • Nesting lets with let and in
    • For and While Loops

  • A Complete Program

    • Compiling and Running

  • Where to Go from Here

• 2. Variables and Functions

  • Variables

    • Why Don’t Variables Vary?
    • Pattern Matching and Let

  • Functions

    • Anonymous Functions
      • let and fun
    • Multiargument Functions
    • Recursive Functions
    • Prefix and Infix Operators
      • The Application Operator
    • Declaring Functions with function
    • Labeled Arguments
      • Where Are Labels Useful?
      • Higher-Order Functions and Labels
    • Optional Arguments
      • Explicit Passing of an Optional Argument
      • Inference of Labeled and Optional Arguments
      • Optional Arguments and Partial Application

• 3. Lists and Patterns

  • List Basics

  • Using Patterns to Extract Data from a List

  • Limitations (and Blessings) of Pattern Matching

    • Performance
    • Detecting Errors

  • Using the List Module Effectively

    • Performance of String.concat and ^
    • More Useful List Functions
      • Combining List Elements with List.reduce
      • Filtering with List.filter and List.filter_map
      • Partitioning with List.partition_tf
      • Combining lists

  • Tail Recursion

  • Terser and Faster Patterns

    • Polymorphic Compare

• 4. Files, Modules, and Programs

  • Single-File Programs

    • Where Is main?
    • Bytecode Versus Native Code

  • Multifile Programs and Modules

  • Signatures and Abstract Types

  • Concrete Types in Signatures

  • Nested Modules

  • Opening Modules

    • Open Modules Rarely
    • Prefer Local Opens
    • Using Module Shortcuts Instead

  • Including Modules

  • Common Errors with Modules

    • Type Mismatches
    • Missing Definitions
    • Type Definition Mismatches
    • Cyclic Dependencies

  • Designing with Modules

    • Expose Concrete Types Rarely
    • Design for the Call Site
    • Create Uniform Interfaces
    • Interfaces Before Implementations

• 5. Records

  • Patterns and Exhaustiveness

    • Compiler Warnings

  • Field Punning

  • Reusing Field Names

  • Functional Updates

  • Mutable Fields

  • First-Class Fields

• 6. Variants

  • Variants, Tuples and Parens

  • Catch-All Cases and Refactoring

  • Combining Records and Variants

    • Embedded Records

  • Variants and Recursive Data Structures

  • Polymorphic Variants

    • Polymorphic Variants and Catch-All Cases
    • Example: Terminal Colors Redux
    • When to Use Polymorphic Variants

• 7. Error Handling

  • Error-Aware Return Types

    • Encoding Errors with Result
    • Error and Or_error
    • bind and Other Error Handling Idioms
      • Monads and Let_syntax

  • Exceptions

    • Declaring Exceptions Using [@@deriving sexp]
    • Helper Functions for Throwing Exceptions
    • Exception Handlers
    • Cleaning Up in the Presence of Exceptions
    • Catching Specific Exceptions
    • Backtraces
    • From Exceptions to Error-Aware Types and Back Again

  • Choosing an Error-Handling Strategy

• 8. Imperative Programming

  • Example: Imperative Dictionaries

  • Primitive Mutable Data

    • Array-Like Data
      • Ordinary arrays
      • bytes and strings.
      • Bigarrays
    • Mutable Record and Object Fields and Ref Cells
      • Ref cells
    • Foreign Functions

  • For and While Loops

  • Example: Doubly Linked Lists

    • Cyclic Data Structures
    • Modifying the List
    • Iteration Functions

  • Laziness and Other Benign Effects

    • Memoization and Dynamic Programming
      • Limitations of let rec

  • Input and Output

    • Terminal I/O
    • Formatted Output with printf
      • Understanding Format Strings
    • File I/O

  • Order of Evaluation

  • Side Effects and Weak Polymorphism

    • The Value Restriction
    • Partial Application and the Value Restriction
    • Relaxing the Value Restriction

  • Summary

• 9. GADTs

  • A Little Language

    • Making the Language Type-Safe
    • Trying to Do Better with Ordinary Variants
    • GADTs to the Rescue
    • GADTs, Locally Abstract Types, and Polymorphic Recursion

  • When Are GADTs Useful?

    • Varying Your Return Type
    • Capturing the Unknown
    • Abstracting Computational Machines
    • Narrowing the Possibilities
      • A Completion-Sensitive Option Type
      • A Completion-Sensitive Request Type
      • Type Distinctness and Abstraction
      • Narrowing Without GADTs

  • Limitations of GADTs

    • Or-Patterns
    • Deriving Serializers

• 10. Functors

  • A Trivial Example

  • A Bigger Example: Computing with Intervals

    • Making the Functor Abstract
    • Sharing Constraints
    • Destructive Substitution
    • Using Multiple Interfaces

  • Extending Modules

• 11. First-Class Modules

  • Working with First-Class Modules

    • Creating First-Class Modules
    • Inference and Anonymous Modules
    • Unpacking First-Class Modules
    • Functions for Manipulating First-Class Modules
    • Richer First-Class Modules
    • Exposing types
      • More on Locally Abstract Types

  • Example: A Query-Handling Framework

    • Implementing a Query Handler
    • Dispatching to Multiple Query Handlers
    • Loading and Unloading Query Handlers

  • Living Without First-Class Modules

• 12. Objects

  • What Is Object-Oriented Programming?

  • OCaml Objects

  • Object Polymorphism

    • Elisions Are Polymorphic

  • Immutable Objects

  • When to Use Objects

  • Subtyping

    • Width Subtyping
    • Depth Subtyping
      • Polymorphic Variant Subtyping
    • Variance
      • Variance Annotations
    • Narrowing
    • Subtyping Versus Row Polymorphism

• 13. Classes

  • OCaml Classes

  • Class Parameters and Polymorphism

  • Object Types as Interfaces

    • Functional Iterators

  • Inheritance

  • Class Types

  • Open Recursion

  • Private Methods

  • Binary Methods

  • Virtual Classes and Methods

    • Create Some Simple Shapes

  • Initializers

  • Multiple Inheritance

    • How Names Are Resolved
    • Mixins
    • Displaying the Animated Shapes

Part 2: Tools and Techniques

• 14. Maps and Hash Tables

  • Maps

    • Sets
    • Modules and Comparators
    • Why Do We Need Comparator Witnesses?
    • The Polymorphic Comparator
      • The Perils of Polymorphic Compare
    • Satisfying Comparator.S with [@@deriving]
      • =, ==, and phys_equal
    • Applying [@@deriving] to Maps and Sets
    • Trees

  • Hash Tables

    • Time Complexity of Hash Tables
    • Collisions with the Polymorphic Hash Function

  • Choosing Between Maps and Hash Tables

• 15. Command-Line Parsing

  • Basic Command-Line Parsing

    • Defining an Anonymous Argument
    • Defining Basic Commands
    • Running Commands
    • Multi-Argument Commands

  • Argument Types

    • Defining Custom Argument Types
    • Optional and Default Arguments
    • Sequences of Arguments

  • Adding Labeled Flags

  • Grouping Subcommands Together

  • Prompting for Interactive Input

  • Command-Line Autocompletion with bash

    • Generating Completion Fragments from Command
    • Installing the Completion Fragment
      • Installing a Generic Completion Handler

  • Alternative Command-Line Parsers

• 16. Concurrent Programming with Async

  • Async Basics

    • Using Let Syntax
    • Ivars and Upon
      • Understanding bind in Terms of Ivars and upon

  • Example: An Echo Server

    • Tail-Calls and Chains of Deferreds
    • Functions that Never Return
    • Improving the Echo Server

  • Example: Searching Definitions with DuckDuckGo

    • URI Handling
    • Parsing JSON Strings
    • Executing an HTTP Client Query

  • Exception Handling

    • Monitors
    • Example: Handling Exceptions with DuckDuckGo

  • Timeouts, Cancellation, and Choices

  • Working with System Threads

    • Multicore OCaml
    • Thread-Safety and Locking

• 17. Testing

  • Inline Tests

    • More Readable Errors with test_eq
    • Where Should Tests Go?
      • Why Can’t Inline Tests Go in Executables?

  • Expect Tests

    • Basic Mechanics
      • open and open!
    • What Are Expect Tests Good For?
    • Exploratory Programming
      • Quoted Strings
    • Visualizing Complex Behavior
    • End-to-End Tests
    • How to Make a Good Expect Test

  • Property Testing with Quickcheck

    • Handling Complex Types
    • More Control with Let-Syntax

  • Other Testing Tools

    • Other Tools to Do (Mostly) the Same Things
    • Fuzzing

• 18. Handling JSON Data

  • JSON Basics

    • Installing the Yojson Library

  • Parsing JSON with Yojson

  • Selecting Values from JSON Structures

    • Functional Combinators

  • Constructing JSON Values

    • Polymorphic Variants and Easier Type Checking

  • Using Nonstandard JSON Extensions

  • Automatically Mapping JSON to OCaml Types

    • ATD Basics
    • ATD Annotations
    • Compiling ATD Specifications to OCaml
    • Example: Querying GitHub Organization Information

• 19. Parsing with OCamllex and Menhir

  • Menhir Versus ocamlyacc

  • Lexing and Parsing

  • Defining a Parser

    • Describing the Grammar
    • Parsing Sequences

  • Defining a Lexer

    • OCaml Prelude
    • Regular Expressions
    • Lexing Rules
      • Unused Lexing Values
    • Recursive Rules
      • Handling Unicode

  • Bringing It All Together

• 20. Data Serialization with S-Expressions

  • Basic Usage

    • Base, Core, and Parsexp
    • More on Top-Level Printing
    • S-Expression Converters for New Types
      • Syntax Extensions and PPX

  • The Sexp Format

  • Preserving Invariants

  • Getting Good Error Messages

  • Sexp-Conversion Directives

    • @sexp.opaque
    • @sexp.list
    • @sexp.option
    • Specifying Defaults

• 21. The OCaml Platform

  • Using the Opam Source-Based Package Manager

  • A Hello World OCaml Project

    • Setting Up an Opam Local Switch
    • Choosing an OCaml Compiler Version
    • Structure of an OCaml Project
    • Defining Module Names
    • Defining Libraries as Collections of Modules
    • Writing Test Cases for a Library
    • Building an Executable Program

  • Setting Up an Integrated Development Environment

    • Using Visual Studio Code
      • What Is The Language Server Protocol?
    • Browsing Interface Documentation
    • Autoformatting Your Source Code

  • Publishing Your Code Online

    • Defining Opam Packages
      • How Do We Name OCaml Modules, Libraries and Packages?
    • Generating Project Metadata from Dune
    • Setting up Continuous Integration
    • Other Conventions
    • Releasing Your Code into the Opam Repository
      • Creating Lock Files for Your Projects

  • Learning More from Real Projects

Part 3: The Compiler and Runtime System

• 22. Foreign Function Interface

  • Installing the Ctypes Library

  • Example: A Terminal Interface

    • Linking Modes: libffi and Stub Generation

  • Basic Scalar C Types

  • Pointers and Arrays

    • Allocating Typed Memory for Pointers
    • Using Views to Map Complex Values
      • OCaml Strings Versus C Character Buffers

  • Structs and Unions

    • Defining a Structure
    • Adding Fields to Structures
    • Incomplete Structure Definitions
      • Recap: a Time-Printing Command
      • Why Do We Need to Use returning?
    • Defining Arrays
      • Pointer Operators for Dereferencing and Arithmetic

  • Passing Functions to C

    • Example: A Command-Line Quicksort
      • Lifetime of Allocated Ctypes

  • Learning More About C Bindings

    • Struct Memory Layout

• 23. Memory Representation of Values

  • Why Do OCaml Types Disappear at Runtime?

  • OCaml Blocks and Values

    • Distinguishing Integers and Pointers at Runtime
      • Some History About OCaml’s Word-Aligned Pointers

  • Blocks and Values

    • Integers, Characters, and Other Basic Types

  • Tuples, Records, and Arrays

    • Floating-Point Numbers and Arrays

  • Variants and Lists

    • Obj Module Considered Harmful

  • Polymorphic Variants

  • String Values

  • Custom Heap Blocks

    • Managing External Memory with Bigarray

• 24. Understanding the Garbage Collector

  • Mark and Sweep Garbage Collection

  • Generational Garbage Collection

    • The Gc Module and OCAMLRUNPARAM

  • The Fast Minor Heap

    • Allocating on the Minor Heap
      • Understanding Allocation
      • Setting the Size of the Minor Heap

  • The Long-Lived Major Heap

    • Allocating on the Major Heap
      • Controlling the Major Heap Increment
    • Memory Allocation Strategies
      • Best-Fit Allocation
      • Next-Fit Allocation
      • First-Fit Allocation
      • Controlling the Heap Allocation Policy
    • Marking and Scanning the Heap
      • Controlling Major Heap Collections
    • Heap Compaction
      • Controlling Frequency of Compactions
    • Intergenerational Pointers
      • The Mutable Write Barrier

  • Attaching Finalizer Functions to Values

    • What Values Can Be Finalized?

• 25. The Compiler Frontend: Parsing and Type Checking

  • An Overview of the Toolchain

    • Obtaining the Compiler Source Code

  • Parsing Source Code

    • Syntax Errors
    • Generating Documentation from Interfaces

  • Preprocessing with ppx

    • Extension Attributes
    • Commonly Used Extension Attributes
    • Extension Nodes

  • Static Type Checking

    • Displaying Inferred Types from the Compiler
      • Which Comes First: The ml or the mli?
    • Type Inference
      • Adding Type Annotations to Find Errors
      • Enforcing Principal Typing
    • Modules and Separate Compilation
      • The Mapping Between Files and Modules
      • Defining a Module Search Path
      • Inspecting Compilation Units with ocamlobjinfo
    • Wrapping Libraries with Module Aliases
    • Shorter Module Paths in Type Errors

  • The Typed Syntax Tree

    • Examining the Typed Syntax Tree Directly

• 26. The Compiler Backend: Bytecode and Native code

  • The Untyped Lambda Form

    • Pattern Matching Optimization
    • Benchmarking Pattern Matching

  • Generating Portable Bytecode

    • Where Did the Bytecode Instruction Set Come From?
    • Compiling and Linking Bytecode
    • Executing Bytecode
    • Embedding OCaml Bytecode in C

  • Compiling Fast Native Code

    • Inspecting Assembly Output
      • The Impact of Polymorphic Comparison
      • Benchmarking Polymorphic Comparison
      • Accessing Stdlib Modules from Within Core
    • Debugging Native Code Binaries
      • Understanding Name Mangling
      • Interactive Breakpoints with the GNU Debugger
    • Profiling Native Code
      • Gprof
      • Perf
      • Using the Frame Pointer to Get More Accurate Traces
    • Embedding Native Code in C
      • Activating the Debug Runtime

  • Summarizing the File Extensions