How do you decide how many intermediate representation levels a small language's compiler should carry between its syntax tree and target code?

## What a level is for An intermediate representation level is a **vocabulary**: a set of node or instruction kinds, and the invariants they obey. Work is easy at a level when the thing the work reasons about is expressible in that vocabulary, and hard when it is not. That is the whole basis for the decision — not the number of boxes in a pipeline diagram. The classic three-level shape: 1. **Near the source.** Constructs are intact, names and positions are attached, surface structure is visible. Only here can work that must *recognise a construct* run — once an iteration has become a test and two jumps, the fact that it was an iteration is gone unless something reconstructs it. 2. **Flat and machine-independent.** Expressions are broken into simple instructions, control flow is explicit, intermediates are named. Order and provenance are written down, which is what most rewrites want. 3. **Near the target.** Address arithmetic, calling conventions and target-specific operations are explicit. Decisions that depend on the machine belong here and nowhere above. ## The cost side, stated plainly Every level you add is a permanent tax: - another data structure, with its own construction and invariants; - another **lowering step** from the level above, which must be correct for every construct; - another **printer**, because a level you cannot read is a level you cannot debug; - another **verifier**, or you will ship malformed intermediate code and find out three stages later; - another hop across which **source positions and debug information** must be carried, or diagnostics degrade; - another place a bug can hide, and one more boundary every new contributor must learn. None of that is paid once. It is paid on every future change, by everyone. ## The decision rule **Add a level when a class of work is natural at it and awkward at both of its neighbours — and not otherwise.** Concretely, the signals that justify a split: 1. A rewrite you want needs structure the lower level has destroyed, and reconstructing that structure is itself a project. 2. Target-specific detail is leaking upward and making a level that was meant to be machine-independent carry machine assumptions. 3. One level's invariants are being violated in two different modes by different passes, which usually means it is really two levels wearing one name. 4. You have more than one target, and everything above the divergence point is genuinely shared. Signals that do **not** justify a split: the node kinds have grown numerous; the pipeline diagram in a paper has more boxes; a contributor would like a nicer printed form (that is a printer, not a level); a pass is slow. ## Sizing it for the case in hand For a small stream-transformation language with one target, a small team and a compiler you intend to keep for years: | Levels | Fits when | Watch for | |---|---|---| | Syntax tree only | The output is another high-level form, or a straightforward walk emits the target | Any analysis needing order or provenance becomes painful | | Tree plus one flat level | The common case — construct-aware work above, everything else below | Target detail creeping into the flat level | | Three or more | Several targets, or a genuinely distinct near-machine vocabulary | The lowering steps and verifiers becoming the bulk of the work | The trajectory that usually goes wrong is the opposite of the one people fear. Teams rarely regret starting with two; they regret starting with four, because each was defensible on paper and the cost only showed up as the pace of every later change. ## The things you must preserve across every level Whatever number you land on, three obligations cross all of them, and they are the ones that get forgotten in the design discussion: 1. **Position mapping**, so a message about generated code can be phrased in terms of what the programmer wrote. 2. **A printed form per level**, so a defect can be localised to a lowering step rather than bisected through the whole compiler. 3. **A verifier per level**, so the invariants you are relying on are checked rather than assumed. A team that adds a level without adding these three has bought the cost without the benefit. ## What interviewers listen for This has no single right answer, and the interviewer is listening for the shape of the reasoning: does the candidate tie levels to *classes of work*, do they name the recurring cost rather than only the structural elegance, and do they have a default they would actually start from and a named trigger for changing it? An answer that recites three levels because that is the standard picture, with no account of what each one earns, misses the question.