Building a stack-based virtual machine, part 7 - conditionals

#rust #language #theory #computerscience

In the last episode we learned all about how to make our stack machine handle function calls. A pretty handy language feature, if I do say so. Today we're going to learn how to model conditionals. If you've been following along at home then you may have already figured this out for yourself, but in case you haven't let's walk through how it's done.

Note that we have all the infrastructure in place already to make conditionals work in our programs, it's all down to making new instructions that can optionally perform jumps.

As with our previous example, we're going to need an operand type which can contain either integers or strings so that we can find the appropriate labels to jump to.

enum Operand {
    I(i64),
    S(String),
}

impl Operand {
    fn to_i(&self) -> Option<i64> {
        match self {
            &Operand::I(i) => Some(i),
            _ => None,
        }
    }

    fn to_s(&self) -> Option<&str> {
        match self {
            &Operand::S(ref s) => Some(s),
            _ => None,
        }
    }
}

impl From<i64> for Operand {
    fn from(i: i64) -> Self {
        Operand::I(i)
    }
}

impl<'a> From<&'a str> for Operand {
    fn from(s: &'a str) -> Self {
        Operand::S(s.to_string())
    }
}

Next we're going to need our standard push instruction:

fn push(machine: &mut Machine<Operand>, args: &[usize]) {
    let arg = machine.get_data(args[0]).clone();
    machine.operand_push(arg);
}

Next an unconditional jump. This instruction uses the machine's jump method to move the IP straight to the position identified by the label. Obviously you'd want to do more checking than what I'm doing here (does the label exist? what if the argument is an integer), but this is a blog so YOLO.

You could also change this to read the jump label or location off the stack. That'd be rad too.

fn jump(machine: &mut Machine<Operand>, args: &[usize]) {
    let label = machine.get_data(args[0]).clone();
    machine.jump(label.to_s().unwrap());
}

The last, and most magic piece is our new jump_if instruction.

This instruction pops the top operand off the stack and assumes it's an integer. If the integer is non-zero then it performs a jump to the specified label, otherwise it's a no-op and the machine just carries on with the next instruction.

fn jump_if(machine: &mut Machine<Operand>, args: &[usize]) {
    let condition = machine.operand_pop().to_i().unwrap();
    if condition != 0 {
        let label = machine.get_data(args[0]).clone();
        machine.jump(label.to_s().unwrap());
    }
}

Let's assemble our instruction table:

fn instruction_table() -> InstructionTable<Operand> {
    let mut it = InstructionTable::new();
    it.insert(Instruction::new(0, "push", 1, push));
    it.insert(Instruction::new(1, "jump_if", 1, jump_if));
    it.insert(Instruction::new(2, "jump", 1, jump));
    it
}

Next we can build a very simple program which pushes an operand onto the stack and if it's "true" then jumps to the "if_true" label, otherwise it jumps to the "end" label.

fn conditional_program(condition: Operand) -> Operand {
    let it = instruction_table();
    let mut builder: Builder<Operand> = Builder::new(&it);

    // Push our condition operand into the stack
    builder.push("push", vec![condition]);

    // Add our `jump_if` instruction and tell it to jump to the `if_true` label.
    builder.push("jump_if", vec![Operand::from("if_true")]);

    // These instructions will be skipped if the operand is true:
    // * Push "it was false" onto the stack.
    // * Unconditionally jump to the end of the program.
    builder.push("push", vec![Operand::from("it was false")]);
    builder.push("jump", vec![Operand::from("end")]);

    // This instruction will be skipped of the operand is false:
    // * Push "it was true" onto the stack.
    builder.label("if_true");
    builder.push("push", vec![Operand::from("it was true")]);

    // Points at the end of the program, which will cause the machine to halt.
    builder.label("end");

    // Run the program:
    let code = Code::from(builder);
    let constants: WriteManyTable<Operand> = WriteManyTable::new();
    let mut machine: Machine<Operand> = Machine::new(code, &constants, &it);
    machine.run();

    // Return the operand at the top of the stack to the caller:
    machine.operand_pop()
}

Now we can write our tests to prove that it works:

#[test]
fn condition_true() {
    let result = conditional_program(Operand::from(1));
    assert_eq!(result.to_s().unwrap(), "it was true")
}

#[test]
fn condition_false() {
    let result = conditional_program(Operand::from(0));
    assert_eq!(result.to_s().unwrap(), "it was false")
}

As you can see modeling conditionals is pretty straight forward, although you will likely have to keep track of a bunch of labels. You might have also noticed how you could model a switch statement where conditional clauses can fall through into the next clause.

This completes our whirlwind tour of how stack-based virtual machines work. I sure hope you've learned something. I encourage you to read the source and feel free to ask any questions you have. If I don't know the answer I'd sure like to find out.