N.I.S.S.E. Virtual Machine Tutorial

A step-by-step guide to building a BEAM-like virtual machine in JavaScript, based on The BEAM Book by Erik Stenman.

Tutorial Steps

Step 1: Memory & Tagging

File: 01-memory.js

Implements tagged memory representation using a 2-bit tagging scheme:

• TAG_INT (00): Immediate integers
• TAG_ATOM (01): Symbols from atom table
• TAG_BOXED (10): Pointers to heap-allocated structures (tuples)
• TAG_LIST (11): Pointers to cons cells (lists)

Run:

node 01-memory.js

Concepts: Memory allocation, heap pointer, tagged pointers, immediate values vs boxed values

Step 2: Pattern Matching

File: 02-pattern-matching.js

Implements unification over tagged 32-bit words:

• Variable binding
• Deep structural matching for tuples and lists
• Fast path for immediate values

Run:

node 02-pattern-matching.js

Concepts: Unification, pattern matching, environment binding, structural recursion

Step 3: Process Control Block

File: 03-process.js

Implements the Process Control Block (PCB) with:

• X Registers: 32 temporary registers for arguments and return values
• Stack: Return addresses and local variables
• Heap: Private per-process memory (256 words, expandable)
• Mailbox: Message queue for inter-process communication
• Reductions: Execution budget for fair scheduling

Run:

node 03-process.js

Concepts: Process isolation, private heaps, garbage collection, register machines

Step 4: The Scheduler

File: 04-scheduler.js

Implements the preemptive scheduler:

• Process Table: Global registry of all processes
• Run Queue: FIFO queue for runnable processes
• Code Server: Shared bytecode storage
• Time slicing: 20 reductions per quantum
• Context switching: Fair CPU allocation

Run:

timeout 2s node 04-scheduler.js

Concepts: Preemptive scheduling, round-robin, context switching, process states

Step 5: Instruction Set Architecture

File: 05-isa.js

Implements the BEAM-like instruction set:

• move: Copy values between registers and stack
• allocate/deallocate: Stack frame management
• call_ext: Built-in function calls (BIFs)
• return: Pop return address
• test_heap: Trigger GC if needed

Includes a simple assembler that parses text assembly into bytecode.

Run:

node 05-isa.js

Concepts: Register machines, operand types, assembler, BIFs, stack frames

Step 6: The Integrated VM

File: 06-vm.js

Ties everything together into a complete virtual machine:

• Loader/Linker: Resolves labels to addresses
• Extended ISA: Jump instructions, message passing
• Full integration: All previous steps working together
• Concurrent execution: Multiple processes with scheduling

Run:

timeout 2s node 06-vm.js

Concepts: Linking, label resolution, complete VM architecture

Running All Tests

Execute the full test suite:

./run-tests.sh

Or run individual steps:

# Step 1: Memory
node 01-memory.js

# Step 2: Pattern Matching
node 02-pattern-matching.js

# Step 3: Process
node 03-process.js

# Step 4: Scheduler (ctrl+c to stop)
node 04-scheduler.js

# Step 5: ISA
node 05-isa.js

# Step 6: Integrated VM (ctrl+c to stop)
node 06-vm.js

Architecture Overview

┌─────────────────────────────────────────┐
│         Code Server (Scrolls)           │
│  ┌─────────┐  ┌─────────┐  ┌─────────┐ │
│  │ Module1 │  │ Module2 │  │ Module3 │ │
│  │Bytecode │  │Bytecode │  │Bytecode │ │
│  └─────────┘  └─────────┘  └─────────┘ │
└─────────────────────────────────────────┘
                  │
                  ▼
┌─────────────────────────────────────────┐
│           Scheduler (Village)           │
│  ┌───────────────────────────────────┐  │
│  │        Run Queue (FIFO)           │  │
│  │  [P1] → [P2] → [P3] → [P4]       │  │
│  └───────────────────────────────────┘  │
└─────────────────────────────────────────┘
                  │
    ┌─────────────┴─────────────┐
    ▼                           ▼
┌─────────┐                ┌─────────┐
│Process 1│                │Process 2│
├─────────┤                ├─────────┤
│ PC: 42  │                │ PC: 103 │
│ X0-X31  │                │ X0-X31  │
│ Stack   │                │ Stack   │
│ Heap    │                │ Heap    │
│ Mailbox │                │ Mailbox │
└─────────┘                └─────────┘

Key Concepts

Memory Isolation

Each process has its own heap. Messages are copied between process heaps for isolation.

Tagged Pointers

All values are 32-bit words. The bottom 2 bits indicate the type:

• 00: Integer
• 01: Atom
• 10: Boxed (pointer to heap)
• 11: List (pointer to cons cell)

Fair Scheduling

Processes run for a fixed number of reductions (function calls) before yielding to other processes. This prevents any single process from monopolizing the CPU.

Tail Call Optimization

Jump instructions don't consume stack space, allowing infinite recursion. They still cost 1 reduction for fair scheduling.

References

• The BEAM Book - Comprehensive BEAM VM internals
• BEAM Instruction Set
• Joe Armstrong's Thesis - Making reliable distributed systems

License

Educational purposes. Based on The BEAM Book and Erlang/OTP documentation.