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, Core and Core_kernel

  • OCaml as a Calculator

  • Functions and Type Inference

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

  • Tuples, Lists, Options, and Pattern Matching

    • Tuples
    • Lists
      • The List module
      • Constructing lists with ::
      • List patterns using match
      • Recursive list functions
    • Options

  • Records and Variants

    • Base and polymorphic comparison

  • Imperative Programming

    • Arrays
    • Mutable Record Fields
    • Refs
    • 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
    • Declaring Functions with function
    • Labeled Arguments
      • 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

  • 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
      • 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. Functors

  • A Trivial Example

  • A Bigger Example: Computing with Intervals

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

  • Extending Modules

• 10. First-Class Modules

  • Working with First-Class Modules

    • 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

• 11. 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
      • Production Note

• 12. 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

• 13. 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

• 14. 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

• 15. Concurrent Programming with Async

  • Async Basics

    • Using Let_syntax with Async
    • 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

    • Thread-Safety and Locking

• 16. 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

    • Installing the ATDgen Library and Tool
    • ATD Basics
    • ATD Annotations
    • Compiling ATD Specifications to OCaml
    • Example: Querying GitHub Organization Information

• 17. 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
    • Recursive Rules
      • Handling Unicode

  • Bringing It All Together

• 18. Data Serialization with S-Expressions

  • Basic Usage

    • More on Top-Level Printing
    • Generating S-Expressions from OCaml 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

Part 3: The Compiler and Runtime System

• 19. Foreign Function Interface

  • Installing the Ctypes Library

  • Example: A Terminal Interface

  • 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
    • 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

• 20. 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

• 21. 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
      • Setting the Size of the Minor Heap

  • The Long-Lived Major Heap

    • Allocating on the Major Heap
      • Controlling Major Heap Growth
    • Memory Allocation Strategies
      • Next-fit allocation
      • First-fit allocation
    • 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?

• 22. The Compiler Frontend: Parsing and Type Checking

  • An Overview of the Toolchain

    • Obtaining the Compiler Source Code

  • Parsing Source Code

    • Syntax Errors
    • Automatically Indenting Source Code
    • Generating Documentation from Interfaces
      • Using Custom ocamldoc Generators

  • 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
    • Packing Modules Together
      • Packing and Search Paths
    • Shorter Module Paths in Type Errors

  • The Typed Syntax Tree

    • Using ocp-index for Autocompletion
    • Examining the Typed Syntax Tree Directly

• 23. Preprocessing with ppx

  • Extension Attributes

    • Commonly used extension attributes
    • ppx in the compiler

  • Building your first ppx extension

    • The AST Mapper and hello world
    • ppxlib

• 24. The Compiler Backend: Bytecode and Native code

  • The Untyped Lambda Form

    • Pattern Matching Optimization
      • Learning More About Pattern Matching Compilation
    • 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
    • Debugging Native Code Binaries
      • Understanding name mangling
      • Interactive breakpoints with the GNU debugger
    • Profiling Native Code
      • Gprof
      • Perf
    • Embedding Native Code in C
      • Activating the Debug Runtime

  • Summarizing the File Extensions