# How the Maru Compiler Handles the Expand and Encode Phases

> Explore how the Maru compiler handles expand and encode phases. Learn about macro expansion, special form normalization, and identifier resolution in source/evaluator/eval.l.

- Repository: [Attila Lendvai/maru](https://github.com/attila-lendvai/maru)
- Tags: internals
- Published: 2026-02-25

---

**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]](https://github.com/attila-lendvai/maru/blob/maru.10/source/evaluator/eval.l#L465-L466). Its signature is:

```lisp
(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]](https://github.com/attila-lendvai/maru/blob/maru.10/source/evaluator/eval.l#L514-L536)), 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]](https://github.com/attila-lendvai/maru/blob/maru.10/tests/evaluator-tests.l#L24-L27), 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]](https://github.com/attila-lendvai/maru/blob/maru.10/source/evaluator/eval.l#L333-L336). 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]](https://github.com/attila-lendvai/maru/blob/maru.10/source/evaluator/eval.l#L550-L570)), 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`](https://github.com/attila-lendvai/maru/blob/main/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:

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

```

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

```lisp
(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]](https://github.com/attila-lendvai/maru/blob/maru.10/source/evaluator/eval.l#L514-L536)

### Example 2: Encode a Previously Expanded `let`

Input: the expanded form from Example 1.

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

```

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

```lisp
; → 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]](https://github.com/attila-lendvai/maru/blob/maru.10/source/evaluator/eval.l#L550-L570)

### Example 3: Using the Public Helper Functions

```lisp
; 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]](https://github.com/attila-lendvai/maru/blob/maru.10/tests/evaluator-tests.l#L24-L27)

## 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]](https://github.com/attila-lendvai/maru/blob/maru.10/source/evaluator/eval.l#L465-L466). The encode phase uses `encode`, `encode-all`, `encode/pair`, and `encode/symbol` around [[source line 333-336]](https://github.com/attila-lendvai/maru/blob/maru.10/source/evaluator/eval.l#L333-L336).

### 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.