Lab 7: Functions and Recursion (Milestone 5)

Background

You will add function definitions, calls, parameters, return values, recursion, a call-depth limit, and tracebacks. At the end of this lab Ember is a real language, and the only things missing from it are data structures (Section 4) and a host (Section 5).

You will also produce, for the first time, the diagnostic that made you want to build a runtime:

error: attempt to add a nil value

  4 │   return a + b
    │              ^

stack traceback:
  in function 'add'    policy.ember:4
  in function 'apply'  policy.ember:9
  in main chunk        policy.ember:12

Why This Lab Matters

• Calls are the operation Section 3 speeds up most. The fib(25) number you record here is the baseline for the entire rest of the curriculum.
• The depth limit is a safety property, not a nicety. Without it, one line of script aborts the host process with a signal no Result can catch.
• The traceback needs five things that were designed in over four labs — spans on tokens, spans on nodes, a call span, a frame stack, and a function name. This is the payoff chapter for all of them.

Prerequisites

• Lab 6 complete.
• Functions and Frames read.

Predict First

1. local f = function() return f() end — what does the inner f refer to? What about local function f() return f() end?
2. local function g(a, b) return b end; return g(1) — what is returned?
3. local function g(a) return a end; return g(1, 2, 3) — error, or something else?
4. return (function() end)() — what does a function that falls off the end return?
5. How many Rust stack frames does one Ember call consume in your implementation? Guess, then measure.
6. local function f() return f() end f() with no depth limit — what does the process do? What is the exit status?
7. Ember's parse-depth limit is 200 and its call-depth limit is 200. What is the deepest possible eval_expr nesting?

Step 1: Function Definitions in the Parser

#![allow(unused)]
fn main() {
fn funcbody(&mut self, name: Option<String>, start: Span) -> Result<Expr> {
    let saved_loop_depth = std::mem::replace(&mut self.loop_depth, 0);   // `break` cannot cross
    self.expect(TokenKind::LParen)?;
    let mut params = Vec::new();
    let mut is_vararg = false;
    if !self.at(&TokenKind::RParen) {
        loop {
            if self.eat(TokenKind::Ellipsis) { is_vararg = true; break; }   // Lab 17
            params.push(self.name()?);
            if !self.eat(TokenKind::Comma) { break; }
        }
    }
    self.expect(TokenKind::RParen)?;
    let body = self.block()?;
    self.expect(TokenKind::End)?;
    self.loop_depth = saved_loop_depth;
    Ok(Expr::Function { name, params, is_vararg, body, span: start.merge(self.prev_span()) })
}
}

Three statement forms desugar to this, and the order of binding versus body differs:

#![allow(unused)]
fn main() {
// `function f(...) ... end`  →  f = function(...) ... end        (a GLOBAL assignment)
// `local function f(...) end`→  local f; f = function(...) end   (binding FIRST — recursion works)
// `local f = function() end` →  local f = <the function>          (binding LAST — `f` inside is global)
}

That middle line is Lua 5.4 §3.4.11 and it is the reason local function exists as a distinct form. Implement it as an explicit Stmt::LocalFunction that declares the name with nil before evaluating the function expression.

Checkpoint question. Why does resetting loop_depth to 0 inside funcbody matter? Write the program that breaks without it.

Step 2: Calls in the Parser

Calls, indexing, and method calls are postfix, and they chain: a.b[c](d):e(f). They live in a suffix loop:

#![allow(unused)]
fn main() {
fn suffixed_expr(&mut self) -> Result<Expr> {
    let mut e = self.primary_expr()?;                  // Name or '(' exp ')'
    loop {
        e = match self.peek() {
            TokenKind::Dot      => { /* Index with a Str key — Lab 13 */ }
            TokenKind::LBracket => { /* Index — Lab 13 */ }
            TokenKind::Colon    => { /* Method — Lab 13 */ }
            TokenKind::LParen   => {
                self.advance();
                let args = if self.at(&TokenKind::RParen) { vec![] } else { self.exprlist()? };
                let close = self.expect(TokenKind::RParen)?;
                Expr::Call { span: e.span().merge(close.span), callee: Box::new(e), args }
            }
            TokenKind::Str(_)   => { /* f"literal" sugar — Lua allows it; Ember: Lab 13 */ }
            _ => break,
        };
    }
    Ok(e)
}
}

Note: Postfix operators are in a suffix loop rather than in the Pratt infix loop because their right-hand sides are not expressions parsed by binding power — t.name takes a name, f(a,b) takes an argument list. See the Pratt chapter's production concerns. This is the decision that chapter told you to note when you got here.

Step 3: Calling

Write Interp::call from the concept chapter, plus:

#![allow(unused)]
fn main() {
Expr::Call { callee, args, span } => {
    let f = self.eval_expr(callee)?;                    // 1. the callee, first
    let mut argv = Vec::with_capacity(args.len());
    for a in args { argv.push(self.eval_expr(a)?); }    // 2. arguments, left to right
    self.budget.tick_call()?;                           // 3. a call is budgeted work
    let results = self.call(f, argv, *span)?;
    // A call in an EXPRESSION position yields exactly one value (or nil).
    // Lab 17 makes the "last in a list" case yield all of them.
    results.into_iter().next().unwrap_or(Value::Nil)
}
}

The one-value adjustment on the last line is a real semantic, and it is the rule from warm-up Experiment 4: a call not in the final position of a list is truncated to one value. Ember truncates everywhere until Lab 17. Note it as a known incompleteness in docs/limitations.md rather than pretending the behavior is final.

Step 4: The Depth Limit and the Frame Stack

#![allow(unused)]
fn main() {
pub struct FrameInfo {
    pub name: Option<String>,      // for the traceback
    pub call_span: Span,           // WHERE the call was made — the caller's line
}

const MAX_CALL_DEPTH: usize = 200;
}

Write push_frame and the FrameGuard from the concept chapter. Then the traceback:

#![allow(unused)]
fn main() {
fn traceback(&self) -> Vec<Frame> {
    let mut out: Vec<Frame> = self.frames.iter().rev()
        .map(|f| Frame { name: f.name.clone().unwrap_or_else(|| "?".into()),
                         span: f.call_span })
        .collect();
    out.push(Frame { name: "main chunk".into(), span: Span::EMPTY });
    // Lua truncates long tracebacks: first 10, "...", last 11. A 200-frame
    // traceback in a log pipeline is expensive and unreadable.
    if out.len() > 22 {
        let tail = out.split_off(out.len() - 11);
        out.truncate(10);
        out.push(Frame::elision(/* skipped */));
        out.extend(tail);
    }
    out
}
}

Attach it at the point the error is created, not where it is caught:

#![allow(unused)]
fn main() {
fn rt(&self, span: Span, msg: impl Into<String>) -> EmberError {
    EmberError { kind: ErrorKind::Runtime, message: msg.into(),
                 span: Some(span), traceback: self.traceback() }   // ← captured HERE
}
}

Warning: Capture the traceback at creation. If you build it where the error is handled, the frames have already been popped by the FrameGuards unwinding through ?, and you get an empty traceback — a bug that looks like "tracebacks do not work" and is actually "tracebacks are captured one frame too late."

Step 5: Measure the Rust Frames Per Ember Call

This is the step that turns MAX_CALL_DEPTH = 200 from a guess into a decision.

#![allow(unused)]
fn main() {
#[test] #[ignore]   // cargo test -- --ignored rust_frames_per_ember_call
fn rust_frames_per_ember_call() {
    // Take the address of a local at depth 1 and at depth N. The difference,
    // divided by (N-1), is the Rust stack consumed per Ember call.
    // Run in RELEASE and in DEBUG — debug frames are much larger, and the
    // limit must be safe for the worse case.
    let bytes_per_call = measure();      // you write this
    eprintln!("bytes of Rust stack per Ember call: {bytes_per_call}");
    // The two limits MULTIPLY: a call whose body is a deeply nested expression
    // consumes call-frames × expression-frames.
    let worst = bytes_per_call * MAX_CALL_DEPTH + EXPR_FRAME_BYTES * MAX_PARSE_DEPTH;
    eprintln!("worst-case stack: {} KiB (2 MiB is a typical spawned-thread stack)",
              worst / 1024);
    assert!(worst < 512 * 1024, "limits are not safe for a 2 MiB thread stack");
}
}

Record the numbers in docs/learning/07-call-frames.md. If the assertion fails, lower the limits — do not raise the threshold. A limit chosen so the runtime is safe on a 2 MiB spawned thread is a limit that works everywhere; one tuned to the 8 MiB main thread will fail in a thread pool, in production, on a Tuesday.

The Trace

$ 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  event
  1    call fib(4)          <argv>:6
  2    │ call fib(3)        <argv>:4
  3    │ │ call fib(2)      <argv>:4
  4    │ │ │ call fib(1)    <argv>:4  → 1
  4    │ │ │ call fib(0)    <argv>:4  → 0
  3    │ │ ret fib(2) → 1
  3    │ │ call fib(1)      <argv>:4  → 1
  2    │ ret fib(3) → 2
  2    │ call fib(2)        <argv>:4
  3    │ │ call fib(1)      <argv>:4  → 1
  3    │ │ call fib(0)      <argv>:4  → 0
  2    │ ret fib(2) → 1
  1    ret fib(4) → 3
stats: 9 calls, max depth 4
3

Three readings:

1. Depth 4, but 9 calls. Depth is bounded by MAX_CALL_DEPTH; call count is bounded by the instruction budget. Two resources, two limits. A host that confuses them will set one and be surprised by the other.
2. fib(2) runs three times. Nothing memoizes, which is exactly why fib(25) (≈243k calls) is the benchmark: it isolates call overhead.
3. The call span is the caller's line (<argv>:4), not the function's definition line. That is what makes a traceback navigable, and it is why FrameInfo stores call_span.

Now the error path, which is the deliverable:

$ cat > /tmp/p.ember <<'EOF'
local function add(a, b)
  return a + b
end
local function apply(f, x)
  return f(x)
end
return apply(add, 1)
EOF
$ ember run /tmp/p.ember

/tmp/p.ember:2:14: error: attempt to add a nil value

   2 │   return a + b
     │              ^

stack traceback:
  in function 'add'     /tmp/p.ember:5
  in function 'apply'   /tmp/p.ember:7
  in main chunk         /tmp/p.ember:7

Read what that required: the caret comes from the Binary node's right operand span (Lab 2 and Lab 4), the line numbers come from the SourceMap (Lab 1), the frame names come from Stmt::LocalFunction (this lab), and the frame lines come from call_span (this lab). Five labs, one message. If any one of them had been deferred, this would say runtime error.

And the limit:

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

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

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

echo $? printing 1 rather than 139 is the whole point of Step 4.

Debugging Steps

local function f cannot call itself

You implemented it as local f = function() end. The binding must be declared before the function expression is evaluated.

break inside a function body compiles

loop_depth is not reset in funcbody.

The traceback is empty

Built at the catch site instead of the throw site. The FrameGuards already popped.

The traceback shows the callee's line for every frame

You stored the function's definition span instead of the call span. FrameInfo.call_span is the caller's.

Deep recursion aborts with SIGSEGV despite the limit

Either the limit is too high for your measured frames-per-call, or the depth counter is not incremented for one call path — commonly the Native path, or a method call. Every route into call must go through push_frame.

g(1, 2, 3) on a one-parameter function errors

You added an arity check. Lua does not have one: extras are discarded, missing are nil. Remove it, or make it an opt-in strict mode with an ADR.

Recursion is correct but absurdly slow

Expected. Record the number; that is Step 6.

Step 6: The Baseline

cargo bench --bench calls -- fib_25 | tee docs/learning/baseline-interp.txt

Write down, in docs/learning/07-call-frames.md, three predictions for Section 3 — before you build it:

1. How much faster will the VM be on fib(25)? Give a factor.
2. Which of the three costs dominates: name resolution (hash + scope walk), the Vec<Value> allocation per call, or Flow/AST traversal overhead?
3. What will not get faster?

You will check these in Lab 11. Predictions written before a measurement are worth ten times ones written after.

Test

#![allow(unused)]
fn main() {
#[test]
fn local_function_can_recurse_but_local_assignment_cannot() {
    // Lua 5.4 §3.4.11: `local function f` declares f BEFORE the body is evaluated.
    assert_eq!(run("local function f(n) if n<=0 then return 0 end return f(n-1) end
                    return f(3)"), "0");
    // The other form: `f` inside the body is a GLOBAL, which is nil.
    assert_eq!(err("local f = function(n) if n>0 then return f(n-1) end return 0 end
                    return f(3)").kind, ErrorKind::Runtime);
}

#[test]
fn arity_mismatch_is_never_an_error() {
    assert_eq!(run("local function g(a,b) return b end return tostring(g(1))"), "nil");
    assert_eq!(run("local function g(a) return a end return g(1,2,3)"), "1");
}

#[test]
fn falling_off_the_end_returns_nothing() {
    assert_eq!(run("local function g() end return tostring(g())"), "nil");
}

#[test]
fn recursion_and_mutual_recursion() {
    assert_eq!(run("local function fib(n) if n<2 then return n end
                    return fib(n-1)+fib(n-2) end return fib(20)"), "6765");
    assert_eq!(run("local is_even, is_odd
                    function is_even(n) if n==0 then return true end return is_odd(n-1) end
                    function is_odd(n) if n==0 then return false end return is_even(n-1) end
                    return tostring(is_even(10))"), "true");
}

#[test]
fn runaway_recursion_is_a_limit_error_not_a_crash() {
    // This test PASSING AT ALL is the assertion: an unguarded implementation
    // aborts the process and takes the whole test binary with it.
    let e = err("local function f() return f() end return f()");
    assert_eq!(e.kind, ErrorKind::Limit);
    assert!(!e.traceback.is_empty(), "a limit error must carry a traceback");
    assert!(e.traceback.len() <= 22, "tracebacks must be truncated");
}

#[test]
fn mutual_recursion_also_hits_the_limit() {
    let e = err("local a, b
                 function a() return b() end
                 function b() return a() end
                 return a()");
    assert_eq!(e.kind, ErrorKind::Limit);
}

#[test]
fn traceback_records_the_callers_line() {
    let e = err("local function add(a,b) return a+b end\n\
                 local function apply(f,x) return f(x) end\n\
                 return apply(add, 1)");
    assert_eq!(e.kind, ErrorKind::Runtime);
    assert_eq!(e.traceback[0].name, "add");
    // Frame 0's span is where `add` was CALLED (line 2), not where it is defined.
    assert_eq!(line_of(e.traceback[0].span), 2);
}
}

Challenge Extensions

1. Proper tail calls. Lua 5.4 §3.4.10 guarantees return f(x) runs in constant stack. In a tree walker this needs a trampoline: call returns either a value or "call this next", and a loop drives it. Implement it, then explain why the same feature is four lines in the VM.
2. Strict arity. Add --strict-arity and run it over your golden corpus. How many real bugs does it find? Would you ship it on by default? Write the ADR.
3. Named-argument tracebacks. Make an anonymous function's traceback entry read function <argv:12> like Lua's, rather than ?.
4. Depth-limit fuzzing. Generate random programs with recursion and assert that none of them aborts the process — only ErrorKind::Limit. This is a preview of Section 6 and it is the single most valuable fuzz target Ember has.
5. pcall. Implement Lua's protected call: pcall(f, ...) returns false, err instead of propagating. It is fifteen lines and it makes the ErrorKind distinction concrete — decide whether ErrorKind::Limit should be catchable by pcall, and defend the answer. (Lua's answer for stack overflow is nuanced; check it.)

Deliverables

• All three function-definition forms work, with the correct binding order for each.
• Calls, recursion, and mutual recursion work.
• Arity mismatches never error; extras discarded, missing are nil.
• break cannot cross a function boundary (parse error).
• MAX_CALL_DEPTH is chosen from a measurement, recorded in docs/learning/07-call-frames.md, and safe for a 2 MiB thread stack.
• Runaway and mutual recursion produce ErrorKind::Limit with a truncated traceback, exit 1.
• Tracebacks record the caller's line and are captured at error creation.
• --trace-calls produces the tree shown above with a call count and max depth.
• cargo bench --bench calls -- fib_25 recorded as docs/learning/baseline-interp.txt.
• Three written predictions for Section 3's speedup.

Validation / Self-check

1. Give the three function-definition forms and the binding order of each. Which one enables recursion and why?
2. Why must loop_depth be reset in funcbody? Give the program that exposes it.
3. Name the five separate pieces of engineering visible in the traceback in The Trace, and the lab each came from.
4. Why is the traceback captured at error creation rather than at the catch site?
5. Why is arity never checked? What does that buy, and what does it cost?
6. How did you choose MAX_CALL_DEPTH? Why is the 2 MiB thread stack the right target rather than the 8 MiB main stack?
7. Explain "the two limits multiply" with your measured numbers.
8. Depth and call count are bounded by different limits. Give a program that hits each without hitting the other.

Next: Lab 8 — The Reference Interpreter.