Why is the frame problem particularly severe for heap-manipulating programs compared to programs with only local variables?
AHeap programs are inherently slower, making verification timeouts more likely
BWith local variables, the set of things that could change is small and explicit. With heap memory, any pointer could potentially alias any cell, so the set of possibly-modified locations is unbounded and not known statically
CHeap programs cannot be expressed in Hoare logic at all
DThe frame problem only exists for heap programs; local-variable programs are immune
For local variables, the frame problem is manageable: a statement x := 5 modifies x and nothing else, and this is evident from the syntax. But a heap write *p := 5 modifies whatever cell p points to, which depends on the runtime value of p. Since p could alias any other pointer, the set of potentially affected locations is the entire heap. This makes specifying 'what did not change' far harder and is the core motivation for separation logic's local reasoning approach.
Question 2 True / False
A modifies clause in a function contract (e.g., 'modifies x, y') addresses the frame problem by explicitly listing what the function may change. Everything else is implicitly unchanged.
TTrue
FFalse
Answer: True
Modifies clauses (also called 'writes' or 'assigns' clauses) are the most common syntactic approach to the frame problem. Verification tools like Dafny, SPARK, and Frama-C use them to automatically generate frame conditions: for any variable or heap location NOT in the modifies clause, its value before the call equals its value after. This shifts the burden from the programmer (listing everything unchanged) to the tool (inferring preservation from the modifies set).
Question 3 Short Answer
Explain how separation logic's frame rule solves the frame problem without requiring explicit modifies clauses.
Think about your answer, then reveal below.
Model answer: In separation logic, a specification {P} C {Q} describes only the heap footprint that C actually uses. The frame rule ({P} C {Q} implies {P * R} C {Q * R}) automatically preserves any disjoint heap region R. Because * enforces disjointness, the untouched heap R is guaranteed unchanged without the programmer listing specific locations. The frame information is structural — built into the logic — rather than syntactic.
This is elegant because the programmer never has to enumerate 'what is not modified.' By specifying only the heap the function touches, everything else is automatically preserved by the frame rule. The disjointness enforced by * ensures no hidden aliasing can violate this preservation. This local reasoning principle is the main reason separation logic scaled to industrial-strength tools.