skip to content

A loop drains a paged result set into a sink; what three obligations must its loop invariant meet to prove the result?

level: middleimportance: must knowfreq 62%

answer

  1. three obligations, not one property
  2. checked at a fixed point each pass
  3. true before the first guard test
  4. the body must restore it
  5. negated guard supplies the last step

basics

~10 s

A loop invariant must be true before the first pass (initialization), be re-established by every pass (maintenance), and, together with the failed loop guard, imply the result the loop promised (exit).

solid answer

~40 s

Take a loop that pulls pages from a cursor and appends each page's records to a sink. A usable invariant is: `sink` holds exactly the records of the pages fetched so far, in order, and `cursor` marks the first record not yet fetched. Three obligations make it a proof. **Initialization**: it is true before the first guard test, when the sink is empty and nothing has been fetched. **Maintenance**: if it is true at the top of a pass, the body restores it by the top of the next pass. **Exit**: when the guard fails, the invariant plus the negated guard — no page remains — gives the postcondition that the sink holds every record. The body may break the invariant mid-pass; only the top of the loop is checked.

code

pseudocode · 14 lines
pseudocode
sink <- empty list
cursor <- START

# INVARIANT (top of loop): sink holds exactly the records of the
# pages already fetched, in order, and cursor marks the first
# record not yet fetched.
while cursor is not EXHAUSTED do
    page <- fetch(cursor)
    for each record in page do
        append record to sink      # invariant temporarily broken here
    cursor <- page.nextCursor      # EXHAUSTED when no page remains

# guard failed: nothing lies beyond cursor,
# so sink holds every record the source yields

go deeper

for a junior

Remember the shape: a loop invariant is one sentence about state that is true each time the loop is about to test its condition, not a comment about what the body does.

for a middle

Be able to name initialization, maintenance and exit for a concrete loop and to show which line of the body re-establishes the claim. Explain why the body may break it mid-pass.

for a senior

Show you use invariants on real code: the reviewable artefact is a one-line claim next to a fragile loop, strong enough that the exit case falls out, and cheap enough to assert at runtime when the loop guards data movement.

for a principal

Weigh where invariants are worth stating at all. On boundary loops that move data between systems they pay for themselves; spread over every loop they become noise nobody maintains, and an unmaintained invariant misleads more than none.

## What a loop invariant actually is A **loop invariant** is a claim about program state that is true at one fixed point in the loop — by convention the top, just before the guard is tested — on **every** pass, including the final test that ends the loop. It is deliberately not a claim about every instruction: the body is allowed, and usually needs, to break the claim temporarily while it moves data around, provided it has restored it by the time control returns to the top. The reason to write one down is that a loop runs an unknown number of times, so you cannot justify it by tracing. The invariant replaces "what happened across all the passes" with a single sentence that never mentions how many passes there were. ## The three obligations 1. **Initialization.** The invariant holds immediately before the first evaluation of the loop guard. For an accumulate-into-a-sink loop this is usually vacuous: the sink is empty and nothing has been fetched, so "the sink holds exactly what has been fetched" is trivially true. 2. **Maintenance.** Assume the invariant at the top of an arbitrary pass and assume the guard is true; show that after the body runs, the invariant holds again at the top of the next pass. This is the only obligation that inspects the body. 3. **Exit.** When the guard is false, the invariant *and* the negated guard together must imply the postcondition — the property you actually wanted. An invariant that survives the first two obligations but says nothing useful here has proved nothing. | Obligation | What you check | What a missing check lets through | |---|---|---| | Initialization | State before the first guard test | A loop whose claim was never true to begin with | | Maintenance | One arbitrary pass, assuming the invariant | A body that quietly drops or duplicates work | | Exit | Invariant together with the failed guard | A loop that finishes in a state you cannot describe | ## Worked example: draining a paged source The postcondition is: the sink holds every record the source would ever yield, in order, with none duplicated. Invariant: *`sink` holds exactly the records of the pages already fetched, in order, and `cursor` denotes the position of the first record not yet fetched.* - **Initialization** — before the first pass the sink is empty and `cursor` points at the start, so both halves of the claim hold. - **Maintenance** — the body fetches the page at `cursor`, appends its records in order and advances `cursor` past them. Records already in the sink are untouched, the new ones follow them in order, and `cursor` again marks the first unfetched record. - **Exit** — the guard fails exactly when the cursor is exhausted, meaning no record lies beyond it. Combined with the invariant, the sink holds every record. That is the postcondition, reached without counting passes. Notice how much work the phrase "and `cursor` denotes the first record not yet fetched" does. Drop it and maintenance becomes unprovable: nothing then rules out a body that refetches the same page forever. ## Maintenance is induction over passes The second obligation is an induction over the number of completed passes, with the invariant as the hypothesis: initialization is the base, maintenance is the step, and the conclusion is "the invariant holds after every pass, however many there are". Stating it that way explains why a single arbitrary pass is enough to examine, and why the invariant must be strong enough to be *assumed*, not merely observed. ## What the three obligations do not buy you - They establish **partial correctness** only: *if* the loop stops, the answer is right. - They say nothing about whether the guard ever becomes false. A loop that never stops satisfies all three obligations vacuously. - Termination is a separate argument about a quantity that strictly decreases and cannot decrease forever. ## Choosing an invariant that works - Mention every object the postcondition mentions; an invariant that omits one cannot imply it. - Describe both what has been done and what remains — the second half is what makes progress provable. - Prefer a statement about *content* ("the sink holds exactly these records") over a statement about *counters* ("the index is at most n"); counters alone survive every pass while proving nothing at exit. - Check it against the guard on purpose: write out the invariant with the guard negated and see whether the postcondition falls out.

  • At exactly which point in the loop is the invariant required to hold?
    At the top of the loop, immediately before each evaluation of the guard — including the final evaluation that fails and ends the loop. Inside the body it may be false; that is expected while the body is mid-update. Requiring it after every statement would rule out almost every useful loop, since the body's job is usually to consume one item and then restore the claim.
  • Is the loop guard itself part of the invariant?
    No. The guard is the thing that changes truth value — true on every pass, false at exit — so it cannot be invariant. They are used together: the invariant carries what is true throughout, and the negated guard supplies the extra fact available only at exit. Confusing the two produces an "invariant" that is false exactly when you need it.
  • Does a sound invariant tell you the loop is correct?
    It gives partial correctness: if the loop halts, the result meets the specification. Halting is a separate obligation, argued from a quantity that strictly decreases and is bounded below. A loop that spins forever satisfies all three invariant obligations vacuously, which is precisely why the two arguments are kept apart.

A stocktaker who may only ever hold one shelf's clipboard at a time: after each shelf the running tally must again equal everything counted so far, so when the shelves run out the tally is the whole warehouse.

saying these in an interview costs you the question

  • Insists the invariant must hold after every statement in the body
  • Checks the invariant only at initialization, never through the body
  • Offers an invariant that is true but implies nothing at exit
  • Claims a sound invariant proves the loop finishes
  • Restates the loop guard and calls it the invariant
  • Picks an invariant that never mentions the result being built