toy_vm — Binary Tree Heap VM with Garbage Collection

A small compiler and virtual machine for managing a heap of binary trees, paired with three garbage collector implementations: mark-sweep, mark-compact, and copy collection. The project includes a custom assembly-like language, a test suite for each GC strategy, and a Makefile-driven build system.

---

Project Structure

.
├── src/
│   ├── ...         # VM, compiler, heap, and GC source files
│   └── Makefile
├── test/
│   ├── Makefile
│   ├── test_mark_sweep
│   ├── test_mark_compact
│   └── test_copy_collection
└── README.md

---

Building and Running

Build

From the src/ directory:

make

This produces the toy_vm executable.

Run

./toy_vm <filename>

where <filename> is a program file in the format described below. An example file, test.toy is provided with the code in the assignment description.

---

Program File Format

A program file consists of two parts: a header line and a body of assembly-like instructions.

Header Line

The first line of the file must specify four space-separated values:

<insert_delete_threshold> <num_roots> <stack_size> <gc_name>

Field	Description
insert_delete_threshold	Threshold that decides between insert/delete operations on the binary trees
num_roots	Number of root pointers maintained by the VM
stack_size	Size of the operand stack
gc_name	Garbage collector to use (see options below)

Available garbage collectors:

Name	Strategy
mark_sweep_gc	Mark-and-sweep
mark_compact_gc	Mark-and-compact
copy_collection_gc	Semi-space copying collection

Body

The remaining lines contain instructions in an assembly-like language. Labels are defined with a trailing colon (__label:) and referenced without it.

Example Program

80 20 1024 mark_sweep_gc
  llp 100
__loop:
  rnd 20
  sel
  rnd 100
  blt __add
  del
  j __end
__add:
  add
__end:
  jlp __loop
  quit

This program uses a 1024-slot stack, 20 roots, a threshold of 80/20, and the mark-sweep collector. It loops for 100 iterations, randomly adding nodes to or deleting nodes from the heap, jumping between labelled sections based on a random condition.

---

Instruction Reference

Instruction	Description
llp <n>	Loads loop-counter with n
rnd <n>	Generates integer up to n, stores it in Stack[top]
sel	Generates integer up to roots-size, stores it in Stack[top]
add	Adds integer Stack[top-1] to tree Roots[Stack[top-2]]
del	Deletes integer Stack[top-1] from tree Roots[Stack[top-2]]
blt <label>	Jumps to <label> if Stack[top] < threshold
j <label>	Jumps to <label>
jlp <label>	Decrements loop-counter, jumps to label if not 0
quit	Prints the inorder traversal of all trees and exits the program

---

Running the Test Suite

Tests live in the test/ directory and have their own Makefile.

Build the tests

cd test/
make

Run individual GC test suites

./test_mark_sweep
./test_mark_compact
./test_copy_collection

Each script exercises the corresponding garbage collector across a set of programs and reports pass/fail results.