The Questions a Language Definition Must Answer
A checklist that is not a checklist: nine questions every language answers whether or not its designers noticed, each with a compiler consequence, and each capable of contradicting the answer to another.
What do I actually have to decide to have a language, rather than a syntax?
The language definition, decomposed into the decisions it must contain: a lexical structure, a grammar, a name-binding discipline, a type discipline, an evaluation strategy, a mutability and memory model, an error model, a concurrency model and a module system. What this decomposition exists to answer is which of your decisions are still implicit — because an unanswered question is answered by the first implementation, permanently.
Each answer constrains what every later phase may assume, and the answers must be mutually consistent. Deciding that expressions are evaluated left to right forbids the optimizer from reordering side-effecting operands; deciding evaluation order is unspecified permits it and simultaneously forbids programmers from relying on it. A definition that answers two questions incompatibly — for instance, promising memory safety while permitting unchecked reinterpretation of memory — has not created a guarantee, it has created a bug report against itself.
Key points
- Every language answers all nine questions; the only variable is whether the answers were chosen or inherited from the first implementation.
- The answers constrain one another — mutability plus threads forces a memory model, laziness forces an effect discipline, subtyping plus full inference is a research problem.
- Each answer lands as a cost in a specific compiler phase, which is what makes design decisions traceable to build times and diagnostics.
- An unanswered question becomes an accidental guarantee that users depend on and later implementations get wrong.
- A one-page answer sheet and a conformance test suite are cheap at the start and are the only things that survive the original team.
Nine questions, and the phase each one lands in
These are not a menu. Every language answers every one of them, and languages that never discussed a question still have an answer, contributed by whoever wrote the first implementation. The value of the list is that it makes the implicit answers visible while they can still be changed.
| Question | What varies | Which phase pays |
|---|---|---|
| Lexical structure | Is layout significant? Are keywords reserved? Can identifiers contain the operator characters? | Lexer, and every editor and formatter afterwards — [[lexer-hazards]] |
| Grammar | Is it context-free? Is it ambiguous? Does parsing require type information? | Parser. C++ needs to know whether a name is a type to parse a declaration, which is why its parser cannot be separated from its semantic analysis — [[context-free-grammars]] |
| Name binding | Lexical or dynamic scoping? Is use-before-declaration legal? Does shadowing warn, error or bind? | Semantic analysis — [[static-vs-dynamic-scoping]], [[shadowing]] |
| Type discipline | Static or dynamic? Inferred or annotated? Nominal or structural? Sound or deliberately not? | Type checker, and the whole tooling story with it — [[what-a-type-system-proves]] |
| Evaluation strategy | Strict or lazy? Is argument evaluation order specified? Call by value, reference or sharing? | Lowering, which must fix an order, and every optimization that wants to move a computation |
| Mutability and aliasing | Is everything mutable by default? May two references to the same object exist? Is mutation through one visible through the other? | Alias analysis, and therefore most of the optimizer — [[alias-analysis]] |
| Error model | Exceptions, result values, panics, or error codes? Are errors part of a function's type? | Lowering and code generation: exceptions need unwind tables, results need no runtime support at all — [[exception-handling]] |
| Concurrency model | Shared memory with locks, message passing, async tasks, or none at all? | The optimizer, via the memory model, and the runtime — [[concurrency-model-choice]] |
| Modules and compilation units | What is separately compilable? What crosses a module boundary? Is there a cycle rule? | The build system and every incremental rebuild — [[compilation-units]], [[modules]] |
The answers interact, and that is where languages go wrong
Individually each question has several defensible answers. The difficulty is that they constrain each other, and the constraints are not obvious until an implementation exists.
Mutability interacts with concurrency: unrestricted shared mutable state plus threads forces you to define a memory model, which is the hardest document any language committee writes, and the alternative — restricting aliasing or restricting sharing — is a decision that must be made in the type system rather than the runtime. Rust made it in the type system; Erlang made it by forbidding sharing outright; Java made neither choice and produced the Java Memory Model, which took years and remains the part of the specification fewest of its users have read.
Type inference interacts with subtyping: full Hindley-Milner inference is decidable and pleasant, and adding subtyping to it is a research problem rather than an implementation task, which is why languages with rich subtyping ask for annotations at boundaries. See [[hindley-milner]] and [[subtyping]].
Lazy evaluation interacts with the error model and with effects: if arguments are not evaluated until used, then when an argument throws is no longer determined by the call, and reasoning about side effects requires something like a type-level marker. Haskell's IO type is not a stylistic preference; it is what laziness cost.
Unanswered questions get answered anyway
The most expensive category is the question nobody realised was a question. Whatever the first implementation happens to do becomes the answer, users depend on it, and it is now the definition — with the additional problem that nobody wrote it down, so the second implementation gets it wrong and is blamed.
Integer overflow is the standard example. C left signed overflow undefined, which turned out to license a large body of optimization and a large body of security vulnerabilities. Java defined wrapping, which is predictable and silently wrong for arithmetic on quantities that should not wrap. Rust defined both — panic in debug, wrap in release — which is a deliberate answer to a question C left implicit, and is itself criticised for making the two profiles behave differently.
Dictionary iteration order, string encoding, the identity of small integers, whether closures capture by value or by reference, and whether a for loop variable is fresh per iteration have all been accidental answers in at least one mainstream language, and at least one of them has been changed later at real cost. JavaScript changed let semantics relative to var precisely to fix the loop-variable capture answer without breaking existing code.
Write the answers down before the implementation
The practical discipline is to write a small document answering all nine questions before writing the lexer, and to write example programs that pin the answers you care about. Not a specification — a page. What it buys is that the first implementation implements a decision instead of making one.
The second discipline is a conformance test suite that encodes the answers as executable examples. It costs a few days at the start and is the only mechanism that survives the original designers leaving. WebAssembly did this from day one and has multiple independent conforming implementations as a result; most languages did not, and have one implementation and a folklore.
How it works
The steps, in the order the compiler takes them.
- Answer the nine questions explicitly, in writing, and note for each the phase that will bear the cost.
- Check each pair of answers for interaction, paying particular attention to mutability against concurrency and inference against subtyping.
- Write example programs whose behavior pins each answer, including the ones you consider obvious.
- Implement the lexer and parser against the grammar answer, and the checker against the type and binding answers, refusing to let the implementation decide anything the document did not.
- Encode the examples as a conformance suite so a second implementation can be checked rather than argued with.
How it breaks
What the engineer observes when it goes wrong — not what goes wrong internally.
- A second implementation of the language is written and is immediately declared buggy, because it made different choices in the places the definition was silent.
- A program compiles and behaves differently under two versions of the same compiler, because an unspecified evaluation order changed with an optimizer improvement.
- A concurrency bug appears only on one processor architecture, because the language never defined a memory model and the implementation inherited the hardware's.
- A feature is added years later and interacts catastrophically with an early implicit decision, producing a rule that requires three paragraphs to state and that nobody remembers.
- A language is criticised for a behavior its designers never chose — it was in the first implementation, it was never questioned, and by the time anyone noticed there were a million programs relying on it.
When it helps
- Starting a new language or a DSL, where an hour spent on this list saves a permanent design defect.
- Reviewing a language proposal: the fastest way to find the flaw is to ask which of the nine answers it changes and what else depended on the old one.
- Learning an unfamiliar language quickly: reading its answers to these nine questions gets you further than any tutorial, because everything else is a consequence.
When it hurts
- Treating the list as a specification. A real definition needs far more; this is the set of decisions, not the document that records them.
- Answering all nine maximally strictly on the theory that guarantees are free. Each one excludes programs, and a language that answers every question strictly is a language whose audience has to fight it constantly.
What it costs
Every one of these is paid by something.
- Specifying an answer tightly buys cross-implementation agreement and programmer confidence, and costs every optimization that the freedom would have permitted — pinning evaluation order forbids reordering side-effecting operands forever.
- Leaving an answer open buys implementation freedom and performance, and costs the programmer: unspecified behavior is a bug that only appears when the compiler changes, and undefined behavior is worse.
- Writing a conformance suite up front costs weeks of work before the language does anything useful, and buys the ability to have more than one implementation ever.
What else you could do
What a different compiler or language does instead, and when that is better.
- Define the language by a reference implementation and accept a single implementation forever, which is a reasonable trade for an internal DSL and a poor one for infrastructure —
[[dsl-tooling-cost]]. - Define it by a mechanised semantics that is itself executable, as WebAssembly and Standard ML do, buying provable properties at the cost of a document most users cannot read.
- Adopt an existing language's answers wholesale by embedding in it, which is what an internal DSL does and what removes eight of the nine questions from your plate —
[[internal-vs-external-dsl]].
See it for yourself
The flag, dump or tool that shows you this directly.
- For any language you use: find its answer to argument evaluation order.
python -c "def f(a,b): pass"with side-effecting arguments, or a C program withf(i++, i++), will show you whether it is specified, and the specification will tell you whether you may rely on it. - Find its answer to integer overflow by overflowing one deliberately in debug and release builds, and compare.
- Find its answer to closure capture by building a list of closures in a loop and calling them afterwards. The result is a one-line summary of a design decision.
- Read the language's own conformance suite if it has one; if it does not, that is itself the answer to how many implementations it will ever have.
Plausible wrong readings
Stated the way a confident engineer states them.
- "These are advanced questions for language committees." They are decided in the first week of any language's life, including yours, by whoever writes the evaluator.
- "Leaving it unspecified keeps our options open." It keeps the *implementation's* options open and closes the programmer's, and it does so silently, which is the worst combination of the two.
- "Syntax first, semantics later." Semantics constrain syntax more than the reverse: a language whose parse depends on type information has already decided that its parser and type checker cannot be separated, which affects every tool anyone ever builds for it.
- "We can specify it once we see what people do." What people do will be what the first implementation permitted, and by then specifying anything else breaks their code.
Misconceptions
The claim, and what is actually true.
Go deeper
The same idea at increasing depth. Stop wherever it stops being useful.
overview
Having a language means answering nine questions: how it is tokenised, how it is parsed, how names bind, how types work, when expressions are evaluated, what can be mutated and shared, what happens when something goes wrong, how concurrency works, and what a module is. If you do not answer one, your first implementation answers it for you and the answer becomes permanent.
practical
Write the nine answers on one page before writing the lexer. Then write ten small programs whose behavior pins the answers you care about most — evaluation order, overflow, closure capture, shadowing — and make them the first tests. Every hour of this is worth a month later, and the failure to do it is why so many languages have exactly one implementation.
advanced
The questions are not independent and the dependency graph has a shape worth knowing. Mutability and sharing sit at the root: answer them permissively and you owe a memory model, an alias analysis and a concurrency story that must all be consistent with each other. Evaluation strategy sits next to the error model, because when something happens determines when it can fail. Type discipline constrains inference, inference constrains subtyping, and subtyping constrains variance, which is why languages tend to pick a coherent cluster rather than best-of-breed answers. The languages that feel arbitrary are usually the ones that took answers from different clusters.
How much this depends on
Nothing in this domain is true of every compiler. These say how much.
let per-iteration binding was introduced in ES2015 specifically because var had answered the question the other way.If you were asked this in an interview
- Name three decisions a language definition must make that are not about syntax, and say which compiler phase pays for each.
- Why does permitting shared mutable state across threads oblige you to write a memory model?
- What is the difference between unspecified and undefined behavior, and why does it matter to a programmer rather than to a compiler writer?
Connections
- Testing & Reliability Engineering — Conformance suites and executable specifications as a testing practicePinning a language's answers with executable examples is an instance of specification testing. The technique is general and owned there; what is ours is which answers must be pinned and what happens when they are not.