Designing a Stack-Based VM in Rust: 44 Instructions, Dual Backends, and Zero-Cost Security Types

Miron Tuteyshi — Sat, 15 Aug 2026 02:58:14 +0000

Designing a Stack-Based VM in Rust: 44 Instructions, Dual Backends, and Zero-Cost Security Types

A deep dive into the architecture of Metalogos — how 30,500 lines of Rust implement a language where XSS and SQL injection are compile-time errors, and why two execution backends crosscheck every program.

Introduction

Most programming languages treat security as an external concern — linters, SAST tools, code review. Metalogos takes a different approach: security constraints are enforced by the type system and erased before execution. This post explores the Rust implementation behind that idea, focusing on architectural decisions that are reusable beyond this specific language.

The codebase is ~30,500 lines of Rust, 91 Architecture Decision Records (ADRs), and two execution backends that must agree on every program's output. It is not a toy. It is not a DSL. It is a compiler, a bytecode VM, an HTTP server, a semantic memory engine, and a security audit tool — all in one workspace.

1. The Grammar as Contract

The parser is a Pest 2.7 PEG grammar: 384 lines, ~180 rules. This was the first component built, and it remained stable for 18 months while everything else changed underneath it.

Why PEG over LALR or a hand-written recursive descent parser? Two reasons:

Operator precedence is declarative. In Pest, ~ (sequence) and | (ordered choice) make precedence explicit without left-factoring boilerplate. Metalogos has custom syntax for fluid types (Float[42.0][0.9] or String["answer"][0.1]) and learnable patterns (learnable pattern Classify(msg: String) -> String). PEG handles this without a separate lexer stage.
The grammar is the spec. Every ADR that changes syntax starts with a grammar rule. If the grammar doesn't parse it, the feature doesn't exist. This eliminated an entire class of "parser drift" bugs where the AST and parser disagree.

The AST has 27 declaration variants, 14 expression types, 12 statement types, and 4 match arm patterns. All nodes use arena-friendly structures — mostly Box and Vec — with shared ownership via Rc where the semantic analyzer needs to reference the same node from multiple contexts.

2. Dual Backends: Correctness Through Disagreement

Metalogos has two execution backends with identical semantics:

Tree-walking interpreter (~4,400 LOC): Recursive evaluation of the AST. Full feature support, including all 246+ builtins.
Bytecode VM (44 instructions, ~2,100 LOC): Stack-based execution of compiled bytecode.

Every program runs through both. If the outputs differ, the test fails. This is not property-based testing. It is a structural guarantee that the compiler and interpreter implement the same semantics.

The 13 Parity Gaps

Recently, a systematic audit (Наряд №72) found 13 hidden divergence points between the interpreter and VM. These were not crashes — they were subtle semantic differences:

Rule priority sorting: the interpreter used stable sort, the VM evaluated rules in declaration order.
Collections flag propagation: the compiler tracked collections_loaded but never passed it to the VM's Program struct, so map/filter/reduce were silently unavailable in VM mode.
Lenient testing: VM mismatches were reported as "skipped" rather than failures, masking drift.

All 13 were fixed. ADR-0075 documents the crosscheck methodology: 58/58 test programs now pass with zero both-error cases — every match is a genuine both-success.

Why Two Backends?

The interpreter is the reference implementation. It is slow but obviously correct. The VM is the production target. It is faster (~3-5x) but complex. The crosscheck ensures that complexity does not introduce semantic bugs.

This pattern is reusable: any system with a reference implementation and an optimized implementation can use crosscheck validation. The cost is ~40% more implementation time. The benefit is confidence that unit tests cannot provide.

3. The VM: 44 Instructions and a Stack

The VM is intentionally minimal. One opcode per action. Everything non-primitive is a builtin call.

Instruction Categories

Constants and variables: Const, LoadGlobal, LoadGlobalByName, StoreGlobal, LoadLocal, StoreLocal.

Calls: CallBuiltin(arity, index), CallPattern(arity, index), Return.

Arithmetic and comparison: Add, Sub, Mul, Div, CmpGt, CmpLt, CmpGe, CmpLe, CmpEq, CmpNe.

Structs and lists: MakeStruct, GetField, IndexAccess, MakeList, ListLen.

Control flow: Jump, JumpIfNot, JumpIfLow(threshold, offset) — the last is unique to Metalogos: it branches based on confidence scores from fluid types.

Metalogos-specific: Collapse (fluid type resolution), Memorize, Recall, Forget, LlmCall, Adapt, Relate, Mutate.

Meta: ExecuteRules, Halt.

Compilation

The compiler is two-pass:

Pass 1: Collect global variables, assign slot indices, resolve imports recursively.
Pass 2: Generate instructions. Expression compilation is context-aware: pattern parameters become LoadLocal, globals become LoadGlobal.

Flow declarations compile into a single FlowPipeline macro instruction. The pipeline steps are resolved at runtime, but the step names are validated at compile time.

Call Frames

The VM uses a stack of CallFrame structs: return address + base pointer. This is standard, but the implementation uses Rust's Vec as the value stack and usize indices for frame boundaries — no unsafe code for stack manipulation.

The `is_pure` Flag

Every compiled pattern carries an is_pure flag, set by the compiler's purity analysis. A pattern is pure if it has no LLM calls, no side effects, and no global access. This flag is currently used for documentation, but the scaffold exists for JIT compilation via Cranelift (ADR-0073). The JIT is not production-ready, but the infrastructure is there.

4. Zero-Cost Security Types

Metalogos has five opaque types: Html, Secret, Encrypted, Hash, SqlQuery. These are not runtime wrappers. They are compile-time constraints enforced during semantic analysis and erased before codegen.

How It Works

The semantic analyzer (semantic.rs) walks the AST after parsing but before compilation. It checks:

Template return types: Only Html is valid. template Page() -> Secret is a compile-time error.
String interpolation in queries: query("SELECT * WHERE id = " + id) fails because String ≠ SqlQuery.
Secret leakage: print(apiKey) where apiKey: Secret fails because Secret has no Display implementation at the language level.
HTML auto-escaping: Values of type String cannot be embedded in templates without explicit conversion to Html.

At the VM level, Secret is just a String. Html is just a String. The security guarantee is enforced once, at compile time, and never checked again. This is the same principle as Rust's borrow checker: invariants at compile time, zero cost at runtime.

Defense in Depth: SVG/HTML Lint

Наряд №74 added a static lint for SVG and HTML builtins (svg_text, html_response, escape_html). It inspects string literals at compile time for javascript: and data:text/html prefixes. This is not a replacement for the type system — it is a second layer for cases where the type system cannot reason about string content.

5. Builtin Dispatch: 246 Functions, One Registry

All builtins are declared in a single const array:

pub const BUILTIN_REGISTRY: &[BuiltinSpec] = &[
    spec!("upper", 1, "string"),
    spec!("lower", 1, "string"),
    // ... 246+ entries
];

The order determines bytecode indices. This is a single source of truth: add a spec! row, add a handler in Builtins::new(), and the builtin exists in both the interpreter and VM.

The dispatch system uses a HashMap<String, BuiltinFn> for the interpreter (name-based) and direct index access for the VM (CallBuiltin(arity, index)). The registry guarantees that both paths resolve to the same implementation.

14 modules: string, math, collections, crypto, llm, http, json, io, memory, cron, server, core, std, tests.

6. Error Handling: Thiserror and Soft Failures

Rust-level errors use thiserror::Error:

#[derive(thiserror::Error, Debug)]
pub enum RuntimeError {
    #[error("parse error: {0}")]
    Parse(String),
    #[error("io error: {0}")]
    Io(#[from] std::io::Error),
    #[error("llm error: {0}")]
    Llm(String),
    #[error("sandbox violation")]
    Sandbox,
}

Language-level errors (type mismatch, undefined variable) are soft failures: they return Value::Unit or Result<Value, String>. The interpreter does not panic. The VM does not crash. This is essential for a language that may run AI-generated code — hard failures on every type mismatch would make the language unusable for LLM outputs.

A custom macro replaces .lock().unwrap():

macro_rules! lock_or_err {
    ($lock_expr:expr) => {
        $lock_expr
            .lock()
            .map_err(|e| $crate::error::RuntimeError::Lock(e.to_string()))
    };
}

No poisoned mutexes crash the runtime.

7. What We Deferred

Self-Hosting

ADR-0023 describes a self-hosted lexer written in Metalogos. It is not functional. The test is #[ignore]. The 5 builtins described in the ADR were never implemented — only opcode indices were registered. The decision (re-measured August 2026): defer self-hosting until post-v1.0. Current priority is VM stabilization and a self-hosted lexer/parser as a stepping stone, not a full bootstrap.

JIT

Cranelift integration exists as a scaffold (ADR-0073). The is_pure flag is set. The JIT module is not connected to the main pipeline. This is intentional — correctness before speed.

8. What We Added Recently

13 TW/VM parity gaps closed — full semantic equivalence
ADR-0023 re-measurement — honest assessment of self-hosting status
SVG/HTML security lint — defense-in-depth for template injection
PDF, Email, Calendar (CalDAV+iCal), Contacts (CardDAV+vCard) — office automation builtins
http_download
Retry/backoff

Conclusion

Building a language alone is possible. Building a correct language alone requires discipline: dual backends for confidence, traits for extensibility, opaque types for security, and ADRs for sanity.

The patterns in this post — crosscheck validation, zero-cost type erasure, const registries, and soft failure modes — are not specific to Metalogos. They are applicable to any Rust project that needs correctness guarantees without runtime overhead.

Repository: https://github.com/ShkodnikAI/Metalogos-

License: MIT/Apache-2.0

ADR Collection: 91 decisions, fully documented in docs/adr/

DEV Community: Miron Tuteyshi

Designing a Stack-Based VM in Rust: 44 Instructions, Dual Backends, and Zero-Cost Security Types

Designing a Stack-Based VM in Rust: 44 Instructions, Dual Backends, and Zero-Cost Security Types

Introduction

1. The Grammar as Contract

2. Dual Backends: Correctness Through Disagreement

The 13 Parity Gaps

Why Two Backends?

3. The VM: 44 Instructions and a Stack

Instruction Categories

Compilation

Call Frames

The is_pure Flag

4. Zero-Cost Security Types

How It Works

Defense in Depth: SVG/HTML Lint

5. Builtin Dispatch: 246 Functions, One Registry

6. Error Handling: Thiserror and Soft Failures

7. What We Deferred

Self-Hosting

JIT

8. What We Added Recently

Conclusion

The `is_pure` Flag