How Variables Are Resolved at Compile Time in Maru

Maru resolves variables at compile time by transforming every identifier into a concrete <variable> 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 <variable> records. As documented in doc/compiler.md, the encode phase "makes sure that all variable references … get resolved to either full <variable> 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 <variable> 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 <variable> 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 <env>-offset from the environment structure, stores this value in <variable>-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 <variable> is appended to the environment’s <env>-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 <variable>-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 <variable> 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】:

• <variable>-name: The symbol identifier
• <variable>-env: Reference to the lexical environment
• <variable>-index: The compile-time assigned slot index
• <variable>-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:

;; During encode phase
;; 1. defined? checks current env → returns false
;; 2. new-variable creates:
;;    <variable>
;;      name  = 'x
;;      env   = <current-env>
;;      index = 0          ; first slot, offset was 0
;;      value = <uninitialized>
;; 3. <env>-offset increments to 1

The generated x86 code uses the pre-calculated offset:

; 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:

;; environment-define creates variable in slave env
;; global-variable? returns true
;; encoder assigns fixed memory address

The back-end emits direct memory addressing:

; Pseudo-assembly for loading global *g*
mov rax, [absolute_address_of_*g*]

Lexical Scoping in Nested Functions

Consider the closure pattern:

(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 <env>
3. Creates a <variable> 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 <variable> 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 <variable>-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 <variable>-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 — 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 <env>-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 <variable> object with a pre-assigned compile-time index. According to 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 <env>-offset from the environment, stores this value in <variable>-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 <variable> 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.

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