skip to content

What can a transformer that rewrites a parsed tree reject that a text-substituting shorthand cannot?

level: seniorimportance: should knowfreq 40%

answer

  1. characters versus parsed nodes
  2. counting separators is not shape
  3. arity, kind, well-formedness
  4. types only where types are resolved
  5. refuse at the caller's own position

basics

~20 s

A tree transformer is handed parsed nodes, so it can refuse a call whose arguments are the wrong number or the wrong kind of construct, and report that at the caller's position. A paste has only characters.

solid answer

~50 s

The difference is what each facility is handed. A paste receives characters; at that moment there is no expression, statement or type in existence, so it can only substitute and let the parser discover the damage wherever it surfaced. A transformer receives the call as a node with its arguments already parsed, so before emitting anything it can check the **count** of arguments, the **kind** of each one — expression or declaration — and the **well-formedness** of the node it returns; where it runs after types are resolved, it can check those too. It can also attach the caller's position to a message, so the report lands on code the author wrote. A facility with a declared parameter list can count separators, but counting is not knowing each argument is one well-formed expression. The guarantee is structural, not semantic: a transformer can still build a tree that means the wrong thing.

code

pseudocode · 12 lines
pseudocode
// text level: the shorthand pastes, then the grammar objects somewhere else
define LARGER(a, b) as ( if (a) > (b) then (a) else (b) )

// tree level: handed nodes, it can refuse before emitting anything
transform LARGER(call):
    if count(call.arguments) != 2:
        reject "expected two expressions" at call.position
    if not isExpression(call.arguments[0]):
        reject "first argument must be an expression" at call.arguments[0].position
    left  = call.arguments[0]
    right = call.arguments[1]
    return Conditional(Compare(">", left, right), left, right)

go deeper

for a junior

Recall the basic split: one facility works on characters before parsing, the other on already-parsed structure, and only the second can look at an argument as a thing rather than as text.

for a middle

List what structure makes checkable — argument count and kind, the well-formedness of the produced node — and say why none of that exists at paste time.

for a senior

Be precise about the limits: types only where they are resolved, positions only if carried through, and structural checking that still permits a well-formed tree with the wrong meaning.

for a principal

Weigh the checking a rewrite buys against what it costs to own — a program producing programs, with its own tests, its own maintainers and its own diagnostic quality bar.

## What each facility is handed Everything here follows from one difference, and it is worth stating before any list of capabilities: - A **text-level paste** is handed characters. It runs before the grammar, so there is no expression, no statement, no declaration and no type in existence yet — only runs of characters and whatever separators the facility was told to split on. - A **tree-level transformer** is handed the call as a node, with each argument already parsed into a node of its own, and it returns a node. Everything one can check and the other cannot is a consequence of that, not an accident of how the two were implemented. ## What a paste can and cannot establish It is easy to overstate this, so be precise. A text facility that declares a parameter list is not completely blind: it can count the separators at a call site and complain when the count does not match, and a reasonable implementation respects grouping while doing so. What it cannot do is anything about **shape**: - It cannot tell whether an argument is one well-formed expression or a fragment that only becomes grammatical because of the characters surrounding it after the paste. - It cannot tell an expression from a declaration, a statement or a stray token run. - It cannot know a type, because types are resolved long after it has finished. - It cannot check that its own output is well formed — the output is characters, and their grammaticality is discovered later, by the parser, at whatever position the damage surfaced. That last point is the practical one in a real codebase: the paste cannot **refuse**, so every failure it causes is reported by something downstream, in text nobody wrote. ## What a tree rewrite can refuse, before emitting anything 1. **Arity and argument kind.** The call node carries its arguments as a list of nodes. Their number and their kind are both inspectable, so "this takes two expressions and you gave it one expression and a declaration" is a message the transformer itself can produce. 2. **Well-formedness of the output.** The transformer constructs the result out of node-building operations, and a node that cannot be built is an error at construction time rather than a mystery for the parser. 3. **Type information, where the transformer runs where types are already resolved.** This one is conditional and depends on the facility: a rewrite positioned before type resolution has structure but no types, and claiming otherwise is a common overstatement. 4. **Position-accurate diagnostics.** Each node carries the position of the source it came from, so the transformer can report against the caller's own line rather than against generated text — but only if it deliberately carries those positions through, which is work, not a freebie. ``` // text level: the paste happens, the grammar objects later, somewhere else define LARGER(a, b) as ( if (a) > (b) then (a) else (b) ) // tree level: the transformer is handed nodes and can refuse the call transform LARGER(call): if count(call.arguments) != 2: reject "expected two expressions" at call.position if not isExpression(call.arguments[0]): reject "first argument must be an expression" at call.arguments[0].position return Conditional(Compare(">", call.arguments[0], call.arguments[1]), call.arguments[0], call.arguments[1]) ``` ## Where the guarantee stops | Property | Text paste | Tree rewrite | |---|---|---| | Argument count | separators can be counted | inspectable as a list of nodes | | Argument shape | not knowable | node kind is inspectable | | Types | not knowable | knowable only where types are already resolved | | Output well-formedness | discovered by the parser | checked while building the node | | Diagnostic position | inside the expanded characters | the caller's position, if carried through | | Wrong *meaning* | possible | still possible | The last row is the one a strong candidate volunteers unprompted. Structural checking is not semantic correctness. A transformer that dutifully verifies two expression arguments and then returns a comparison with its operands swapped produces a perfectly well-formed tree that computes the wrong answer, and no amount of arity checking catches it. What the tree level buys is that a whole family of failures — regrouped expressions, statements falling out of branches, errors reported against generated text — stops being possible by accident. ## What those checks cost - The transformer is ordinary code written against the language's own tree shapes, so it must be maintained as those shapes evolve, and fewer engineers on a team can read it. - It needs tests of its own, because it is a program that produces programs. - Carrying positions and producing readable messages is deliberate effort; skipping it gives back exactly the diagnostic problem the paste had. - A paste is a few characters in a header-like declaration, and for a genuinely trivial one-expression shorthand that cheapness is a real argument.

  • Why is it wrong to say a text-level facility cannot check anything about its arguments?
    Because one with a declared parameter list can count the separators at a call site and reject a mismatched count. The honest limit is shape, not counting: it cannot tell whether each argument is one well-formed expression, what kind of construct it is, or what type it has, since none of those exist before the grammar runs.
  • A transformer checks arity and argument kinds and still ships a wrong result. What did the checking not cover?
    Meaning. Those checks are structural: they establish that the input is the shape the rewrite expects and that the output is a buildable node. Nothing in them says the node computes what the author intended, so a swapped operand or an inverted comparison passes every check and produces a well-formed, wrong program.
  • Why can a transformer's diagnostics still land on generated code?
    Because position is data on a node, not a property of the rewrite. If the transformer builds new nodes without copying positions from the caller's nodes, the resulting report points at code that exists only after the rewrite — the same complaint made against pasting, arrived at a different way.

saying these in an interview costs you the question

  • Says a text-level facility cannot even detect a mismatched argument count
  • Claims a tree rewrite guarantees the output means what was intended
  • Assumes a rewrite always has type information available to it
  • Thinks a transformer inspects the values the arguments will evaluate to
  • Believes good caller-side diagnostics come for free with a tree rewrite