Jumping Back and Forth

The order that our mind imagines is like a net, or like a ladder, built to attain something. But afterward you must throw the ladder away, because you discover that, even if it was useful, it was meaningless.

Umberto Eco, The Name of the Rose

It’s taken a while to get here, but we’re finally ready to add control flow to our virtual machine. In the tree-walk interpreter we built for jlox, we implemented Lox’s control flow in terms of Java’s. To execute a Lox if statement, we used a Java if statement to run the chosen branch. That works, but isn’t entirely satisfying. By what magic does the JVM itself or a native CPU implement if statements? Now that we have our own bytecode VM to hack on, we can answer that.

When we talk about “control flow”, what are we referring to? By “flow” we mean the way execution moves through the text of the program. Almost like there is a little robot inside the computer wandering through our code, executing bits and pieces here and there. Flow is the path that robot takes, and by controlling the robot, we drive which pieces of code it executes.

In jlox, the robot’s locus of attention—the current bit of code—was implicit based on which AST nodes were stored in various Java variables and what Java code we were in the middle of running. In clox, it is much more explicit. The VM’s ip field stores the address of the current bytecode instruction. The value of that field is exactly “where we are” in the program.

Execution proceeds normally by incrementing the ip. But we can mutate that variable however we want to. In order to implement control flow, all that’s necessary is to change the ip in more interesting ways. The simplest control flow construct is an if statement with no else clause:

if (condition) print("condition was truthy");

The VM evaluates the bytecode for the condition expression. If the result is truthy, then it continues along and executes the print statement in the body. The interesting case is when the condition is falsey. When that happens, execution skips over the then branch and proceeds to the next statement.

To skip over a chunk of code, we simply set the ip field to the address of the bytecode instruction following that code. To conditionally skip over some code, we need an instruction that looks at the value on top of the stack. If it’s falsey, it adds a given offset to the ip to jump over a range of instructions. Otherwise, it does nothing and lets execution proceed to the next instruction as usual.

When we compile to bytecode, the explicit nested block structure of the code evaporates, leaving only a flat series of instructions behind. Lox is a structured programming language, but clox bytecode isn’t. The right—or wrong, depending on how you look at it—set of bytecode instructions could jump into the middle of a block, or from one scope into another.

The VM will happily execute that, even if the result leaves the stack in an unknown, inconsistent state. So even though the bytecode is unstructured, we’ll take care to ensure that our compiler only generates clean code that maintains the same structure and nesting that Lox itself does.

This is exactly how real CPUs behave. Even though we might program them using higher-level languages that mandate structured control flow, the compiler lowers that down to raw jumps. At the bottom, it turns out goto is the only real control flow.

Anyway, I didn’t mean to get all philosophical. The important bit is that if we have that one conditional jump instruction, that’s enough to implement Lox’s if statement, as long as it doesn’t have an else clause. So let’s go ahead and get started with that.

23 . 1If Statements

This many chapters in, you know the drill. Any new feature starts in the front end and works its way through the pipeline. An if statement is, well, a statement, so that’s where we hook it into the parser.

  if (match(TOKEN_PRINT)) {
    printStatement();

  } else if (match(TOKEN_IF)) {
    ifStatement();

  } else if (match(TOKEN_LEFT_BRACE)) {

When we see an if keyword, we hand off compilation to this function:

static void ifStatement() {
  consume(TOKEN_LEFT_PAREN, "Expect '(' after 'if'.");
  expression();
  consume(TOKEN_RIGHT_PAREN, "Expect ')' after condition."); 

  int thenJump = emitJump(OP_JUMP_IF_FALSE);
  statement();

  patchJump(thenJump);
}

First we compile the condition expression, bracketed by parentheses. At runtime, that will leave the condition value on top of the stack. We’ll use that to determine whether to execute the then branch or skip it.

Then we emit a new OP_JUMP_IF_FALSE instruction. It has an operand for how much to offset the ip—how many bytes of code to skip. If the condition is falsey, it adjusts the ip by that amount. Something like this:

But we have a problem. When we’re writing the OP_JUMP_IF_FALSE instruction’s operand, how do we know how far to jump? We haven’t compiled the then branch yet, so we don’t know how much bytecode it contains.

To fix that, we use a classic trick called backpatching. We emit the jump instruction first with a placeholder offset operand. We keep track of where that half-finished instruction is. Next, we compile the then body. Once that’s done, we know how far to jump. So we go back and replace that placeholder offset with the real one now that we can calculate it. Sort of like sewing a patch onto the existing fabric of the compiled code.

We encode this trick into two helper functions.

static int emitJump(uint8_t instruction) {
  emitByte(instruction);
  emitByte(0xff);
  emitByte(0xff);
  return currentChunk()->count - 2;
}

The first emits a bytecode instruction and writes a placeholder operand for the jump offset. We pass in the opcode as an argument because later we’ll have two different instructions that use this helper. We use two bytes for the jump offset operand. A 16-bit offset lets us jump over up to 65,535 bytes of code, which should be plenty for our needs.

The function returns the offset of the emitted instruction in the chunk. After compiling the then branch, we take that offset and pass it to this:

static void patchJump(int offset) {
  // -2 to adjust for the bytecode for the jump offset itself.
  int jump = currentChunk()->count - offset - 2;

  if (jump > UINT16_MAX) {
    error("Too much code to jump over.");
  }

  currentChunk()->code[offset] = (jump >> 8) & 0xff;
  currentChunk()->code[offset + 1] = jump & 0xff;
}

This goes back into the bytecode and replaces the operand at the given location with the calculated jump offset. We call patchJump() right before we emit the next instruction that we want the jump to land on, so it uses the current bytecode count to determine how far to jump. In the case of an if statement, that means right after we compile the then branch and before we compile the next statement.

That’s all we need at compile time. Let’s define the new instruction.

  OP_PRINT,

  OP_JUMP_IF_FALSE,

  OP_RETURN,

Over in the VM, we get it working like so:

        break;
      }

      case OP_JUMP_IF_FALSE: {
        uint16_t offset = READ_SHORT();
        if (isFalsey(peek(0))) vm.ip += offset;
        break;
      }

      case OP_RETURN: {

This is the first instruction we’ve added that takes a 16-bit operand. To read that from the chunk, we use a new macro.

#define READ_CONSTANT() (vm.chunk->constants.values[READ_BYTE()])

#define READ_SHORT() \
    (vm.ip += 2, (uint16_t)((vm.ip[-2] << 8) | vm.ip[-1]))

#define READ_STRING() AS_STRING(READ_CONSTANT())

It yanks the next two bytes from the chunk and builds a 16-bit unsigned integer out of them. As usual, we clean up our macro when we’re done with it.

#undef READ_BYTE

#undef READ_SHORT

#undef READ_CONSTANT

After reading the offset, we check the condition value on top of the stack. If it’s falsey, we apply this jump offset to the ip. Otherwise, we leave the ip alone and execution will automatically proceed to the next instruction following the jump instruction.

In the case where the condition is falsey, we don’t need to do any other work. We’ve offset the ip, so when the outer instruction dispatch loop turns again, it will pick up execution at that new instruction, past all of the code in the then branch.

Note that the jump instruction doesn’t pop the condition value off the stack. So we aren’t totally done here, since this leaves an extra value floating around on the stack. We’ll clean that up soon. Ignoring that for the moment, we do have a working if statement in Lox now, with only one little instruction required to support it at runtime in the VM.

23 . 1 . 1Else clauses

An if statement without support for else clauses is like Morticia Addams without Gomez. So, after we compile the then branch, we look for an else keyword. If we find one, we compile the else branch.

  patchJump(thenJump);

  if (match(TOKEN_ELSE)) statement();

}

When the condition is falsey, we’ll jump over the then branch. If there’s an else branch, the ip will land right at the beginning of its code. But that’s not enough, though. Here’s the flow that leads to:

If the condition is truthy, we execute the then branch like we want. But after that, execution rolls right on through into the else branch. Oops! When the condition is true, after we run the then branch, we need to jump over the else branch. That way, in either case, we only execute a single branch, like this:

To implement that, we need another jump from the end of the then branch.

  statement();

  int elseJump = emitJump(OP_JUMP);

  patchJump(thenJump);

We patch that offset after the end of the else body.

  if (match(TOKEN_ELSE)) statement();

  patchJump(elseJump);

}

After executing the then branch, this jumps to the next statement after the else branch. Unlike the other jump, this jump is unconditional. We always take it, so we need another instruction that expresses that.

  OP_PRINT,

  OP_JUMP,

  OP_JUMP_IF_FALSE,

We interpret it like so:

        break;
      }

      case OP_JUMP: {
        uint16_t offset = READ_SHORT();
        vm.ip += offset;
        break;
      }

      case OP_JUMP_IF_FALSE: {

Nothing too surprising here—the only difference is that it doesn’t check a condition and always applies the offset.

We have then and else branches working now, so we’re close. The last bit is to clean up that condition value we left on the stack. Remember, each statement is required to have zero stack effect—after the statement is finished executing, the stack should be as tall as it was before.

We could have the OP_JUMP_IF_FALSE instruction pop the condition itself, but soon we’ll use that same instruction for the logical operators where we don’t want the condition popped. Instead, we’ll have the compiler emit a couple of explicit OP_POP instructions when compiling an if statement. We need to take care that every execution path through the generated code pops the condition.

When the condition is truthy, we pop it right before the code inside the then branch.

  int thenJump = emitJump(OP_JUMP_IF_FALSE);

  emitByte(OP_POP);

  statement();

Otherwise, we pop it at the beginning of the else branch.

  patchJump(thenJump);

  emitByte(OP_POP);

  if (match(TOKEN_ELSE)) statement();

This little instruction here also means that every if statement has an implicit else branch even if the user didn’t write an else clause. In the case where they left it off, all the branch does is discard the condition value.

The full correct flow looks like this:

If you trace through, you can see that it always executes a single branch and ensures the condition is popped first. All that remains is a little disassembler support.

      return simpleInstruction("OP_PRINT", offset);

    case OP_JUMP:
      return jumpInstruction("OP_JUMP", 1, chunk, offset);
    case OP_JUMP_IF_FALSE:
      return jumpInstruction("OP_JUMP_IF_FALSE", 1, chunk, offset);

    case OP_RETURN:

These two instructions have a new format with a 16-bit operand, so we add a new utility function to disassemble them.

static int jumpInstruction(const char* name, int sign,
                           Chunk* chunk, int offset) {
  uint16_t jump = (uint16_t)(chunk->code[offset + 1] << 8);
  jump |= chunk->code[offset + 2];
  printf("%-16s %4d -> %d\n", name, offset,
         offset + 3 + sign * jump);
  return offset + 3;
}

There we go, that’s one complete control flow construct. If this were an ’80s movie, the montage music would kick in and the rest of the control flow syntax would take care of itself. Alas, the ’80s are long over, so we’ll have to grind it out ourselves.

23 . 2Logical Operators

You probably remember this from jlox, but the logical operators and and or aren’t just another pair of binary operators like + and -. Because they short-circuit and may not evaluate their right operand depending on the value of the left one, they work more like control flow expressions.

They’re basically a little variation on an if statement with an else clause. The easiest way to explain them is to just show you the compiler code and the control flow it produces in the resulting bytecode. Starting with and, we hook it into the expression parsing table here:

  [TOKEN_NUMBER]        = {number,   NULL,   PREC_NONE},

  [TOKEN_AND]           = {NULL,     and_,   PREC_AND},

  [TOKEN_CLASS]         = {NULL,     NULL,   PREC_NONE},

That hands off to a new parser function.

static void and_(bool canAssign) {
  int endJump = emitJump(OP_JUMP_IF_FALSE);

  emitByte(OP_POP);
  parsePrecedence(PREC_AND);

  patchJump(endJump);
}

At the point this is called, the left-hand side expression has already been compiled. That means at runtime, its value will be on top of the stack. If that value is falsey, then we know the entire and must be false, so we skip the right operand and leave the left-hand side value as the result of the entire expression. Otherwise, we discard the left-hand value and evaluate the right operand which becomes the result of the whole and expression.

Those four lines of code right there produce exactly that. The flow looks like this:

Now you can see why OP_JUMP_IF_FALSE leaves the value on top of the stack. When the left-hand side of the and is falsey, that value sticks around to become the result of the entire expression.

23 . 2 . 1Logical or operator

The or operator is a little more complex. First we add it to the parse table.

  [TOKEN_NIL]           = {literal,  NULL,   PREC_NONE},

  [TOKEN_OR]            = {NULL,     or_,    PREC_OR},

  [TOKEN_PRINT]         = {NULL,     NULL,   PREC_NONE},

When that parser consumes an infix or token, it calls this:

static void or_(bool canAssign) {
  int elseJump = emitJump(OP_JUMP_IF_FALSE);
  int endJump = emitJump(OP_JUMP);

  patchJump(elseJump);
  emitByte(OP_POP);

  parsePrecedence(PREC_OR);
  patchJump(endJump);
}

In an or expression, if the left-hand side is truthy, then we skip over the right operand. Thus we need to jump when a value is truthy. We could add a separate instruction, but just to show how our compiler is free to map the language’s semantics to whatever instruction sequence it wants, I implemented it in terms of the jump instructions we already have.

When the left-hand side is falsey, it does a tiny jump over the next statement. That statement is an unconditional jump over the code for the right operand. This little dance effectively does a jump when the value is truthy. The flow looks like this:

If I’m honest with you, this isn’t the best way to do this. There are more instructions to dispatch and more overhead. There’s no good reason why or should be slower than and. But it is kind of fun to see that it’s possible to implement both operators without adding any new instructions. Forgive me my indulgences.

OK, those are the three branching constructs in Lox. By that, I mean, these are the control flow features that only jump forward over code. Other languages often have some kind of multi-way branching statement like switch and maybe a conditional expression like ?:, but Lox keeps it simple.

23 . 3While Statements

That takes us to the looping statements, which jump backward so that code can be executed more than once. Lox only has two loop constructs, while and for. A while loop is (much) simpler, so we start the party there.

    ifStatement();

  } else if (match(TOKEN_WHILE)) {
    whileStatement();

  } else if (match(TOKEN_LEFT_BRACE)) {

When we reach a while token, we call:

static void whileStatement() {
  consume(TOKEN_LEFT_PAREN, "Expect '(' after 'while'.");
  expression();
  consume(TOKEN_RIGHT_PAREN, "Expect ')' after condition.");

  int exitJump = emitJump(OP_JUMP_IF_FALSE);
  emitByte(OP_POP);
  statement();

  patchJump(exitJump);
  emitByte(OP_POP);
}

Most of this mirrors if statements—we compile the condition expression, surrounded by mandatory parentheses. That’s followed by a jump instruction that skips over the subsequent body statement if the condition is falsey.

We patch the jump after compiling the body and take care to pop the condition value from the stack on either path. The only difference from an if statement is the loop. That looks like this:

  statement();

  emitLoop(loopStart);

  patchJump(exitJump);

After the body, we call this function to emit a “loop” instruction. That instruction needs to know how far back to jump. When jumping forward, we had to emit the instruction in two stages since we didn’t know how far we were going to jump until after we emitted the jump instruction. We don’t have that problem now. We’ve already compiled the point in code that we want to jump back to—it’s right before the condition expression.

All we need to do is capture that location as we compile it.

static void whileStatement() {

  int loopStart = currentChunk()->count;

  consume(TOKEN_LEFT_PAREN, "Expect '(' after 'while'.");

After executing the body of a while loop, we jump all the way back to before the condition. That way, we re-evaluate the condition expression on each iteration. We store the chunk’s current instruction count in loopStart to record the offset in the bytecode right before the condition expression we’re about to compile. Then we pass that into this helper function:

static void emitLoop(int loopStart) {
  emitByte(OP_LOOP);

  int offset = currentChunk()->count - loopStart + 2;
  if (offset > UINT16_MAX) error("Loop body too large.");

  emitByte((offset >> 8) & 0xff);
  emitByte(offset & 0xff);
}

It’s a bit like emitJump() and patchJump() combined. It emits a new loop instruction, which unconditionally jumps backwards by a given offset. Like the jump instructions, after that we have a 16-bit operand. We calculate the offset from the instruction we’re currently at to the loopStart point that we want to jump back to. The + 2 is to take into account the size of the OP_LOOP instruction’s own operands which we also need to jump over.

From the VM’s perspective, there really is no semantic difference between OP_LOOP and OP_JUMP. Both just add an offset to the ip. We could have used a single instruction for both and given it a signed offset operand. But I figured it was a little easier to sidestep the annoying bit twiddling required to manually pack a signed 16-bit integer into two bytes, and we’ve got the opcode space available, so why not use it?

The new instruction is here:

  OP_JUMP_IF_FALSE,

  OP_LOOP,

  OP_RETURN,

And in the VM, we implement it thusly:

      }

      case OP_LOOP: {
        uint16_t offset = READ_SHORT();
        vm.ip -= offset;
        break;
      }

      case OP_RETURN: {

The only difference from OP_JUMP is a subtraction instead of an addition. Disassembly is similar too.

      return jumpInstruction("OP_JUMP_IF_FALSE", 1, chunk, offset);

    case OP_LOOP:
      return jumpInstruction("OP_LOOP", -1, chunk, offset);

    case OP_RETURN:

That’s our while statement. It contains two jumps—a conditional forward one to escape the loop when the condition is not met, and an unconditional loop backward after we have executed the body. The flow looks like this:

23 . 4For Statements

The other looping statement in Lox is the venerable for loop, inherited from C. It’s got a lot more going on with it compared to a while loop. It has three clauses, all of which are optional:

• The initializer can be a variable declaration or an expression. It runs once at the beginning of the statement.

• The condition clause is an expression. Like in a while loop, we exit the loop when it evaluates to something falsey.

• The increment expression runs once at the end of each loop iteration.

In jlox, the parser desugared a for loop to a synthesized AST for a while loop with some extra stuff before it and at the end of the body. We’ll do something similar, though we won’t go through anything like an AST. Instead, our bytecode compiler will use the jump and loop instructions we already have.

We’ll work our way through the implementation a piece at a time, starting with the for keyword.

    printStatement();

  } else if (match(TOKEN_FOR)) {
    forStatement();

  } else if (match(TOKEN_IF)) {

It calls a helper function. If we only supported for loops with empty clauses like for (;;), then we could implement it like this:

static void forStatement() {
  consume(TOKEN_LEFT_PAREN, "Expect '(' after 'for'.");
  consume(TOKEN_SEMICOLON, "Expect ';'.");

  int loopStart = currentChunk()->count;
  consume(TOKEN_SEMICOLON, "Expect ';'.");
  consume(TOKEN_RIGHT_PAREN, "Expect ')' after for clauses.");

  statement();
  emitLoop(loopStart);
}

There’s a bunch of mandatory punctuation at the top. Then we compile the body. Like we did for while loops, we record the bytecode offset at the top of the body and emit a loop to jump back to that point after it. We’ve got a working implementation of infinite loops now.

23 . 4 . 1Initializer clause

Now we’ll add the first clause, the initializer. It executes only once, before the body, so compiling is straightforward.

  consume(TOKEN_LEFT_PAREN, "Expect '(' after 'for'.");

  if (match(TOKEN_SEMICOLON)) {
    // No initializer.
  } else if (match(TOKEN_VAR)) {
    varDeclaration();
  } else {
    expressionStatement();
  }

  int loopStart = currentChunk()->count;

The syntax is a little complex since we allow either a variable declaration or an expression. We use the presence of the var keyword to tell which we have. For the expression case, we call expressionStatement() instead of expression(). That looks for a semicolon, which we need here too, and also emits an OP_POP instruction to discard the value. We don’t want the initializer to leave anything on the stack.

If a for statement declares a variable, that variable should be scoped to the loop body. We ensure that by wrapping the whole statement in a scope.

static void forStatement() {

  beginScope();

  consume(TOKEN_LEFT_PAREN, "Expect '(' after 'for'.");

Then we close it at the end.

  emitLoop(loopStart);

  endScope();

}

23 . 4 . 2Condition clause

Next, is the condition expression that can be used to exit the loop.

  int loopStart = currentChunk()->count;

  int exitJump = -1;
  if (!match(TOKEN_SEMICOLON)) {
    expression();
    consume(TOKEN_SEMICOLON, "Expect ';' after loop condition.");

    // Jump out of the loop if the condition is false.
    exitJump = emitJump(OP_JUMP_IF_FALSE);
    emitByte(OP_POP); // Condition.
  }

  consume(TOKEN_RIGHT_PAREN, "Expect ')' after for clauses.");

Since the clause is optional, we need to see if it’s actually present. If the clause is omitted, the next token must be a semicolon, so we look for that to tell. If there isn’t a semicolon, there must be a condition expression.

In that case, we compile it. Then, just like with while, we emit a conditional jump that exits the loop if the condition is falsey. Since the jump leaves the value on the stack, we pop it before executing the body. That ensures we discard the value when the condition is true.

After the loop body, we need to patch that jump.

  emitLoop(loopStart);

  if (exitJump != -1) {
    patchJump(exitJump);
    emitByte(OP_POP); // Condition.
  }

  endScope();
}

We do this only when there is a condition clause. If there isn’t, there’s no jump to patch and no condition value on the stack to pop.

23 . 4 . 3Increment clause

I’ve saved the best for last, the increment clause. It’s pretty convoluted. It appears textually before the body, but executes after it. If we parsed to an AST and generated code in a separate pass, we could simply traverse into and compile the for statement AST’s body field before its increment clause.

Unfortunately, we can’t compile the increment clause later, since our compiler only makes a single pass over the code. Instead, we’ll jump over the increment, run the body, jump back up to the increment, run it, and then go to the next iteration.

I know, a little weird, but hey, it beats manually managing ASTs in memory in C, right? Here’s the code:

  }

  if (!match(TOKEN_RIGHT_PAREN)) {
    int bodyJump = emitJump(OP_JUMP);
    int incrementStart = currentChunk()->count;
    expression();
    emitByte(OP_POP);
    consume(TOKEN_RIGHT_PAREN, "Expect ')' after for clauses.");

    emitLoop(loopStart);
    loopStart = incrementStart;
    patchJump(bodyJump);
  }

  statement();

Again, it’s optional. Since this is the last clause, when omitted, the next token will be the closing parenthesis. When an increment is present, we need to compile it now, but it shouldn’t execute yet. So, first, we emit an unconditional jump that hops over the increment clause’s code to the body of the loop.

Next, we compile the increment expression itself. This is usually an assignment. Whatever it is, we only execute it for its side effect, so we also emit a pop to discard its value.

The last part is a little tricky. First, we emit a loop instruction. This is the main loop that takes us back to the top of the for loop—right before the condition expression if there is one. That loop happens right after the increment, since the increment executes at the end of each loop iteration.

Then we change loopStart to point to the offset where the increment expression begins. Later, when we emit the loop instruction after the body statement, this will cause it to jump up to the increment expression instead of the top of the loop like it does when there is no increment. This is how we weave the increment in to run after the body.

It’s convoluted, but it all works out. A complete loop with all the clauses compiles to a flow like this:

As with implementing for loops in jlox, we didn’t need to touch the runtime. It all gets compiled down to primitive control flow operations the VM already supports. In this chapter, we’ve taken a big leap forward—clox is now Turing complete. We’ve also covered quite a bit of new syntax: three statements and two expression forms. Even so, it only took three new simple instructions. That’s a pretty good effort-to-reward ratio for the architecture of our VM.

// See if the matrix contains a zero.
bool found = false;
for (int x = 0; x < xSize; x++) {
  for (int y = 0; y < ySize; y++) {
    for (int z = 0; z < zSize; z++) {
      if (matrix[x][y][z] == 0) {
        printf("found");
        found = true;
        break;
      }
    }
    if (found) break;
  }
  if (found) break;
}

for (int x = 0; x < xSize; x++) {
  for (int y = 0; y < ySize; y++) {
    for (int z = 0; z < zSize; z++) {
      if (matrix[x][y][z] == 0) {
        printf("found");
        goto done;
      }
    }
  }
}
done: