Programming with OCaml's Local Mode

In this final installment of the current series on locals, I want to work through a small programming example using the experimental feature in Jane Street's OCaml compiler branch. The example is deliberately contrived, but the errors we encounter illustrate practical issues that can arise when working with local values.

Imagine a map of widgets indexed by integers. We want the best widget associated with a prime below 100. A list of primes is already available, and a get_best function takes a widget list and returns the best element. For the demonstration, I supply placeholder helpers that compile but are not intended to run.

The initial implementation maps over the primes, looks up each widget, collects the results in a list, and passes that list to get_best. It compiles. But the intermediate list is only needed during this function, so I would prefer not to allocate it on the heap.

Annotating the list as local produces an escape error: the original get_best signature expects a global list and makes no promise that it will not store the argument. Marking its list parameter local gives the compiler the needed non-escape promise.

That exposes another error: get_best is in tail position, so the local argument cannot be passed in that tail call. Adding a nontail annotation keeps the relevant region alive. In this nonrecursive example, sacrificing tail-call optimization is acceptable.

The placeholder signature now accepts a local list and returns a global widget, but we have not implemented it. A real implementation that takes the first element reveals the next problem: a value extracted from a local list is treated as local, so returning it globally would let it escape.

After I mark get_best's input local, its inferred result is also local. The caller wants to return a global widget from the original table, however. The distinction we need is a list whose cells are local but whose elements are global.

The solution demonstrated is a wrapper type with a global modality on its single field. The wrapper is marked unboxed, a general OCaml feature for this kind of single-field record: the wrapped value and wrapper have the same runtime representation, so the wrapper itself does not require an extra allocation.

The global modality says that the field remains global even when the enclosing wrapper is local. A local list of these wrappers can therefore contain global elements. Pattern matching extracts the field, allowing get_best to return it globally without letting the local list itself escape.

The inferred input type initially expects a map of wrapped widgets, which is not what we started with. Wrapping each widget after the lookup fixes the interface: the input remains a map of ordinary widgets, the result is global, and the intermediate list is local.

There is still a subtlety. A local annotation says the list does not escape; it does not by itself guarantee stack allocation. Ordinary List.map allocates its result on the heap, and a global value can be treated as local. The code may type-check while failing to achieve the desired allocation behavior.

To actually allocate the intermediate list locally, I write a separate recursive map. In a full Jane Street environment, library functions can provide this functionality, but the example uses the standard library context and defines its own version.

The map's type must say its result is local. Its cons cells need to be allocated in the caller's region, so the implementation uses exclave in a tail position. With that change, the map returns a locally allocated list and the caller can infer its locality without an explicit annotation.

The example exposes two sharp corners: preserving global elements in a local list requires wrapping and unpacking them, and ordinary map needs a local-producing counterpart to control allocation. The team hopes mode polymorphism may improve this and is exploring possible syntax for inline modalities, but the work remains experimental.