skip to content

Why prove the contrapositive of 'if a block is on the free list, no live pointer refers to it'?

level: middleimportance: must knowfreq 58%

answer

  1. same claim, different starting fact
  2. start where the information lives
  3. negate both sides, then swap
  4. a pointer has a history to trace
  5. still direct, nothing false assumed

basics

~20 s

The contrapositive — if a live pointer refers to a block, that block is not on the free list — states the same claim, but starts from a fact you can trace: a pointer, and the call that produced it.

solid answer

~50 s

An implication has two ends, and you get to choose which one you start from. Argued head-on, you begin with `b is on the free list`, which is a membership fact and tells you nothing about the rest of the heap. Argued as the contrapositive, you begin with `some live pointer refers to b`, and a pointer is an object with a history: some call returned it, and every path that returns a block removes it from the free list first. From there you reach `b is not on the free list`, which is the negated hypothesis, and you are done. It is the same claim, not a weaker one, and it is still a direct argument — nothing false is assumed anywhere. The rule of thumb is to pick the direction whose hypothesis names something you can follow.

code

pseudocode · 7 lines
pseudocode
release(b):
    assert live_refs(b) == 0     # rules out the flipped hypothesis
    push(free_list, b)

acquire():
    b = pop(free_list)           # b leaves the list before any caller sees it
    return b

go deeper

for a junior

Recall that a claim of the form if-then can be argued from either end, and that flipping it means negating both sides and swapping them, not just reversing the order.

for a middle

Be able to write both opening lines for a given claim and say which one gives you something to work with, then carry the flipped argument through to the negated hypothesis.

for a senior

Show the judgment in review: name the shape at the top, check the negation of a compound or time-bounded conclusion, and reject arguments that drift into a different statement.

for a principal

Decide which invariants in a design are stated as implications at all. A claim written so that neither end is traceable is usually a drafting defect, and rewriting the claim beats forcing an argument through it.

## The claim, and the three shapes available A design document says: **if a block is on the free list, then no live pointer refers to it.** That is an implication — a hypothesis (`b` is on the free list) and a conclusion (no live pointer refers to `b`). Before writing a single line of argument, you choose the **shape** the argument will take, and the choice is not cosmetic: it decides what you are allowed to write down on line one. | Shape | You assume | You must reach | It fits when | |---|---|---|---| | Direct | the hypothesis: `b` is on the free list | the conclusion: no live pointer refers to `b` | the hypothesis names something with structure you can use | | Contrapositive | the negated conclusion: some live pointer refers to `b` | the negated hypothesis: `b` is not on the free list | the negated conclusion is the concrete, traceable fact | | Contradiction | the hypothesis **and** the negated conclusion together | any impossibility at all | the claim is a flat negative with no usable starting fact | All three establish the same statement. Interviewers probe the choice, because the choice is where an engineer's judgment shows, and the algebra afterwards is usually routine. ## Why the flip helps on this particular claim Compare the two candidate opening lines: - **`b` is on the free list.** This is membership in a data structure. It gives you one bit. To get anywhere you would have to enumerate every way a block could reach that list and every way a pointer could still be live, which is a case analysis over the whole system. - **Some live pointer `p` refers to `b`.** This gives you an *object with a history*. A pointer only exists because some call produced it. Follow that call: the allocation path pops `b` from the free list before returning it, and the only thing that puts a block back is the release path, which runs when the caller is done with it. So on any path that could have produced `p`, `b` left the free list and has not returned to it. The second line ends at **`b` is not on the free list**, which is exactly the negated hypothesis. The claim is established. The work went into tracing a pointer, which is the kind of reasoning the code supports, rather than into enumerating a list membership, which it does not. ## Contrapositive arguments are not weaker, and they are not contradiction Two confusions are worth naming. First, the flipped form is **the same claim**, not a lesser one. A reviewer who would accept the head-on argument must accept this one. There is no discount applied for having flipped it, and there is no residual obligation left over. Second, this is **not** a proof by contradiction. Nothing false has been assumed. `Some live pointer refers to b` is a perfectly possible situation — it is true of every block currently in use. You assumed a real case and derived a real consequence. In a contradiction argument you would instead assume both sides at once and hunt for an impossibility; that machinery is unnecessary here and, because it puts more on the table, it is easier to get wrong. ## Choosing the direction in a review 1. **Write the claim as an explicit if-then**, with both sides spelled out. Claims in documents are usually stated as a bare sentence, and half the ambiguity dies here. 2. **Write down both opening lines** — the hypothesis, and the negation of the conclusion. 3. **Ask which one names an object you can follow.** A pointer, a call, a message, a record you can trace beats a membership or a state label. 4. **If neither is usable and the claim is a flat negative** — *never*, *no two*, *at most one* — reach for contradiction instead, which manufactures the object by assuming a violating case exists. 5. **State the shape at the top of the argument.** A reader who knows you are arguing the contrapositive reads the last line as the finish; a reader who does not will think you proved the wrong thing. ## Where the flip goes wrong - **Negating only one side.** Swapping without negating, or negating without swapping, produces a different statement that may simply be false. - **Careless negation of a compound conclusion.** If the conclusion is *no live pointer and no queued pointer refers to `b`*, its negation is *some pointer of one kind or the other refers to `b`* — **De Morgan's laws** turn the *and* into an *or*, and the argument must then handle both cases. - **Ignoring a hidden time quantifier.** *No live pointer refers to it* usually means *at every moment while it sits there*; the negation must name a moment, or the argument proves something narrower than the document claims. - **Choosing by taste.** The direction is picked by which hypothesis carries information, not by which reads more naturally in prose.

  • What makes one hypothesis more usable than the other when you are choosing the direction?
    A usable hypothesis names an object with a history you can follow — a pointer, a returned handle, a recorded call — so the next line of the argument writes itself. A hypothesis that only asserts membership in a structure, or a state label, forces you into a case analysis over every way that state could have arisen.
  • When does flipping to the contrapositive fail to help?
    When both sides negate into something equally opaque, or when the conclusion is itself a flat negative so its negation is an existence claim you have no way to pin down. That is the signal to try contradiction, which lets you assume both the hypothesis and the violating case and hunt for an impossibility.
  • Is a contrapositive argument ever weaker evidence than a head-on one?
    No. It establishes the same statement, with the same force, and leaves nothing extra to prove. Reviewers should judge it on clarity alone. The only practical cost is that a reader who has not been told the shape may misread the last line, which is why the shape belongs in the first sentence.

Tracking a parcel is easier from the delivery scan backwards than from the empty shelf forwards: the scan is a record of something that happened, the empty shelf is not.

saying these in an interview costs you the question

  • Swaps the two sides without negating either of them.
  • Thinks the flipped form is a weaker claim, so cheaper to establish.
  • Calls a contrapositive argument a proof by contradiction.
  • Negates a compound conclusion by keeping the and instead of an or.
  • Picks the direction by prose style rather than by usable hypothesis.