56. Calls and call frames

A loop can’t call itself

In chapter 40 a Drip call in the tree-walker was a chain of TypeScript calls. Where to return to, and what each caller was in the middle of, lived in TypeScript’s own frames on the host stack. Each call also built a fresh Environment with its own Map (chapter 39).

The VM is a single for (;;) loop over bytes. If fib calls fib, the loop must remember where it was in the caller, run the callee’s bytecode, and later resume the caller. All of that has to be data.

Every function gets a chunk

First, the compiler. A function body is compiled into its own chunk, by its own little compiler, from compiler.ts:

function fnBody(type: FnType) {
  initCompiler(type);
  beginScope();
  // ( params ) {
  if (!check(')')) {
    do {
      fc().fn.arity++;
      defineVariable(parseVariable(
        'Expect parameter name.'));
    } while (match(','));
  }
  block();
  const fn = endCompiler();
  emit(OP.CLOSURE, makeConstant(fn));
}

initCompiler makes a new function object and a new FnCompiler linked to the enclosing one, with its own locals array, and reserves slot 0 just as in chapter 54. Each parameter is then declared as an ordinary local, so parameters get slots 1, 2, …. endCompiler appends NIL and RETURN, for a body that falls off its end, and switches back to the enclosing compiler. The finished function becomes a constant in the enclosing chunk, and CLOSURE (chapter 57 says why it’s called that) pushes it at run time.

fn add(a, b) {
  return a + b;
}
print add(1, 2);

== script ==
0000    3 OP_CLOSURE          1 <fn add>
0002    | OP_DEFINE_GLOBAL    0 'add'
0004    4 OP_GET_GLOBAL       2 'add'
0006    | OP_CONSTANT         3 '1'
0008    | OP_CONSTANT         4 '2'
0010    | OP_CALL             2
0012    | OP_PRINT
0013    5 OP_NIL
0014    | OP_RETURN
== add ==
0000    2 OP_GET_LOCAL        1
0002    | OP_GET_LOCAL        2
0004    | OP_ADD
0005    | OP_RETURN
0006    3 OP_NIL
0007    | OP_RETURN

Inside add, a and b are just slots 1 and 2.

The arguments are already in place

Look at the script’s code before CALL 2. It pushes the callee, then 1, then 2. So at the moment of the call, the top of the stack reads add, 1, 2, which is exactly the layout add expects for its slots 0, 1 and 2. If the callee’s slot 0 is simply placed at the callee’s position on the stack, nothing needs copying at all.

So each active call needs just three facts, kept in a record from vm.ts:

interface CallFrame {
  closure: ObjClosure; // what runs
  ip: number;     // next byte in it
  slots: number;  // its slot 0
}

That explains the frame.slots + in last chapter’s GET_LOCAL. The same bytecode works for every call of fib, because each call reads its slots through a different frame pointer.

CALL and RETURN

CALL n finds the callee n places below the top of the stack and hands it to callValue, which checks that it is something callable. For a Drip function, it ends up in call:

call(closure, argCount) {
  const want = closure.fn.arity;
  if (argCount !== want)
    this.runtimeError(`Expected ` +
      `${want} arguments but got ` +
      `${argCount}.`);
  if (this.frames.length === 64)
    this.runtimeError(
      'Stack overflow.');
  this.frames.push({ closure, ip: 0,
    slots: this.sp - argCount - 1 });
}

That is the whole call. No new environment, no Map, no host call: one record pushed. The dispatch loop then reloads its cached frame, code and constants from the new top frame, and the next byte it reads is the callee’s first instruction. A native function such as clock is the exception: callValue runs it directly and pushes its result, with no frame. Anything else, like 123(), is a runtime error: Can only call functions and classes.

RETURN undoes it:

case OP.RETURN: {
  const result = this.pop();
  this.frames.pop();
  if (this.frames.length === 0) {
    this.pop();
    return; // the script is done
  }
  this.sp = frame.slots;
  this.push(result);
  reload();
  break;
}

Setting sp back to the frame’s slots throws away the callee’s function, its arguments and all its locals in one assignment. The result goes where the callee was. To the caller, the call has turned into a single value, exactly as if an expression had been evaluated. (The real case also closes upvalues; chapter 57.)

Step through fib(2):

fn fib(n) {
  if (n < 2) return n;
  return fib(n - 1) + fib(n - 2);
}
print fib(2);

Errors that know the stack

Because frames are data, a runtime error can walk them and say where every waiting call was. From runtimeError:

for (let i = this.frames.length - 1;
     i >= 0; i--) {
  const f = this.frames[i];
  const fn = f.closure.fn;
  const line = fn.chunk.lines[f.ip - 1];
  this.err.push(`[line ${line}] in ` +
    (fn.name ? fn.name.chars + '()'
      : 'script'));
}

Each frame’s ip has moved just past the instruction it was running, so ip - 1 finds that instruction’s line. The tree-walker couldn’t do this: its waiting calls were buried in TypeScript’s frames.

fn a() { b(); }
fn b() { c(); }
fn c() {
  c("too", "many");
}

a();

The limit of 64 frames is the VM’s own choice, not the host’s. A recursion with no base case gets 63 calls deep below the script, then stops with Stack overflow. and a trace 64 lines long.

Your turn

const FRAMES_MAX = 64;
const arityMsg = (want, got) =>
  `Expected ${want} arguments ` +
  `but got ${got}.`;

// vm = { stack: [...], frames: [...] }
// fn = { name, arity }

// The callee and its argc args are on
// top of the stack. Push a frame.
function call(vm, fn, argc) {
  // your code here
}

// The result is on top. Pop it and the
// frame, drop the frame's slots, then
// push the result.
function ret(vm) {
  // your code here
}

// Stack index of local slot i of the
// current (top) frame.
function slotAddr(vm, i) {
  // your code here
}

fn sum(n) {
  if (n == 0) return 0;
  return n + sum(n - 1);
}

print sum(10);
print sum(1000);

What you learned

• Each function is compiled into its own chunk, with slot 0 reserved and its parameters as its first locals. The finished function is a constant in the enclosing chunk.
• A call frame records the running function, its own ip, and its frame pointer (slots): where its slot 0 is on the shared stack.
• CALL n checks arity and depth, then pushes a frame whose slots start at the callee: the arguments are already in place.
• RETURN pops the frame, cuts the stack back to slots and pushes the result.
• Frames are data, so the VM can print a stack trace and choose its own depth limit.

Next: closures, and variables that must outlive their frame.