Functions and Frames

Three concepts: the function as a value, the calling convention, and recursion with its limit.

This is where the tree walker's central weakness becomes visible: an Ember call is a Rust call, so the script's recursion depth is bounded by the host's stack and a runaway script can abort the process. Section 3 fixes that by making frames data instead of Rust stack frames. Understanding exactly why is the point of this chapter.

Concept 1: The Function Object

1. Concept

A function is a value: it can be stored in a variable, passed as an argument, returned, and put in a table. It carries the code to run, the parameter names, and (from Lab 14) the variables it captured.

2. Problem

function add(a, b) return a + b end must produce something a later add(1, 2) can call. That something has to survive the statement that created it, live in the environment alongside numbers and strings, and be distinguishable from them at run time.

3. Mental model

A function value is a pointer to code plus the environment it remembers. In the tree walker the "code" is a subtree of the AST. In the VM it is an index into a chunk. The plus the environment half is what makes it a closure, and it is Section 4's whole subject.

4. Implementation

#![allow(unused)]
fn main() {
// src/value.rs (tree-walker version; the VM's version is in Lab 14)
pub struct FnDef {
    pub name: Option<String>,        // for tracebacks only; anonymous functions have none
    pub params: Vec<String>,
    pub is_vararg: bool,
    pub body: Block,                 // the AST subtree — shared, never cloned
    pub span: Span,
}

pub enum Value {
    // ...
    Function(Rc<FnDef>),             // Rc: the AST is shared by every closure over it
    Native(Rc<NativeFn>),            // a Rust function the host registered (§5)
}
}

Why Rc, in the tree walker only. Two closures created from the same function expression share one body. Copying the AST per call would be absurd; borrowing it would tie Value's lifetime to the AST, which would infect everything. Rc is the pragmatic answer for the reference implementation, where correctness and readability outrank everything.

Note: This is exactly the Rc that ADR-006 refuses to use in the VM, and the difference is instructive. Here, FnDef is immutable and acyclic — an AST subtree cannot point back at a Value — so Rc cannot leak. In Section 4, closures capture upvalues that can point back at the closure, and that cycle is precisely what Rc cannot collect. The rule is not "Rc is bad"; it is "Rc cannot collect cycles, so use it only where cycles are structurally impossible." Write that in docs/learning/09-closures.md.

Two statement forms produce functions, and one of them has a subtlety:

local function f(n) ... f(n-1) ... end    -- the binding exists BEFORE the body is evaluated,
                                          -- so `f` inside the body is the local. Recursion works.
local f = function(n) ... f(n-1) ... end  -- the binding is created AFTER; `f` inside the body is
                                          -- a GLOBAL. This is a real Lua rule (§3.4.11) and a
                                          -- real source of confusion.

Verify it: lua -e 'local f = function(n) if n>0 then return f(n-1) end return 0 end print(f(3))' errors with "attempt to call a nil value (global 'f')". Ember copies this. Test both forms.

5–7. Alternatives, decision, tradeoffs

Decision: A in the tree walker, B in the VM, C for host functions. Three representations of "callable", unified behind Value. That the call site does not care which it has is the point of the enum.

8. Production concerns

• Function identity. function() end == function() end is false — two evaluations of the same expression produce two distinct functions. But is f == f true after local f = function() end? Yes: comparing the same Value. Decide and test it; Lua compares by reference.
• Names are for humans. FnDef::name exists only for tracebacks. It must never affect semantics, and an anonymous function must produce a usable traceback entry anyway — function <policy.ember:12> is what Lua prints, and it is worth copying.

Concept 2: The Calling Convention

1. Concept

A calling convention is the contract between caller and callee: who evaluates the arguments, where they are put, who allocates the frame, what happens on arity mismatch, and who cleans up.

2. Problem

Every call in the language goes through this contract, so any ambiguity in it is a bug that appears everywhere. And Lua's convention has two rules that are unusual enough to state explicitly.

3. Mental model

   CALLER                                CALLEE
   ──────                                ──────
   1. evaluate the callee expression
   2. evaluate arguments, LEFT TO RIGHT
   3. check it is callable  ──────────▶  4. open a new scope
                                         5. bind parameters to arguments
                                            (pad with nil / discard extras)
                                         6. run the body
                                         7. Flow::Return(values) ─┐
   8. adjust the result count ◀──────────────────────────────────┘
      to what the CALL SITE wants

The two unusual rules: arity never errors, and the call site decides how many results it wants. Both come from Lua and both have consequences that reach into Section 4.

4. Implementation

#![allow(unused)]
fn main() {
fn call(&mut self, callee: Value, args: Vec<Value>, span: Span) -> Result<Vec<Value>> {
    let f = match callee {
        Value::Function(f) => f,
        Value::Native(n)   => return (n.f)(self, args),           // §5
        other => return Err(rt(span,
            format!("attempt to call a {} value", other.type_name()))),
    };

    // The depth guard. This is a SAFETY property, not a nicety — see Concept 3.
    let _frame = self.push_frame(f.name.clone(), span)?;

    self.env.push_scope();
    // Lua 5.4 §3.4.11: extra arguments are DISCARDED, missing ones are NIL.
    // An arity mismatch is NEVER an error. This is a language decision that
    // makes optional parameters free and typos silent.
    for (i, p) in f.params.iter().enumerate() {
        self.env.declare(p.clone(), args.get(i).copied().unwrap_or(Value::Nil));
    }

    let flow = self.eval_block(&f.body);
    self.env.pop_scope();

    match flow? {
        Flow::Return(vs) => Ok(vs),
        Flow::Normal     => Ok(vec![]),          // falling off the end returns nothing
        Flow::Break      => Err(internal("break escaped a function body")),
    }
}
}

The parts that carry meaning:

• Flow::Return is absorbed here. This is the third row of the absorbs/forwards table. A Flow::Break reaching this point is an internal error, because the parser rejected break outside a loop.
• Arity is not checked. f(1) on a two-parameter function binds the second to nil. That is Lua, it makes optional parameters free, and it also means a typo'd call site fails somewhere inside the function rather than at the call. Section 6's diagnostics work is partly about making that failure legible.
• The scope is pushed after the arguments are evaluated, because arguments are evaluated in the caller's scope. Push first and f(x) inside f would resolve x to the parameter. This is the same ordering rule as local x = x.

5. Alternatives

Option B is the important one. In the VM, arguments are already on the value stack where the caller evaluated them, and the callee's frame simply says "your slots start here". No copying, no allocation. Lua's C API exposes exactly this model to hosts — lua_pushnumber then lua_call — which is why it never hands out pointers to collectable objects.

6–7. Decision and tradeoffs

A now, B in Section 3. The Vec<Value> per call is a real cost you will measure in Lab 8, and it is one of the three reasons the VM is faster (the others being name resolution and dispatch). Record all three in docs/learning/07-call-frames.md before building the VM, as predictions.

8. Production concerns

• Deep argument lists. f(a, b, ..., 10000 args) allocates a large Vec. Section 5 caps argument count; the cap belongs with the other limits, not scattered.
• Re-entrancy. In Section 5, Native functions call back into the interpreter. call must therefore be re-entrant, which it is here only because &mut self is released before (n.f) runs — look closely at that line, and note that it does not hold a borrow across the callback. The VM will have to work harder for the same property. This is the single hardest Rust problem in the curriculum and Lab 19 is where it lands.
• Tail calls. Lua 5.4 §3.4.10 guarantees proper tail calls: return f(x) reuses the caller's frame, so a tail-recursive loop runs in constant stack. Ember does not implement this, in either backend, and that is a divergence with a real consequence: a Lua program written as a tail-recursive state machine will hit Ember's depth limit. Document it in appendix/lua-differences.md; implementing it in the VM is a Section 3 challenge extension and is genuinely easy there (reuse the frame instead of pushing) and genuinely hard here.

9. References

rg -n 'luaD_precall|luaD_poscall|luaD_call' ldo.c
rg -n 'OP_CALL|OP_TAILCALL|OP_RETURN' lvm.c lopcodes.h

• Lua's ldo.c — luaD_precall sets up the frame, luaD_poscall adjusts results. Read them together; the pair is the calling convention.
• Lua 5.4 Reference Manual §3.4.10 (tail calls) and §3.4.11 (function calls).
• The System V AMD64 ABI's section on the calling convention, for what the same document looks like at the machine level. You will need it in Section 7.

Concept 3: Frames, Recursion, and the Limit

1. Concept

A frame is the per-call state: which function, its local scope, and where to resume. Recursion creates frames faster than anything else, and unbounded recursion is how a script kills a host.

2. Problem

In the tree walker there is no explicit frame — the state lives in Rust's own stack frames. Therefore:

local function f() return f() end
f()

recurses in Rust until the host process's stack overflows, which on Linux and macOS delivers SIGSEGV and aborts. Not a panic. Not a Result. The process dies, and a host embedding Ember cannot catch it, log it, or recover. For a library that will be embedded in a service, that is a release blocker.

3. Mental model

Two stacks are in play and only one of them is yours. The Ember call stack is a concept; the Rust call stack is the machine's, it is finite (typically 8 MiB on the main thread, 2 MiB on spawned threads), and you do not get to catch its overflow. So you must count, and refuse, before it happens.

4. Implementation

#![allow(unused)]
fn main() {
pub struct FrameInfo { pub name: Option<String>, pub call_span: Span }

const MAX_CALL_DEPTH: usize = 200;      // TODO(§5): configurable via Engine limits

fn push_frame(&mut self, name: Option<String>, span: Span) -> Result<FrameGuard<'_>> {
    if self.frames.len() >= MAX_CALL_DEPTH {
        return Err(EmberError {
            kind: ErrorKind::Limit,                       // NOT Runtime: the host cares
            message: format!("stack overflow (call depth limit {MAX_CALL_DEPTH} exceeded)"),
            span: Some(span),
            traceback: self.traceback(),                  // built from `frames`
        });
    }
    self.frames.push(FrameInfo { name, call_span: span });
    Ok(FrameGuard { frames: &mut self.frames })           // Drop pops
}
}

self.frames exists only to produce the depth check and the traceback — the actual execution state is still on the Rust stack. That is the tree walker's compromise, and naming it makes Section 3's improvement precise: the VM's frames vector holds the real state, so the Rust stack stays flat and the limit becomes a policy number rather than a proxy for a hardware constraint.

5–7. Alternatives, decision, tradeoffs

Decision: A, with D available to hosts in Section 5. Determinism decides it: the same script must fail at the same depth on every machine, and B and C make the failure point depend on the environment. A ranking policy that works on the developer's laptop and hits the limit in production because the thread stack is smaller is exactly the outcome to design out.

How to choose the number. Measure it, do not guess:

#![allow(unused)]
fn main() {
#[test] #[ignore]  // run manually: cargo test -- --ignored measure_rust_frames
fn measure_rust_frames_per_ember_call() {
    // Recurse to depth N with the limit raised, and record the process's stack
    // usage. Divide. Then set MAX_CALL_DEPTH so that
    //     MAX_CALL_DEPTH × bytes_per_ember_call  <  0.25 × smallest_expected_stack
    // The 4× margin covers the deepest EXPRESSION nesting on top of the deepest
    // call nesting — the two limits multiply, and that is the trap.
}
}

That last sentence is the one people miss: the parser's depth limit and the call depth limit compose. A 200-deep call stack where each call evaluates a 200-deep expression is 40,000 nested eval_expr frames. Both numbers must be chosen together.

8. Production concerns

• The error kind must be Limit, not Runtime. A host needs to distinguish "the script has a bug" from "the script hit the wall we put up". The first pages the script author; the second is a metric, and possibly a signal to raise the budget. This is why ErrorKind::Limit was declared in Lab 0, before anything could produce it.
• The traceback must be truncated. A 200-frame traceback printed in full is unreadable and, in a log pipeline, expensive. Lua prints the first ~10 and last ~11 with ... between. Copy that.
• Mutual recursion counts too. Test f calls g calls f; a limit that only catches direct self-calls catches nothing real.
• Native functions must count. A host function that calls back into Ember adds Rust frames without adding Ember frames unless call counts them. Section 5 revisits this; note it now.

9. References

• Lua's LUAI_MAXCCALLS in luaconf.h and luaE_checkcstack in lstate.c — Lua faces exactly this problem for its C-call depth and solves it the same way, with a counted limit.
• The stacker crate, for option C, and its README's honest discussion of why it is a last resort.
• CPython's sys.setrecursionlimit and the long history of segfaults from setting it too high — the best available cautionary tale for why the limit must be conservative.

The Trace: fib(4)

$ ember run --trace-calls -e '
local function fib(n)
  if n < 2 then return n end
  return fib(n-1) + fib(n-2)
end
return fib(4)'

depth  call
  1    fib(4)
  2    ├─ fib(3)
  3    │  ├─ fib(2)
  4    │  │  ├─ fib(1) → 1
  4    │  │  └─ fib(0) → 0
  3    │  └─ fib(2) → 1
  3    │  ├─ fib(1) → 1
  2    └─ fib(3) → 2
  2    ├─ fib(2)
  3    │  ├─ fib(1) → 1
  3    │  └─ fib(0) → 0
  2    └─ fib(2) → 1
  1    fib(4) → 3
frames: 9 calls, max depth 4

Three things to read off that trace:

1. Max depth is 4, but there were 9 calls. Depth is what the limit constrains; call count is what the instruction budget constrains. Two different resources, two different limits, and confusing them is a Section 5 bug.
2. fib(2) is computed three times. Nothing memoizes. That is why fib(25) is the benchmark: it is ~243,000 calls, which makes call overhead the dominant cost and therefore a clean measurement of exactly what Section 3 improves.
3. The tree is the Rust call stack. Each │ is roughly ten Rust frames deep in eval_expr / eval_stmt / eval_block / call. Measure your own number; it is what sets the limit.

Now the failure case:

$ ember run -e 'local function f() return f() end return f()'
error: stack overflow (call depth limit 200 exceeded)

  1 │ local function f() return f() end return f()
    │                            ^^^

stack traceback:
  in function 'f'   <argv>:1
  in function 'f'   <argv>:1
  ... (190 more)
  in function 'f'   <argv>:1
  in main chunk     <argv>:1
$ echo $?
1

Exit code 1, not 139. That difference is the deliverable.

Things to Notice

• Rc is safe here and unsafe-in-spirit in Section 4, and the distinguishing property is whether cycles are structurally possible. Immutable, acyclic, shared → Rc. Mutable object graph → tracing GC.
• local function f and local f = function differ, and the difference is one line of ordering — the same ordering rule as local x = x. Three appearances of "when does the binding come into existence" in one section.
• Arity is never an error in Lua. That is a deliberate design that trades a class of caught errors for optional parameters and forward compatibility. Whether it was the right trade is worth an opinion.
• The tree walker's depth limit is a proxy for a hardware constraint; the VM's is a policy. That is the sharpest single statement of what making frames data buys you.
• Two limits multiply. Expression depth × call depth. Choose them together or discover it in production.

Validation / Self-check

1. What is in a function value, and what does "plus the environment it remembers" refer to?
2. Why is Rc<FnDef> acceptable in the tree walker when ADR-006 rejects Rc for the VM's objects?
3. Give the eight steps of Ember's calling convention and say which two are unusual.
4. Why is the callee's scope pushed after the arguments are evaluated?
5. local f = function() ... f() ... end — what does the inner f refer to, and why?
6. Why does unbounded recursion in the tree walker abort the process rather than return an error, and why can't catch_unwind help?
7. Why is the limit a counted depth rather than a real stack probe? State the property that decides it.
8. Why is the error ErrorKind::Limit rather than ErrorKind::Runtime? Give a host behavior that depends on the distinction.
9. Explain "two limits multiply" with a concrete pair of numbers.
10. Name the three reasons the VM will be faster at calls, before you have built it.

Next: The Reference Implementation.