Hoare Logic and Proving a Program Meets Its Specification · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.

Proving code correct with Hoare triples

Computing · Software Engineering · ages 23-24
Name ______________________   Date ____________

  1. Who supplies the loop invariant?

    • You do, the person proving the program
    • The solver guesses it every time
    • The compiler inserts it

  2. In a triple, what sits on each side of the code?

    • The runtime and the memory used
    • The author and the reviewer
    • What holds before and what holds after

  3. Triples for straight-line code compose in order along the program.

    Circle one:   True   False

  4. Your invariant holds initially and is preserved, but at exit it is too weak to imply the goal. What now?

    • Weaken it further and hope
    • Drop the invariant entirely
    • Strengthen it so that, with the loop ended, it implies the goal

  5. Two assignments stand in a row. How do you prove them?

    • Prove each alone and never join them
    • Chain the first triple into the second
    • Guess the ending and skip the middle

  6. What does the tool hand to the solver?

    • The leftover verification conditions
    • The whole program text
    • The loop invariants to invent

  7. A loop proof shows the invariant preserved but never shows it held at the start. Is the program proved?

    • Yes, preservation alone is enough
    • Yes, the start never matters
    • No, it must also hold before the loop begins

  8. A tool computes the weakest precondition instead of the strongest postcondition. Why, in one idea?

    • Forwards reasoning is forbidden by logic
    • Working backwards from the goal keeps the proof aimed at what you want
    • Solvers cannot read postconditions
LightMySky · lightmysky.comW1-mt_bJZnbBrUIP-s1

Answer key

For grown-ups. Fold this page away before handing over the rest.

Proving code correct with Hoare triples W1-mt_bJZnbBrUIP-s1

  1. You do, the person proving the program · The invariant is a human gift to the proof.
  2. What holds before and what holds after · A triple is a before-claim, code, and after-claim.
  3. True · Each triple feeds the next along the shape of the code.
  4. Strengthen it so that, with the loop ended, it implies the goal · Preserved is not enough; it must be strong at exit.
  5. Chain the first triple into the second · Feed the first ending in as the second start.
  6. The leftover verification conditions · Composing triples leaves small checks for the solver.
  7. No, it must also hold before the loop begins · All three duties matter, starting with holding at entry.
  8. Working backwards from the goal keeps the proof aimed at what you want · Backwards keeps the goal in view the whole way.
Worksheet · LightMySky