real world ocaml

www.it-ebooks.info

www.it-ebooks.info

Yaron Minsky, Anil Madhavapeddy, and Jason Hickey

Real World OCaml

www.it-ebooks.info

Real World OCaml

by Yaron Minsky, Anil Madhavapeddy, and Jason Hickey

Copyright © 2014 Yaron Minsky, Anil Madhavapeddy, Jason Hickey. All rights reserved.

Printed in the United States of America.

Published by O’Reilly Media, Inc., 1005 Gravenstein Highway North, Sebastopol, CA 95472.

O’Reilly books may be purchased for educational, business, or sales promotional use. Online editions are

also available for most titles (http://my.safaribooksonline.com). For more information, contact our corporate/

institutional sales department: 800-998-9938 or [email protected].

Editors: Mike Loukides and Andy Oram

Production Editor: Christopher Hearse

Copyeditor: Amanda Kersey

Proofreader: Becca Freed

Indexer: Judith McConville

Cover Designer: Randy Comer

Interior Designer: David Futato

Illustrator: Rebecca Demarest

November 2013: First Edition

Revision History for the First Edition:

2013-10-31: First release

See http://oreilly.com/catalog/errata.csp?isbn=9781449323912 for release details.

Nutshell Handbook, the Nutshell Handbook logo, and the O’Reilly logo are registered trademarks of O’Reilly

Media, Inc. Real World OCaml, the image of a Bactrian camel, and related trade dress are trademarks of

O’Reilly Media, Inc.

Many of the designations used by manufacturers and sellers to distinguish their products are claimed as

trademarks. Where those designations appear in this book, and O’Reilly Media, Inc., was aware of a trade‐

mark claim, the designations have been printed in caps or initial caps.

While every precaution has been taken in the preparation of this book, the publisher and authors assume

no responsibility for errors or omissions, or for damages resulting from the use of the information contained

herein.

ISBN: 978-1-449-32391-2

[LSI]

www.it-ebooks.info

For Lisa, a believer in the power of words, who helps me find mine. —Yaron

For Mum and Dad, who took me to the library and unlocked my imagination. —Anil

For Nobu, who takes me on a new journey every day. —Jason

www.it-ebooks.info

www.it-ebooks.info

Table of Contents

Prologue. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xv

Part I. Language Concepts

1. A Guided Tour. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

OCaml as a Calculator 3

Functions and Type Inference 5

Type Inference 7

Inferring Generic Types 8

Tuples, Lists, Options, and Pattern Matching 10

Tuples 10

Lists 11

Options 16

Records and Variants 18

Imperative Programming 20

Arrays 20

Mutable Record Fields 21

Refs 22

For and While Loops 23

A Complete Program 25

Compiling and Running 26

Where to Go from Here 26

2. Variables and Functions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

Variables 27

Pattern Matching and let 30

Functions 31

Anonymous Functions 31

Multiargument functions 33

v

www.it-ebooks.info

Recursive Functions 34

Prefix and Infix Operators 35

Declaring Functions with Function 39

Labeled Arguments 40

Optional Arguments 43

3. Lists and Patterns. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

List Basics 49

Using Patterns to Extract Data from a List 50

Limitations (and Blessings) of Pattern Matching 52

Performance 52

Detecting Errors 54

Using the List Module Effectively 55

More Useful List Functions 58

Tail Recursion 61

Terser and Faster Patterns 63

4. Files, Modules, and Programs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

Single-File Programs 67

Multifile Programs and Modules 70

Signatures and Abstract Types 71

Concrete Types in Signatures 74

Nested Modules 75

Opening Modules 77

Including Modules 79

Common Errors with Modules 81

Type Mismatches 81

Missing Definitions 81

Type Definition Mismatches 81

Cyclic Dependencies 82

Designing with Modules 83

Expose Concrete Types Rarely 83

Design for the Call Site 84

Create Uniform Interfaces 84

Interfaces before implementations 85

5. Records. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

Patterns and Exhaustiveness 88

Field Punning 91

Reusing Field Names 92

Functional Updates 96

Mutable Fields 97

vi | Table of Contents

www.it-ebooks.info

First-Class Fields 98

6. Variants. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

Catch-All Cases and Refactoring 105

Combining Records and Variants 107

Variants and Recursive Data Structures 111

Polymorphic Variants 114

Example: Terminal Colors Redux 116

When to Use Polymorphic Variants 121

7. Error Handling. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

Error-Aware Return Types 123

Encoding Errors with Result 125

Error and Or_error 125

bind and Other Error Handling Idioms 127

Exceptions 128

Helper Functions for Throwing Exceptions 131

Exception Handlers 132

Cleaning Up in the Presence of Exceptions 132

Catching Specific Exceptions 133

Backtraces 135

From Exceptions to Error-Aware Types and Back Again 137

Choosing an Error-Handling Strategy 138

8. Imperative Programming. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139

Example: Imperative Dictionaries 139

Primitive Mutable Data 143

Array-Like Data 143

Mutable Record and Object Fields and Ref Cells 145

Foreign Functions 146

for and while Loops 146

Example: Doubly Linked Lists 147

Modifying the List 149

Iteration Functions 150

Laziness and Other Benign Effects 151

Memoization and Dynamic Programming 153

Input and Output 159

Terminal I/O 160

Formatted Output with printf 161

File I/O 163

Order of Evaluation 165

Side Effects and Weak Polymorphism 167

Table of Contents | vii

www.it-ebooks.info

The Value Restriction 168

Partial Application and the Value Restriction 170

Relaxing the Value Restriction 170

Summary 173

9. Functors. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175

A Trivial Example 176

A Bigger Example: Computing with Intervals 177

Making the Functor Abstract 181

Sharing Constraints 182

Destructive Substitution 184

Using Multiple Interfaces 185

Extending Modules 189

10. First-Class Modules. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193

Working with First-Class Modules 193

Example: A Query-Handling Framework 199

Implementing a Query Handler 200

Dispatching to Multiple Query Handlers 202

Loading and Unloading Query Handlers 205

Living Without First-Class Modules 208

11. Objects. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211

OCaml Objects 212

Object Polymorphism 213

Immutable Objects 215

When to Use Objects 216

Subtyping 217

Width Subtyping 217

Depth Subtyping 218

Variance 219

Narrowing 222

Subtyping Versus Row Polymorphism 224

12. Classes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227

OCaml Classes 227

Class Parameters and Polymorphism 228

Object Types as Interfaces 230

Functional Iterators 232

Inheritance 233

Class Types 234

Open Recursion 235

viii | Table of Contents

www.it-ebooks.info

Private Methods 237

Binary Methods 239

Virtual Classes and Methods 242

Create Some Simple Shapes 242

Initializers 245

Multiple Inheritance 245

How Names Are Resolved 245

Mixins 246

Displaying the Animated Shapes 249

Part II. Tools and Techniques

13. Maps and Hash Tables. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253

Maps 254

Creating Maps with Comparators 255

Trees 257

The Polymorphic Comparator 258

Sets 260

Satisfying the Comparable.S Interface 260

Hash Tables 264

Satisfying the Hashable.S Interface 266

Choosing Between Maps and Hash Tables 267

14. Command-Line Parsing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271

Basic Command-Line Parsing 272

Anonymous Arguments 272

Defining Basic Commands 273

Running Basic Commands 273

Argument Types 275

Defining Custom Argument Types 276

Optional and Default Arguments 277

Sequences of Arguments 279

Adding Labeled Flags to the Command Line 280

Grouping Subcommands Together 282

Advanced Control over Parsing 284

The Types Behind Command.Spec 285

Composing Specification Fragments Together 286

Prompting for Interactive Input 287

Adding Labeled Arguments to Callbacks 289

Command-Line Autocompletion with bash 290

Generating Completion Fragments from Command 290

Table of Contents | ix

www.it-ebooks.info

Installing the Completion Fragment 291

Alternative Command-Line Parsers 292

15. Handling JSON Data. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293

JSON Basics 293

Parsing JSON with Yojson 294

Selecting Values from JSON Structures 296

Constructing JSON Values 300

Using Nonstandard JSON Extensions 302

Automatically Mapping JSON to OCaml Types 303

ATD Basics 304

ATD Annotations 305

Compiling ATD Specifications to OCaml 305

Example: Querying GitHub Organization Information 307

16. Parsing with OCamllex and Menhir. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311

Lexing and Parsing 312

Defining a Parser 314

Describing the Grammar 314

Parsing Sequences 316

Defining a Lexer 318

OCaml Prelude 318

Regular Expressions 318

Lexing Rules 319

Recursive Rules 320

Bringing It All Together 322

17. Data Serialization with S-Expressions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325

Basic Usage 326

Generating S-Expressions from OCaml Types 328

The Sexp Format 329

Preserving Invariants 331

Getting Good Error Messages 334

Sexp-Conversion Directives 336

sexp_opaque 336

sexp_list 337

sexp_option 338

Specifying Defaults 338

18. Concurrent Programming with Async. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341

Async Basics 342

Ivars and Upon 345

x | Table of Contents

www.it-ebooks.info

Examples: An Echo Server 347

Improving the Echo Server 350

Example: Searching Definitions with DuckDuckGo 353

URI Handling 353

Parsing JSON Strings 354

Executing an HTTP Client Query 354

Exception Handling 357

Monitors 358

Example: Handling Exceptions with DuckDuckGo 361

Timeouts, Cancellation, and Choices 363

Working with System Threads 366

Thread-Safety and Locking 369

Part III. The Runtime System

19. Foreign Function Interface. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373

Example: A Terminal Interface 374

Basic Scalar C Types 378

Pointers and Arrays 380

Allocating Typed Memory for Pointers 381

Using Views to Map Complex Values 382

Structs and Unions 383

Defining a Structure 383

Adding Fields to Structures 384

Incomplete Structure Definitions 384

Defining Arrays 388

Passing Functions to C 389

Example: A Command-Line Quicksort 390

Learning More About C Bindings 392

Struct Memory Layout 393

20. Memory Representation of Values. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395

OCaml Blocks and Values 396

Distinguishing Integers and Pointers at Runtime 397

Blocks and Values 398

Integers, Characters, and Other Basic Types 399

Tuples, Records, and Arrays 400

Floating-Point Numbers and Arrays 400

Variants and Lists 401

Polymorphic Variants 403

String Values 404

Table of Contents | xi

www.it-ebooks.info

Custom Heap Blocks 405

Managing External Memory with Bigarray 405

21. Understanding the Garbage Collector. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407

Mark and Sweep Garbage Collection 407

Generational Garbage Collection 408

The Fast Minor Heap 408

Allocating on the Minor Heap 409

The Long-Lived Major Heap 410

Allocating on the Major Heap 411

Memory Allocation Strategies 412

Marking and Scanning the Heap 413

Heap Compaction 414

Intergenerational Pointers 415

Attaching Finalizer Functions to Values 418

22. The Compiler Frontend: Parsing and Type Checking. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 421

An Overview of the Toolchain 422

Parsing Source Code 424

Syntax Errors 424

Automatically Indenting Source Code 425

Generating Documentation from Interfaces 426

Preprocessing Source Code 428

Using Camlp4 Interactively 430

Running Camlp4 from the Command Line 431

Preprocessing Module Signatures 433

Further Reading on Camlp4 434

Static Type Checking 434

Displaying Inferred Types from the Compiler 435

Type Inference 436

Modules and Separate Compilation 440

Packing Modules Together 443

Shorter Module Paths in Type Errors 444

The Typed Syntax Tree 445

Using ocp-index for Autocompletion 446

Examining the Typed Syntax Tree Directly 446

23. The Compiler Backend: Bytecode and Native code. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 449

The Untyped Lambda Form 449

Pattern Matching Optimization 450

Benchmarking Pattern Matching 452

Generating Portable Bytecode 454

xii | Table of Contents

www.it-ebooks.info

Compiling and Linking Bytecode 455

Executing Bytecode 456

Embedding OCaml Bytecode in C 456

Compiling Fast Native Code 458

Inspecting Assembly Output 459

Debugging Native Code Binaries 462

Profiling Native Code 465

Embedding Native Code in C 467

Summarizing the File Extensions 468

Index. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471

Table of Contents | xiii

www.it-ebooks.info