ENGGEN 131 Chap.8 C Loops, Arrays and Functions

C Loops, Arrays and Functions

This chapter develops zero-based C array traversal, explicit length contracts, reductions, scalar pass-by-value and array mutation through shared element storage. It uses legal-index lists and loop invariants to prove reductions, then diagnoses skipped final elements, out-of-range accesses and biased initial candidates. Empty-input policy is kept separate from nonempty algorithms.

What this chapter covers

• 01

  Zero-based legal index domains

• 02

  Array parameters and explicit lengths

• 03

  For-loop boundaries and iteration counts

• 04

  Reduction initialisation from valid data

• 05

  Scalar copies and array element mutation

Worked example · free

Find an array maximum

Key terms

Array length

The number of elements the caller authorises a function to process.

Reduction

Combining a sequence into one result such as a sum or maximum.

Undefined behaviour

Program behaviour for which the C language gives no required result.

C Loops, Arrays and Functions FAQ

Exam move

Write the array contract before the loop: element type, length, valid indices and whether the function may modify elements. For length n, the legal forward domain is zero through n minus one. Predict the first executed index, last executed index and first rejected index from the loop header.

Treat any access at n as out of bounds even if a test run appears normal; undefined behaviour is not made valid by nearby readable memory. Design reverse loops with index signedness in mind. Trace loops in a table containing index, condition result, values read, state before, update and state after. Give every iteration a row.

For nested loops, record which dimension controls each boundary and compute the expected total iteration count. Use one-element and boundary-sized arrays to test whether initialisation and stopping are correct. For neighbour logic, identify the shortest legal input and show why the loop stops before an index whose neighbour would lie outside the array. State a loop invariant for reductions.

A maximum candidate should equal the maximum of the processed prefix after every completed iteration. Initialise it from the first element when length is positive, then inspect remaining positions. Initialising to zero invents a candidate and fails on all-negative data. Define the empty-array policy separately: either the contract forbids zero length or the function reports it without reading element zero.

Explain initialisation, preservation and termination rather than merely presenting the final value. Track function boundaries explicitly. Scalar parameters are local copies, so changing a parameter does not alter the caller’s scalar. Array parameters permit access to caller-owned element storage, but they do not carry a general element count; pass the length or provide another stated termination rule.

Mark whether element mutation is intended and whether a result is returned. A function can calculate correctly yet violate its interface by modifying input unexpectedly or relying on a missing length. Use adversarial tests. For a maximum, include all-negative values and a maximum at the first and final positions. For a sum, include values that cancel. For a search, include absent, first-position and last-position targets.

For every test, predict iteration count and final state before running. If a failure occurs, compare the executed index list with the legal domain and compare the invariant with the first row where it becomes false. This localises boundary and update-order errors efficiently.

End by writing one reduction function from its contract, then produce a correctness explanation containing precondition, initial candidate, invariant, legal domain and returned result. Add input validation where the contract requires it and trace the smallest permitted case. Keep an error log separating off-by-one bounds, biased initialisation, missing length, pass-by-value misunderstanding and unintended mutation.

Mastery means being able to justify every array access and show why the invariant delivers the required answer when the loop terminates. As a closing exercise, specify and trace a function that returns the maximum of a nonempty integer array without modifying it. Write the positive-length precondition, legal index domain, first-element initialisation and invariant before coding.

Test one element, an all-negative array, and cases with the maximum first and last. For each, list executed indices and the first rejected index. Then create a deliberately biased zero initialisation and identify the smallest counterexample. Extend the contract with an explicit empty-input response and show that no access occurs before validation.

Finally, distinguish local scalar parameters, shared array elements and the returned value. This synthesis proves every access, update and function-boundary effect rather than relying on a successful run over convenient positive data.