Exploring Continuations and CPS Transformation

Introduction

Continuations are one of those ideas that seem abstract at first — but once they click, you’ll start seeing them everywhere: in asynchronous code, in exception handling, in generators, even in the way you reason about program flow.

In this post, we’ll explore what continuations are, how Continuation-Passing Style (CPS) transforms your code, and how these concepts are quietly powering modern async constructs like async/await.

We’ll walk through synchronous code, asynchronous patterns with callbacks and promises, and finally reach a new understanding of what’s really going on under the hood. You won’t need to reimplement a language or build a compiler to follow along — we’ll do everything with regular JavaScript, Python, and Rust.

What is a Continuation?

A continuation is a representation of “what to do next” in a program. At any point in your code, the rest of the computation can be thought of as a function — the continuation.

Let’s start simple:

function addOne(x) {
  return x + 1;
}

console.log(addOne(2)); // prints 3

Now, instead of returning, what if we passed the result to another function — the continuation?

function addOneCPS(x, cont) {
  cont(x + 1);
}

addOneCPS(2, (result) => {
  console.log(result); // prints 3
});

This style is called Continuation-Passing Style (CPS). In CPS, functions never return — they call their continuation instead.

This isn’t immediately remarkable. Callbacks have been used widely in code for quite some time now. This is just building a picture of where we’ve come from.

From Sync Code to CPS

Let’s expand our example to chain two operations:

function double(x) {
  return x * 2;
}

function addOne(x) {
  return x + 1;
}

console.log(addOne(double(5))); // 11

Now in CPS:

function doubleCPS(x, cont) {
  cont(x * 2);
}

function addOneCPS(x, cont) {
  cont(x + 1);
}

doubleCPS(5, (doubled) => {
  addOneCPS(doubled, (result) => {
    console.log(result); // 11
  });
});

We’ve restructured our program so that each step explicitly passes control to the next.

This may seem verbose, but it turns out to be extremely powerful — especially when dealing with asynchronous code.

CPS is Everywhere in JavaScript

Let’s look at an example from the Node.js world:

const fs = require("fs");

fs.readFile("data.txt", "utf8", (err, data) => {
  if (err) return console.error("Failed to read file:", err);
  processData(data, (result) => {
    console.log("Result:", result);
  });
});

This is literally CPS — instead of returning data, fs.readFile passes it to a callback.

What’s the callback? The continuation.

Promises: CPS with a Better API

JavaScript promises are built around the same idea, just cleaner:

fetch("/api/data")
  .then((res) => res.json())
  .then((data) => {
    console.log("Fetched:", data);
  })
  .catch((err) => {
    console.error("Error:", err);
  });

Every .then(fn) is passing the result to a new continuation function. But promises let us flatten the nesting and chain more cleanly.

async/await: The Illusion of Sync

Now the same thing with async/await:

async function loadData() {
  try {
    const res = await fetch("/api/data");
    const data = await res.json();
    console.log("Fetched:", data);
  } catch (err) {
    console.error("Error:", err);
  }
}

But this isn’t “real” synchronous code — it just looks like it.

Behind the scenes, the JavaScript engine is:

• Splitting the function into pieces at each await
• Saving the continuation (the rest of the function) in a hidden state machine
• Resuming that continuation when the awaited promise resolves

That’s CPS at work.

Manual CPS in Other Languages

You don’t need a JavaScript engine to try this out. Let’s look at Rust and Python examples to see how CPS can be expressed in ordinary code.

Rust Example

fn double_cps(x: i32, cont: impl FnOnce(i32)) {
    cont(x * 2);
}

fn add_one_cps(x: i32, cont: impl FnOnce(i32)) {
    cont(x + 1);
}

fn main() {
    double_cps(5, |doubled| {
        add_one_cps(doubled, |result| {
            println!("Result: {}", result); // prints 11
        });
    });
}

Rust’s closures let us express continuations cleanly without needing async runtimes or macros.

Python Example

The same example can be implemented using python pretty simply.

def double_cps(x, cont):
    cont(x * 2)

def add_one_cps(x, cont):
    cont(x + 1)

double_cps(5, lambda doubled:
    add_one_cps(doubled, lambda result:
        print("Result:", result)
    )
)

Python’s lambdas work just like JavaScript’s arrow functions here. Every step is chained by explicitly passing the next operation as a continuation.

async/await in Python: CPS in the Runtime

Just like JavaScript, Python’s async def and await are built on top of generators and continuations:

import asyncio

async def get_data():
    await asyncio.sleep(1)
    return 42

async def main():
    value = await get_data()
    print("Got:", value)

asyncio.run(main())

Here, too, the interpreter:

• Splits your function at each await
• Stores the rest of the computation (continuation) to run later

Why Learn CPS?

Once you can see continuations, you start to understand:

• How async runtimes work
• How exception handling works (dual continuations!)
• How interpreters implement tail calls and coroutines
• How to reason about control flow in state machines

Bonus: Control Flow as a Tree

You can visualize your program’s control flow like a tree. Each continuation is a branch.

When you await, you’re pausing on one branch — and resuming it later.

Conclusion

Continuations and CPS transform how we think about execution.

They explain:

• Why callbacks exist
• How async/await works under the hood
• How control flow can be captured, resumed, or redirected

You don’t need to write a compiler to use CPS — just pass the “rest of your program” as a function.

By making the invisible visible, continuations give us precise control over what our code does next.

A Practical Guide to Compiler Phases

Introduction

Compilers often sound mysterious — full of dragons, jargon, and intimidating diagrams. But under the hood, they all follow the same basic blueprint.

In this post, we’ll walk through every major compiler phase by implementing them in Rust. We’ll start with a raw source string and end with real output — step by step — using this ultra-simple language:

let x = 1 + 2;

We’ll transform that line through tokenization, parsing, type checking, intermediate representation, optimization, and finally evaluation — all in plain Rust. Every phase will be practical, with real code you can run. By the end, you’ll have a minimal but complete compiler front-end — a solid foundation you can build on.

Here’s a high-level view of the journey:

Let’s dive in!

Lexical Analysis

Lexical analysis — also called tokenization or scanning — is the first phase of a compiler. It takes a stream of raw characters (your source code) and breaks it into tokens: the smallest meaningful units of the language.

Tokens include things like keywords (let), identifiers (x), operators (+), and literals (1, 2). Once tokenized, the compiler can start to reason about structure instead of individual characters.

In our example:

let x = 1 + 2;

The tokenizer will produce something like:

[Let, Identifier("x"), Equals, Integer(1), Plus, Integer(2), Semicolon]

So, we need to define our tokens:

#[derive(Debug, PartialEq)]
pub enum Token {
    Let,
    Identifier(String),
    Equals,
    Integer(i64),
    Plus,
    Semicolon,
}

Now we need to actually turn a string into a set of tokens.

pub fn tokenize(input: &str) -> Vec<Token> {
    let mut chars = input.chars().peekable();
    let mut tokens = Vec::new();

    while let Some(&ch) = chars.peek() {
        match ch {
            ' ' | '\n' | '\t' => {
                chars.next();
            }

            '=' => {
                chars.next();
                tokens.push(Token::Equals);
            }

            '+' => {
                chars.next();
                tokens.push(Token::Plus);
            }

            ';' => {
                chars.next();
                tokens.push(Token::Semicolon);
            }

            '0'..='9' => {
                let mut num = String::new();
                while let Some('0'..='9') = chars.peek() {
                    num.push(chars.next().unwrap());
                }
                let value = num.parse().unwrap();
                tokens.push(Token::Integer(value));
            }

            'a'..='z' | 'A'..='Z' | '_' => {
                let mut ident = String::new();
                while let Some(ch) = chars.peek() {
                    if ch.is_alphanumeric() || *ch == '_' {
                        ident.push(chars.next().unwrap());
                    } else {
                        break;
                    }
                }

                match ident.as_str() {
                    "let" => tokens.push(Token::Let),
                    _ => tokens.push(Token::Identifier(ident)),
                }
            }

            _ => panic!("Unexpected character: {}", ch),
        }
    }

    tokens
}

You can see here that there’s no real validation going on here. We’re just turning significant characters into tokens. The only piece of validation that does occur is if a character isn’t supported by the process, we’ll panic.

Parsing

Now that we have a stream of tokens, it’s time to make sense of them structurally. That’s the job of parsing — converting a flat list of tokens into a tree-like structure that represents the hierarchy and meaning of the code.

This structure is called an Abstract Syntax Tree (AST).

An AST is a simplified, structured representation of your source code that captures its grammatical structure — without worrying about superficial syntax details like commas, parentheses, or whitespace. It lets the compiler understand what the code means rather than just what it looks like.

Taking our simple example from above, we want to produce a tree that looks like this:

The parser turns our flat tokens into this rich structure — making it possible for later phases (like type checking and code generation) to analyze, transform, and ultimately execute the code.

The expressions that our parser will support can be a literal value, or it can be a binary operation. You’ll notice that the binary operation is also self-referencing Expr.

#[derive(Debug)]
pub enum Expr {
    Literal(i64),
    BinaryOp {
        left: Box<Expr>,
        op: char,
        right: Box<Expr>,
    },
}

#[derive(Debug)]
pub struct LetBinding {
    pub name: String,
    pub value: Expr,
}

The let binding is a type to bind our expression to a symbolic name.

Now we can take a list of tokens, and parse that out into a LetBinding:

pub fn parse(tokens: &[Token]) -> LetBinding {
    let mut pos = 0;

    fn expect_token(tokens: &[Token], pos: &mut usize, expected: &Token) {
        if &tokens[*pos] != expected {
            panic!("Expected {:?}, got {:?}", expected, tokens[*pos]);
        }
        *pos += 1;
    }

    expect_token(tokens, &mut pos, &Token::Let);

    let name = match &tokens[pos] {
        Token::Identifier(s) => {
            pos += 1;
            s.clone()
        }
        other => panic!("Expected identifier, got {:?}", other),
    };

    expect_token(tokens, &mut pos, &Token::Equals);

    let left = match &tokens[pos] {
        Token::Integer(n) => {
            pos += 1;
            Expr::Literal(*n)
        }
        _ => panic!("Expected integer"),
    };

    let op = match &tokens[pos] {
        Token::Plus => {
            pos += 1;
            '+'
        }
        _ => panic!("Expected '+'"),
    };

    let right = match &tokens[pos] {
        Token::Integer(n) => {
            pos += 1;
            Expr::Literal(*n)
        }
        _ => panic!("Expected integer"),
    };

    expect_token(tokens, &mut pos, &Token::Semicolon);

    LetBinding {
        name,
        value: Expr::BinaryOp {
            left: Box::new(left),
            op,
            right: Box::new(right),
        },
    }
}

Semantic Analysis

Once we have an Abstract Syntax Tree (AST), we know how the code is structured. But we still don’t know if the code makes sense.

That’s where semantic analysis comes in. This phase checks the meaning of the code — validating things like:

• Are all variables declared before they’re used?
• Are types used correctly?
• Can the operations actually be performed?

Even though let x = 1 + 2; is syntactically valid, we still need to ensure the types on both sides of + are compatible, and that x is a valid target for assignment.

Semantic analysis walks the AST and performs:

• Type checking (e.g., can you add these two things?)
• Scope resolution (e.g., is this variable declared?)
• Error reporting for violations (e.g., type mismatches)

We need to tell our compiler about types.

#[derive(Debug, PartialEq)]
enum Type {
    Int,
}

Now we can lean on the recursive nature of our Expr struct to process it recursively. Very simply, we only support one type: Int.

fn type_check(expr: &Expr) -> Result<Type, String> {
    match expr {
        Expr::Literal(_) => Ok(Type::Int),
        Expr::BinaryOp { left, right, .. } => {
            let lt = type_check(left)?;
            let rt = type_check(right)?;
            if lt == Type::Int && rt == Type::Int {
                Ok(Type::Int)
            } else {
                Err("Type mismatch".into())
            }
        }
    }
}

Intermediate Representation (IR)

At this point, we have code that’s both structurally valid (parsed into an AST) and semantically correct (passes type checking). Now it’s time to lower that code into something simpler and easier to manipulate: an Intermediate Representation, or IR.

Think of IR as the “compiler’s private language” — a stripped-down version of your program that’s:

• Easier to optimize
• Easier to analyze
• Easier to transform into real machine instructions

In real-world compilers, IR might take the form of:

• LLVM IR: used by Rust itself
• MIR: Rust’s internal mid-level representation
• Bytecode: as used by interpreters like Java

In our toy compiler, we’ll build a stack-based IR — a sequence of simple instructions like:

LoadConst 1
LoadConst 2
Add
Store x

These IR instructions are:

• Flat (no nesting like ASTs)
• Uniform (each step is explicit)
• Machine-friendly (easy to interpret or compile)

This gives us a stable, minimal foundation for:

• Optimizations like constant folding
• Code generation for interpreters or assembly
• Debugging and instrumentation

We’ll now:

• Define an IR instruction set in Rust
• Walk the AST to emit IR
• Prepare for later phases like optimization and evaluation

This is the compiler’s bridge between high-level intent and low-level action.

We need a way to define our IR:

#[derive(Debug)]
pub enum IR {
    LoadConst(i64),
    Add,
    Store(String),
}

Now we can generate IR from our LetBinding:

pub fn generate_ir(binding: &LetBinding) -> Vec<IR> {
    let mut ir = Vec::new();

    match &binding.value {
        Expr::BinaryOp { left, right, op } => {
            if let Expr::Literal(l) = **left {
                ir.push(IR::LoadConst(l));
            }
            if let Expr::Literal(r) = **right {
                ir.push(IR::LoadConst(r));
            }

            if *op == '+' {
                ir.push(IR::Add);
            }
        }
        _ => panic!("Unsupported expression"),
    }

    ir.push(IR::Store(binding.name.clone()));
    ir
}

Optimization

Once we have our Intermediate Representation (IR), we can start to improve it.

That’s what the optimization phase is all about — rewriting the IR to make it:

• Faster to run
• Simpler to execute
• More efficient in terms of operations

Crucially, optimizations don’t change the meaning of the program. They just make it better.

In our toy compiler, we’ll implement a classic example: constant folding. This is when the compiler evaluates constant expressions ahead of time.

Instead of this:

LoadConst 1
LoadConst 2
Add
Store x

We generate this:

LoadConst 3
Store x

That means less work at runtime — and it’s a stepping stone to more advanced techniques like dead code elimination, common subexpression elimination, or register allocation.

Even in small compilers, optimization is important because:

• It reduces unnecessary instructions
• It prepares the IR for efficient code generation
• It gives you experience with real-world compiler passes

In this section, we’ll:

• Walk through our IR instructions
• Detect simple constant patterns
• Replace them with pre-computed values

The logic will be basic — but the mechanism will mirror what real compilers do at massive scale.

pub fn optimize(ir: &[IR]) -> Vec<IR> {
    if let [IR::LoadConst(a), IR::LoadConst(b), IR::Add, IR::Store(name)] = &ir[..] {
        vec![
            IR::LoadConst(a + b),
            IR::Store(name.clone()),
        ]
    } else {
        ir.to_vec()
    }
}

Code Generation / Evaluation

Rather than generating x86 assembly, let’s just interpret the IR.

use std::collections::HashMap;

pub fn run(ir: &[IR]) {
    let mut stack = Vec::new();
    let mut vars = HashMap::new();

    for instr in ir {
        match instr {
            IR::LoadConst(n) => stack.push(*n),
            IR::Add => {
                let b = stack.pop().unwrap();
                let a = stack.pop().unwrap();
                stack.push(a + b);
            }
            IR::Store(name) => {
                let val = stack.pop().unwrap();
                vars.insert(name.clone(), val);
                println!("{} = {}", name, val);
            }
        }
    }
}

Putting it all together

Now we can use each of these functions in a pretty neat sequence:

fn main() {
    let source = "let x = 1 + 2;";
    let tokens = tokenize(source);
    let parsed = parse(&tokens);
    let _ = type_check(&parsed.value).expect("Type error");
    let ir = generate_ir(&parsed);
    let opt_ir = optimize(&ir);
    run(&opt_ir);
}

Output:

x = 3

Summary

Well, that’s the basics of the internals of a compiler!

We’ve built the start of something here that could be built upon with new pieces at every step.

Tagged Unions

Introduction

In a previous post, we built a dynamic variant type in C that could safely hold integers, floats, strings, and arrays — all while tracking its current type.

That implementation used a simple, effective trick from the C toolbox: the tagged union.

But what is a tagged union, really? What does it look like in memory? How does it behave across different languages like Rust or Swift? And how can understanding this help you write better low-level code?

In this article, we’ll go deep into the mechanics of tagged unions — demystifying how they work, how they’re laid out in memory, and how other languages leverage this idea at a higher level.

What is a Tagged Union?

A tagged union is a structure that lets you store different types of data in the same memory space — but only one of them at a time.

It consists of two parts:

1. A tag (also called a discriminator or type id) — this tells you what kind of value the union currently holds.
2. A union — this is a single memory region that can represent multiple types, but only one is valid at any given time.

Together, they form a tagged union, also known as:

• Variant type (C++)
• Discriminated union (TypeScript)
• Sum type (Haskell, Rust)
• enum with payloads (Rust, Swift, F#)

A Simple C Implementation

Let’s take a minimal version of the ced_var_t type we saw earlier:

typedef enum {
    TYPE_INT32,
    TYPE_FLOAT,
    TYPE_STRING,
} value_type_t;

typedef struct {
    value_type_t type;

    union {
        int32_t   i32;
        float     f;
        char*     str;
    } data;
} tagged_value_t;

Here:

• type is the tag.
• data is the payload.

When you store a value, you must set both correctly:

tagged_value_t v;
v.type = TYPE_INT32;
v.data.i32 = 42;

When you want to read the value, you must check the tag first.

What Does This Look Like in Memory?

Let’s visualize what’s in memory for the above:

+--------+---------+------------------+
| tag    | padding | data             |
| (4B)   | (4B)    | (8B - union)     |
+--------+---------+------------------+

Because str is a char*, which is typically 8 bytes on 64-bit systems, the entire union needs to reserve 8 bytes. So the full struct is:

• 4 bytes for type (as “tag”)
• 4 bytes padding (for alignment)
• 8 bytes for union

Total: 16 bytes

Even if you’re only storing a small int32_t, the full memory block remains the same.

Why Is This Useful?

Tagged unions give you flexibility:

• Store different types dynamically
• Inspect and branch on their type at runtime
• Compact representation (compared to void* + metadata hacks)
• Zero-cost abstraction in low-level code

They’re great for interpreters, configuration systems, scripting languages, or anything where types can vary dynamically.

But It’s Also Dangerous

C won’t stop you from misusing the union:

v.type = TYPE_FLOAT;
v.data.i32 = 1234;  // Invalid — tag and payload don't match!

Accessing a union member that doesn’t match the tag is undefined behavior. It might work. Or it might crash. Or silently corrupt your data.

That’s why you must manage the tag manually, and treat it as the single source of truth.

How Rust Does It Better

In Rust, you’d write this as:

enum Value {
    Int32(i32),
    Float(f32),
    Str(String),
}

Rust does three major things better:

1. Enforces valid construction — you can’t create an invalid state.
2. Requires match exhaustiveness — you have to handle all cases.
3. Uses niche optimization — it can sometimes omit the tag entirely.

For example, Option<&T> takes no extra space. Rust uses the null pointer as the tag for None.

Comparison with Other Languages

Performance Considerations

Tagged unions are generally compact, but there are trade-offs:

• The size of the union is dictated by the largest member.
• On 64-bit platforms, alignment often causes padding (e.g., 4-byte tag + 4-byte pad + 8-byte payload).
• If a variant holds something heap-allocated (like strings), you may incur pointer-chasing and memory fragmentation.

You can use tools like sizeof(), offsetof(), or pahole to understand the exact layout.

Debugging Tips

If you’re building or debugging a tagged union system in C:

• Use assert() to guard tag-to-union access:

  assert(v->type == TYPE_INT32);
  

• Use valgrind to catch misuses or memory leaks.
• Inspect raw memory using gdb, hexdump, or print helpers.
• Consider printing the tag as a string to make logs easier to read.

Further Reading

• Rust enum layout documentation
• Valgrind
• pahole: show data structure layout

Understanding Pin-safe Types in Rust

Introduction

Rust is famous for giving you memory safety without a garbage collector. But when you start doing lower-level work — self-referential structs, async state machines, or FFI — you run into a powerful but mysterious feature: Pin.

In this article, we’ll answer the following:

• What does it mean for a type to be pin-safe?
• Why would a type need to be pinned in the first place?
• How do you build one safely — without fighting the borrow checker?

We’ll walk through simple examples first, then build up to a self-referential type.

What is a Pin-safe Type?

A pin-safe type is a type that can be safely used with Rust’s Pin API.

You create a Pin-safe type when:

• You need to guarantee that a value won’t move in memory after being created.
• You want to allow self-referencing inside a struct (e.g., a field pointing to another field).
• You’re building async state machines, generators, or intrusive data structures.

Self-Referential Structs: The Core Problem

Let’s look at a classic case. Say you have a struct like this:

struct Example {
    a: String,
    b: *const String, // b points to a
}

This is a self-referential struct: b stores a pointer to another field inside the same struct.

Seems harmless?

Here’s the catch: Rust moves values around freely — into function calls, collections, etc. If you set up a pointer inside a struct and then move the struct, your pointer is now invalid. This opens the door to use-after-free bugs.

Rust’s borrow checker normally prevents you from doing this. But sometimes you do need this — and that’s where Pin comes in.

Pin to the Rescue

This is perfect for self-referential types — it guarantees their memory address won’t change.

But you have to build your type carefully to uphold this contract.

A Pin-safe Self-Referential Type

Now let’s build a Pin-safe type step-by-step.

Step 1: Define the structure

use std::pin::Pin;
use std::marker::PhantomPinned;

struct SelfRef {
    data: String,
    data_ref: *const String, // raw pointer, not a safe Rust reference
    _pin: PhantomPinned,     // opt-out of Unpin
}

• data: holds some content.
• data_ref: stores a pointer to that data.
• PhantomPinned: tells Rust this type is not safe to move after being pinned.

Step 2: Pin and initialize

impl SelfRef {
    fn new(data: String) -> Pin<Box<SelfRef>> {
        let mut s = Box::pin(SelfRef {
            data,
            data_ref: std::ptr::null(),
            _pin: PhantomPinned,
        });

        let data_ref = &s.data as *const String;

        unsafe {
            let mut_ref = Pin::as_mut(&mut s);
            Pin::get_unchecked_mut(mut_ref).data_ref = data_ref;
        }

        s
    }

    fn get(&self) -> &String {
        unsafe { &*self.data_ref }
    }
}

Step 3: Use it

fn main() {
    let s = SelfRef::new("Hello, world!".into());
    println!("Data ref points to: {}", s.get());
}

Key Points

• You must pin the struct before setting the self-reference.
• Box::pin allocates it on the heap and returns a pinned pointer.
• PhantomPinned disables auto-Unpin so it can’t be accidentally moved.
• unsafe is required to set the internal pointer — you must guarantee it’s only done after pinning.

Summary Table

Conclusion

Most types in Rust are move-safe and don’t need Pin. But when you’re working with:

• self-referential structs,
• low-level async primitives,
• foreign function interfaces (FFI),

…you may need to reach for Pin.

A Pin-safe type is your promise to the compiler that “this won’t move again — and I’ve made sure everything inside is OK with that.”

Building a Stack-Based VM in Rust - Part 5

Introduction

In Part 4, we introduced named words and a dictionary that allowed our VM to call subroutines by name. But there was still one major gap:

We couldn’t write Forth-like code.

You still had to manually build vec![Instruction::Push(5), ...] in Rust. That changes now.

In this post, we’ll add a hand-rolled parser that understands simple Forth syntax — including word definitions like : square dup * ; — and emits instructions automatically.

By the end of this part, you’ll be able to write:

5 square : square dup * ;

And run it on your virtual machine with no hardcoded addresses or manual instruction building.

The Goal

Our parser will:

• Tokenize simple Forth input
• Track whether we’re inside a : definition
• Split instructions into main and definitions
• Insert a Halt after top-level code to prevent fall-through
• Track the correct addresses for word definitions
• Build a final list of instructions ready to run

Here’s the full updated code.

Parser Support

First of all, we define our Parser struct — this separates the parsing logic from the VM runtime.

struct Parser {
    main: Vec<Instruction>,
    definitions: Vec<Instruction>,
    dictionary: HashMap<String, usize>,
}

Here’s what each member does:

• main: Top-level code that runs first. This is where calls like 5 square are emitted.
• definitions: Instructions belonging to : word ... ; definitions.
• dictionary: A mapping of word names (like "square") to their starting address in the final instruction stream.

We initialize the parser with empty sections:

impl Parser {
    fn new() -> Self {
        Self {
            main: Vec::new(),
            definitions: Vec::new(),
            dictionary: HashMap::new(),
        }
    }
}

Token Parsing

The heart of the parser is the parse method. We split the input on whitespace and interpret each token in turn.

fn parse(&mut self, input: &str) {
    let mut tokens = input.split_whitespace().peekable();
    let mut defining: Option<String> = None;
    let mut buffer: Vec<Instruction> = Vec::new();

    while let Some(token) = tokens.next() {
        match token {
            ":" => {
                // Beginning of a word definition
                let name = tokens.next().expect("Expected word name after ':'");
                defining = Some(name.to_string());
                buffer.clear();
            }
            ";" => {
                // End of word definition
                if let Some(name) = defining.take() {
                    buffer.push(Instruction::Return);
                    let addr = self.main.len() + self.definitions.len() + 1; // +1 for HALT
                    self.dictionary.insert(name, addr);
                    self.definitions.extend(buffer.drain(..));
                } else {
                    panic!("Unexpected ';' outside of word definition");
                }
            }
            word => {
                // Otherwise, parse an instruction
                let instr = if let Ok(n) = word.parse::<i32>() {
                    Instruction::Push(n)
                } else {
                    match word {
                        "dup" => Instruction::Dup,
                        "drop" => Instruction::Drop,
                        "swap" => Instruction::Swap,
                        "over" => Instruction::Over,
                        "+" => Instruction::Add,
                        "*" => Instruction::Mul,
                        "depth" => Instruction::Depth,
                        _ => Instruction::CallWord(word.to_string()),
                    }
                };

                // Add to appropriate section
                if defining.is_some() {
                    buffer.push(instr);
                } else {
                    self.main.push(instr);
                }
            }
        }
    }
}

Breakdown of the cases:

• : begins a new named word definition.
• ; ends the definition, emits a Return, and stores the word’s starting address in the dictionary.
• A number becomes a Push(n) instruction.
• Built-in words like + and * become direct Instruction variants.
• Any unknown token is assumed to be a user-defined word, and gets translated to CallWord("name").

Finalizing the Program

Once parsing is complete, we combine the main program with definitions — separated by a Halt to ensure we don’t fall through.

fn finalize(self) -> (Vec<Instruction>, HashMap<String, usize>) {
    let mut instructions = self.main;
    instructions.push(Instruction::Halt); // Halts after main program
    instructions.extend(self.definitions);
    (instructions, self.dictionary)
}

Main Program

Our main() function now uses the parser to construct the program from a Forth-style string.

fn main() {
    let mut parser = Parser::new();
    parser.parse("5 square : square dup * ;");

    let (instructions, dictionary) = parser.finalize();

    for instr in &instructions {
        println!("{:?}", instr);
    }

    let mut vm = VM::new(instructions);
    vm.dictionary = dictionary;
    vm.run();

    println!("Final stack: {:?}", vm.stack); 
}

You should see the following output:

Push(5)
CallWord("square")
Halt
Dup
Mul
Return
Final stack: [25]

Conclusion

This was a big leap forward: we now parse and run real Forth-like programs, entirely from text.

The parser separates top-level code from definitions, calculates addresses correctly, inserts a Halt, and builds a dictionary of reusable named words.

We now have:

• A working VM
• An extensible instruction set
• Named words and subroutines
• A parser for Forth-style input

The code for this part can be found up on GitHub.