Writing a Programming Language From Scratch - Part 3

In the previous post on this series, we went over parsing let declarations (let <name> = <expr>) and wrapping expressions in statements. This set us up for extending our grammar further - in this part, we’ll add identifier expressions then compile our AST to bytecode and execute it in a stack VM.

Alright, let’s move on to adding our new AST node type, VarExpr:

/// ast.hpp

struct Expr {
    virtual ~Expr() = default;
};

struct VarExpr : Expr {
    std::string name;

    explicit VarExpr(std::string name) : name { std::move(name) } { }
};

struct Literal : Expr {
    ...
};

Here we go, nice and simple. VarExpr owns a std::string which refers to an identifier in the source code. Let’s parse this now, but where should we do it? Since it’s an expression, and we’re expecting the token Ident, it should be handled in parse_primary:

/// parser.hpp

Box<Expr> parse_primary() {
    switch (m_current.ty) {
        case TokenType::Ident: {
            
        }

        ...
    }
}

So right now we’re at an identifier, the current token holds the value we want, so let’s just take it and advance, and return a new VarExpr:

Box<Expr> parse_primary() {
    switch (m_current.ty) {
        case TokenType::Ident: {
            auto value = m_current.value;
            advance();

            return std::make_unique<VarExpr>(value);
        }

        ...
    }
}

Very simple right, we take the value from the Ident token and advance, and return a VarExpr. Alright let’s test this!

/// main.cpp

constexpr std::string format(const Expr* expr, const int indent = 0) {
    ...

    if (auto* var = dynamic_cast<const VarExpr*>(expr))
        return std::format("{}VarExpr({})\n", fmt, var->name);

    ...
}

int main() {
    Parser parser { "sum + 56" };

    for (const auto stmts = parser.parse(); auto& stmt : stmts) {
        if (auto* let = dynamic_cast<const LetDecl*>(stmt.get())) {
            std::println("LetDecl.name = {}", let->name);
            std::println("LetDecl.init = {}", format(let->init.get()));
        }

        if (auto* expr = dynamic_cast<const ExprStmt*>(stmt.get())) {
            std::println("{}", format(expr->expr.get()));
        }
    }
}

Here we go, you should expect the following output:

Binary(+)
  VarExpr(sum)
  Literal(56)

If you see this, that means we have identifiers being treated as expressions, and more importantly, references to variables/bindings.

Bytecode

What is bytecode? Traditionally, it’s a compact, platform-independent instruction set designed to be processed and executed by a VM rather than hardware. If we were to interpret the AST directly, this would result in a slow evaluator. Bytecode VMs are closer to how real languages like Python and Lua are implemented.

The VM we will be implementing is stack-based, meaning operands are pushed onto a stack and popped from it, instructions operate on them.

The opcodes we need are the following:

Push, pushes a constant onto the stack.
Add, Sub, Mul, Div, each pops two values from the stack, and pushes the result.
Load, push a value of a variable onto the stack.
Store, pop a value and store it under a variable name.

/// opcode.hpp
#pragma once

#include <cstdint>

enum class Opcode : uint8_t {
    Push,
    Load,
    Store,
    Add,
    Sub,
    Mul,
    Div,
};

Great, we have a nice enum of all the instructions we covered, we’ll extend this as our language grows. So now we should think of how we could hold our bytecode, I like the sound of Block; a structure which owns the instruction stream and constants pool.

Because instructions are single bytes (uint8_t), we can’t fit a 64-bit integer, so we should store them in a pool of integers, that’s what the constant pool is for - 56 is a constant. Additionally, the Push instruction would carry an index which points to the integer in the constant pool, Push 0 means “push constants[0] onto the stack”.

Okay, let’s define our Block structure:

/// block.hpp

#pragma once

#include "opcode.hpp"
#include <vector>
#include <cstdint>

struct Block {
    std::vector<uint8_t> bytecode;
    std::vector<int64_t> constants;
};

Clean. I think we’re ready to move onto the compiler. The idea is that we walk our generated AST from the parser, and emit opcodes into a Block. We also need the compiler to own a symbol table, this will map our variable names to their indices, this is important for the instructions Load and Store. Let’s get started.

/// compiler.hpp

#pragma once

#include "block.hpp"
#include "ast.hpp"
#include <string>
#include <unordered_map>

class Compiler {
public:
    Block compile(const std::vector<Box<Stmt>>& stmts);
private:
    std::unordered_map<std::string, uint8_t> m_symbols;
    Block                                    m_block;

    void compile_stmt(const Stmt* stmt);
    void compile_expr(const Expr* expr);
};

This looks great, we can start walking the AST and emitting the appropriate opcodes. First let’s fill in compile, it’s simple; iterate over stmts, call compile_stmt and push the result into the block’s bytecode vector, and return the block.

/// compiler.hpp

Block compile(const std::vector<Box<Stmt>>& stmts) {
    for (const auto& stmt : stmts)
        compile_stmt(stmt.get());
    
    return m_block;
}

We should now implement compile_expr as compile_stmt would use it. Let’s think of this first, for a Literal it’s simple, we’ll create an index from the size of m_block.constants, we’ll then push lit->value onto m_block.constants, and then push Opcode::Push and index onto m_block.bytecode. Let’s create a few helper methods to make this easier, and nicer to read:

void emit(const uint8_t val) {
    m_block.bytecode.push_back(val);
}

void emit(const Opcode opcode) {
    m_block.bytecode.push_back(static_cast<uint8_t>(opcode));
}

uint8_t emit_constant(const int64_t constant) {
    const auto idx = static_cast<uint8_t>(m_block.constants.size());
    m_block.constants.push_back(constant);
    return idx;
}

Beautiful, now let’s implement compile_expr, the first expression we’ll compile is Literal:

void compile_expr(const Expr* expr) {
    if (auto* lit = dynamic_cast<const Literal*>(expr)) {
        const auto idx = emit_constant(lit->value);
        emit(Opcode::Push);
        emit(idx);
    }
}

Simple isn’t it, we push the literal’s value to the constant pool, we grab the index, emit Push and then emit the index of the constant. We can now move onto the other expressions:

void compile_expr(const Expr* expr) {
    if (auto* lit = dynamic_cast<const Literal*>(expr)) {
        const auto idx = emit_constant(lit->value);
        emit(Opcode::Push);
        emit(idx);
    }

    if (auto* var = dynamic_cast<const VarExpr*>(expr)) {
        emit(Opcode::Load);
        emit(m_symbols.at(var->name));
    }

    if (auto* bin = dynamic_cast<const BinaryExpr*>(expr)) {
        compile_expr(bin->lhs.get());
        compile_expr(bin->rhs.get());

        switch (bin->op) {
            case BinaryOp::Add: emit(Opcode::Add); break;
            case BinaryOp::Sub: emit(Opcode::Sub); break;
            case BinaryOp::Mul: emit(Opcode::Mul); break;
            case BinaryOp::Div: emit(Opcode::Div); break;
        }
    }
}

For VarExpr, we grab the index of var->name, it’s that simple. And BinaryExpr shows the beauty of this approach, we recursively call compile_expr for lhs and rhs, and switch on the BinaryOp and emit the correct instruction, it’s just so beautiful.

And compile_stmt is identical, just matching on the statement nodes we have:

uint8_t emit_symbol(const std::string& sym) {
    const auto idx = static_cast<uint8_t>(m_symbols.size());
    m_symbols[sym] = idx;

    return idx;
}

void compile_stmt(const Stmt* stmt) {
    if (auto* let = dynamic_cast<const LetDecl*>(stmt)) {
        compile_expr(let->init.get());

        const auto idx = emit_symbol(let->name);
        emit(Opcode::Store);
        emit(idx);
    }

    if (auto* expr = dynamic_cast<const ExprStmt*>(stmt)) {
        compile_expr(expr->expr.get());
    }
}

I also included another helper for adding symbols and retrieving the index. But yet again, it’s elegant. We should test our compiler, but we need to see some output which means something; so we’ll write a Block dumper:

/// block.hpp

...

#include <print>

...

inline void dump_block(const Block& block) {
    for (auto i { 0uz }; i < block.bytecode.size(); i++) {
        switch (const auto opcode = static_cast<Opcode>(block.bytecode[i])) {
            case Opcode::Push: {
                const auto idx = block.bytecode[++i];
                std::println("{:04d} | Push {}    @ idx {}", i - 1, block.constants[idx], idx);
                break;
            }

            case Opcode::Load:  std::println("{:04d} | Load  [{}]", i, block.bytecode[++i]); break;
            case Opcode::Store: std::println("{:04d} | Store [{}]", i, block.bytecode[++i]); break;
            case Opcode::Add:   std::println("{:04d} | Add", i); break;
            case Opcode::Sub:   std::println("{:04d} | Sub", i); break;
            case Opcode::Mul:   std::println("{:04d} | Mul", i); break;
            case Opcode::Div:   std::println("{:04d} | Div", i); break;
        }
    }
}

Very simple, just iterate over block.bytecode and cast the current position to Opcode and switch on it. Okay, now let’s write a simple program and see the compiled output!

/// main.cpp

...

#include "compiler.hpp"

...

int main() {
    Parser   parser { "1 + 2" };
    Compiler compiler;

    const auto block { compiler.compile(parser.parse()) };
    dump_block(block);
}

Run it and we should see the output:

0000 | push 1    @ idx 0
0002 | push 2    @ idx 1
0004 | Add

If you see this, you’ve successfully written a bytecode compiler! Our pipeline is almost complete, but let’s test it further:

int main() {
    Parser   parser { "let x = 56 * 23 x * 2" };
    Compiler compiler;

    const auto block { compiler.compile(parser.parse()) };
    dump_block(block);
}

Should output:

0000 | push 56    @ idx 0
0002 | push 23    @ idx 1
0004 | Mul
0006 | Store [0]
0008 | Load  [0]
0009 | push 2    @ idx 2
0011 | Mul

Beautiful. Now I think it’s time to design and implement our VM, I want to see some execution going on here. Alright, it’s stack-based so we need a stack for values, a store for variables, a reference to a Block to execute, an instruction pointer, and a run method with the FDE loop (fetch, decode, execute). So let’s get to writing:

/// vm.hpp
#pragma once

#include "opcode.hpp"
#include "block.hpp"

class VM {
public:
    int64_t run(Block& block) {
        
    }
private:
    std::vector<int64_t> m_values;
    std::vector<int64_t> m_variables;
    std::size_t          m_ip { };
    Block*               m_block { nullptr };
};

So this is good structure for our VM, run allows us to run any Block when we want, this allows for flexibility. But let’s implement run, it’s just a FDE loop but we should reset m_ip before running, and set m_block to &block:

int64_t run(Block& block) {
    m_block = &block;
    m_ip = 0;
}

Alright, let’s define the FDE loop:

int64_t run(Block& block) {
    m_block = &block;
    m_ip = 0;

    while (m_ip < m_block->bytecode.size()) {

    }
}

The first step is to fetch and decode the byte at m_ip, this is the opcode:

while (m_ip < m_block->bytecode.size()) {
    const auto opcode = static_cast<Opcode>(m_block->bytecode[m_ip++]);
}

Awesome, we can now switch on opcode since we casted it to Opcode, the first instruction we’ll handle is Push:

switch (opcode) {
    case Opcode::Push: {
        const auto idx = m_block->bytecode[m_ip++];
        m_values.push_back(m_block->constants[idx]);
        break;
    }
}

This looks great, but I feel like we could create some helpers to make this more readable and structured; define these in the private scope of the VM class:

void push(const int64_t value) {
    m_values.push_back(value);
}

int64_t pop() {
    const auto v = m_values.back();
    m_values.pop_back();
    return v;
}

void load(const uint8_t idx) {
    push(m_variables[idx]);
}

void store(const uint8_t idx) {
    if (m_variables.size() <= idx) m_variables.resize(idx + 1);
    m_variables[idx] = pop();
}

These will help a ton, now our FDE loop looks even better, let’s implement the other opcodes:

while (m_ip < m_block->bytecode.size()) {
    const auto opcode = static_cast<Opcode>(m_block->bytecode[m_ip++]);

    switch (opcode) {
        case Opcode::Push:    push(m_block->constants[m_block->bytecode[m_ip++]]); break;
        case Opcode::Load:    load(m_block->bytecode[m_ip++]); break;
        case Opcode::Store:   store(m_block->bytecode[m_ip++]); break;
        case Opcode::Add:   { const auto b = pop(); m_values.back() += b; break; }
        case Opcode::Sub:   { const auto b = pop(); m_values.back() -= b; break; }
        case Opcode::Mul:   { const auto b = pop(); m_values.back() *= b; break; }
        case Opcode::Div:   { const auto b = pop(); m_values.back() /= b; break; }
    }
}

And run can return the top of the stack, so simple:

    return m_values.back();
}

Okay let’s test! Write this in your entry point to your program:

/// main.cpp

int main() {
    Parser   parser { "let x = 24 * 24 x / 2" };
    Compiler compiler;
    VM       vm;

    auto block { compiler.compile(parser.parse())};
    const auto result { vm.run(block) };
    std::println("{}", result);
}

You should see the output:

That’s it, we’ve successfully compiled our simple language into bytecode and ran it on our own stack-based VM!

What’s Next?

In the next post, we’ll implement the following:

Comparison operators
Booleans
if, else with jump opcodes

Bytecode#

What’s Next?#

Bytecode

What’s Next?