How OCaml Represents Values in Memory

I work on the OCaml language team at Jane Street. Earlier videos in this series discussed modes such as locality; another area of development is the kind system, which can express properties including memory layout. Before discussing unboxed types, I want to explain OCaml's conventional value representation.

The first category is immediate values. Unit has just one value, written (), and is commonly used when a computation performs an effect rather than returning meaningful information. Booleans, characters, and signed integers are also immediate types.

These values are represented as OCaml integers. To inspect them, I write a helper that checks a value's representation and uses Obj.magic, an unsafe reinterpretation, to view it as an integer. Unit and false are represented as 0, true as 1; a character gives its byte code, and an integer gives itself.

Values can also be composed into structures: a list or array can contain elements of one type, a tuple can contain different types, and a record can name fields with their own types. Unlike the immediate types, these compound values are boxed and represented by heap-allocated blocks.

A second helper uses Obj.repr to view the runtime representation, checks that it is a block, and calls Obj.size. In the examples, a four-element array has size four words, a triple has size three, and a two-field record has size two. Obj.repr is an identity operation that lets us inspect the representation.

How does the runtime distinguish an integer from a pointer, and how does it determine the size of a block? This matters not just for inspection: the garbage collector must distinguish immediate values from references and understand the memory they point to.

OCaml uses tagged integers. On the 64-bit layout shown here, heap blocks are word-aligned, so their addresses end in zero bits. The runtime uses the least significant bit as a discriminator: one denotes an immediate integer, while zero denotes a pointer. That leaves 63 bits for the integer representation.

Every heap block also has an extra header word. In the layout shown, its size field records the block's length in words; Obj.size reads that field. Two color bits are used by the garbage collector, and a one-byte tag tells the runtime more about the block.

A 64-bit floating-point value cannot always reserve a bit to distinguish it from a pointer. In the ordinary boxed representation, a float is stored in a heap block whose tag is Double_tag, 253. The garbage collector recognizes the tag and does not scan the float's bits as pointers.

I can verify that by using Obj.repr and Obj.tag on a float: the reported tag is 253. Strings have a similar issue because their tightly packed bytes can contain arbitrary bit patterns. A string block uses tag 252, so its contents are not mistaken for pointers.

More generally, tags at or above 251 identify blocks whose contents the garbage collector does not scan as ordinary pointer-containing fields. The tag has another important use: distinguishing constructors of variant types.

Consider a variant with constructors A, B of int, C, and D of string. To represent a value, the runtime needs both the constructor's identity and any associated payload. OCaml separates constructors without arguments from those with arguments, and numbers the two groups independently from zero.

The constructors without payloads are immediate integers. In this example A is 0 and C is 1; a further payload-free constructor would be 2. For payload-carrying constructors, the block tag records the constructor number: B has tag 0 and D has tag 1.

Because the tag is finite, the number of payload-carrying constructors in one variant is bounded, though the limit is ample for most uses. This straightforward representation makes it possible to reason about how many types are laid out and helps keep the runtime and garbage collector relatively simple. Future videos will discuss how these value types interact with unboxed types.