Loweringspec

Desugaring

The pass that rewrites high-level syntax into a core language every later phase can assume. Doing it early makes every later phase simpler; doing it early is also how compilers end up reporting errors about code nobody wrote.

The question

When in the pipeline should high-level syntax be rewritten into the core language, and what does the choice cost?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute
What the program is here

Two trees, and the pass between them. The input is the surface AST — one node kind per construct the grammar has. The output is a core AST with a deliberately small node vocabulary: calls, branches, loops, bindings, and little else. The core exists to answer one question for every subsequent phase, which is "how few cases do I have to handle", and the whole design tension of this lesson is that the surface tree answers a different and equally necessary question: "what did the user actually type".

What this phase may assume or do

A desugaring is legal only if the core program has the same observable behavior as the surface program for every input, including the order and number of evaluations, the short-circuiting the surface form promised, and the exceptions or traps that occur. Any temporary the pass introduces must be fresh — capable of colliding with no user name — and any subexpression the surface form evaluated once must be bound to a temporary rather than duplicated. The pass may assume the program parsed; it may not assume it type-checked, unless it runs after the checker, which is exactly the ordering decision the lesson is about.

Key points

  • Desugaring rewrites surface constructs into a deliberately small core language that every later phase can assume.
  • The rewrite must preserve evaluation order, evaluation count, short-circuiting and trapping — not merely the result.
  • Desugaring early multiplies out of the pipeline: N passes over M constructs becomes N passes over a handful.
  • Desugaring early also destroys the ability to report errors about constructs the user actually wrote.
  • Modern frontends keep the surface tree because they are also language servers, formatters and refactoring engines.
  • Introduced temporaries must be un-nameable by the user, and introduced nodes must carry the surface span plus a "generated" marker.
  • A C-style for cannot be rewritten as a while with the step at the end of the body — continue would skip the step.

One rewrite, and what it must not lose

The canonical example is the for loop, because every language has one and no language executes one. for item in collection is defined in terms of an iteration protocol: obtain an iterator from the collection, ask it repeatedly for the next element, bind the element, and stop when it says there are no more. That is four operations and a loop, and the source shows none of them.

The rewrite below is the shape every mainstream language uses, with the protocol details changed. It is worth reading for what it introduces rather than for what it removes: a temporary holding the iterator, a loop whose condition is a call, and an explicit binding. Each of those is a thing the back end already knows how to compile, which is the entire point.

And it is worth reading for what it must not do. The collection expression is evaluated once, before the loop; a rewrite that re-evaluates it per iteration turns for x in expensive() into a program that calls expensive() on every step. The iterator temporary must be fresh, or a user variable named it in the loop body is captured by the compiler.

A for-in loop desugared into the iteration protocol
Before
for item in collection {
    body(item)
}
After
let $it = collection.iterator()      // evaluated exactly once
loop {
    match $it.next() {
        None       => break,
        Some(item) => { body(item) }
    }
}
Legal only when

Only if collection is evaluated exactly once and before the first iteration, the temporary $it cannot collide with any name the user can write, break and continue in the body still target this loop, and the iterator protocol's exhaustion signal terminates the loop rather than propagating as an error. If the language permits the collection to be mutated during iteration, the rewrite must also preserve whatever the language promises about that — usually that it is an error, detected by the iterator.

Illegal when

If the rewrite inlines collection into the loop condition, so for x in expensive() calls expensive() once per iteration. If the introduced temporary uses a writable identifier and the loop body declares its own it, which then silently shadows the iterator. And if the language's for has a semantics the protocol does not model — a C-style for(init; cond; step) with a continue in the body must still run the step expression, so rewriting it as a while with the step at the end of the body changes the meaning of every continue.

Early desugaring simplifies everything after it

Suppose the core language has one loop form. Then the CFG builder has one loop case, the liveness analysis has one loop case, the optimizer has one loop case, and the code generator has one loop case. Add while, for-in, do-while, repeat-until and a comprehension as distinct core constructs and you have multiplied five passes by five forms, and each of the twenty-five combinations is a place a bug can live and a test that has to exist.

This is why compilers with large back ends desugar hard and early. GHC is the extreme and the clearest illustration: Haskell's enormous surface syntax — do-notation, list comprehensions, where clauses, guards, sections, typeclass method calls — is desugared into Core, a tiny lambda calculus with nine constructors, and every optimization GHC has is written against those nine. The optimizer is simple because the language it optimizes is small.

The saving compounds in a way that is easy to underestimate. It is not just fewer cases per pass; it is that every *invariant* the core guarantees can be relied on everywhere. If the core has no expressions with statements inside them, no pass ever has to ask. If the core binds every intermediate value to a name, every analysis has something to attach a fact to.

Surface node kinds versus core node kinds, for one small language
Surface AST node kinds
For, While, DoWhile, ForIn, Comprehension
If, Match, Ternary, And, Or, Not
Call, MethodCall, OptionalCall, Index, OptionalIndex
Assign, CompoundAssign, Increment, Decrement
Let, Destructuring, Interpolation, Lambda
Core node kinds after desugaring
▸Loop { body }  + Break/Continue
▸If { cond, then, else }
▸Call { callee, args }
▸Let { name, init }  + Assign { name, value }
▸Lambda { params, body }

Read it asTwenty surface kinds become five. Every pass written after this point handles five. The information that was in the other fifteen has not been destroyed — it has been re-expressed using the five — but the *name* of the construct is gone, and with it the ability to say "you wrote a comprehension and it has a type error" rather than "this call to map has a type error".

Which is exactly why compilers stopped doing it early

implementationThe three-tree shape describes rustc (AST, HIR, MIR) and, with different names, Swift and Kotlin. It does not describe GHC, which desugars to Core very early and accepts the diagnostic cost as a deliberate trade, nor CPython, which compiles the AST almost directly to bytecode with no core language in between. A claim about when desugaring happens is a claim about one compiler, and it changes between major versions of the same compiler.

The counter-pressure is diagnostics, and it is decisive in modern language design. A compiler that has already rewritten a comprehension into a chain of calls cannot report an error about the comprehension. It reports an error about the chain of calls, mentioning names the user never typed, at spans that point into the middle of their expression. Everyone who has read a Haskell type error about a monad the source does not mention has met this.

The pressure got stronger when compilers became the backing implementation for editors. A language server must answer "what is under my cursor", "rename this", "what does this comprehension iterate over" — all questions about the surface form. A frontend that desugars in the parser cannot serve those queries at all, which is why the same frontend now maintains the surface tree far longer than a batch compiler would need to.

The standard resolution is a middle tree: keep the surface AST for the tools and for diagnostics, desugar into a *high-level IR* after type checking, and desugar again into the real IR after that. Rust names these explicitly — AST, then HIR, then MIR — and each drop in level is a batch of surface forms disappearing. Swift, Kotlin and modern C++ frontends all have some version of this shape. The cost is that a frontend now maintains three representations of every program and the mapping between them, which is a substantial amount of the code in any modern compiler.

Where the sugar goes in a frontend that keeps the surface formimplementation
  1. Surface ASTbuild time
    One node per construct the grammar has, with spans into the original text.
    Everything the tools need: what the user typed, where, and in what form.
  2. Name-resolved ASTbuild time
    The same tree with every identifier bound to a declaration.
    Which declaration each name refers to, under the scope rules.
  3. Typed ASTbuild time
    The same tree with a type on every expression.
    That the program is well-formed, and what each construct means for its operand types.
  4. High-level IRbuild time
    A tree over a smaller core vocabulary, still with control flow as a tree.
    The names of the surface constructs. A comprehension is now a call chain and there is no node saying it was ever anything else.
  5. Control-flow IRbuild time
    A control-flow graph over three-address instructions.
    Explicit blocks and edges, so data-flow analysis becomes possible.
    Structured control flow. A loop is now a back edge, and reconstructing which source loop it was requires metadata.

Read it asRead the loses column: the ability to say "your comprehension" dies at the high-level IR, and the ability to say "your loop" dies at the control-flow IR. Every diagnostic a compiler emits after those points either carries a span recorded before them or is about a construct the user did not write. This is the same argument as [[information-loss]], applied to one specific piece of information.

The pass itself

Mechanically a desugaring pass is a tree rewriter — the standard shape being a visitor that returns a new node for each surface node it recognises and copies everything else. Two disciplines separate a correct one from a plausible one.

First, hygiene. Every temporary the pass introduces must be in a namespace the user cannot write into, or the rewrite captures user names. Lisp macro systems made this a named problem and solved it with gensym and hygienic expansion; a compiler's internal desugarer has the same problem in a smaller form and usually solves it by giving temporaries names containing a character the lexer rejects.

Second, spans. Every introduced node carries a span pointing back at the surface construct it came from, and typically a marker saying it was introduced rather than written. Without the span, diagnostics and debug information point nowhere. With the span but without the marker, a debugger will happily step onto a line the user did not write and stop there, which is worse.

  • Rewrite bottom-up, so nested sugar is already core by the time the outer construct is rewritten.
  • Bind every subexpression the surface form evaluated once to a fresh temporary before duplicating any reference to it.
  • Name temporaries so they cannot collide with any identifier the lexer accepts.
  • Attach the surface span to every introduced node, plus a flag distinguishing written code from generated code.
  • Run the same verifier over the output that runs over hand-written core, so a bad rewrite fails loudly rather than compiling to something odd.

How it works

The steps, in the order the compiler takes them.

  • A visitor walks the typed AST bottom-up so that nested sugar is already in core form before an enclosing construct is rewritten.
  • For each recognised surface node, the pass emits a subtree built only from core constructs, binding any once-evaluated subexpression to a freshly generated name first.
  • Fresh names are drawn from a namespace the lexer cannot produce, so no user identifier can collide with or shadow them.
  • Each emitted node inherits the span of the surface node it replaces, plus a flag marking it as compiler-generated so debug information can skip it.
  • Control-flow-carrying constructs are rewritten with their break, continue and return targets rebound explicitly, since the enclosing loop in the core form is a different node from the one in the source.
  • An IR verifier runs over the result and rejects any node kind outside the core vocabulary, which is what stops a partially-implemented rewrite from reaching the optimizer.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

  • A type error names Iterator, IntoIterator or a monad the source does not mention, and the engineer cannot connect it to any line they wrote.
  • A loop over an expensive call becomes quadratic because the desugaring re-evaluated the collection expression per iteration; the symptom is a performance cliff with no change in the source.
  • A user variable is silently captured by an introduced temporary with a nameable identifier, and a loop body reads the iterator instead of its own variable.
  • A continue inside a rewritten C-style for stops running the step expression, producing an infinite loop that only triggers on the path containing the continue.
  • A debugger stops on a line the author did not write, or steps repeatedly over one source line, because generated nodes carried real spans without a generated marker.
  • A lint or a borrow check runs after desugaring and reports on the expansion, so a suggested fix rewrites code that does not exist in the file.

When it helps

  • Any compiler with a substantial middle end, where the cost of a construct is paid once per pass rather than once.
  • Languages with large surface syntax and a small semantic core, where the ratio is most favourable — Haskell is the extreme case.
  • Shrinking the surface a verifier or a formal semantics has to cover, which is how verified compilers keep their proof obligations finite.

When it hurts

  • When diagnostics matter more than pass simplicity, which is most of the time in a language people are learning.
  • When the compiler is also the editor backend, where every desugared construct is a query the language server can no longer answer.
  • When the surface construct has a semantics the core cannot express without a contortion, at which point the rewrite becomes the source of subtle bugs.
  • When the rewrite happens before type checking, so the checker sees calls it cannot attribute and the inference errors become unreadable.

What it costs

Every one of these is paid by something.

  • A smaller core buys fewer cases in every later pass and a smaller verifier, and pays in diagnostic quality: no phase after the rewrite can name a construct the rewrite removed.
  • A later desugaring buys precise errors, working editor tooling and honest debug information, and pays in frontend complexity — every pass before the rewrite must handle every surface form.
  • Maintaining both trees (surface plus core, or AST plus HIR plus MIR) buys both properties and pays in memory, in the mapping between representations, and in the discipline of keeping them consistent as the language grows.
  • Hygienic temporaries buy freedom from capture and pay in debuggability: dumps and stack traces are full of names no human chose, and every tool that prints a variable has to decide whether to hide them.

What else you could do

What a different compiler or language does instead, and when that is better.

  • Do not desugar at all — give each surface construct its own path through the back end. Feasible for a small language, and the standard approach for a tree-walking interpreter, where the interpreter loop simply has more cases.
  • Desugar in the parser, which is what CPython largely does. The parser is simpler than a separate pass and the error messages are consequently reported against bytecode-level constructs.
  • Expose the desugaring to users as a macro system, so the core is small *and* the surface is extensible. Rust and Lisp do this, and pay for it with expansion-time diagnostics and a language whose reader must know which forms are macros.
  • Keep the sugar all the way to code generation and let the back end pattern-match on it, which is how some JIT compilers keep enough information to emit a specialised sequence for a common surface idiom.

See it for yourself

The flag, dump or tool that shows you this directly.

  • Rust: rustc -Z unpretty=hir on nightly prints the tree after most desugaring — for loops appear as loop/match and ? appears as a match on Try. rustc -Z unpretty=mir goes one level further to the CFG.
  • Haskell: ghc -ddump-ds dumps the program immediately after desugaring to Core, and -ddump-simpl after the simplifier. The size difference between the source and the Core is the point.
  • Python: ast.dump(ast.parse(src)) shows what survives as nodes, and dis.dis shows what the compiler emitted. Comprehensions are notable — they become a separate code object.
  • JavaScript: run the source through a transpiler targeting an older standard and diff. Async functions, classes, optional chaining and destructuring each show a different rewrite shape.
  • Our desugaring viewer at /compilers/lowering runs the AtlasLang desugarer live and highlights which core nodes came from which surface span.

Plausible wrong readings

Stated the way a confident engineer states them.

  • "Desugaring is a text transformation." It is a tree transformation, and for several constructs the correct tree contains bindings the text does not.
  • "If the compiler desugars it, I can write the desugared form myself and get identical code." Usually yes, and not when the rewrite uses names or intrinsics the surface language cannot express.
  • "Bad error messages are a quality problem the compiler team can just fix." They are frequently a consequence of when the rewrite happens, and fixing them means restructuring the frontend — which is why compilers do exactly that.
  • "A smaller core language is always the better design." It is the better design for the optimizer and the worse design for the person reading the error. Which one you are optimizing for is the actual decision.

Misconceptions

The claim, and what is actually true.

Desugaring happens right after parsing.
In a modern frontend most of it happens after name resolution and often after type checking, precisely so that errors can be reported against the surface form.
The core language is a subset of the surface language, so I could write core by hand.
Usually mostly true, and the exceptions matter: core forms often include intrinsics, hygienic names and control-flow constructs with no surface spelling.
A C-style for is a while with the step moved to the end of the body.
Not with a continue in the body, which must still run the step. The correct rewrite puts the step in a separate block that continue targets.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

Before doing real work, a compiler rewrites the convenient forms of the language into a handful of basic ones. A for loop becomes "get an iterator, call next, stop when it is empty". A ?. becomes a null test. After the rewrite there is much less to handle, so every later stage of the compiler is smaller.

practical

Two practical consequences. When a compiler error mentions something you did not write, dump the desugared form — every mainstream toolchain has a flag for it — and read the error against that. And when writing a rewrite yourself, in a macro or a code generator, the two things that go wrong are duplicating a subexpression that had a side effect, and generating a name that a user could also have chosen. Bind to a temporary, and make the temporary un-typeable.

advanced

Phase placement of the desugaring is one of the highest-leverage decisions in a frontend, because it determines the ceiling on diagnostics for the entire life of the language. Push it late and every pass before it pays: name resolution, type inference and borrow checking each need a case for every surface form, and the type checker in particular has to state typing rules for constructs that are not primitive. Push it early and the ceiling on error quality is set forever, because no later pass can reconstruct which surface form it was looking at. The observable trend is that languages designed after roughly 2010 push it late and add an intermediate tree, and languages designed for a powerful optimizer push it early — GHC and Haskell being the clearest example of the second, with error messages that are the standard criticism of the language.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

specSeveral desugarings are specified rather than chosen: the Haskell Report defines do-notation and list comprehensions by translation, and the Python language reference defines for in terms of iter() and __next__. In those cases a conforming implementation must produce the specified behaviour but is not required to implement it as a rewrite at all — CPython compiles for directly to FOR_ITER bytecode rather than emitting a call chain.
implementationRust desugars for, ?, if let, while let and async blocks during AST-to-HIR lowering, after macro expansion and name resolution but before type checking; the MIR build then removes structured control flow entirely. Kotlin and Swift place their equivalents differently, and rustc has moved individual desugarings between phases across editions. Do not carry a phase ordering from one compiler to another, or from one version to the next.
typicalMainstream compilers attach the surface span to generated nodes and mark them as compiler-generated, which is what lets a debugger skip them and a diagnostic point at real source. Compilers that skipped this — and several early transpilers did — produce stack traces that reference lines the user never wrote, and the fix is not local.

If you were asked this in an interview

  • Where in the pipeline would you desugar a for loop, and what does putting it earlier or later cost you?
  • Write the desugaring of a C-style for loop containing a continue. What is the trap?
  • Why do languages with the smallest core languages tend to have the worst error messages?

Connections

DSAbinary-treedfs
Backendparse-dont-validate