Resumable Frames for Generators and Coroutines

A normal function’s frame lives from call to return, and its lifetime is bounded by the call. The machine stack implements exactly that lifetime: push on entry, pop on exit, with the stack pointer restoring both frame and caller in one move. A generator breaks that model. It returns a value to its caller while its frame is still logically alive, and it must resume later at the exact instruction where it suspended, with its locals and its operand stack intact.

The machine stack cannot express this, because the frames above the generator’s frame belong to callers that have already returned. Suspending a frame in place would leave the stack in a state where the region above the generator is dead but cannot be reclaimed, and resuming would require reconstructing the dead frames. Every implementation therefore moves the generator’s state somewhere else, and the layout it is moving away from is the ordinary interpreter stack frame with its header, locals, and operand stack.

Lifting the frame into a heap object

The common design compiles a generator function into a state machine whose state is an object. The generator’s locals become fields of that object rather than slots in a stack frame. The function body is rewritten so that each suspension point becomes a return that stores the resumption point, and each resumption dispatches to the code for that point.

The compiler performs this transformation because the source language does not have continuations. A generator function is recognized syntactically, and the body is split at each yield into segments. A switch on a saved state number selects the segment on entry.

typedef struct {
    int      state;      /* resumption point: 0 = start */
    long     counter;    /* a local lifted out of the frame */
    long     limit;
} CounterGen;

long counter_next(CounterGen *g)
{
    switch (g->state) {
    case 0:
        g->counter = 0;
        g->state = 1;
        /* fall through */
    case 1:
        if (g->counter < g->limit) {
            g->counter++;
            return g->counter - 1;    /* the yielded value */
        }
        g->state = 2;
        /* fall through */
    case 2:
        return -1;                    /* exhausted */
    }
    return -1;
}

Every local that is live across a suspension point must be lifted into the object, because the C stack frame holding it is gone after the return. Locals that live only within one segment can stay in the frame of counter_next, since the function’s frame is recreated on each call. The compiler’s liveness analysis decides which is which, and getting it wrong produces a value that silently resets on resumption.

The object is allocated when the generator is created and freed when it is exhausted or collected. Its size is fixed at compile time: the compiler knows the set of lifted locals, so it emits a struct layout. That makes allocation a single sized request, and it makes the generator’s footprint predictable.

The JVM is the clearest case of a format that leaves this to the compiler. The specification gives a frame no existence after its method returns and provides no operation that captures one, so a language targeting the JVM implements generators by compiling the generator function into a class with a state field and a switch over resumption points: the same transformation as above, performed ahead of time rather than at run time.

Suspending in the middle of an expression

The transformation gets harder when a yield appears inside an expression rather than as a statement. An expression such as f(yield x, y) requires that the partially evaluated call be resumable: the argument x has been yielded, the function f and the second argument y are still pending, and on resumption the call must proceed with the yielded value substituted.

Compilers handle this by treating the operand stack itself as state that must be lifted. Every value on the operand stack at a suspension point becomes a field of the generator object, and the resumption point encodes which stack shape to restore. In a stack-machine bytecode this is natural, because the operand stack is already an array; the compiler records its depth at each yield and emits code that copies the live portion into the object on suspend and back on resume.

In a register-machine bytecode the same information is a set of live registers, and the compiler emits the moves explicitly. Both approaches turn the implicit stack state into explicit fields, and both pay a cost proportional to the stack depth at the suspension point. A yield deep inside nested expressions therefore produces a larger generator object than one at statement level.

An alternative avoids the transformation entirely: implement the generator on a separate stack. The runtime allocates a small stack for the generator, switches to it on resume, and switches back on suspend. The frame stays in place, and no locals are lifted. This is what a fiber or green-thread implementation does, and it makes any function resumable without compiler support.

Stack switching and its constraints

A separate stack per generator means the runtime must be able to save the current machine state, change the stack pointer to the generator’s stack, and restore later. On a platform with a documented context-switch primitive, this is a handful of register saves. Without one, the runtime must save and restore the callee-saved registers itself, and it must handle the fact that the C compiler assumes a single stack.

That assumption is the source of the difficulty. A C compiler may cache the address of a local in a register across a call, and if the call switches stacks, the address is stale. It may also compute addresses relative to a frame pointer that the switch invalidates. Implementations that use separate stacks therefore restrict the code that runs on them to a form the compiler cannot optimize across the switch, or they rely on platform-specific primitives that the compiler is aware of.

The separate-stack design also costs memory per generator. A stack must be large enough for the generator’s deepest call, and stacks cannot be shared. A thousand live generators with 16 KiB stacks each reserve 16 MiB of address space, and the pages a generator never reaches are never touched. Lifted-frame generators cost only the size of their object, often a few dozen bytes. That ratio is why most language runtimes that expose generators as a first-class feature lift the frame rather than allocating a stack.

Symmetric and asymmetric transfer

A generator is asymmetric: control passes from a caller to the generator and back to the same caller. A general coroutine allows transfer between any two coroutines, which means the runtime cannot assume a caller-callee relationship and must maintain a set of runnable coroutine states rather than a stack discipline.

With lifted frames, symmetric transfer is straightforward: each coroutine object holds its state and its resumption point, and a transfer stores the current coroutine’s state and loads the target’s. The runtime’s notion of “current” becomes a variable rather than a stack pointer, and the machine stack is used only for the duration of one coroutine’s step. Because each step returns to a scheduler-like trampoline, the machine stack never holds more than one coroutine’s frame, which also bounds stack usage independent of coroutine count.

The cost is that every transfer returns to the trampoline, so a chain of transfers costs a return plus a dispatch per hop. With separate stacks, a transfer is a context switch that does not return, which is fewer instructions but requires the platform primitive. The trade is between portability and per-transfer cost, and it is the same trade that appears in green-thread schedulers.

Interaction with the collector and with unwinding

A suspended generator’s object holds references in its lifted local fields, and those references must be traced. Because the fields are ordinary object fields with a static layout, the collector’s existing object scanning finds them without any special case. That is a significant advantage over the separate-stack design, where the suspended stack is a raw region that the collector must scan using metadata about which slots hold references.

Exceptions crossing a suspension boundary need a decision. If a generator is resumed and throws, the exception propagates in the resumer’s frame, which is the caller’s stack, not the generator’s. If the generator was suspended in the middle of a try block, its handler must apply on resumption, which means the lifted state must include the fact that a handler is active and which one. Compilers encode this by including the handler’s identity in the resumption point: each suspension point inside a protected region gets its own state number that maps to the correct handler table entry.

Garbage collection of abandoned generators is another edge. A generator that is never exhausted and becomes unreachable must have its object collected, and if the generator holds a finally block that should run on abandonment, the collector cannot run user code. Languages that require deterministic cleanup on abandonment expose an explicit close operation instead: Lua 5.4’s coroutine.close resumes a suspended coroutine only far enough to close its to-be-closed variables and unwind its stack, and the object’s finalizer, if any, only releases runtime resources.

The debugger’s view of a suspended frame is the last piece: a stack trace must show the generator’s frame as live, at the suspension point, even though no machine frame exists for it. That requires the runtime to map a generator object back to a code offset, which is exactly the metadata problem covered in debug metadata and single stepping.