A macro expands into a call to itself and expansion never stops, so what did the author get wrong?
answer
- rewriting that feeds itself
- termination needs a shrinking measure
- the measure must be known while expanding
- an emitted conditional decides too late
- a budget, not a loop detector
basics
~20 sThe base case was emitted as a run-time test instead of being decided while expanding. The recursive call is present in the emitted text either way, so the next pass rewrites it again and the guard never gets to run.
solid answer
~40 sExpansion rewrites the text it produced, so a macro that emits a call to itself will be rewritten again. It terminates only if some measure shrinks on each step *and* the shrinking is judged in the expanding stage, on something already known while compiling -- a literal count, the length of an argument list, a written-down structure. If the author instead emits a conditional guarding the recursive call, the guard is just text: it decides nothing until run time, while the self-call sits in the output waiting for the next pass. The toolchain stops the runaway with a fixed depth or step **budget**, which is a blunt guard, not a loop detector: a legitimately deep expansion trips it exactly the same way.
code
pseudocode · 16 lines// terminates: the decision is made while expanding
macro countdown(n):
if n == 0:
return quote( done() )
return quote( step(splice(n)) ; splice(countdown(n - 1)) )
// countdown(2) -> step(2) ; step(1) ; done()
// runs away: the decision is emitted as code for later
macro bad_countdown(n):
return quote(
if splice(n) > 0 then step() ; bad_countdown(splice(n) - 1)
)
// the emitted text still contains bad_countdown(...), so the next
// pass rewrites it again and the guard never gets a chance to rungo deeper
Remember that expansion can feed itself: the text a macro produces gets looked at again, so a macro really can expand into itself.
Explain where the base case has to live, decided by the stage on something it already knows, and why a conditional in the emitted code is far too late to help.
Read the failure correctly. A budget error names a limit, not a cause, so decide whether the expansion is non-terminating or merely large before touching the limit.
Own the budget as a build-health setting. Raising it trades compile time and memory for convenience, and a codebase that keeps asking for more is reporting a design problem.
## Expansion feeds itself Rewriting is not a single pass. An expander typically looks again at the text it has just produced, so a macro whose output contains a call to itself is rewritten again, and again. That is a feature: it is how a macro walks a list of arguments, unrolls a fixed count, or builds a structure one level at a time. It is also how an expansion runs away, and the two differ by one thing only: **where the decision to stop is made**. ## Where the base case has to live A recursive expansion terminates when some measure shrinks at every step and the expanding stage can *see* it shrink. Suitable measures are things known while compiling: - a literal number written at the call site; - the number of arguments the call actually has; - the depth or width of a written-down type or structure description; - the length of a list the stage itself is building. The defect is putting the base case in the **emitted** code. An author writes a conditional that tests the counter and, in the false branch, the recursive call. That conditional is text. It will be evaluated when the program runs, which is far too late: the text of the output already contains the self-call, so the next pass rewrites it, producing another copy containing another self-call. Nothing about the emitted conditional stops the rewriting, because rewriting is not running the program. The corrected shape makes the decision one level earlier: the stage tests the measure itself, and in the base case it returns output that **contains no recursive call at all**. ## The compiler's guard is a budget No toolchain can decide in general whether an expansion terminates, because the expanding stage runs arbitrary computation and the question is the halting problem in disguise. So compilers do the only practical thing: they impose a fixed budget -- a maximum nesting depth, a maximum number of rewrite steps, or both -- and fail hard when it is exhausted. That has three consequences worth stating precisely: - **The error names a limit, not a cause.** It reports that the budget was exceeded, and, if the toolchain keeps a trace, the chain of calls it was deepest in. - **A legitimate expansion can trip it.** A large but finite expansion -- a generated table with a few thousand entries -- fails in exactly the same way as one that would never end. Hitting the budget proves only that the expansion went further than the budget allowed. - **Raising it is sometimes right and often not.** The budget also protects build time and compiler memory. A codebase that keeps needing a bigger one is usually telling you that a macro is doing work that belongs in ordinary run-time code. ## Depth is not the only way to blow up An expansion can terminate and still ruin the build, because the budget on depth says nothing about the *size* of the output. If each step splices its argument into two positions and then recurses, the emitted text doubles per level: after n levels there are on the order of 2^n copies of the original argument. Depth stays comfortably under any budget while compile time and memory go through the roof, and the artifact ends up carrying that duplicated code as well. The cure for that one is structural: have the stage loop over n and emit n pieces, rather than emitting a shape that contains two copies of itself. ## Making a recursive expansion terminate 1. **Pick the measure first** and confirm the expanding stage can read it. If the only thing that shrinks is a run-time value, the recursion does not belong in the expansion. 2. **Write the base case as a return from the stage**, producing output with no self-call in it. Check by eye that the base-case branch is free of the macro's own name. 3. **Prefer iteration in the stage over recursion in the output.** A loop that builds a list of fragments and splices them once is easier to reason about and cannot recurse by accident. 4. **Bound yourself.** Have the stage raise a clear error at the call site when the measure exceeds what the macro is designed for, so callers get your message rather than the compiler's budget message. ## Reading the failure When a budget error appears, resist the urge to raise the limit. Ask instead: what shrinks on each step, and who evaluates the shrinking? If the answer is "an emitted conditional", the macro is non-terminating and no budget will save it. If the answer is a genuine compile-time measure and the input really is that big, then the expansion works and the question becomes whether you want to pay for it on every build.
- When is a deep expansion legitimate rather than a bug?When the depth is a function of real input, such as a long argument list or a wide structure description, and each step shrinks a measure the stage can read. It terminates; it is merely large. The fix is then a bigger budget or a flatter design, not a rewrite of the logic.
- How can a terminating expansion still wreck the build?By growing output instead of depth. If each step splices its argument into two positions and recurses, the emitted text doubles per level, so n levels produce on the order of 2^n copies. Depth stays small while compile time, memory and artifact size explode.
saying these in an interview costs you the question
- Says the compiler detects the expansion loop and reports it precisely
- Puts the base case in emitted code and expects rewriting to stop
- Thinks raising the depth limit is always the right fix
- Assumes recursive expansion output grows linearly however it splices
- Treats hitting the budget as proof the macro is buggy, never as a budget