Tracing loops and proving a prefix calculation

By UK A Level Computer Science · independent study · myAudience

Original textbook concept plate generated with OpenAI imagegen; labels and states checked against the lesson model. · Generated original teaching artwork; pending operator rights/provenance review before publication.

Tracing loops and proving a prefix calculation

A trace records state at a precise execution point. Without that convention, two correct-looking tables can disagree because one records values before an update and another after it. Our loop consumes nonnegative readings until the first negative sentinel or the end of the list. Its state is the index i and running total. The output counts only readings before the sentinel. A negative reading is therefore a control marker in this model; if genuine negative measurements were possible, this encoding would lose information and need redesign.

Sequence executes instructions in order. Assignment evaluates the right-hand expression using the current state and then changes the target. Definite iteration has a known iteration range, while indefinite iteration continues until a condition changes. Python's while is a pre-test loop and may execute zero times. A post-test repeat-until structure executes its body at least once; it can be emulated with while True and an explicit break after the body. Choosing between them changes the empty-input case, not simply the spelling of the loop.

Our invariant at every loop-condition evaluation is: 0≤i≤n, total equals the sum of values[0:i], and every consumed value is nonnegative. Initially i=0 and total=0; the empty prefix has sum zero. If the condition holds, values[i] exists and is nonnegative. Adding it and incrementing i restores the invariant. This preservation argument depends on update order: incrementing first would skip the initial reading and might access position n. An invariant is a claim proved at a chosen program point, not a wish that every intermediate statement must satisfy.

Termination needs another argument. The variant n−i is a nonnegative integer and decreases by one on each iteration, so the loop cannot continue forever on a finite fixed list. The sentinel can terminate it sooner. On exit, either i=n or values[i]<0, and the invariant proves that the returned sum includes exactly the intended prefix. Correctness plus termination is total correctness on the stated domain. We assume the list is not concurrently modified; changing its size during execution invalidates this simple proof.

The short-circuit guard protects values[i] when i=n. Runtime cost is proportional to the number k of consumed readings plus the final guard, giving O(k+1) and worst-case O(n). The trace list is deliberately retained for teaching, so this implementation uses O(k) additional space. A production version that returns only total and i could use O(1) auxiliary space. Complexity must describe the implementation actually supplied; ignoring the trace would falsely describe its memory use.

Reading the diagram: The shaded prefix is exactly 4,0,7 at indices 0,1,2. After each completed body execution the trace is (i,total)=(1,4),(2,4),(3,11), following the initial (0,0). The zero advances i even though total stays 4. At index 3, −1 is tested by the guard but is not added; the final 9 is not consumed. The bracket depicts values[0:i], whose sum is the invariant, not every item that has ever been inspected.

Runnable original Python 3, independently executed on Python the related topic. Read the stated input contract before running. These examples use fictional data and are teaching models, not production services.

```python
def prefix_until_negative(values):
"""Return sum/count before first negative; do not include the sentinel."""
total = 0
i = 0
trace = [(i, total)]
while i < len(values) and values[i] >= 0:
total += values[i]
i += 1
trace.append((i, total))
return total, i, trace
```

Worked example: Hand-trace prefix_until_negative([4,0,7,-1,9]) at the initial state and after each completed iteration.

The initial state is (i,total)=(0,0). After consuming 4 it is (1,4).

Consuming zero changes the index but not the total: (2,4). Consuming 7 produces (3,11).

The next value is −1, so the body does not execute. The final 9 is never read by the body.

Answer: Total=11; count=3; trace=[(0,0),(1,4),(2,4),(3,11)].

Check your understanding: 1. Give the result for [] and [-2,5]. 2. Why does replacing >=0 with >0 fail? 3. Adapt the contract so that at most m readings are consumed and state the new guard and variant.

Answer: 1. Both return total 0, count 0 and only the initial trace. 2. Zero is a valid nonnegative reading; >0 would incorrectly stop on it. 3. Require integer m≥0 and use i<min(m,len(values)) and values[i]>=0. The invariant is unchanged with i≤min(m,n); the variant min(m,n)−i decreases. With m=0 the body executes zero times.

Why: A sentinel is excluded from the sum. A zero value still requires an index update. Tests provide concrete evidence, but the invariant and decreasing variant explain arbitrary valid inputs. Adding a consumption limit requires both a revised contract and a revised termination argument.