40. Return and the call stack

A way out from deep inside

Drip functions can do work but can’t hand back an answer. They need return. Here is a function that finds the first number whose square is bigger than a limit:

fn find(limit) {
  let i = 0;
  while (true) {
    if (i * i > limit) return i;
    i = i + 1;
  }
}
print find(50); // 8

Think about where the interpreter is when it reaches return i. It is not in one place. It is inside a whole pile of its own TypeScript calls:

executeFunctionBody   the call of find
  executeBlock        find's body
    execute(while)
      execute(block)  the loop body
        executeBlock
          execute(if)
            execute(return)

Each of these is a TypeScript function in the middle of its own work. execute(while) is half-way round a while loop that, on its own, would go round forever. return has to abandon all of them at once and land back at the call, carrying i.

Two ways out

The note-passing way is possible. execute could return a value meaning “a return is happening”, and every caller would have to check it: the while loop, the block loop, the if. Forget the check in one place and return stops working there.

The fire-alarm way is an exception. Chapter 11 showed that a throw abandons every frame between it and the nearest matching catch. That is exactly the shape of return, so the companion’s interpreter.ts throws:

class ReturnSignal {
  constructor(readonly value: Value) {}
}

// in execute:
case 'return':
  throw new ReturnSignal(s.value
    ? this.evaluate(s.value) : null);

return; with no value, or falling off the end of the body, both give nil. ReturnSignal is a plain class, not an Error. It isn’t an error, and nothing needs a message from it. The catch sits at the edge of every function call:

executeFunctionBody(decl, env) {
  try {
    this.executeBlock(decl.body, env);
  } catch (e) {
    if (e instanceof ReturnSignal) {
      return e.value;
    }
    throw e;
  }
  return null;
}

Only a ReturnSignal is caught. A real RuntimeError is thrown on again with throw e, so it keeps travelling to the top and is reported.

Remember the finally in executeBlock, from chapter 37? This is its everyday job. Every block that the signal passes through switches the current environment back as it goes, so when the call ends, the caller is back in its own environment.

Watching it in a recursive call

In fib, every call returns, and most calls make two more calls first. Step through fib(3). Each Drip call is drawn with the host frames it adds; the ReturnSignal is drawn in red as it passes through them:

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

Each signal travels only as far as its own call’s catch. fib(3) never sees the throws inside fib(2): to it, fib(2) simply returned 1.

Borrowing TypeScript’s call stack

Look again at the step-through. Drip has a call stack: fib(3) waiting for fib(2) waiting for fib(1). But the interpreter never built one. There’s no array of Drip frames anywhere in interpreter.ts. Each Drip call is a chain of TypeScript calls (evaluate, call, executeFunctionBody, executeBlock, execute), so Drip’s stack is part of TypeScript’s stack. “Where do I go back to?” and “what was I in the middle of?” are answered by TypeScript’s frames. The Drip variables live separately, in Environment objects on the heap.

That’s a great bargain for very little code. Recursion, mutual recursion and calls nested inside arguments all work for free. But three costs come with it.

Depth. Every Drip call level costs several host frames. In the step-through, three Drip calls already put twenty of the interpreter’s methods on the host stack: about six per level. So Drip runs out of stack long before an equivalent TypeScript program would. When the host stack is full, JavaScript throws a RangeError^[2]. drip.ts catches that and reports it in Drip’s terms:

if (e instanceof RangeError) {
  stderr.push('Stack overflow.',
    '[line 0]');
  return { stdout, stderr,
           exitCode: 70 };
}

fn down(n) {
  return down(n + 1);
}

print "going down";
down(0);
print "never printed";

Visibility. Drip can’t look at its own stack, because the stack isn’t Drip data: it’s buried in the host’s frames. That makes features like pausing a Drip program, or listing its active calls in an error message, hard to add.

Speed. Each Drip call pays for several host calls, plus the Environment and its Map, plus a thrown object for every return.

Your turn

class Ret {
  constructor(value) {
    this.value = value;
  }
}

// Runs one statement. Given: don't
// change it.
function exec(s, log) {
  switch (s.kind) {
    case 'log':
      log.push(s.text);
      return;
    case 'block':
      for (const t of s.body) {
        exec(t, log);
      }
      return;
    case 'return':
      throw new Ret(s.value);
    default:
      throw new Error('bad: ' + s.kind);
  }
}

function callFn(body, log) {
  // your code here
}

fn pow(b, e) {
  // your code here
}

print pow(2, 10);
print pow(3, 4);
print pow(5, 0);

What you learned

• return can sit deep inside loops, blocks and ifs, and must leave them all in one move: return unwinding.
• Drip throws a ReturnSignal holding the value, and executeFunctionBody catches it, returns the value, and rethrows anything else. executeBlock’s finally restores environments on the way out. No return means nil.
• The tree-walker reuses the host stack: each Drip call is a chain of TypeScript calls, so Drip’s call stack lives inside TypeScript’s.
• That is simple and makes recursion free, but it limits depth (a deep Drip recursion becomes a host RangeError), hides the stack from the interpreter, and costs speed. The VM will keep its own frames.

Next: closures in Drip, and environments that outlive the call that made them.