Understanding the Structure of Maru's VM: Architecture and Execution Pipeline

Maru's VM is a self-hosted Lisp interpreter organized into four distinct layers—platform abstraction, core evaluator infrastructure, primitive function definitions, and file/REPL support—that processes code through a three-phase expand-encode-eval pipeline.

The Maru programming language, maintained in the attila-lendvai/maru repository, implements a compact virtual machine entirely in Maru itself. This architecture enables the system to bootstrap from minimal platform primitives while providing a complete environment for interactive development. Understanding the structure of Maru's VM requires examining its layered file organization, core data structures, and the execution pipeline that transforms source code into evaluated results.

Layered Architecture of the Maru VM

The VM implementation spans four source files in source/evaluator/, each representing a distinct architectural layer that builds upon the previous one.

Platform Abstraction Layer (vm-early.l)

The foundation resides in source/evaluator/vm-early.l, which defines the platform API that the VM expects from its host environment. This file declares low-level operations including memory allocation, I/O primitives, and system calls. It also initializes feature flags such as backtrace support and establishes the call-stack mechanism through the *call-stack-index* variable (lines 5–9). These definitions allow the VM to remain portable across different target platforms while maintaining consistent semantics for core operations.

VM Core Infrastructure (vm.l)

The central evaluator lives in source/evaluator/vm.l, implementing the execution loop, error handling, and the define-vm-function macro (lines 70–140). This layer manages the global lexical environment through the *globals* binding and maintains the primitive type table used for boxing and unboxing values. The file defines type accessors for <array>, <pair>, <string>, and <long> (lines 56–62), establishing how the VM represents data at runtime.

Primitive Operations (vm-functions.l)

Built atop the core infrastructure, source/evaluator/vm-functions.l contains the bulk of Maru's standard library implemented as VM primitives. Using the define-vm-function macro, this file exposes fundamental operations including arithmetic (+), control flow (if), assignment (set!), and module loading (load). These functions handle argument marshaling between the evaluator and the underlying implementation, including unboxing <long> values for numeric operations.

File and REPL Support (vm-with-file-support.l)

The highest layer, source/evaluator/vm-with-file-support.l, provides the bridge between the VM and the operating system. This file implements stream handling, command-line processing, and the load and repl functions that enable interactive development. It orchestrates file operations through helpers like file-open-or-die and expand-encode-eval-stream, which drive the compilation pipeline.

Core Data Structures

Maru's VM manages program state through four interconnected structures that separate compile-time binding information from runtime value storage.

Environment and Variable Management (<env> and <variable>)

The <env> structure represents lexical scopes, mapping symbols to <variable> objects. During the encoding phase, the compiler creates <env> instances for each scope (including the global scope stored in *globals*), allocating <variable> objects that contain the symbol name, an optional environment reference, and an integer index. These indices determine where values reside in the runtime context array, enabling efficient variable lookup without symbol table searches during evaluation.

Runtime Contexts (<context>)

While <env> objects exist at compile time, <context> instances serve as the runtime containers for variable bindings. Implemented as arrays indexed by the variable allocations established during encoding, contexts represent stack frames for function calls and let bindings. The VM maintains the current call stack depth through *call-stack-index*, with optional back-trace support compiled when the backtrace feature is enabled.

Primitive Types and Boxing

The VM operates on boxed objects for all types except small integers. The type hierarchy includes <array>, <pair>, <string>, and <long>, with the latter typically unboxed for arithmetic operations. The define-vm-function macro handles automatic unboxing via the *vm-function-type-accessors* table, ensuring type safety while allowing primitive implementations to work with native machine representations.

The Execution Pipeline

Maru's VM processes source code through three distinct phases documented in doc/vm.md, separating macro expansion from variable resolution and evaluation.

Macro Expansion (expand)

The first phase transforms the input S-expression by applying macro definitions. This pass expands syntactic sugar into core forms while preserving the tree structure of the program.

Encoding (encode)

During encoding, the VM transforms the expanded AST into an encoded form containing concrete <env> objects and variable indices. This phase allocates slots for variables in lexical environments, creating the mapping between symbolic names and numeric indices that enables the runtime to use array indexing rather than hash lookups.

Evaluation (eval)

The final phase walks the encoded AST and invokes VM functions. When encountering a function call, the evaluator creates a new <context> array sized according to the environment's variable count, evaluates arguments, and executes the primitive implementation. For arithmetic operations, this involves unboxing <long> values, performing the calculation, and boxing the result back into a heap-allocated object.

Defining VM Functions with define-vm-function

The define-vm-function macro in vm.l automates the boilerplate required to expose primitives to the evaluator. For each primitive, the macro generates two functions: a public name (e.g., +) and a hidden evaluator stub that prepares arguments.

;; Simplified view of the macro (see vm.l lines 70–140)
(define-form define-vm-function (name-and-props args . body)
  ;; builds a stub that unboxes args according to *vm-function-type-accessors*
  (define-function stub-name (-args- -ctx-)
    (let (… bind args …)
      (… body …)))

Primitive implementations use this macro to handle type coercion automatically:

;; arithmetic – defined in vm-functions.l
(define-vm-function (+ ()) _
  (let ((result 0) (rest ()))
    (when (pair? -args-)
      (set result (unbox <long> (get/head -args-))
      (set rest (get/tail -args-)))
    (while (pair? rest)
      (set result (+ result (unbox <long> (get/head rest)))))
    (box <long> result)))

The macro extracts arguments from the -args- list, applies unboxing based on type annotations, and manages interaction with the current <context> passed as -ctx-.

Summary

• Maru's VM consists of four layers: Platform primitives (vm-early.l), core infrastructure (vm.l), built-in functions (vm-functions.l), and file/REPL support (vm-with-file-support.l).
• Execution follows a three-phase pipeline: Source code undergoes macro expansion, encoding (which creates <env> and <variable> objects), and evaluation against <context> arrays.
• Variable access uses numeric indexing: The encoding phase maps symbols to integer indices, allowing the evaluator to use fast array lookups in <context> objects rather than symbol table searches.
• Primitives are defined via define-vm-function: This macro generates evaluator stubs that handle argument unboxing, type checking, and boxing of return values.
• The architecture is self-hosted: The VM is implemented in Maru itself, relying on a minimal platform API for memory and I/O operations.

Frequently Asked Questions

What files make up Maru's VM implementation?

The VM spans four files in source/evaluator/: vm-early.l defines the platform API and global symbols; vm.l contains the core evaluator, error handling, and define-vm-function macro; vm-functions.l implements primitives like arithmetic and control flow; and vm-with-file-support.l provides stream handling and the REPL. Documentation resides in doc/vm.md.

How does Maru's VM handle lexical scoping?

The VM separates compile-time scope representation from runtime storage. During encoding, it creates <env> objects that map symbols to <variable> instances containing array indices. At runtime, the evaluator creates <context> arrays where these indices locate actual values, enabling proper lexical scoping with efficient access.

What is the difference between <env> and <context> in Maru?

An <env> (environment) exists during compilation and encoding, mapping symbols to variable metadata including allocation indices. A <context> exists at runtime as an array of actual values indexed by those allocations. While <env> objects persist to support closures, <context> instances represent transient stack frames during evaluation.

How are primitive operations like + implemented in the VM?

Primitives are defined using the define-vm-function macro in vm-functions.l. The macro generates a wrapper that extracts arguments from the -args- list, unboxes them from <long> objects to raw integers, performs the operation, and boxes the result back into a <long>. This pattern applies to all arithmetic, logical, and data-structure operations exposed to user code.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}