Languages & compilers

A grammar can encode precedence through separate nonterminals. Associativity determines how repeated operators group at one precedence level.

The first tree is Add(Mul(Neg(2),3),4), evaluating to−2. The second is Add(2,Mul(3,4)), evaluating to 14. The ambiguous grammar also permits Mul(Add(2,3),4), evaluating to 20, so the same token sequence has two meanings unless an extra disambiguation rule is supplied.

Extend E to T {( + | − ) T}. Folding the repetition left gives Sub(Sub(8,3),2)=3. A right fold would give Sub(8,Sub(3,2))=7 and violate the stated associativity. Unary minus remains in U, so it binds more tightly than multiplication in this toy language.

A lexer recognizes tokens and can reject an unsupported character or malformed numeral under its lexical rules. A parser can reject a valid token sequence such as 2+*3 or an unmatched parenthesis because it has no grammatical structure. Neither phase establishes all semantic properties, such as whether a referenced name exists or a division will use zero.

Check your reasoning

• Draw trees that make precedence and associativity visible.
• Give two interpretations to demonstrate ambiguity.
• Distinguish lexical, grammatical, and semantic rejection.

d and c name the same closure; e comes from a different factory invocation. Lexical scope follows definition environments, not spelling alone.

The results are 1,2,1,3. c and d reference one closure with one mutable cell for n; e references a separate closure with a separate cell. Each factory call creates its own binding even though both variables are named n in the source. Assigning d=c copies a function reference, not the captured environment.

For make_adder(x), the returned function resolves x through the environment captured at its definition. An unrelated caller variable named x does not replace that binding. If the captured binding itself is mutable and the language permits mutation, later changes to that binding can be observed; lexical scope is not a universal promise of value snapshots.

A closure that survives the call cannot safely retain a pointer into a stack slot that will be reused. Implementations can move captured cells to longer-lived storage, close upvalues when a frame exits, or use another representation preserving lifetime and sharing semantics. Copying the value separately into c and d would be wrong for the mutable-counter contract because updates must remain shared.

Check your reasoning

• Distinguish closure identity from a second factory invocation.
• Explain binding capture without assuming all captures are immutable snapshots.
• Preserve both lifetime and intentional sharing.

Typing rules describe a language's chosen proof discipline. Reachability and ordinary type compatibility are different analyses.

Under x:Int, x+1 has type Int because both operands do. The condition true has type Bool. The else branch false has type Bool, so the branch-equality premise fails and the if expression has no type under the stated rules. Replace false with an integer such as 0, or replace the then branch x+1 with the boolean literal true. Both repairs use only the stated types and rules.

An untyped evaluator that evaluates only the selected branch returns 4 without visiting false. That execution does not establish that the program satisfies this static typing discipline. A language could include more precise reachability reasoning, but doing so changes the analysis rather than proving the existing judgment succeeds.

For 1/0, both operands satisfy the integer-type requirement. The zero divisor violates a separate operational precondition. Runtime checks, a nonzero-divisor type with suitable construction rules, or a refinement analysis could address it. A claim of type safety must specify which errors are excluded and which remain permitted behaviors or exceptions.

Check your reasoning

• Locate the exact failed rule premise.
• Provide repairs that satisfy the declared rules.
• Avoid treating ordinary type correctness as proof of all runtime safety.

A phi-like merge selects the value from the executed predecessor; it is not a runtime choice independent of control flow.

The true block defines x1=2 and the false block x2=5. At the join, x3=phi(trueBlock:x1,falseBlock:x2); then y1=x3*3; return y1. With unknown c, returns are 6 or 15. If c is proven true for the relevant execution, the false edge is unreachable, x3 becomes 2, and y1 becomes 6.

Choosing x1 unconditionally would return 6 even when c is false; choosing x2 has the symmetric error. SSA names encode definitions, while the merge preserves which definition reaches the use. A conservative value analysis can record the set{2,5} without pretending it is a single constant.

A call in a branch proven unreachable under the language's evaluation rules can be removed because it would not execute. Hoisting a printing call before a branch makes it execute on paths where it previously did not, changing observable output. Similar concerns apply to exceptions, volatile access, and memory mutation. Optimization needs a definition of observable behavior and a proof relative to it.

Check your reasoning

• Associate each merge input with a predecessor.
• Propagate only facts justified by control-flow information.
• Account for observable effects when moving or deleting operations.

Reachability starts at roots. A positive incoming count can come entirely from an unreachable cycle.

Tracing marks A and F from roots, then B from A and C from B. The C→B edge reaches an already marked object. D and E remain unmarked and can be collected. Counts are A: 1 from its root; F: 1 from its root; B: 2 from A and C; C: 1 from B; D: 1 from E; E: 1 from D. The unreachable D/E cycle has no zero-count object, so simple immediate reference counting leaves it allocated.

In the separate incremental example, moving the reference from gray G to black A keeps D reachable, but the later scan of G no longer discovers it and A is not automatically rescanned. D may therefore remain white. Sweeping white objects would then reclaim live D. An insertion barrier can shade D when a scanned object gains a reference to it, ensuring D is scheduled for tracing; another strategy can record and rescan the affected source. Exact barriers depend on the collector's invariant.

The example separates liveness from allocation age and reference count. A moving collector adds another obligation: every relevant reference and root must be updated or mediated through a representation that remains valid after relocation.

Check your reasoning

• Trace from roots rather than count all edges as liveness evidence.
• Identify the unreachable cycle explicitly.
• State the collector invariant protected by the barrier.

Observable behavior includes exceptions and state changes, not only the final number on ordinary inputs.

For unbounded integers x+1>x always holds. In 32-bit signed wraparound, x=2^31−1 produces−2^31 after adding 1, so the comparison is false. In checked arithmetic, that input traps instead of returning a boolean. Replacing either with true changes behavior. A proven range excluding overflow can justify the rewrite for the bounded models.

For floating point, infinity times zero and NaN times zero yield NaN under the usual IEEE operations, not numeric zero. Signed-zero distinctions or floating-point exception behavior can add further obligations. A restricted finite-value contract and permitted treatment of zero signs/exceptions must be explicit.

Let the counter start 0 and f increment before returning. f()+f() yields 1+2=3 and leaves counter 2. 2*f() yields 2 and leaves counter 1. Purity and repeatable return values would be needed to remove one call, and arithmetic overflow semantics still need checking. The general method is to list the language's observations, then prove the transformation preserves them for every permitted input.

Check your reasoning

• Use boundary inputs permitted by each arithmetic model.
• Include traps and state changes in observable behavior.
• State sufficient preconditions rather than dismiss every optimization.