No, the stack isn't a list of frames where each frame is a separate heap allocated list of slots for values. You're right that that's a very common (but not super fast) implementation technique.

The Lua stack is a single contiguous array of value slots that is used by all call frames. In fact, call frames use overlapping stack windows so that function call arguments don't need to be moved during a call.

That makes implementing closures particularly tricky since when a function returns, its region of the stack is immediately reused by later code.

Upvalues address that by moving just the local variables that are closed over off that contiguous stack array and into the heap. And they do that only when the function where the variable is declared returns so that during that functionn's lifetime, it can be accessed directly from the stack. Also, the compiler is able to manage all this just with a single pass compilation.

It's really clever.

Multiple returns are from Common Lisp (I don't know if the history goes back further though), and they aren't tuples. They're the return-position analogue of what are default arguments in argument-position; like default args allow callers to ignore arguments they don't care about, multiple returns allow callers to ignore the return values they don't care about. You can add a secondary return value to a function without breaking existing callers, just like you can add a new default arg.

I’m pretty sure I saw multiple returns used in pseudo-code on a class handout the semester before I started working on CLU. The class was “Structure and Interpretation of Computer Programs” that would lead to the writing of SICP.

> From CLU we took multiple assignment and multiple returns from function calls. We regarded multiple returns as a simpler alternative to reference parameters used in Pascal and Modula and to in-out parameters used in Ada; we also wanted to avoid explicit pointers (used in C).

Lisp Machine Lisp is claimed to be the first Lisp to have that feature (end 70s), from where Common Lisp got it.

Edit: And yeah I don't think it's anything unique to Lua, it's an implementation detail of closures and lexical scope generally. It's a non-stack wrapper for closed-over variables, the end of the introduction to chapter 25 explains:

> For locals that aren’t used in closures, we’ll keep them just as they are on the stack. When a local is captured by a closure, we’ll adopt another solution that lifts them onto the heap where they can live as long as needed.

I sort of thought about mentioning something like that; that's in what I categorize as an optimization. (A good one, since the common case is that there probably isn't a closure at all in the scope, and the entire scope can thus be moved to the stack, kept out of heap, and not GC'd, reducing GC pressure.)

^ I mean internal stack structures, not a public stack, which is fully dynamic and may be cleared without affecting anything, e.g. in lua_CFunction. There’s nothing you can refer to on the stack, the same way you don’t want to refer to a temporary technical `push` in Assembly. Consider this:

  function f()
    local arr = []
    for i = 0, 100000000 do
      table.insert(arr, function ()
        return i
      end)
    end
  end

(For those unaware: `for i …` “creates” a new variable/upvalue at each iteration. Every arr[?]() returns a different value in this example.)

(A corrected version of your counter-example:

  function f()
    local arr = {}
    for i = 0, 5 do
      table.insert(arr, function ()
        return i
      end)
    end
    return arr
  end

That's good counter-example, and does run counter to my intuition. (The behavior I describe, e.g., in Python, is different; the closures in Python all close over the same variable.) One might be able to boil this down to instead using "scope" where I was saying "stack frame". (The difference being that for loops in Lua create scopes, vs. Python, where they do not. IMO Lua's is the better of the two options.)

To combine the optimization in the sibling thread (that I was attempting to avoid for simplicity's sake), then the implementation could be a stack of scope-ishes, consisting of the unclosed variables only, and then optionally some structure under GC, containing the closed-over variables (none, if nothing is closed over). The scopes on the stack would need to know of the (potential) GC object holding the closed over variables; a (normal) use of `i` here would have to look up the same `i` as what the closure hold, and as you note, cannot live on the stack.

… this is where, again, I think a diagram would help. I don't know that terms like "upvalue" and "activation record" help build understanding of Lua to new practitioners, and IMO, do more to obscure it. (This isn't your fault, ofc.; these are the terms Lua itself uses for these concepts.)