A compiler engineer wants to prove that replacing the expression 'x * 2' with 'x + x' is always valid. Which formal semantics approach most directly supports this?
AOperational semantics, by tracing execution steps and showing both evaluate to the same final value on every input
BDenotational semantics, because if two expressions have identical denotations they are guaranteed to behave identically in any context
CAxiomatic semantics, by writing a Hoare triple that holds for both expressions
DSyntactic analysis, because structurally similar expressions have equivalent behavior
Denotational semantics assigns each expression a mathematical object — its 'denotation' — independently of any execution strategy. If 'x * 2' and 'x + x' have the same denotation (they map to the same function from environments to values), they can be freely substituted in any context. Operational semantics can show equivalence by tracing specific examples, but it is harder to use for a general proof across all possible contexts. Syntactic analysis tells you nothing about behavior. Denotational semantics provides the clean algebraic framework that makes optimization proofs tractable.
Question 2 Multiple Choice
What is the correct interpretation of the Hoare triple {x > 5} x = x - 3 {x > 2}?
AThe program x = x - 3 is only allowed to execute when x > 5
BIf x > 5 holds before execution, then x > 2 is guaranteed to hold after execution
CAfter executing x = x - 3, the postcondition x > 2 implies x > 5 was true beforehand
DThe triple asserts that x = x - 3 transforms x > 5 into exactly x > 2
A Hoare triple {P} S {Q} is a partial correctness assertion: if the precondition P holds before executing S, then postcondition Q holds after. It says nothing about whether the program runs or whether the precondition is sufficient — only that P → (after S) Q. Option A mistakes the precondition for a guard. Option C reverses the direction of implication. Option D misreads the triple as defining an exact transformation. The triple is a one-directional guarantee from pre- to post-condition.
Question 3 True / False
Operational semantics defines the meaning of a program by specifying how it executes step by step, making it closely analogous to an interpreter specification.
TTrue
FFalse
Answer: True
True. Operational semantics provides reduction rules of the form 'expression e in state σ reduces to expression e' in state σ''. Small-step operational semantics makes every individual reduction step explicit, while big-step (natural) semantics goes directly from expression to final value. Both read like interpreter rules: 'to evaluate an if-then-else with a true condition, evaluate the then-branch.' This is why operational semantics is typically the first semantics a compiler writer learns — it directly guides interpreter and code generator implementation.
Question 4 True / False
A program that parses successfully according to a language's grammar necessarily has a well-defined, unambiguous meaning.
TTrue
FFalse
Answer: False
False. Syntax and semantics are independent. A program can be syntactically valid (grammatically well-formed) while being semantically undefined, ambiguous, or meaningless. Classic examples: 'int x = x + 1;' may be syntactically valid but semantically undefined (reading an uninitialized variable); 'a + b' in a language without operator overloading disambiguation may be syntactically valid but semantically ambiguous if + applies to multiple types. Syntax checking (parsing) is a prerequisite for semantics, not a substitute for it.
Question 5 Short Answer
Why is it not enough for a compiler to test an optimization on a large number of inputs to prove it is valid? What does formal semantics provide that testing cannot?
Think about your answer, then reveal below.
Model answer: Testing can only show an optimization produces the same output for specific inputs; it cannot rule out corner cases where behavior differs — edge inputs, unusual environments, non-terminating programs, or expressions embedded in complex contexts. Formal semantics provides a mathematical proof of equivalence that holds for all possible inputs and all possible contexts simultaneously. Denotational semantics in particular enables equational reasoning: two expressions with identical denotations are substitutable everywhere by definition, making the proof context-independent and unconditional.
The fundamental limitation of testing is that the number of possible program states and input combinations is typically infinite. A single counterexample disproves an optimization, but no finite set of examples can prove it universally valid. Formal semantics — especially denotational — turns the question into a mathematical one: are the two mathematical objects (denotations) identical? This proof strategy is used in modern compiler verification projects like CompCert, where the entire C compiler is proved correct using formal semantics, giving a guarantee that no amount of testing could.