# How Variables Are Resolved at Compile Time in Maru > Discover how Maru resolves variables at compile time by transforming identifiers into concrete objects with fixed stack indices for efficient memory access. - Repository: [Attila Lendvai/maru](https://github.com/attila-lendvai/maru) - Tags: internals - Published: 2026-02-25 --- **Maru resolves variables at compile time by transforming every identifier into a concrete `` object during the `encode` phase, pre-assigning each a fixed stack index or global address that the back-end uses for fast, direct memory access.** Maru is a self-hosting Lisp implementation where the compiler operates in two distinct phases before generating machine code. According to the attila-lendvai/maru source code, understanding this compile-time resolution is essential for grasping how the language achieves efficient execution while maintaining dynamic semantics. ## The Compile-Time Pipeline: Expand and Encode Maru’s compiler processes source code through two sequential phases. During the **expand** phase, macro expansion produces a pure s-expression tree. The subsequent **encode** phase walks this tree and performs the critical work of variable resolution. In `source/evaluator/eval.l`, the encoder calls `encode` on each form, which recursively processes symbols and converts them into `` records. As documented in [`doc/compiler.md`](https://github.com/attila-lendvai/maru/blob/main/doc/compiler.md), the encode phase "makes sure that all variable references … get resolved to either full `` objects … each variable is pre-assigned a fixed index at compile time"【/cache/repos/github.com/attila-lendvai/maru/maru.10/doc/compiler.md#L10-L27】. ## The Six Steps of Variable Encoding When the encoder encounters a symbol, it follows a precise resolution sequence implemented across the evaluator and compiler sources. ### Step 1: Environment Lookup with `defined?` The encoder first queries the current environment to determine if the symbol already exists. In `source/evaluator/eval.l`, the `defined?` function walks the environment chain using `find-local-variable` to locate existing bindings【/cache/repos/github.com/attila-lendvai/maru/maru.10/source/evaluator/eval.l#L44-L48】. If the symbol is found, the encoder reuses the existing `` object. If not, the system proceeds to create a new one. ### Step 2: Variable Creation with `new-variable` For undefined symbols, the compiler invokes `new-variable` in `source/evaluator/eval.l`【/cache/repos/github.com/attila-lendvai/maru/maru.10/source/evaluator/eval.l#L51-L61】. This function: - Creates a `` record - Stores the symbol name and environment reference - Assigns a compile-time index - Appends the variable to the environment’s bindings array ### Step 3: Index Assignment and Stack Slot Allocation The critical optimization occurs during index assignment. In `new-variable`, the system reads the current `-offset` from the environment structure, stores this value in `-index`, then increments the offset. This ensures each local variable receives a unique, sequential stack slot number at compile time. The next variable created in the same environment receives the incremented offset, guaranteeing non-overlapping stack allocations. ### Step 4: Binding Registration The freshly created `` is appended to the environment’s `-bindings` array. This makes the variable visible to all subsequent passes of the compiler, ensuring consistent resolution throughout the compilation unit. ### Step 5: Value Slot Reuse for Code Generation The `-value` field serves dual purposes. During compilation, it holds runtime initialization data. During code generation in `source/compiler/emit-x86-common.l` and related emitters, the back-end repurposes this field to store the **CPU stack offset** (or a fixed memory address for globals)【/cache/repos/github.com/attila-lendvai/maru/maru.10/source/compiler/emit-x86-common.l#L574-L635】. ### Step 6: Global vs. Local Distinction Global variables receive special handling. In `source/evaluator/eval.l`, `environment-define` creates variables in the *slave* environment (the target runtime environment) before the encode phase begins. These globals have a fixed memory address, and `global-variable?` identifies them so the back-end emits absolute addresses rather than stack-relative offsets【/cache/repos/github.com/attila-lendvai/maru/maru.10/source/evaluator/eval.l#L51-L61】. Local variables, created on-the-fly during encode, receive stack indices relative to the current frame pointer. ## The Data Structure The `` record defined in `source/types.l` contains four fields that enable compile-time resolution【/cache/repos/github.com/attila-lendvai/maru/maru.10/source/types.l#L99-L100】: - **`-name`**: The symbol identifier - **`-env`**: Reference to the lexical environment - **`-index`**: The compile-time assigned slot index - **`-value`**: Runtime value or stack offset/global address This structure allows the compiler to pass fully-typed variable objects to the back-end, eliminating the need for runtime symbol table lookups during execution. ## Practical Examples of Compile-Time Resolution ### Local Variable Definition When compiling `(define x 42)`, the encoder performs the following resolution: ```lisp ;; During encode phase ;; 1. defined? checks current env → returns false ;; 2. new-variable creates: ;; ;; name = 'x ;; env = ;; index = 0 ; first slot, offset was 0 ;; value = ;; 3. -offset increments to 1 ``` The generated x86 code uses the pre-calculated offset: ```asm ; Pseudo-assembly for storing 42 to x mov rax, 42 mov [rbp + 0], rax ; index 0 becomes offset 0 from frame pointer ``` ### Global Variable Resolution For `(define *g* 100)` in the global environment: ```lisp ;; environment-define creates variable in slave env ;; global-variable? returns true ;; encoder assigns fixed memory address ``` The back-end emits direct memory addressing: ```asm ; Pseudo-assembly for loading global *g* mov rax, [absolute_address_of_*g*] ``` ### Lexical Scoping in Nested Functions Consider the closure pattern: ```lisp (define (make-adder n) (lambda (x) (+ x n))) ``` During encode of the inner lambda: 1. The encoder encounters `n` as a free variable 2. `defined?` walks the environment chain and finds `n` in the outer `` 3. Creates a `` in the inner closure's environment pointing to the outer index 4. The compiled code accesses `n` through the closure's environment chain at runtime ## Key Source Files for Variable Resolution The compile-time resolution mechanism spans these critical files in attila-lendvai/maru: - **`source/types.l`** — Defines the `` record structure with `name`, `value`, `env`, and `index` fields【/cache/repos/github.com/attila-lendvai/maru/maru.10/source/types.l#L99-L100】 - **`source/evaluator/eval.l`** — Implements `new-variable` (creation and indexing) and `defined?`/`find-local-variable` (lookup chain)【/cache/repos/github.com/attila-lendvai/maru/maru.10/source/evaluator/eval.l#L51-L61】 - **`source/evaluator/vm-functions.l`** — Accesses `-index` during compiled code execution for loading and storing locals【/cache/repos/github.com/attila-lendvai/maru/maru.10/source/evaluator/vm-functions.l#L54-L71】 - **`source/compiler/target.l`** — Sets up slave/target environments to ensure `define-form` evaluates bodies in the correct compile-time environment【/cache/repos/github.com/attila-lendvai/maru/maru.10/source/compiler/target.l#L39-L46】 - **`source/compiler/emit-x86-*.l`** — Consumes `-value` to emit proper stack offsets or global addresses in machine code【/cache/repos/github.com/attila-lendvai/maru/maru.10/source/compiler/emit-x86-common.l#L574-L635】 - **[`doc/compiler.md`](https://github.com/attila-lendvai/maru/blob/main/doc/compiler.md)** — Documents the expand/encode phases and the pre-assigned index strategy【/cache/repos/github.com/attila-lendvai/maru/maru.10/doc/compiler.md#L10-L27】 ## Summary - Maru’s compiler uses a two-phase approach: **expand** (macro expansion) followed by **encode** (variable resolution). - During **encode**, the `defined?` function walks environment chains to locate existing variables or trigger creation. - **new-variable** assigns a compile-time index by reading and incrementing `-offset`, ensuring each local gets a unique stack slot. - Global variables are created via **environment-define** in the slave environment and receive fixed memory addresses. - The **** record stores the name, environment, index, and a value field repurposed for stack offsets during code generation. - This resolution strategy enables the back-end to emit efficient, direct memory accesses without runtime symbol lookups. ## Frequently Asked Questions ### What is the difference between the expand and encode phases in Maru? The **expand** phase performs macro expansion to produce a pure s-expression tree, eliminating all macro calls. The **encode** phase then walks this tree and transforms every symbol into a concrete `` object with a pre-assigned compile-time index. According to [`doc/compiler.md`](https://github.com/attila-lendvai/maru/blob/main/doc/compiler.md), encode ensures all variable references are resolved to full objects before code generation begins. ### How does Maru assign stack slots to local variables? During the encode phase, `new-variable` in `source/evaluator/eval.l` reads the current `-offset` from the environment, stores this value in `-index`, and increments the offset for the next variable. This sequential allocation guarantees that each local variable receives a unique, fixed stack slot number that the back-end uses to calculate `[rbp + offset]` addressing in the generated machine code. ### What happens if a variable is not found during the encode phase? If `defined?` (which uses `find-local-variable`) fails to locate a symbol in the environment chain, the encoder creates a new `` object via `new-variable`. For local variables, this happens on-the-fly during encode. For globals, the symbol should have been defined previously via `environment-define` in the slave environment; otherwise, it may result in a compile-time error or undefined behavior depending on the compilation context. ### How does Maru distinguish between global and local variables at compile time? Global variables are identified by the `global-variable?` predicate, which checks if the variable's environment level indicates it resides in the global (slave) environment. These variables receive fixed memory addresses. Local variables have indices relative to the current stack frame. The back-end in `source/compiler/emit-x86-common.l` uses this distinction to emit absolute addressing for globals versus stack-relative addressing for locals.