Closures and upvalues

Deep dive

How it works

In: a function that refers to variables of enclosing functions · Out: a function value (closure) that can run after those frames exit · State: one upvalue cell per captured variable, plus a list of open upvalues for live frames · Cost: O(1) per access

1. The compiler resolves each free name (name resolution) and records, per function, a list of captures: "local slot k of the parent" or "upvalue j of the parent" (for a variable two levels out).
2. Executing the closure-creation instruction in the bytecode interpreter builds a closure with an upvalue array, one entry per recorded capture.
3. A "local" capture calls capture(slot): search the open-upvalue list for that stack slot; reuse the upvalue if found, else create Open(slot) and add it. This reuse is what makes two closures share one variable.
4. An "upvalue" capture copies the parent closure's upvalue pointer (same cell).
5. Reading or writing an upvalue: if Open(slot), use stack[slot]; if Closed(v), use the heap cell.
6. At function return, and at the end of any block scope that declared a captured variable (a loop body), close(from) visits open upvalues at slots >= from, copies each value into its cell and removes it from the list.
7. After closing, the stack slot may be reused freely; the upvalue lives as long as some closure references it (traced by mark-sweep or generational collectors, or counted, see reference counting).

Other designs for the same job:

• Linked environments (classic interpreters): each scope is a heap record with a parent pointer; a closure holds a pointer to its scope; variable access walks depth hops. Creation is O(1), but one captured variable keeps the whole chain alive.
• Closure conversion (compilers): rewrite each function to take an explicit environment. A flat environment is a struct of the captured values; the closure is a pair (code pointer, env pointer).
• Lambda lifting: if the closure never escapes, turn the captured variables into extra parameters of a top-level function and pass them at each call; no closure object is allocated.

Code

Rust model of Lua's scheme: a VM stack, a shared open list, Rc<RefCell<..>> upvalues. A shared upvalue means one Rc in several closures.

use std::{cell::RefCell, rc::Rc};

pub enum Up { Open(usize), Closed(i64) } // Open: index into the VM stack
pub type UpRef = Rc<RefCell<Up>>;

#[derive(Default)]
pub struct Vm {
    pub stack: Vec<i64>,
    open: Vec<UpRef>, // open upvalues of the live frames
}
pub struct Closure { ups: Vec<UpRef> }

impl Vm {
    /// Capture a stack slot: reuse the open upvalue if one exists.
    pub fn capture(&mut self, slot: usize) -> UpRef {
        for u in &self.open {
            if matches!(*u.borrow(), Up::Open(s) if s == slot) { return u.clone(); }
        }
        let u = Rc::new(RefCell::new(Up::Open(slot)));
        self.open.push(u.clone());
        u
    }
    /// Close every open upvalue at slot >= from: copy the value to the heap cell.
    pub fn close(&mut self, from: usize) {
        let stack = &self.stack;
        self.open.retain(|u| {
            let slot = match *u.borrow() { Up::Open(s) => s, Up::Closed(_) => return false };
            if slot < from { return true; }
            *u.borrow_mut() = Up::Closed(stack[slot]);
            false
        });
    }
    pub fn ret(&mut self, base: usize) { self.close(base); self.stack.truncate(base); }
}

impl Closure {
    pub fn new(ups: Vec<UpRef>) -> Self { Closure { ups } }
    pub fn get(&self, vm: &Vm, i: usize) -> i64 {
        match *self.ups[i].borrow() { Up::Open(s) => vm.stack[s], Up::Closed(v) => v }
    }
    pub fn set(&self, vm: &mut Vm, i: usize, v: i64) {
        match &mut *self.ups[i].borrow_mut() { Up::Open(s) => vm.stack[*s] = v, Up::Closed(c) => *c = v }
    }
}

fn main() {
    let mut vm = Vm::default();
    // make_counter(): local n = 0; inc = fn() n += 1; get = fn() n
    let base = vm.stack.len();
    vm.stack.push(0);
    let inc = Closure::new(vec![vm.capture(base)]);
    let get = Closure::new(vec![vm.capture(base)]);
    let v = inc.get(&vm, 0) + 1; inc.set(&mut vm, 0, v); // open: writes the stack slot
    assert_eq!(vm.stack[base], 1);
    assert_eq!(get.get(&vm, 0), 1);
    vm.ret(base); // frame exits: value moves to the heap
    let v = inc.get(&vm, 0) + 1; inc.set(&mut vm, 0, v);
    assert_eq!(get.get(&vm, 0), 2); // still one shared variable

    // for i in 0..3 { push(fn() i) } with a fresh i per iteration
    let base = vm.stack.len();
    vm.stack.push(0);
    let mut fs = vec![];
    for i in 0..3 {
        vm.stack[base] = i;
        fs.push(Closure::new(vec![vm.capture(base)]));
        vm.close(base); // end of the iteration scope closes i
    }
    vm.ret(base);
    let seen: Vec<i64> = fs.iter().map(|f| f.get(&vm, 0)).collect();
    assert_eq!(seen, vec![0, 1, 2]);
}

Without the vm.close(base) in the loop, all three closures would share one variable and see the last value.

Complexity and constants

• Access: one pointer load (closed) or two (open: upvalue, then stack); no chain walk.
• capture here scans the whole list; Lua keeps the list sorted by stack level, so the search stops at the first slot below the target and close stops at the first slot below from.

Efficiency

• Cost: a closure call is an ordinary call plus one extra pointer load per captured-variable access; creation allocates the closure and any new upvalues. The cost that matters is allocation and GC pressure, not the access.
• Levers:
  • Capture only what the body uses (free-variable analysis): smaller closures, no retained dead data.
  • Keep upvalues open, move to heap only on exit (Lua) so a non-escaping closure never allocates a cell, see Lua 5.0 paper.
  • Do not allocate a closure when it does not escape: escape analysis with inlining or lambda lifting removes the object entirely (what Rust and C++ do by default with monomorphized closures).
  • In a JIT, turn the closure's code pointer and shape into constants guarded by an inline cache so calls become direct.
• Naive → standard → state of the art:
  • Linked environment, every scope on the heap · one heap record per scope entry, deep chains.
  • Flat closures with open/closed upvalues · allocation only for escaping captured variables.
  • Escape analysis + inlining/lambda lifting · no allocation and no indirection when the closure does not escape.

Implementation notes

• Mark a local "captured" at compile time so only blocks that declare one emit a close instruction.
• Close upvalues before the frame is popped; afterwards the slot holds garbage.
• Keep the open list sorted by stack slot; resize of the stack must repoint open upvalues (use slot indices, as here, not raw pointers, or fix pointers on reallocation).
• Lua 5.4: luaF_findupval (capture), luaF_closeupval (close) in lfunc.c.

Pitfalls

• Loop variables: if the language says each iteration has a fresh variable (Lua, JavaScript let, Go 1.22+), the compiler must close the upvalue each iteration. Pre-ES6 var and C-style loops share one variable.
• Capture by reference to a local that dies: in C++ [&] or [&x] on a lambda that outlives the frame is a dangling reference. Rust refuses this at compile time; use move.
• Rust move moves the variable into the closure: the closure and the original no longer share it. Copy types are copied; other types are moved, and a move closure that mutates its own copy never changes the original. To share, use Rc<RefCell<T>> or Arc<Mutex<T>> explicitly.
• C++ [=] copies at creation (later changes invisible) and captures this by pointer.
• Reference cycles: a closure stored in an object it captures forms a cycle; invisible to reference counting, fine for tracing GCs.

Variants and alternatives

In production

• Lua and LuaJIT: open/closed upvalues as above; Lua is embedded as the scripting layer in many game engines (see lua.org/uses.html).
• V8: closures capture "context" objects, uncaptured variables stay in registers; every DOM event handler is one.
• CPython: captured variables become "cell" objects, shared by the closures that reference them (__closure__).
• Rust and C++: each closure or lambda is an anonymous struct holding captures; the compiler monomorphizes and usually inlines, so iterator pipelines (map, filter) in data code have no closure allocation.

Implementations

Sources

• R. Ierusalimschy, L. H. de Figueiredo, W. Celes, The Implementation of Lua 5.0, J.UCS 11(7), 2005. paper
• Lua 5.4 source, lfunc.c (luaF_findupval, luaF_closeupval). code
• R. Nystrom, Crafting Interpreters, ch. 25 "Closures". book
• The Rust Reference, Closure types. docs
• cppreference, Lambda expressions (capture lists). docs
• T. Johnsson, Lambda lifting: transforming programs to recursive equations, FPCA 1985 (LNCS 201).