Questions: Certified Compilation

Question 1

A compiler is 'certified' if its output is proven to preserve program semantics. What does 'preserve semantics' formally mean?

Model answer: Semantic preservation means: for any source program P and any input I, if P produces output O (or diverges, or crashes), then the compiled code produces the same output O (or diverges, or crashes identically). Formally, this is expressed as a **simulation** or **bisimulation** relation: the compiled code's execution trace matches the source code's trace up to irrelevant differences (like variable names or intermediate machine states). The proof establishes that no behavior of the source program is changed by compilation.

This is a theorem of the form: ∀ source, compiled. compile(source) = compiled → ∀ input. semantics(source, input) ~ semantics(compiled, input), where ~ is a simulation or bisimulation relation. The proof is done in a proof assistant (Coq, Isabelle, Agda), making it machine-checkable. The key is that semantic preservation is stronger than 'the compiler doesn't crash' — it says the compiler's output has the exact same behavior as the input.

Question 2

CompCert is verified in Coq and handles a subset of C. Why not verify a compiler for the full C language?

Model answer: Verifying a compiler requires: (1) a formal semantics of the source language (every rule, every edge case), (2) a formal semantics of the target language (the machine/virtual machine), (3) proof that every transformation preserves semantics. Full C has thousands of pages of specification, undefined behavior in many contexts, and complex interactions between features (pointer arithmetic, type casting, volatile access). Verifying all of this is infeasible within reasonable effort. CompCert handles a safe subset of C (excluding undefined behaviors, dangerous casts, etc.), which is suitable for many real applications. Full verification of realistic languages remains an active research area.

This is a fundamental tension in certified compilation: completeness vs. tractability. A complete compiler for full C would be incredibly difficult to verify because the semantics is complex and sometimes underspecified. CompCert made a strategic choice: verify a safe subset thoroughly rather than attempt a fragile claim about the full language. In practice, many critical systems don't use the dangerous corners of C anyway, so CompCert's scope is reasonable. As proof assistant tooling and proof techniques improve, the scope of certified compilers expands.

Question 3

A certified compiler must prove a simulation relation between source and compiled code. Which of the following can be assumed as part of the proof, and which must be verified?

• A. The source language semantics and the target language semantics are both assumed; only the transformation is verified
• B. All of these are assumed — the compiler is certified by testing
• C. The source language semantics must be verified, but the target language (hardware) semantics is assumed
• D. The source language semantics is given; the target language semantics is given; the transformation (each optimization pass) is verified to establish a simulation

Answer: (D)

In certified compilation, the source and target language semantics are **given** (formalized in the proof assistant, not proven). These are the inputs to the certification effort. The **transformation** — the actual compiler code and its optimization passes — is what is verified. Each pass (constant propagation, dead code elimination, register allocation, etc.) is verified to preserve semantics: given any source program satisfying the source semantics, the output of this pass satisfies the target semantics. CompCert formalizes C semantics and x86 (or PowerPC) semantics, then verifies each pass.

Question 4

If a certified compiler has a bug in its output, what does that imply?

Model answer: Either: (1) the formal semantics of the source or target language is incorrect (doesn't accurately model the language), or (2) the proof itself has a bug (which is rare but possible if the proof assistant has a soundness bug). It does NOT imply a bug in the verified compiler transformation, because the transformation is machine-checked by the proof assistant. The power of certified compilation is that bugs in the transformation are impossible — the machine-checked proof provides absolute assurance of the compiler's correctness (modulo the semantics and the proof assistant).

This illustrates the scope of certification: the proof is only as good as its inputs (the semantics) and the tool that checks it (the proof assistant's kernel). In practice, the semantics of C and x86 used in CompCert are carefully validated against the official specifications, and the Coq kernel is extensively tested. The result is compiler correctness with extremely high confidence — far higher than any compiler verified by testing alone.