This article compares two concrete representations of the same handler semantics, beginning with a free encoding that reifies each operation and delimited remainder before relating that model to OCaml's segmented stack implementation.
At every perform site the implementation must preserve the operation's result index, delimit the active evaluation context at the accepting handler and make that context available as a typed continuation.
The free encoding is a semantic lowering model rather than the literal intermediate representation used by OCaml, whose runtime captures ordinary direct style frames without constructing visible Pure and Impure nodes.
Placing both representations beside one another keeps handler scope, resumption semantics and continuation ownership explicit while distinguishing a useful compiler model from the machinery used by the concrete runtime.
1. Operation signatures and answer types
We take the first order signature \(\Sigma = \{\mathsf{Fresh} : 1 \to \mathbb{Z},\; \mathsf{Log} : \mathsf{String} \to 1\}\) with no equations between its operations, and leave the target carrier unspecified until a handler interprets the resulting computation.
Fresh returns an integer to its resumption while Log returns unit, so the source remains direct style even though either operation can transfer control beyond the current activation.
The signature fixes the typed interface presented at each perform site without committing the computation to a counter, an accumulating writer or any concrete scheduling policy.
That separation is the invariant the lowering must preserve when it replaces implicit evaluation contexts with values while retaining indexed request semantics throughout the target IR:
open Effect
type _ Effect.t +=
| Fresh : int Effect.t
| Log : string -> unit Effect.t
let program () =
let number = perform Fresh in
perform (Log (Printf.sprintf "allocated %d" number));
number + 1
The GADT index on each constructor determines the value accepted by the corresponding continuation and survives existential packaging inside the handler dispatcher where its concrete result type becomes locally abstract.
At perform Fresh the captured continuation expects an integer before it can format the message and complete the addition, while the continuation captured at perform (Log message) expects unit.
Handler dispatch therefore has to preserve the equality witness introduced by the constructor match rather than coerce every request through an untyped operation payload.
The continuation's second type parameter is the handler answer type, which permits a clause to resume the source computation and still regain control while constructing the handler's final carrier.
This result index doesn't constitute an effect system because OCaml doesn't record the set of performed effects in ordinary function types or statically guarantee that every operation reaches a matching handler.
2. Reifying the suspended computation
A simple compiler can expose this control transfer by replacing each performed operation with an Impure node containing the operation and a function representing the remaining computation.
Ordinary returns become Pure nodes, so a whole computation is either finished or suspended at precisely one operation boundary with enough information to continue later.
The existential result type hidden by Impure connects the selected operation to its continuation and prevents a handler from supplying a value of the wrong type.
With no equations imposed on the two operations this representation is the free monad generated by the signature, although a production compiler doesn't have to allocate these exact constructors after specialization has selected a concrete runtime strategy:
type _ operation =
| Fresh : int operation
| Log : string -> unit operation
type 'a computation =
| Pure : 'a -> 'a computation
| Impure : 'b operation * ('b -> 'a computation) -> 'a computation
let perform operation =
Impure (operation, fun value -> Pure value)
Sequencing must walk through an already suspended request without interpreting it because the eventual handler hasn't yet supplied the result needed by its continuation.
The bind function therefore applies next immediately to a pure value but composes it after the continuation stored inside every Impure node before exposing the resulting suspension to a handler.
This single recursive definition preserves the order of operations while turning implicit evaluation context into an ordinary OCaml function that can be stored and invoked.
A front end which begins with direct syntax can produce the same shape after administrative normalization has named intermediate results and made evaluation order explicit.
Defunctionalization can then replace the higher order resumptions with first order continuation frames when the target IR needs a closed representation that later analyses can inspect and emit directly:
let rec bind : type a b.
a computation -> (a -> b computation) -> b computation =
fun computation next ->
match computation with
| Pure value -> next value
| Impure (operation, resume) ->
Impure (operation, fun value -> bind (resume value) next)
let ( let* ) = bind
let program =
let* number = perform Fresh in
let* () = perform (Log (Printf.sprintf "allocated %d" number)) in
Pure (number + 1)
3. A handler is a fold over requests
Once effects have this explicit form, a handler for the free representation is an interpreter that folds the computation into some chosen carrier while providing one clause for each recognized operation.
The handler below owns a counter for Fresh and accumulates messages for Log, yet neither policy appears inside the original program or operation signature.
Each clause decides the operation result before applying resume, after which handling continues recursively because later requests remain represented by further Impure nodes along the translated computation spine.
Returning without calling resume would discard the suspended remainder while calling it more than once would duplicate that remainder in this encoding because its continuations remain unrestricted OCaml functions:
let run ~(initial : int) computation =
let next : int ref = ref initial in
let rec handle : type a. a computation -> a * string list = function
| Pure value -> value, []
| Impure (operation, resume) -> handle_request operation resume
and handle_request : type a b.
b operation -> (b -> a computation) -> a * string list =
fun operation resume ->
match operation with
| Fresh ->
let number : b = !next in
incr next;
handle (resume number)
| Log message ->
let value, messages = handle (resume (() : b)) in
value, message :: messages
in
handle computation
Running the sample with an initial counter of 40 records allocated 40 and returns 41, which demonstrates that the value supplied by one clause becomes an ordinary binding in the source program.
The logging clause handles the remainder first and then prepends its current message, thereby preserving source order without mutating a global log as execution crosses each operation boundary.
Different carriers can change that interpretation substantially because a handler might count operations, produce a trace, construct a promise or suspend the continuation inside a scheduler queue.
The operation syntax therefore remains unchanged because only the enclosing fold determines what each request means for one particular invocation of the suspended computation under that handler.
4. The lowering rule
Write \(E[-]\) for the call by value evaluation context up to the current handler boundary and \(\mathcal{L}\) for the lowering into the free representation.
Values map to Pure, while a performed operation becomes an Impure node whose resumption closes over exactly the translated context between the perform site and its delimiter.
Lowering a handler folds Pure through its return clause and dispatches a recognized Impure request with a resumption that recursively reinstalls the same deep handler around the remaining computation.
In an open signature an unrecognized operation is reconstructed for an outer handler with that same handled resumption, thereby composing successive contexts until a handler accepts it rather than swallowing the request or reconstructing the wrong continuation extent:
This presentation is deliberately semantic rather than a claim about one mandatory intermediate representation, since real compilers can encode the same boundary through selective CPS, stack segments or specialized runtime calls. A whole program CPS conversion makes continuations explicit everywhere and is conceptually direct, but it can disrupt existing calling conventions and tooling when added to a mature native compiler. Selective transformations restrict continuation conversion to effectful regions yet require the compiler to preserve compatible boundaries between ordinary direct calls and resumable control flow. OCaml chose a stack based implementation because its compiler didn't already use a CPS intermediate representation and backwards compatibility with native stacks mattered to the design.
5. The same handler with OCaml
Against the explicit free encoding, OCaml keeps the source term in direct style and materializes a resumption when perform transfers control to the nearest handler that accepts the operation.
The extensible GADT Effect.t carries the operation index, while match_with separates normal return, exceptional return and effect dispatch inside a handler record that controls the overall answer type.
Pattern matching on Fresh or Log refines the locally abstract result type and therefore determines exactly which value may be passed to continue when execution reenters the remaining program.
The following implementation preserves the counter and log semantics of the explicit fold while relying on the runtime to avoid allocating a visible Pure or Impure tree in user code:
open Effect
open Effect.Deep
type _ Effect.t +=
| Fresh : int Effect.t
| Log : string -> unit Effect.t
let run ~(initial : int) thunk =
let next : int ref = ref initial in
match_with thunk ()
{
retc = (fun value -> value, []);
exnc = raise;
effc =
(fun (type a) (operation : a Effect.t) ->
match operation with
| Fresh ->
Some
(fun (continuation : (a, _) continuation) ->
let number : a = !next in
incr next;
continue continuation number)
| Log message ->
Some
(fun (continuation : (a, _) continuation) ->
let value, messages = continue continuation (() : a) in
value, message :: messages)
| _ -> None);
}
A deep handler remains installed when its captured continuation resumes, so the later Log request returns to the same handler after the earlier Fresh clause calls continue.
A shallow handler instead handles one operation and requires continue_with to install the handler that should govern the resumed computation, which is useful when accepted operations change with protocol state.
These forms are semantically distinct even when both can express a particular program, because handler reinstatement determines where subsequent effects travel after each resumption.
Semantically the choice changes whether the handler is captured inside the continuation that reaches a clause, while the payload and result index carried by the performed operation remain unchanged.
6. What OCaml captures
OCaml implements handlers with runtime managed and dynamically growing stack segments called fibers, allocating a fresh fiber for the computation enclosed when match_with installs a handler.
Performing an effect creates a heap continuation object that initially points to the current fiber, then an unrecognized effect is forwarded by appending each intervening fiber until an accepting handler is reached.
Resuming traverses that linked chain and connects its last fiber to the current stack without copying the suspended frames, while a dynamic check enforces that the captured chain is consumed at most once.
This concrete representation realizes the same operation and continuation interface shown by Impure while avoiding a universal source level CPS conversion across portions of the program that remain in direct style.
OCaml continuations are one shot and attempting to resume the same continuation twice raises Continuation_already_resumed, unlike the unrestricted function stored in the earlier teaching representation.
One shot use avoids copying suspended stack frames and suits schedulers, generators and asynchronous I/O where ownership of a suspended task normally moves between queues exactly once.
It also means that a nondeterminism handler can't explore two branches by invoking one captured continuation twice unless the program is transformed or its continuation is represented through another explicitly duplicable structure.
A suspended continuation should eventually be continued or discontinued because abandoning it can retain its fiber and any resources held by frames inside the suspended computation.
7. Execution
The fixed sample expands into the following sequence of control transfers, exposing the requests, captured resumptions and handler results that direct syntax normally leaves implicit.
The first clause supplies 40 to k1, which resumes until Log suspends the computation again with k2 waiting for a value of type unit.
Recording the message and resuming k2 with () completes the arithmetic before the return clause maps Pure 41 into the handler's final answer.
This trace describes the explicit computation datatype rather than OCaml's physical fiber layout, though both representations preserve the same typed exchange between an operation, its delimited continuation and the accepting clause:
8. Boundaries
Lowering should preserve the nearest handler boundary because moving a perform across a handler can change both the clause selected and the extent of the continuation supplied to it.
Common subexpression elimination is similarly unsafe for arbitrary operations since two syntactically identical requests may observe different counter state or suspend at different points in a scheduler.
Total and effect free work may still move across a boundary when the compiler can prove that evaluation order and captured environments remain observationally unchanged, while known handlers can sometimes be specialized into ordinary branches.
The important invariant is that every transformation preserves operation order, handler selection and the exact continuation delimited at each perform site after optimization has rearranged the surrounding intermediate representation.
Tail resumptions deserve particular attention because OCaml's implementation optimizes a clause which does nothing after continue so repeated tail resumptions don't accumulate additional stack.
A clause such as the logging implementation above can't use that tail resumption path because it must regain control and prepend the current message after the remaining computation returns.
The difference is visible in the explicit fold and remains present in a stack implementation even though the continuation is represented by fibers instead of an OCaml closure.
Treating every resumption as a tail call would silently change handlers whose result construction depends on returning from the resumed computation before control reenters the enclosing operation clause.
9. Closing the boundary
The lowering boundary consists of an indexed operation, a delimited continuation whose input is that operation's result type and a handler answer type returned by both the continuation and its selected clause.
The free representation exposes those components as constructors and higher order functions, while OCaml realizes the same interface through stack segments that retain ordinary direct style frames.
Neither representation fixes the carrier of Fresh or Log before handler installation, so specialization remains a property of a particular handler context rather than the operation signature.
Any correct lowering must therefore preserve handler scope, forwarding semantics, continuation extent and the one shot ownership discipline imposed when the concrete runtime resumes a suspended chain of frames.