How the Maru Compiler Handles the Expand and Encode Phases

The Maru compiler processes source code through two distinct compile-time phases—expand for macro expansion and special form normalization, followed by encode for resolving identifiers to concrete runtime objects—both implemented in source/evaluator/eval.l before any target code is emitted.

Maru’s compilation pipeline is a two-step compile-time process that transforms raw s-expressions into executable VM objects. According to the attila-lendvai/maru source code, the expand and encode phases work sequentially to eliminate macros and bind identifiers to concrete runtime representations.

The Expand Phase: Macro Expansion and Special Form Normalization

The expand phase performs macro-expansion on the source s-expression tree, transforming special forms (let, quote, set, define, lambda, and user-defined expanders) into their fully-expanded representation. The result remains a pure Maru s-expression suitable for the next phase.

Entry Point and Dispatch Logic

The primary entry point is the VM-function expand, defined in source/evaluator/eval.l at [source line 465-466]. Its signature is:

(expand exp (env <env>) (one-step? <long> false))

The function dispatches on the type of exp:

• Pairs are handled by expand/pair
• Symbols are handled by expand/symbol
• Custom expanders registered in the global *expanders* array are applied if present

Handling Special Forms

Inside expand/pair (around [source line 514-536]), the compiler recognizes special forms by comparing the head symbol with built-in symbols like symbol/let, symbol/quote, symbol/set, symbol/define, and symbol/lambda.

For let expressions, the binder list is recursively expanded using expand-all so that each binding expression is fully expanded before the body is re-wrapped as a normal (let ...) form.

For set expressions, the compiler attempts a set-conversion (transforming (set (foo ...) v) into a dedicated set-foo form) and falls back to a plain (set ...) when no conversion is available.

User-Defined Expanders

The expand phase detects user-defined expanders via maybe-form-in-env/function when processing the head of a pair. If the head symbol resolves to an expander function in the current environment, that function is invoked with the expression. The result is then optionally expanded again based on the one-step? parameter, allowing both single-step debugging and full recursive expansion. Custom expanders can also be registered globally in the *expanders* array.

The result of the expand phase is a pure Maru s-expression where all macros have been eliminated and all let bindings have been normalized. This is verified by tests such as eval/expand/bug/1 in tests/evaluator-tests.l at [test line 24-27], which ensures that expand does not treat let-bindings as call forms.

The Encode Phase: Resolving Identifiers to Runtime Objects

The encode phase walks the already-expanded tree and resolves every identifier to a concrete runtime object. After this pass, the tree contains only objects that the Maru VM can execute directly, such as fixed primitives (<fixed>) for global symbols and variable objects for locals.

From S-Expressions to Heap Objects

The entry point is the VM-function encode in source/evaluator/eval.l at [source line 333-336]. Its implementation dispatches to:

• encode/pair for list processing
• encode/symbol for identifier resolution
• encode-all for recursive processing of sub-expressions

Literals such as numbers and strings remain unchanged, as they are already concrete heap objects.

Environment Handling and Variable Binding

When encode/pair encounters a let form (around [source line 550-570]), it performs a three-phase binding process:

1. Phase 1 – Creates a fresh inner environment and defines each binding name as a <variable> placeholder.
2. Phase 2 – Encodes the initializer expressions using encode-all on each initializer.
3. Phase 3 – Encodes the body of the let in the inner environment, turning variable references into the <variable> objects defined in Phase 1.

For symbols, encode/symbol looks up the identifier in the current environment. If found, it returns the associated object (typically a <variable> or <fixed> primitive). Unbound symbols remain as raw symbols in the encoded tree; these later become global references at the top level when the VM executes the code, allowing for late-bound global variables and forward references.

The encoded tree is therefore a graph of heap objects (<pair>, <variable>, <fixed>, etc.) that the Maru VM can evaluate directly without further name lookups. This architecture is documented in the encode section of doc/compiler.md.

Interaction Between the Expand and Encode Phases

The expand and encode phases operate as separate passes with distinct responsibilities:

• Expand works purely on syntax using expand, expand-all, expand/pair, and expand/symbol, handling special forms like let, quote, set, define, and lambda. It never creates runtime objects.
• Encode uses encode, encode-all, encode/pair, and encode/symbol to resolve identifiers in environments, creating inner environments for let bindings and converting symbols to heap objects.

This separation provides clarity and modularity. While a comment in the test suite (;; maybe the fix is that expand and encode should be merged…) suggests a potential future optimization to combine the passes, the current implementation in attila-lendvai/maru maintains them as distinct stages in the compile-time pipeline.

Code Examples

Example 1: Manual Expand of a let with a Macro

Source code before expansion:

(let ((zork 42)
      (helper (lambda (v) `(zork ,v))))
  (helper 1))

After the expand phase (via (expand …)):

(let ((zork 42)
      (helper (lambda (v) (zork v))))   ; macro-expanded: the back-quote is resolved
  (helper 1))

Implementation: expand/pair recognises symbol/let and calls expand-all on each binding, then rebuilds the let form. [source line 514-536]

Example 2: Encode a Previously Expanded let

Input: the expanded form from Example 1.

(let ((zork 42)
      (helper (lambda (v) (zork v))))
  (helper 1))

After the encode phase (via (encode …)):

; → a <pair> whose head is the fixed primitive `let`
;   the two bindings become <variable> objects bound in a new inner env
;   the body `(helper 1)` becomes a call that fetches the <variable> for `helper`

Implementation: encode/pair detects fixed-primitive-function/let, creates an inner environment, defines the bindings, encodes the init-expressions, then encodes the body. [source line 550-570]

Example 3: Using the Public Helper Functions

; In a REPL or test file
(define-test demo-expand-encode ()
  (let ((x 10))
    (test-assert (= 5 (expand '(let ((x 5)) x))) ; → 5 after expand
    (test-assert (type? <variable> (first (encode-all (expand '(let ((x 5)) x)) (environment)))))))

The test suite (tests/evaluator-tests.l) already contains similar checks, e.g. the eval/expand/bug/1 case. [test line 24-27]

Summary

• The expand phase in source/evaluator/eval.l performs macro expansion and special form normalization on s-expressions before any code generation occurs.
• The encode phase transforms the expanded tree into a graph of concrete runtime objects (<variable>, <fixed>, <pair>) that the Maru VM can execute directly.
• Expand operates purely on syntax using expand, expand-all, expand/pair, and expand/symbol, handling special forms like let, quote, set, define, and lambda.
• Encode uses encode, encode-all, encode/pair, and encode/symbol to resolve identifiers in environments, creating inner environments for let bindings and converting symbols to heap objects.
• The phases remain separate for clarity and modularity, though the codebase acknowledges potential future optimization through merging.

Frequently Asked Questions

What is the difference between the expand and encode phases in Maru?

The expand phase works purely on syntactic forms to eliminate macros and normalize special forms like let and lambda, producing a pure s-expression tree without creating runtime objects. The encode phase then walks this expanded tree to resolve every identifier to concrete runtime objects such as <variable> or <fixed> primitives, resulting in a heap object graph that the VM executes directly without further name lookups.

Where are the expand and encode phases implemented in the Maru source code?

Both phases are implemented in source/evaluator/eval.l. The expand phase uses the VM-functions expand, expand-all, expand/pair, and expand/symbol around [source line 465-466]. The encode phase uses encode, encode-all, encode/pair, and encode/symbol around [source line 333-336].

How does the expand phase handle user-defined macros?

The expand phase detects user-defined expanders via maybe-form-in-env/function when processing the head of a pair. If the head symbol resolves to an expander function in the current environment, that function is invoked with the expression. The result is then optionally expanded again based on the one-step? parameter, allowing both single-step debugging and full recursive expansion. Custom expanders can also be registered globally in the *expanders* array defined in boot.l.

What happens to unbound symbols during the encode phase?

During the encode phase, encode/symbol attempts to look up each symbol in the current environment. If the symbol is bound, it returns the associated object (typically a <variable> or <fixed> primitive). Unbound symbols remain as raw symbols in the encoded tree; these later become global references at the top level when the VM executes the code, allowing for late-bound global variables and forward references.

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