C01: Programs as precise state changes

A. Prerequisites and observable goals#

Level: Foundation; accelerate only after an unaided trace and implementation.

B. The central question: what changes, and what must remain true?#

A program is not merely a collection of commands that happens to produce a useful screen. It is a description of permitted computations. Begin with an observable contract: given a sequence of signed integer changes, return a new sequence containing the running total after each change. The input [2,-1,3] should produce [2,1,4]. An empty input should produce an empty output. The input must not be changed. A decision about invalid inputs belongs in the specification, not in a last-minute exception after a test fails.

The mathematical function maps one finite sequence to another. An implementation chooses representations, local variables, an iteration order, and error behavior. Two implementations can realize the same function while taking different amounts of time or memory. Conversely, two implementations may agree on the three examples you tried but disagree on a fourth input. Describe the contract before writing the mechanism.

C. Notation, values, names, and types#

An expression is evaluated to obtain a value: 2 + 3 produces the integer 5. An assignment such as total = total + value first evaluates the right-hand side using the current bindings, then binds the left-hand name to the result. It is not the algebraic equation $t=t+v$. In Python, == tests equality, whereas = performs assignment. A Boolean is a truth value, not an English sentence.

A type determines which operations are defined and what they mean. Python integers can grow beyond a fixed machine word, subject to available memory; C++ integer types ordinarily have bounded ranges. The language difference will matter in C09. A list is an ordered, mutable sequence of references to objects. The name values refers to a list; the name is not itself the list. Strings such as "2" contain characters and are not interchangeable with the integer 2. Conversion must have a specified interpretation and can fail. These are language semantics, not matters of coding taste. [PY]

D. An execution trace that explains the result#

values = [2, -1, 3]
total = 0
out = []
for value in values:
    total = total + value
    out.append(total)

The loop’s useful invariant is: after processing the first $k$ inputs, total equals their sum, and out contains exactly their $k$ prefix sums. Initially $k=0$: the empty sum is zero and the empty result has length zero. One iteration adds precisely the next input and appends precisely the new sum, so the statement remains true. After $n$ iterations, the invariant is the desired postcondition. Since a finite list contributes one item per iteration, the loop terminates. This is already a small correctness argument; induction in C05 makes its structure explicit.

Putting total = 0 inside the loop destroys the accumulated state. Appending before adding produces totals for the wrong boundaries. Returning from inside the loop prematurely stops after one item. These mistakes are best located by asking which invariant first becomes false, not by randomly editing syntax until an example works.

E. Decomposition and method selection#

Separate validation, computation, and presentation. Validation decides whether input satisfies the contract. Computation returns a value without printing it. Presentation converts that value to text, JSON, a graph, or a user interface. This separation lets tests call the computational function without pretending to be a terminal user. For this lab, returning a list is clearer than printing a stream of partial results. A streaming interface is a legitimate later extension when inputs are too large to keep in memory, but it changes the interface and testing obligations.

Use a loop when the next state follows regularly from the current state. Use an explicit state table when order matters. Before execution, predict at least one ordinary result and one boundary result. Then compare the actual result with the prediction. An exception gives evidence about where execution stopped; it does not tell you automatically whether the input, contract, or implementation is wrong.

F. Aliasing: two names need not mean two objects#

a = [1, 2]
b = a
b.append(3)
c = a.copy()
c[0] = 9

After the first mutation, both a and b refer to [1,2,3]. The copy creates a different outer list. Thus the final lists are a == [1,2,3] and c == [9,2,3]. This is a shallow copy: nested mutable objects would still be shared. Predict this from the object graph rather than memorizing that “Python passes by reference,” a phrase that obscures rebinding versus mutation.

Schematic object graph, not physical memory addresses. Arrows represent name bindings.

G. Independent practice#

F foundation C standard course work T transfer S optional stretch L runnable lab or project. Attempt the complete set before opening its solutions.

H. Complete solutions: C01#

Compare the first step where your work differs. A corrected answer is not yet an independent success.

Open every solution

"""C01.05: prefix sums with an explicit state invariant."""
def prefix_sums(values: list[int]) -> list[int]:
    """Return a new list; reject non-integers (including bool)."""
    out: list[int] = []
    total = 0
    for value in values:
        if type(value) is not int:
            raise TypeError("all inputs must be integers")
        total += value
        out.append(total)
    return out

if __name__ == "__main__":
    print(prefix_sums([2, -1, 3]))

I. Retention and readiness#

Retrieve function input versus output from Module 02 and the difference between $=$ and a limiting statement from Module 06. Advance when you can trace a changed recurrence, explain shallow copying with a diagram, and implement the prefix-sum contract from a blank file. A working game subsystem does not waive this small independent demonstration; an excellent demonstration does waive repetitive beginner syntax drills.