CSSE2002 — Week 12 Notes
Correct Programming
See csse2002 for course logistics.
Not examinable — confirmed in 2026-05-28-course-summary-and-exam-preparation. Worth knowing, but don’t spend revision time here.
Correctness is the prime quality. If a system does not do what it is supposed to do, everything else about it […] matters little.
— Bertrand Meyer, Object-Oriented Software Construction, §1.2 p.4, 1997
Outline
- Specification — what does it mean for a program to be correct?
- Deriving preconditions — propagating a postcondition backward through code
- Loop invariants — reasoning about (and designing) loops
- Pragmatic considerations — when is this worth the effort?
All content is in java-hoare-logic and java-loop-invariants.
Applied class
See week12-tutorial-lambdas-and-streams — 22 tasks on lambdas and streams, extending java-lambdas-and-streams (Week 11). Nothing about correctness: §1 is the three \(\lambda\)-function forms, the standard java.util.function interfaces (Function, BiFunction, UnaryOperator, Predicate, Supplier, Consumer, BiConsumer), method references, effectively-final capture and andThen composition; §2 is filter/map/mapToInt/reduce/sum/forEach and converting a loop into a pipeline.
Practical
See week12-lab-generics — 6 tasks on generics, extending java-generics (Week 9), built on a Bus/Passenger class hierarchy supplied as provided.zip. §1 rewrites a non-generic Bus (which stores Object and forces casts) into Bus<T>, then bounds it to T extends Passenger and subclasses it as NoPetsBus<T extends Person>; §2 adds a BusStop class whose methods need ? extends, ? super, and a generic method — the first two also asking for a @require/@ensure Javadoc comment.
Next steps
Where this material goes next. Treat the list as background reading:
- CSSE3100 — Reasoning About Programs
- Floyd, 1967 — Assigning Meanings to Programs
- Hoare, 1969 — introduced the triple \(\{P\}\,S\,\{Q\}\)
- Dijkstra, 1975 — weakest-precondition reasoning
CSSE3610/7610 is the follow-on course for concurrent and distributed algorithms (see java-loop-invariants).
Generics
Practical for 2026-05-21-correct-programming (Week 12). Extends java-generics (Week 9) with practice designing a generic class, bounding its type parameter, and using wildcards and generic methods.
All of the classes below are supplied in a provided.zip on the course website. Make a new IntelliJ project and drop the contents in.
Setup
Every later question refers back to one class hierarchy. Each child has one solid arrow pointing straight up into its superclass, and a hollow diamond sits on the Bus end of the Bus–Passenger line.
Figure 1: The passenger hierarchy the whole practical is built on. Each child has one solid arrowhead into its superclass, and a hollow aggregation diamond sits on the Bus end of the Bus–Passenger line.
Passenger is the common supertype of everything that can ride; Pet and Person are its two direct subtypes; TransportWorker (with subtypes MaintenanceStaff and BusDriver) and GeneralPublic (with subtype Concession) are both Persons. A Bus holds passengers up to a fixed capacity.
Keep Figure 1 in view — every wildcard bound in §2 is just a region of this tree.
§1 Generic Bus
Task 0. The provided Bus stores instances of Object. That forces callers to cast on the way out — passengerOff() hands back an Object, not a Passenger:
// The starting Bus class, before the rewrite.
public void passengerOn(Object passenger) { ... }
public Object passengerOff() { ... }
Passenger p = (Passenger) bus.passengerOff(); // cast needed at every call siteYou could rewrite Bus to store a Passenger[] instead, but then a bus that may only carry the general public would need an entirely new class storing a GeneralPublic[].
Rewrite Bus to be generic, with one type parameter, so both the casting and the duplication go away. (An Unchecked Cast warning during the rewrite is expected and can be safely ignored here.)
public class Bus<T> {
private T[] passengers;
private int currentCount;
private int capacity;
public Bus(int capacity) {
// Creation of an array of objects, that is cast to be of type
// T, is required due to how generics are implemented in Java.
this.passengers = (T[]) new Object[capacity];
this.capacity = capacity;
this.currentCount = 0;
}
public void passengerOn(T passenger) {
if (currentCount < capacity) {
passengers[currentCount++] = passenger;
}
}
public T passengerOff() {
T exitingPassenger = null;
if (currentCount > 0) {
exitingPassenger = passengers[--currentCount];
}
return exitingPassenger;
}
public int getCurrentCount() {
return currentCount;
}
public int getCapacity() {
return capacity;
}
}The (T[]) new Object[capacity] line is the awkward part: Java erases type parameters at compile time, so new T[capacity] is not something the runtime can do — you allocate an Object[] and lie to the compiler about its type. That lie is exactly what the Unchecked Cast warning is about.
passengerOn/passengerOff are a stack, not a queue: passengerOff returns passengers[--currentCount], i.e. the passenger who got on most recently, and returns null on an empty bus rather than throwing.
The remaining tasks extend Bus using bounded generic types. As with every prac, test your code as you go.
Task 1. Modify your class so that only instances of Passenger (and its subclasses) are allowed on the bus.
public class Bus<T extends Passenger> {
...
public Bus(int capacity) {
this.passengers = (T[]) new Passenger[capacity];
...
}
...
}Two things change together. The bound T extends Passenger restricts the type argument to Passenger or a subtype, so Bus<String> no longer compiles. And because T’s erasure is now Passenger rather than Object, the backing array is allocated as new Passenger[capacity].
A bound also means code inside Bus<T> may call any Passenger method directly on a T value.
Now suppose there is a type of bus that does not allow pets on board — only people.
Task 2. Write a new class NoPetsBus which extends the generic Bus class and only allows non-pets on board.
public class NoPetsBus<T extends Person> extends Bus<T> {
public NoPetsBus(int capacity) {
super(capacity);
}
}The subclass declares a stricter bound than its parent: T extends Person rather than T extends Passenger. Pet is a Passenger but not a Person (see Figure 1), so NoPetsBus<Pet> simply fails to compile — the exclusion is enforced by the type system, with no instanceof check anywhere.
§2 Bus Stop
The remaining questions need generic methods and wildcards (?). Create a new non-generic class called BusStop; each method below goes in it.
Training Bus
Bus stops are the starting points of training routes for new bus drivers. While a driver is being trained, only the trainee driver and other transport workers are allowed on board. The crew training the driver could be any combination of transport workers: only other bus drivers (List<BusDriver>), only maintenance staff (List<MaintenanceStaff>), or a mix (List<TransportWorker>).
Task 3. Write the trainingBus method:
static Bus<TransportWorker> trainingBus(BusDriver trainee, List<...> trainers)where ... is replaced with something that allows any of the List types mentioned above to be passed in. The method returns a new bus (capacity 10) with the trainee driver and all the trainers on board. Write a Javadoc comment with appropriate @require and @ensure tags.
Hint. If a
List<A>is required, aList<B>cannot be passed in, even ifB extends A. SoList<TransportWorker>alone will not do — you need wildcards.
/**
* Populate a bus to be used to train a new driver.
*
* @param trainee New driver to be trained.
* @param trainers TransportWorkers who will train the new driver.
* @require trainee != null && trainers.size() < 10
* @ensure \result contains trainee and all trainers
*/
public static Bus<TransportWorker> trainingBus(BusDriver trainee,
List<? extends TransportWorker> trainers) {
Bus<TransportWorker> bus = new Bus<>(10);
bus.passengerOn(trainee);
for (TransportWorker trainer : trainers) {
bus.passengerOn(trainer);
}
return bus;
}The hint is the whole point: generic types are invariant, so List<BusDriver> is not a subtype of List<TransportWorker>. List<? extends TransportWorker> is the supertype of all of them.
The precondition trainers.size() < 10 is what keeps the postcondition honest — passengerOn silently does nothing once the bus is full, so without a bound on the crew size the bus would not actually contain all the trainers.
Transfer Students
At bus stops, transfers happen between school buses — used exclusively for school children on concession fares, i.e. Bus<Concession> — and ordinary buses. When school children depart their bus they can only get onto buses that allow concession holders on board (not, for example, a bus meant exclusively for transport workers). So they can move either onto another concession-only bus, or onto a bus that allows superclasses of concession holders on board.
Task 4. Write the transferStudents method:
static void transferStudents(Bus<Concession> students, Bus<...> bus)where ... is replaced with something that ensures concession holders are allowed onto bus. All students on the students bus should be transferred to bus. Write a Javadoc comment with appropriate @require and @ensure tags.
Hint. Valid bus types are
Bus<Concession>,Bus<GeneralPublic>,Bus<Person>andBus<Passenger>. Wildcards will be useful here too.
/**
* Transfer students to the new bus.
*
* @param students Bus only containing Concession fare riders.
* @param bus Bus to which students will transfer.
* @require students != null
* && bus.getCapacity() >= students.getCurrentCount()
* @ensure students.getCurrentCount() == 0
* && bus.getCurrentCount >= \old(students).getCurrentCount()
* && bus contains all passengers from \old(students)
*/
public static void transferStudents(Bus<Concession> students,
Bus<? super Concession> bus) {
// Ensure loop condition does not change while iterating
int numStudents = students.getCurrentCount();
for (int i = 0; i < numStudents; i++) {
Concession student = students.passengerOff();
bus.passengerOn(student);
}
}Two things worth pulling out:
- The lower-bounded wildcard.
busis only ever written to, soBus<? super Concession>is the right bound — it accepts a bus whose type argument isConcessionor any supertype of it, which covers the four types the hint lists, all of which can legally accept aConcessionviapassengerOn. (Bus<Object>satisfies the bound too; the hint stops atPassenger.) - The cached loop bound. Writing
for (int i = 0; i < students.getCurrentCount(); i++)would be a bug: everypassengerOff()decrements the count whileiincrements, so the two meet in the middle and only half the students get transferred. Reading the count once, before the loop, is what the code comment (“Ensure loop condition does not change while iterating”) is about.
Reading the two wildcard directions off the hierarchy
Tasks 3 and 4 need wildcards in opposite directions. Task 3 accepts List<BusDriver>, List<MaintenanceStaff> and List<TransportWorker>. Task 4 accepts Bus<Concession>, Bus<GeneralPublic>, Bus<Person> and Bus<Passenger>. Laid on the same tree, ? extends reaches down from its bound and ? super reaches up.
Figure 2: The two wildcard bounds this practical needs, mapped onto the hierarchy. Grey fill marks the type arguments accepted by List<? extends TransportWorker> (Task 3); a dashed border marks those accepted by Bus<? super Concession> (Task 4).
Which direction you need falls out of what the method does with the parameter: trainers is only read (upper bound, ? extends), bus is only written (lower bound, ? super).
Transfer Concession
Suppose new subclasses of Concession were added at a later stage — say SchoolStudent and UniStudent.
Task 5. Write the transferAllConcession method:
static ... void transferAllConcession(Bus<...> students, Bus<...> bus)which does the same thing as transferStudents, except it works for Concession or any potential subclass of it. That is, if SchoolStudent were a subclass of Concession, this should work without error:
Bus<SchoolStudent> students = new Bus<>(30);
Bus<GeneralPublic> bus = new Bus<>(50);
transferAllConcession(students, bus);Hint. You will need a generic method for this one.
public static <T extends Concession> void transferAllConcession(
Bus<T> students,
Bus<? super T> bus) {
int numStudents = students.getCurrentCount();
for (int i = 0; i < numStudents; i++) {
T student = students.passengerOff();
bus.passengerOn(student);
}
}Declaring <T extends Concession> on the method (before the return type) is what makes the two parameters move together: T is inferred per call site from students, and bus’s bound ? super T is then resolved relative to that same T. With Bus<SchoolStudent> and Bus<GeneralPublic>, T infers as SchoolStudent, and GeneralPublic is indeed a supertype of it.
Task 4’s transferStudents is exactly the special case where T is pinned to Concession.
Lambdas and Streams
Applied class for 2026-05-21-correct-programming (Week 12). Extends java-lambdas-and-streams (Week 11) with practice reading λ-function traces and standard functional interfaces (Function, BiFunction, Predicate, Supplier, Consumer, BiConsumer, UnaryOperator).
On the HTML site, fill in each blank with your answer as a quoted string (e.g. "6", "Hello World"), then click Run Code to check it. Interactive checking needs a browser, so the blanks do not appear in the PDF; the collapsed Working callout under each task holds the answer either way.
§1 \(\lambda\)-functions
In Java, if an implementation of a functional interface is expected, it can be substituted with a \(\lambda\) (lambda) function. \(\lambda\)-functions take three forms — the general shape on top, a concrete instance boxed beneath it:
Figure 3: The three lambda-function forms, one per column: the general form on top and a boxed concrete example below it.
Lambdas are short-hand for an implementation of a functional interface — an interface with only one method. A motivating example:
interface GrabData<T> {
void takeThis(T data);
}
class LambdaExample {
public <T> void distributeData(List<T> data, GrabData<T> grabber) {
for (T element : data) {
grabber.takeThis(element);
}
}
}To supply a GrabData<T> you can take the traditional approach and write a named class:
class PrintData<T> implements GrabData<T> {
public void takeThis(T data) {
System.out.println(data);
}
}
...
List<String> words = List.of("alpha", "bravo", "charlie", "delta");
distributeData(words, new PrintData<>());The diamond matters: a bare new PrintData() is the raw type.
…or use a \(\lambda\)-function, which is the same implementation with the class, its name and the method signature deleted:
List<String> words = List.of("alpha", "bravo", "charlie", "delta");
distributeData(words, (data) -> {
System.out.println(data);
});This is much more concise, and encourages using functional interfaces throughout the code base.
The tasks below use the standard functional interfaces from java.util.function. Each has a single abstract method, and the Used in column lists the tasks that use it:
| Interface | Abstract method | Used in |
|---|---|---|
Function<T, R> |
R apply(T) |
Tasks 0, 2, 3, 6, 8, 9, 10, 13, 14 |
BiFunction<T, U, R> |
R apply(T, U) |
Tasks 5, 13 |
UnaryOperator<T> |
T apply(T) |
Tasks 7, 14 |
Predicate<T> |
boolean test(T) |
Task 4 |
Supplier<T> |
T get() |
Tasks 1, 12, 13 |
Consumer<T> |
void accept(T) |
Tasks 11, 12 |
BiConsumer<T, U> |
void accept(T, U) |
Task 12 |
Task 0. What is printed by:
Function<Integer, Integer> f = x -> 2 * x;
System.out.println(f.apply(3));6
Task 1. What is printed by:
Supplier<String> c = () -> "Hello World";
System.out.println(c.get());Hello World
Task 2. What is printed by:
int power = 3;
Function<Integer, Double> g = x -> Math.pow(x, power);
System.out.println(g.apply(5));125.0 (\(5^3\))
Task 3. What is printed by:
int power = 3;
Function<Integer, Double> g = x -> Math.pow(x, power);
power = 2;
System.out.println(g.apply(5));Does not compile — power is reassigned after the lambda captures it, so it is not effectively final, which lambdas require of any local variable they capture.
Task 4. What is printed by:
Predicate<Integer> p = x -> x % 2 == 0;
System.out.println(p.test(4));true
Task 5. What is printed by:
BiFunction<Integer, Integer, Integer> add = (x, y) -> x + y;
System.out.println(add.apply(3, 5));8
Task 6. What is printed by:
Function<String, Integer> strLength = String::length;
System.out.println(strLength.apply("Hello"));5 — String::length is a method reference, equivalent to s -> s.length().
Task 7. What is printed by:
UnaryOperator<Integer> square = x -> x * x;
System.out.println(square.apply(4));16
Task 8. What is printed by:
int base = 2;
Function<Integer, Double> exp = x -> Math.pow(base, x);
System.out.println(exp.apply(3));8.0 (\(2^3\))
Task 9. What is printed by:
Function<Integer, Integer> factorial = n -> {
int result = 1;
for (int i = 2; i <= n; i++) {
result *= i;
}
return result;
};
System.out.println(factorial.apply(4));24 (\(4! = 4 \times 3 \times 2 \times 1\))
Task 10. What is printed by:
Function<Integer, Integer> f1 = x -> x + 1;
Function<Integer, Integer> f2 = x -> x * 2;
Function<Integer, Integer> composed = f1.andThen(f2);
System.out.println(composed.apply(3));8 — andThen runs f1 first (3 + 1 = 4), then f2 on that result (4 * 2 = 8).
Task 11. What is printed by:
List<Integer> numbers = new ArrayList<>();
Consumer<Integer> addTo = (number) -> numbers.add(number);
addTo.accept(24);
addTo.accept(42);
System.out.println(numbers);{24, 42}
Task 12. What is printed by:
Supplier<StringBuilder> supplier = StringBuilder::new;
BiConsumer<StringBuilder, String> appender = StringBuilder::append;
Consumer<StringBuilder> printer = System.out::println;
StringBuilder sb = supplier.get();
appender.accept(sb, "cher");
appender.accept(sb, "ryp");
appender.accept(sb, "ick");
printer.accept(sb);cherrypick
Task 13. What code snippet replaces ??? so this prints 10?
BiFunction<Integer, Function<Integer, Integer>, Supplier<Integer>> g =
(i, f) -> ??? ;
System.out.println(g.apply(5, x -> x * 2).get());() -> f.apply(i) — g returns a Supplier<Integer>, a zero-argument lambda that, when later called via .get(), applies f to i (5 * 2 = 10).
Task 14. What is printed by:
Function<Integer, Integer> f = x -> x * 2;
UnaryOperator<Integer> g = x -> x + 1;
Function<Integer, Integer> h = f.andThen(g).andThen(f).andThen(g);
System.out.println(h.apply(3));15 — chained left to right: f(3)=6, g(6)=7, f(7)=14, g(14)=15.
How a chain of andThen runs
andThen reads left to right: a.andThen(b) means “run a, then feed its result into b”. Task 14’s four-link chain traced out:
Figure 4: Task 14’s chain h = f.andThen(g).andThen(f).andThen(g) evaluated at 3, with the value passed between each pair of stages. The stages apply left to right and the answer is 15.
The trap is reading f.andThen(g) as \(f \circ g\) — it is the other way round, \(g \circ f\). (Function also has a compose method that does go the other way, but none of these tasks use it.)
Task 10 is the same idea with one link: f1.andThen(f2) on 3 gives 3 + 1 = 4, then 4 * 2 = 8.
§2 Streams
In Java, most built-in collections can be converted to a stream for processing, and lambdas tend to be very useful in applying transformations to streams. See java.util.stream.
List results are written with set braces throughout — {2, 4, 6, 8}, and {24, 42} back in Task 11. A real List prints with square brackets: [2, 4, 6, 8]. Every Working callout that reports a list — Task 11 above, and Tasks 15 and 16 below — uses the brace notation, and the checkers accept either form.
Task 15. What is the value of:
Stream.of(1, 2, 3, 4, 5, 6, 7, 8).filter(x -> x % 2 == 0).toList();{2, 4, 6, 8}
Task 16. What is the value of:
Stream.of(1, 2, 3, 4, 5, 6, 7, 8).map(x -> x * x).toList();{1, 4, 9, 16, 25, 36, 49, 64}
Task 17. What is the value of:
List<String> list = Arrays.asList("apple", "banana", "cherry");
list.stream()
.map(String::toUpperCase)
.filter(s -> s.startsWith("A"))
.forEach(System.out::println);APPLE — only "apple" survives the startsWith("A") filter once upper-cased.
Task 18. What is the value of:
Stream<Integer> stream = Stream.iterate(1, n -> n * 2).limit(5);
Integer result = stream.reduce(0, (a, b) -> a + b);
System.out.println(result);31 — Stream.iterate(1, n -> n * 2).limit(5) produces 1, 2, 4, 8, 16, and \(1+2+4+8+16 = 31\).
Task 19. Convert the following method into streams:
static int sumOfSquareNumbers(List<String> words) {
int sum = 0;
for (String word : words) {
if (word.matches("[0-9]+")) {
int number = Integer.parseInt(word);
if (Math.sqrt(number) == Math.floor(Math.sqrt(number))) {
sum += number;
}
}
}
return sum;
}static int sumOfSquareNumbers(List<String> words) {
return words.stream()
.filter(word -> word.matches("[0-9]+"))
.mapToInt(Integer::parseInt)
.filter(number -> Math.sqrt(number) == Math.floor(Math.sqrt(number)))
.sum();
}The hint for this task points at filter, map, mapToInt, reduce and sum. Each if becomes a filter, the Integer.parseInt step becomes a mapToInt, and the sum accumulator becomes the terminal sum().
mapToInt (rather than map) is what makes the last step available: it produces an IntStream, which has sum(); a Stream<Integer> does not, and would need .reduce(0, Integer::sum) instead.
The return is required: a body that starts with words.stream() and no return would not compile for an int-returning method.
Task 20. What does this print?
List<String> words = Arrays.asList("cat", "dog", "elephant", "giraffe");
String details = words.stream()
.reduce("", (word1, word2) -> word1 + "-" + word2);
System.out.println(details);-cat-dog-elephant-giraffe — the identity "" is the first word1, so even the first element gets a leading - prepended.
Task 21. What does this print?
Stream<String> stream = Stream.of("hello", "world", "java");
stream.map(String::toUpperCase)
.forEach(System.out::print);HELLOWORLDJAVA — print (not println) concatenates every element with no separator.
From loop to pipeline
Task 19 is the one worth re-reading, because the conversion is mechanical once you see which construct maps to which stage. Pairing the two versions up row by row:
Figure 5: Task 19’s imperative method beside its stream solution, with each construct paired to the stage that replaces it. The code is split across rows with the enclosing method signature and braces dropped and intervening lines elided as ...; the last imperative row gathers the three accumulator lines, which are not adjacent in the method. The dashed arrow means is replaced by.
The reusable rule: the loop header becomes the source, each guard becomes a filter, each per-element computation becomes a map, and the accumulator becomes the terminal operation. Task 20’s reduce is the general case of that last step — sum() is just the special case for an IntStream.
Reference material
Java Generics
Introduced in 2026-04-30-generics-in-java (Lecture, Week 9). Practised again in week12-lab-generics.
Generics let reference types (Integer, String, … and user-defined types) be parameters when defining classes, interfaces and methods. There are two separate motivations for that, and they are worth keeping apart.
Why generics? (1) Type safety
Prior to Java 1.5, collection classes could hold any type of object — ArrayList.add was declared
public boolean add(Object o) {
// code to implement add method.
}so anything could go in, and an explicit cast was needed on the way out (see java-casting):
List list = new ArrayList();
list.add("Hello");
list.add(123); // allowed
list.add(new Date()); // allowed
String str = (String) list.get(0); // OK
Integer num = (Integer) list.get(1); // OK
Date date = (Date) list.get(2); // OKThe trap: Integer num = (Integer) list.get(2); compiles, because the compiler only knows get returns Object. It fails at run time with a ClassCastException, because slot 2 holds a Date. Nothing about the list stops a String being mixed into a collection that was only ever meant to hold Cars, because add accepts any Object.
Declaring the element type fixes both problems at once:
List<String> list = new ArrayList<>(); // <> is the diamond operator
list.add("Hello");
list.add(123); // compile-time error
String str = list.get(0); // no cast neededList<Car> carList = new ArrayList<Car>();
Car c = carList.get(0); // the compiler already knows it is a CarThis is type safety: type-related errors are caught and prevented early, at compile time, instead of surfacing as unintended bugs at run time.
List<Object>?
List<Object> list = new ArrayList<>();
list.add("Hello");
list.add(123);
Object object1 = list.get(0);
Object object2 = list.get(1);It compiles, and it accepts both. But parameterising by Object buys nothing, because everything is an Object. Elements come back typed Object, so you are casting again, and add accepts anything again. Generics only pay off when the parameter is a specific type.
Why generics? (2) One class instead of one class per type
The second motivation is duplication, not safety. A class that prints an Integer:
public class PrintInt {
Integer i;
PrintInt(Integer i) { this.i = i; }
public void print() { System.out.println(i); }
}Wanting the same thing for Double, Float and String means writing PrintDouble, PrintFloat and PrintString — four classes with identical bodies and one word changed. Generics collapse them into one class that still preserves type safety.
Generic classes
A generic class parameterises a type across its whole body:
public class Print<T> {
T i;
Print(T i) { this.i = i; }
public void print() { System.out.println(i); }
}
Print<Integer> print = new Print<>(1);
Print<Double> print2 = new Print<>(1.1);
Print<String> print3 = new Print<>("1.1");By convention, type parameters are single letters: T (Type), E (Element — used extensively by the Java Collections Framework, see java-collections-framework), K (Key), V (Value), N (Number), and S/U/V… for a 2nd/3rd/4th type.
Generic methods
A single method can be made generic, independently of whether its enclosing class is. The type parameter is declared between the modifiers and the return type:
public <T> void genericsMethod(T data) {
// do something with data
}
public <T> T genericsMethod(T data) {
// do something with data here
return data; // returning any T-type value
}Multiple type parameters can be declared together, and the return type can be a third one:
public <T, S, R> R genericMethod(T value1, S value2) {
return null;
}
String result = genericMethod(42, 3.14);Type inference
A Printer whose print method is generic, in place of a fixed-type one:
public class Printer {
public <T> void print(T data) {
System.out.println("Lets shout " + data + "!!!");
}
}
Printer printer = new Printer();
printer.print(124); // T inferred as Integer
printer.print("I love CSSE2002"); // T inferred as StringThe Java compiler can automatically determine the type of
Tbased on the type of the argument you pass to the method. This is known as type inference.
Printer were a generic class instead?
public class Printer<T> {
public void print(T data) {
System.out.println("Lets shout " + data + "!!!");
}
public static void main(String[] args) {
Printer<String> printer = new Printer<>();
printer.print("data");
printer.print(123);
}
}A class type parameter is fixed once, when the object is created. new Printer<>() assigned to Printer<String> pins T = String for the life of that object, so printer.print(123) is a compile-time error. A method type parameter is inferred afresh at every call, which is why the generic-method version above accepted an Integer and a String through the same object. Choose the class parameter when one object should work with one type throughout; choose the method parameter when each call is independent.
Bounded generics
A type parameter can normally accept any reference type. Bounded generics restrict it to a specific type or its subtypes, using extends. The form is <T extends X>, and it means T can only accept data that are subtypes of X. Restricting the Printer to numbers:
public class Printer {
public <T extends Number> void print(T data) {
System.out.println("Lets shout " + data + "!!!");
}
}
printer.print(123); // OK, Integer is a Number
printer.print(123.2); // OK, Double is a Number
printer.print("123"); // compile-time error - String is not a NumberDespite the keyword, extends here also covers implementing an interface.
Bounds through wildcards
Generic-type bounding restricts what may be substituted for the type parameter. Wildcards (?) do this at the use site — in a method’s parameter list — rather than where a generic class or method is declared. Three forms:
| Form | Name |
|---|---|
List<?> |
unbounded wildcard |
? extends T |
upper bound wildcard |
? super T |
lower bound wildcard |
Figure 6: The two bounded wildcards drawn on the Number hierarchy. ? extends Number admits Number and everything below it — you may read elements as Number, but add is refused; ? super Integer admits Integer and everything above it — you may add an Integer, and List<Double> is refused. Object is on top because the addNumbers example passes a List<Object>.
Unbounded wildcard: List<?>
List<?> means “a list of some unknown type”. Java does not know whether it is actually a List<String>, a List<Integer> or a List<Product> — therefore it prevents the caller from writing to the list:
public class Main {
public static void main(String[] args) {
List<Integer> numbers = new ArrayList<>();
addSomething(numbers);
}
public static void addSomething(List<?> list) {
list.add("Hello"); // error
}
}The compiler has to refuse: if Java allowed "Hello" to be added, the List<Integer> would now contain a String, breaking type safety.
Choosing between <T> and <?> for a read-only method:
public <T> void printList(List<T> toPrint) {
for (int i = 0; i < toPrint.size(); i++) {
System.out.println(toPrint.get(i));
}
}public void printList(List<?> toPrint) {
for (int i = 0; i < toPrint.size(); i++) {
System.out.println(toPrint.get(i));
}
}Use
<T>when you need to work with the type. Use<?>when you only need to read values.Wildcards are usually bounded (
<? extends T>,<? super T>) to reduce flexibility and improve safety.
Upper bounded wildcard: ? extends T
Represents T or any subclass of T. Used mainly to read data from a structure — you cannot safely add to it, because the exact subtype is unknown:
List<? extends Number> nums = new ArrayList<Integer>();
Number n = nums.get(0); // OK: read as Number
nums.add(10); // compile-time errorThe reason this form is needed at all is invariance. Write a sum over a List<Number>:
public static double sum(List<Number> list) {
double sum = 0;
for (Number n : list) {
sum += n.doubleValue();
}
return sum;
}
List<Double> numbers = new ArrayList<>();
numbers.add(1.1);
sum(numbers); // does not compileIn standard inheritance Number n = 5.0; is fine, because Double is a subclass of Number. But generics in Java are invariant: even though Double is a subclass of Number, List<Double> is not a subclass of List<Number>. (Effective Java, Item 31: parameterized types are invariant; List<Type1> is neither a subtype nor a supertype of List<Type2>.) Widening the parameter with an upper bound is what makes the method accept both:
public static double sum(List<? extends Number> list) {
double sum = 0;
for (Number n : list) {
sum += n.doubleValue();
}
return sum;
}…and the price is that the method still cannot safely write, because it does not know whether the actual list is a List<Double>, a List<Integer>, or something else.
Lower bounded wildcard: ? super T
Represents T or any of its superclasses. Used when you want to perform write operations on a generic collection but keep flexibility in which collections are accepted:
public class Main {
public static void addNumbers(List<? super Integer> list) {
list.add(1); // Allowed: Integer is within bounds
list.add(2); // Allowed: Integer is within bounds
}
public static void main(String[] args) {
List<Number> numbers = new ArrayList<>();
addNumbers(numbers); // fine: Number is a superclass of Integer
List<Object> objects = new ArrayList<>();
addNumbers(objects); // fine: Object is also a superclass of Integer
List<Double> doubles = new ArrayList<>();
addNumbers(doubles); // compilation error
}
}Type erasure
Generics provide type checking at compile time only. Java implements them by type erasure, which removes all type parameters during compilation, replacing each with
- its upper bound (e.g.
Number, for<T extends Number>), or Object, if unbounded.
As a result, generic type information is not available at run time.
Figure 7: Type erasure as a pipeline: the compiler checks the source against the type parameters, erases each parameter to its bound (Object if unbounded), and inserts the casts the erased code needs — so the cast you were told you did not have to write still happens, just not by you. The top row is the compile-time source and what runs after javac, with the inserted cast in the red rectangle. The bottom row is what an unbounded and a bounded parameter each erase to.
Spelled out for a bounded parameter — the compiler replaces T with the extended class:
// Source
class SomeClass<T extends Number> {
private T t;
public void add(T t) { this.t = t; }
public T get() { return t; }
}
// After type erasure, the compiler generates
class SomeClass {
private Number t;
public void add(Number t) { this.t = t; }
public Number get() { return t; }
}and for an unbounded one, T becomes Object (private Object t;, public void add(Object t), public Object get()).
Practical example: a bookshop
Imagine you are developing a system for a bookshop that sells books across various genres:
Fiction,Action, andFantasy. Books are in bookshelves. Your job is to design the system in a way that allows the shop to store books of these different genres and retrieve them when needed.
The genres are subclasses of an abstract Book:
public abstract class Book {
private String title;
private String author;
public Book(String title, String author) {
this.title = title;
this.author = author;
}
public String getTitle() { return title; }
public String getAuthor() { return author; }
public abstract String getGenre();
}
public class Fiction extends Book {
public Fiction(String title, String author) { super(title, author); }
@Override
public String getGenre() { return "Fiction"; }
}
// Action is identical, returning "Action"Figure 8: The three shelf designs, and why only the third is both reusable and type safe. One shelf of Book is reusable but needs a cast; a separate shelf class per genre gives better type safety but creates duplicated code; class BookShelf<T extends Book> gets both. The stacked outlines behind FictionShelf stand for the same class written out again for the other genres.
Without generics
One BookShelf storing the abstract Book type loses the genre on retrieval:
public class BookShelf {
private List<Book> inventory = new ArrayList<>();
public void addItem(Book item) { inventory.add(item); }
public Book getItem(int index) { return inventory.get(index); }
public void displayBooks() {
for (Book book : inventory) {
System.out.println(book.getTitle() + " (" + book.getGenre() + ")");
}
}
}The failure, worked through. The commented-out line is the one that breaks:
BookShelf shelf = new BookShelf();
shelf.addItem(new Fiction("The Hobbit", "J.R.R. Tolkien"));
shelf.addItem(new Action("Die Hard", "Roderick Thorp"));
shelf.addItem(new Fiction("Harry Potter", "J.K. Rowling"));
Book b = shelf.getItem(0); // returns Book
Fiction f = (Fiction) shelf.getItem(0); // fine
// Fiction f2 = (Fiction) shelf.getItem(1); // breaks: index 1 is an
// // Action -> ClassCastException
Action f2 = (Action) shelf.getItem(1); // the caller has to knowgetItem() returns only Book, so retrieving a genre needs a cast, and a wrong cast is a ClassCastException — not type safe.
Writing separate FictionShelf/ActionShelf classes instead does give better type safety, but every shelf is the same class copied out again:
public class FictionShelf {
private List<Fiction> inventory = new ArrayList<>();
public void addItem(Fiction book) { inventory.add(book); }
public Fiction getItem(int index) { return inventory.get(index); }
public void displayBooks() { for (Book book : inventory) { /* ... */ } }
}
// class ActionShelf { ...the same again with Action... }With generics
A single generic BookShelf<T extends Book> gives type safety and reuse from one class. The bound matters twice over: it is what lets displayBooks call book.getGenre() (the compiler knows every T is at least a Book), and what stops a BookShelf<String> ever being created.
public class BookShelf<T extends Book> {
private List<T> inventory = new ArrayList<>();
public void addItem(T item) { inventory.add(item); }
public T getItem(int index) { return inventory.get(index); }
public void displayBooks() {
for (T book : inventory) {
System.out.println(book + "(" + book.getGenre() + ")");
}
}
}
BookShelf<Fiction> fictionShelf = new BookShelf<>();
BookShelf<Action> actionShelf = new BookShelf<>();
fictionShelf.addItem(new Fiction("The Hobbit", "J.R.R. Tolkien"));
fictionShelf.addItem(new Fiction("Harry Potter", "J.K. Rowling"));
actionShelf.addItem(new Action("Die Hard", "Roderick Thorp"));
fictionShelf.displayBooks(); // getItem() here returns Fiction, no cast
actionShelf.displayBooks();Java Hoare Logic
Introduced in 2026-05-21-correct-programming (Lecture, Week 12). Formalises reasoning about java-specification’s preconditions/postconditions.
What does it mean for a program to be correct?
A correct program satisfies its specification.
Correctness is only meaningful relative to a specification — asking “is this program correct?” without one is unanswerable:
public int indexOf(int[] numbers, int number) {
for (int i = 0; i < numbers.length; i++) {
if (numbers[i] == number) {
return i;
}
}
return -1;
}- With no spec at all: maybe correct, maybe not — we can’t say without knowing what it’s meant to do.
- Spec’d as
/** Returns how many times number occurs in numbers. */: incorrect — counter-exampleindexOf({1, 1, 1, 1}, 1) == 0, but a correct implementation of that spec should return4. - Spec’d as
/** Returns the index of number within numbers, if number is in numbers. */: correct, but the spec is underspecified — it says nothing about what happens whennumberisn’t innumbers.
A specification restricts the space of acceptable implementations: think of all possible input/output pairs as arrows crossing an Implementation/Specification boundary — an implementation is correct exactly when every arrow it draws stays within the region the specification permits. A @requires/@ensures Javadoc comment (see java-specification) states the precondition and postcondition that bound this region.
Hoare triples
Preconditions and postconditions aren’t just for whole methods — every block of code has them. We write this as a Hoare triple:
\[\{P\}\ S\ \{Q\}\]
meaning: if precondition \(P\) holds before statement(s) \(S\) run, postcondition \(Q\) holds afterwards. E.g.:
// {true}
if (x > y) {
max = x;
} else {
max = y;
}
// {max >= x && max >= y}Deriving preconditions by propagating backward
Given a method’s postcondition, we can work out its precondition (or verify a block of code) by propagating the postcondition backward through each statement, substituting as we go.
Straight-line code
/**
* @requires numbers != null && 2 < numbers.length && numbers[2] == number
* @ensures numbers[\result] == number
*/
public int indexOf(int[] numbers, int number) {
// {numbers[0 - 10 + 12] == number}
int result = 0;
// {numbers[result - 10 + 12] == number}
result = result + 12;
// {numbers[result - 10] == number}
result = result - 10;
// {numbers[result] == number}
return result;
// {numbers[\result] == number}
}Each line’s precondition is obtained by substituting the assigned expression into the next line’s already-derived precondition, working from the @ensures postcondition backward to the top of the method — the resulting @requires is whatever’s left once you reach the very first line.
The direction is the part that trips people up: the listing reads top-to-bottom but is derived bottom-to-top, and each rung of the derivation is a single textual substitution.
Figure 9: The same derivation as the listing above, laid out so the direction of the reasoning is visible: the @ensures at the bottom is given, each statement rewrites the assertion below it by replacing the assigned variable with the expression assigned to it, and whatever is left at the top is the @requires. The assertions are in green; they are // comments in the listing.
Through if/else
Each branch is handled separately, and the two derived preconditions are combined into a single condition depending on which branch executes:
/**
* @requires numbers != null && 12 < numbers.length
* && numbers[12] == number && number % 2 == 0
* @ensures numbers[\result] == number
*/
public int indexOf(int[] numbers, int number) {
// {number % 2 == 0 ==> numbers[0 + 12] == number
// && number % 2 != 0 ==> numbers[0 - 10] == number}
int result = 0;
if (number % 2 == 0) {
// {numbers[result + 12] == number}
result = result + 12;
} else {
// {numbers[result - 10] == number}
result = result - 10;
}
// {numbers[result] == number}
return result;
}Both branches must reach the same postcondition {numbers[result] == number}, so the derivation forks there, runs up each branch independently, and only rejoins once each branch’s precondition has been guarded by the condition that selects it:
Figure 10: The if/else derivation above drawn as a fork and join. Reading upward: one shared postcondition, two independent branch derivations, then a single combined condition in which each branch’s requirement is guarded by the test that reaches it, and finally one more substitution through int result = 0;. The combined assertion in the middle is the top condition one substitution earlier, a step the listing skips over.
Compare the top of Figure 10 with the @requires the method actually declares. The derived condition covers both branches; the declared one, numbers != null && 12 < numbers.length && numbers[12] == number && number % 2 == 0, pins number to the even case. That is legal — a stronger precondition than the derived one is always safe, because it still implies it (with number % 2 == 0 fixed, the second disjunct is vacuously true) — it just means the method promises less than the code could deliver. Deriving gives you the weakest precondition; what you write in the Javadoc may be anything that implies it.
Proving a block correct
The same backward-propagation technique proves an arbitrary block of code satisfies a given Hoare triple — substitute back through each branch/statement and confirm the starting precondition (true, in these examples) is actually implied:
// {true}
if (x > y) {
// {x > y} ==> {x >= x && x >= y}
max = x;
// {max >= x && max >= y}
} else {
// {y >= x} ==> {y >= x && y >= y}
max = y;
// {max >= x && max >= y}
}
// {max >= x && max >= y}A three-statement swap works the same way, substituting each assignment’s right-hand side backward through \old(...) references:
// {true}
// {y == \old(y) && x == \old(x)}
int tmp = x;
// {y == \old(y) && tmp == \old(x)}
x = y;
// {x == \old(y) && tmp == \old(x)}
y = tmp;
// {x == \old(y) && y == \old(x)}A trickier variant swaps x/y using only arithmetic (no temporary variable), which still propagates the same way:
// {true}
// {y == \old(y) && x == \old(x)}
// {y - (y - x) + (y - x) == \old(y) && y - (y - x) == \old(x)}
x = y - x;
// {y - x + x == \old(y) && y - x == \old(x)}
y = y - x;
// {y + x == \old(y) && y == \old(x)}
x = y + x;
// {x == \old(y) && y == \old(x)}(A similar swap is possible using bitwise XOR instead of subtraction, exploiting \(a \oplus b = b \oplus a\), \((a \oplus b) \oplus c = a \oplus (b \oplus c)\), \(a \oplus 0 = a\), \(a \oplus a = 0\).)
Writing the triple down: \result and \old(...)
A Hoare triple written in Java lives in a Javadoc comment (see java-specification): \(P\) goes in the precondition tag, \(Q\) in the postcondition tag, and \(S\) is the method body. Two pieces of vocabulary let a postcondition say things a plain Java boolean expression cannot.
\resultnames the value the method returns. It is the established way to refer to a return value inside a postcondition.\old(e)names the value the expressionehad before the call. It is defined in java-specification and is used again in the Week 12 practical. Without it the swap derivations above could not be stated at all:x == y && y == xsays nothing, whereasx == \old(y) && y == \old(x)is exactly the swap.
The tags are @requires / @ensures here and in the tag table in java-specification. The Week 12 practical sheet (week12-lab-generics) writes @require / @ensure, with no trailing s, and so do the SOLID contracts. Neither form is canonical. Use whichever form the sheet in front of you uses.
A worked contract from the Week 12 practical
The practical’s transferStudents (Task 4) is the fullest contract in the Week 12 material, and it uses both pieces of vocabulary. Its @ensure writes bus.getCurrentCount without the parentheses:
/**
* Transfer students to the new bus.
*
* @param students Bus only containing Concession fare riders.
* @param bus Bus to which students will transfer.
* @require students != null
* && bus.getCapacity() >= students.getCurrentCount()
* @ensure students.getCurrentCount() == 0
* && bus.getCurrentCount >= \old(students).getCurrentCount()
* && bus contains all passengers from \old(students)
*/
public static void transferStudents(Bus<Concession> students,
Bus<? super Concession> bus) { ... }The method returns void, so there is no \result to talk about; everything the postcondition has to say is about how two objects’ states changed, which is what makes \old(...) indispensable here. students.getCurrentCount() == 0 is a fact about the state after; \old(students).getCurrentCount() reaches back to the state before, so the middle clause can hold the target bus’s final count up against the number of passengers the source bus had before the call.
Figure 11: The Week 12 practical’s transferStudents contract as a before/after picture, on a source bus of capacity 4 carrying three passengers and a target bus of capacity 6 already carrying two. Each bus is an array with its name to the left. The contract text is in green and the annotation in magenta.
Two things about this contract as written.
The postcondition mixes Java and English in the same tag. students.getCurrentCount() == 0 is a boolean expression; bus contains all passengers from \old(students) is a sentence. The course convention is that conditions are written in Java boolean syntax, not mathematical notation, but the only queries Bus exposes are getCurrentCount() and getCapacity() (its other two methods, passengerOn and passengerOff, both mutate), so there is no expression in the API that can say “contains”. The contract falls back to prose rather than inventing one, and the same happens in Task 3, whose whole postcondition is @ensure \result contains trainee and all trainers.
The precondition is weaker than the postcondition needs. bus.getCapacity() >= students.getCurrentCount() compares the target’s total capacity against the number of students, not its free space. Bus.passengerOn (Task 0) silently does nothing when the bus is full:
public void passengerOn(T passenger) {
if (currentCount < capacity) {
passengers[currentCount++] = passenger;
}
}so a bus of capacity 6 already carrying 4, given a students bus of 3, satisfies the precondition (6 >= 3) yet drops the third student on the floor — students.getCurrentCount() == 0 still holds, because passengerOff removes them regardless, but bus contains all passengers from \old(students) does not. The precondition that actually discharges the postcondition is bus.getCapacity() - bus.getCurrentCount() >= students.getCurrentCount(). The marked solution is the contract above, with the weaker precondition.
The loop inside that method — and why its bound is copied into a local variable before the loop starts — is taken up in java-loop-invariants.
Java Lambdas and Streams
Introduced in 2026-05-14-lambdas-streams-and-events (Guest lecture, Week 11). Practised further in week12-tutorial-lambdas-and-streams.
Lambdas (anonymous functions)
A lambda is a function as a value — it isn’t declared with a name, and can be passed around like any other reference value, such as an object. JavaScript and Python have the same idea.
Scope: like in most languages, a Java lambda can hold references to things accessible in scope at the time of creation.
Functional interfaces
Because Java is typed, you cannot have an anonymous function without clearly defined type information — the JVM would not know what to do. So Java supplies a set of interfaces that are combined with generics (see java-generics) to give easily-adjustable type descriptions for lambdas. They live in java.util.function. Four of them:
| Interface | Signature | Purpose |
|---|---|---|
Consumer<T> |
takes a T, returns nothing (void) |
by convention indicates the function has some kind of side effect — if it returned nothing and had no side effect it would do nothing at all |
Predicate<T> |
takes a T, returns boolean |
useful in filtering especially |
Function<T, R> |
takes a T, returns an R |
turning a T into an R |
BiFunction<T, U, R> |
takes a T and a U, returns an R |
deriving one value from two, e.g. the distance between two positions, or custom sorting |
A minimal lambda of each shape:
Consumer<String> print = s -> System.out.println(s);
Predicate<Integer> isEven = n -> n % 2 == 0;
Function<String, Integer> length = s -> s.length();
BiFunction<Integer, Integer, Integer> add = (a, b) -> a + b;Consumer<T> is the one that matters most for events: the toy event system in java-events types every listener as a Consumer<SimpleEvent>.
Streams
Added in Java 8 to enable a different, more declarative style of programming. Brian Goetz’s IBM article on Java streams is a very good resource on their benefits.
This style is particularly effective when you have data you need to conduct multiple operations on sequentially, or retrieve a single resulting value from a sequence of operations, which is often the case in a real job. At a simple level they are an alternative to writing lots and lots of very samey for loops over a sequential set of data (most often a List or similar, see java-collections-framework); the JavaScript equivalents are .filter(), .map() and .reduce().
The worked example
One pipeline, taken a line at a time:
int totalHpFromFireEnemies =
enemies.stream()
.filter(enemy -> enemy.faction.equals("Fire"))
.mapToInt(enemy -> enemy.hp)
.sum();| Stage | Line | What it does |
|---|---|---|
.stream() |
enemies.stream() |
opens a stream over the collection |
.filter() |
.filter(enemy -> enemy.faction.equals("Fire")) |
drops every enemy whose faction isn’t Fire |
.mapToInt() |
.mapToInt(enemy -> enemy.hp) |
replaces each surviving Enemy with its int hp |
.sum() |
.sum() |
reduces what is left to a single total |
Figure 12: The stream example as a pipeline, one stage per line of the chain. Each box is the type between stages: .stream() turns the list into a Stream<Enemy>, .filter() takes a Predicate and hands on a Stream<Enemy>, .mapToInt() hands on an IntStream, and .sum() collapses it to one int. The braces mark the intermediate operations and the terminal operation.
Anatomy of a stream pipeline
A pipeline has three steps:
- Start a stream with
.stream(). - Chain any number of intermediate operations:
.filter()|.map()|.distinct()|.sorted()|.mapToInt()etc. - Resolve it into a final value with one of the terminal operations:
.sum()|.count()|.toList()|.collect()|.reduce().
You chain the first kind and resolve with the second. The rule underneath: an intermediate operation hands on another stream, a terminal one resolves to a value. That is what puts .mapToInt() in the first list and .sum() in the second, and why exactly one terminal operation ends a pipeline.
Java Loop Invariants
Introduced in 2026-05-21-correct-programming (Lecture, Week 12). Extends java-hoare-logic’s backward-reasoning technique to loops, where the number of iterations isn’t known up front.
…proving the correctness of algorithms has another aspect that is even more important: it mirrors the way we understand an algorithm.
— Donald Knuth, The Art of Computer Programming (Vol. 1), 1997
What is an invariant?
An invariant is a property of a system that does not change.
Motivating puzzle
A jar contains 100 red and 100 blue beans. Repeatedly: pick two random beans; if they’re the same colour, discard both; if they’re different colours, discard the blue one. What colour is the last bean?
Let \(r, b\) be the current counts of red/blue beans. Each step does exactly one of:
| Pick | Action | Effect |
|---|---|---|
| two reds | discard both | \(r \mapsto r - 2,\ b \mapsto b\) |
| two blues | discard both | \(r \mapsto r,\ b \mapsto b - 2\) |
| one of each | discard blue | \(r \mapsto r,\ b \mapsto b - 1\) |
What never changes? The parity of \(r\) — every action either leaves \(r\) unchanged or decreases it by exactly 2, so \(r\) stays even throughout (it starts at 100, itself even). When one bean remains, \(r + b = 1\); since \(r\) must be even, \(r \neq 1\), so \(r = 0\) and \(b = 1\) — the last bean is blue.
The property “\(r\) is even” is an invariant of the process: it (1) holds before any step, (2) is preserved by every step, and (3), combined with the termination condition (\(r + b = 1\)), implies what we wanted to prove. This is exactly the structure of a loop invariant.
Loop invariants
A loop invariant is a condition that: (1) holds before the loop is entered, (2) is preserved by each iteration, and (3) combined with the negation of the guard, implies the postcondition.
Those three clauses are three separate proof obligations, and they attach to three different places around the loop:
Figure 13: The three obligations in the definition above, each pinned to the point in the loop where it has to be discharged. The invariant point is the top of the loop, before the guard is tested: establishment is the arrow into it, preservation is the arrow back to it, and exit is what the guard’s failure adds to it. Connectors are teal and assertions are green.
None of the three clauses in Figure 13 says anything about the loop finishing. An invariant that survives all three checks establishes only “if the loop ends, the postcondition holds”; termination is a separate argument — in power below, that exp - i strictly decreases and is bounded below.
int count = 0;
while (count < n) {
// invariant: count >= 0
count = count + 1;
}// {0 >= 0}
int count = 0;
// {count >= 0} <-- invariant holds before the loop
while (count < n) {
// invariant: count >= 0
// {count + 1 >= 0}
count = count + 1;
// {count >= 0} <-- preserved by the body
}
// {count >= 0 && count >= n}Deriving an invariant for power
/**
* @requires ????
* @ensures \result == base^exp
*/
int power(int base, int exp) {
int result = 1;
int i = 0;
while (i < exp) {
result = result * base;
i = i + 1;
}
return result;
}Step 1 — guess an invariant. Replace exp in the postcondition with the loop variable i: \(I : \text{result} = \text{base}^i\).
Step 2 — verify. Three checks:
- Does \(I\) hold before the loop first executes?
result = base^i\(\equiv 1 = \text{base}^0 \equiv\) true. ✓ - Assuming \(I\) holds at the top of the loop body, does it still hold after?
result * base = base^i * base = base^{i+1}, and afteri = i + 1, that’s exactlyresult = base^iagain. ✓ - Does \(I\) combined with the negated guard (\(i \geq \text{exp}\)) imply the postcondition?
result = base^i\(\land\ i \geq \text{exp} \Rightarrow \text{result} = \text{base}^{\text{exp}}\)? Not quite — we can only conclude \(i \geq \text{exp}\), but we need \(i = \text{exp}\).
Step 3 — strengthen. Add the bound \(i \leq \text{exp}\) to the invariant: \(I : \text{result} = \text{base}^i \land i \leq \text{exp}\). Re-checking: \(I\) now holds initially iff \(\text{exp} \geq 0\) (giving us our precondition), is still preserved by the loop body, and combined with \(i \geq \text{exp}\) now forces \(i = \text{exp}\) exactly, giving the postcondition:
/**
* @requires exp >= 0
* @ensures \result == base^exp
*/
int power(int base, int exp) {
// {0 <= exp}
// {1 == base^0 && 0 <= exp}
int result = 1;
int i = 0;
// {result == base^i && i <= exp}
while (i < exp) {
...
}
// {result == base^i && i <= exp && i >= exp}
// {result == base^exp}
return result;
}The precondition comes from obligation (1) of Figure 13, failing, and being read backwards. exp >= 0 was never designed in — it is whatever the establishment check needed in order to succeed.
Designing an algorithm from an invariant: fast exponentiation
The power above runs in \(O(\text{exp})\) multiplications. We can do better using the identity:
\[b^e = \begin{cases} (b^{e/2})^2 & \text{if } e \text{ is even} \\ b \times (b^{(e-1)/2})^2 & \text{if } e \text{ is odd} \end{cases}\]
E.g. computing \(3^{13}\): \(3^{13} = 3 \times 3^{12}\) [13 odd] \(= 3 \times (3^2)^6\) [12 even] \(= 3 \times 9^6 = 3 \times (9^2)^3\) [6 even] \(= 3 \times 81^3 = 3 \times 81 \times 81^2\) [3 odd] \(= 3 \times 81 \times 6561 = 1{,}594{,}323\) — only a handful of multiplications instead of 12 sequential ones.
Design from the invariant: rather than writing code and then finding its invariant, pick the invariant first and let the code follow. We want a loop maintaining:
\[I : \text{result} \times b^e = \text{base}^{\text{exp}}\]
starting from result = 1, b = base, e = exp, terminating when e == 0:
/**
* @requires exp >= 0
* @ensures \result == base^exp
*/
int power(int base, int exp) {
int result = 1;
int b = base;
int e = exp;
while (e > 0) {
// invariant: result * b^e == base^exp
if (e % 2 == 1) {
result = result * b;
e = e - 1;
}
b = b * b;
e = e / 2;
}
return result;
}Verifying \(I\) (using \(b^e = (b^{e/2})^2\) when even, \(b \times (b^{(e-1)/2})^2\) when odd, and \((a^b)^c = (a^c)^b\)):
- Before the loop:
result * b^e == base^exp\(\equiv 1 \times \text{base}^{\text{exp}} = \text{base}^{\text{exp}} \equiv\) true. ✓ - Through the body: splitting on
e % 2, both branches reduce back to exactlyresult * b^e == base^expafter the update (theifbranch peels off one factor ofbintoresultand decrementsefirst; both branches then squareband halvee). ✓ - On exit (
e <= 0):result * b^e == base^expwithe <= 0only concludes the postcondition whene >= 0too (i.e.e == 0) — which holds as long asexp >= 0, giving the same precondition as before. ✓
The invariant is easiest to believe by watching it not move. Running the loop on the same \(3^{13}\) worked above:
Figure 14: The fast-power loop traced on power(3, 13), one box per arrival at the top of the loop. The three variables change on every step; the product result * b^e underneath does not, and the five products it takes are exactly the chain the section above works by hand (the section’s 3 x 81 x 6561 and this trace’s 243 x 6561 are the same number). Connectors are teal and the invariant is green.
This preserves the exact same specification as the slow version — both satisfy @requires exp >= 0 / @ensures \result == base^exp — but the fast version reaches it in \(O(\log \text{exp})\) multiplications instead of \(O(\text{exp})\).
Invariants in the Week 12 exercises
Neither Week 12 exercise set is about correctness — the applied class is lambdas and streams (week12-tutorial-lambdas-and-streams) and the practical is generics (week12-lab-generics) — but both contain loops whose behaviour is only explicable in these terms, and the practical writes contracts for two of them.
The loop bound that must not move
The practical’s transferStudents (Task 4) empties one bus into another. Its loop carries a one-line comment:
// Ensure loop condition does not change while iterating
int numStudents = students.getCurrentCount();
for (int i = 0; i < numStudents; i++) {
Concession student = students.passengerOff();
bus.passengerOn(student);
}The contract this loop has to establish is its @ensure (given in full in java-hoare-logic), whose first clause is students.getCurrentCount() == 0. Taking the invariant at the top of the iteration with counter i to be
0 <= i && i <= numStudents && students.getCurrentCount() == numStudents - i, and bus holds everything it started with plus the i students already moved,
the three obligations of Figure 13 go through: at i == 0 nothing has moved and getCurrentCount() is still numStudents; each iteration takes exactly one passenger off and puts exactly one on before i++, restoring it; and exiting with i == numStudents gives students.getCurrentCount() == 0 together with all numStudents students on bus.
Now write the guard the obvious way instead, reading the count live, and the invariant has nothing to hold onto: i climbs by one per iteration while students.getCurrentCount() falls by one, so the two meet halfway and the loop stops with half the bus still loaded.
Figure 15: Why the practical snapshots its loop bound. Both columns run the same body on a source bus of four; the left column is the loop with the bound read once into numStudents, the right is the same loop with students.getCurrentCount() in the guard. Reading the count live makes the guard chase a quantity the body is decreasing, and the two meet after two iterations. Bus contents are drawn as array rows and the verdict on each column is in magenta.
In general the live-bound version runs \(\lceil n/2 \rceil\) iterations and leaves \(\lfloor n/2 \rfloor\) students behind, because i and the count meet at \(i = n - i\). The fix is the standard one: a loop guard should not read state the body is mutating. Copying the bound into a local before the loop is what turns numStudents into something the invariant can be stated against. Task 5’s transferAllConcession uses the same body and the same snapshot, with the type parameter T in place of Concession, so the same invariant carries over unchanged.
An accumulator loop inside a lambda
The applied class’s Task 9 hides an ordinary counting loop inside a Function:
Function<Integer, Integer> factorial = n -> {
int result = 1;
for (int i = 2; i <= n; i++) {
result *= i;
}
return result;
};
System.out.println(factorial.apply(4)); // 24The task asks only for the printed value. The invariant, following the power recipe of replacing the target quantity’s bound with the loop variable, is \(I : \text{result} = (i-1)!\ \land\ 2 \leq i \leq n+1\):
- Establishment. At the top,
i == 2andresult == 1 == 1!. ✓ — but the bound clause needs \(2 \le n+1\), so this invariant establishes only forn >= 1, which is the derived precondition. (factorial.apply(0)still returns1, correctly; that just isn’t something this invariant proves.) - Preservation.
result * i == (i-1)! * i == i!, andi++then makes that(i-1)!again. ✓ - Exit. The guard fails at
i > n, which withi <= n + 1forcesi == n + 1, soresult == n!. ✓
At n == 4 that is 4! == 24, derived rather than simulated.
The same idea, written into a method signature
The applied class’s Task 18 computes the same shape of thing with no loop at all:
Stream<Integer> stream = Stream.iterate(1, n -> n * 2).limit(5);
Integer result = stream.reduce(0, (a, b) -> a + b); // 31reduce’s first argument is the identity and its second is the step. Read as a loop, those are precisely obligations (1) and (2): the identity 0 establishes the invariant “the accumulator holds the sum of the elements consumed so far”, and (a, b) -> a + b is the step that preserves it. When the stream runs out — the negated guard — the accumulator holds the sum of all five elements, \(1 + 2 + 4 + 8 + 16 = 31\). Nothing about the reasoning has changed; the fold’s signature just makes you write the invariant’s two halves down where a for loop would have let you leave them implicit. See java-lambdas-and-streams for reduce itself.
Pragmatic considerations
Proving correctness can be vital, but it’s also time-consuming — you want code running on a plane or controlling trains to be correct; you may not care nearly as much whether a weekend web-scraping script is correct. Where formal reasoning tends to pay off:
- Combinatorial algorithms — proving a faster/trickier implementation still satisfies the original spec (as with
powerabove). - Distributed and concurrent algorithms — notoriously hard to reason about by testing alone (see CSSE3610/7610).
Reasoning about programs this way provides (1) a more rigorous way to think about your software, and (2) a better interface design for others to interact with it — it doesn’t remove the need to think about your programs, but gives a framework to structure that thinking.
A loop invariant is not the only kind of invariant in this course: a class invariant is the same idea applied to an object’s fields across every public method rather than to a loop’s variables across every iteration — established by the constructor, preserved by each method, relied on by all of them. See week8-tutorial-class-invariants.
Beware of bugs in the above code; I have only proved it correct, not tried it.
— Donald Knuth (memo to Peter van Emde Boas, 1977)
Java Specification
Introduced in 2026-03-12-object-oriented-programming-ii (Lecture, Week 3). Extended in 2026-03-19-exceptions and formalised later in java-hoare-logic; pre/postconditions come back as class invariants in week8-tutorial-class-invariants and as the substitution principle in week9-tutorial-substitution-principle-and-pre-post-conditions.
The order below: Javadoc → restrictiveness → generality → formality → contracts → defensive programming.
Javadoc
- Ordinary comments:
//and/* ... */. - Javadoc comments:
- begin with
/**— note the second*; the Javadoc generator ignores all other comments; - end with
*/; - must sit immediately above the thing being documented;
- use tags beginning with
@; - some tags take parameters, some just text.
- begin with
A worked example:
/**
* Calculates a sum by combining the hash code of the provided string
* and the long value of the provided float.
*
* @param inputString the input string whose hash code will be used
* @param inputFloat the float value to be converted to long and combined with the string hash code
* @return a long value representing the sum of the string's hash code and the long value of the float
*/
public long doCalculation(String inputString, float inputFloat){
long floatToLong = (long) inputFloat;
// Combine the hash code of the string with the float-to-long value
long result = inputString.hashCode() + floatToLong;
return result;
}What makes a good specification
Ideally a specification will:
- Allow the use of a method by only reading the specification, not by reading and understanding the implementation.
- Allow a method to be re-implemented without requiring changes to any methods that use it.
And it should:
- Rule out all implementations that are unacceptable — i.e. be sufficiently restrictive.
- Not preclude acceptable implementations — i.e. be sufficiently general.
- Be easy for users (programmers) to understand — i.e. be clear.
The next three sections take one method, search, and fail each of those three tests in turn.
Restrictiveness — keep out incorrect implementations
/**
* Returns an index (i) of ar such that
* ar[i] == x, if any.
*/
public int search(int[] ar, int x) {…}This does not say what happens if x is not in ar. It is tempting to assume the obvious answer, but the specification doesn’t say, so don’t assume. By its silence, the specification allows any value to be returned. So a return of 1 or 0 could mean “It’s at index 1/0” or “I didn’t find it”.
Adding the missing case makes it better, still bad:
/**
* Returns an index (i) of ar such that
* ar[i] == x, if any
* else, return -1
*/
public int search(int[] ar, int x) {…}Suppose x appears in ar multiple times. There is nothing in the spec that requires:
- that you will get the lowest index;
- that you will get the same answer running multiple times.
The specification is non-deterministic.
Figure 16: With the spec worded as ‘returns an index i such that ar[i] == x’, both cells holding 3 are legal answers, and nothing forbids the method returning a different one on each call. That is what makes the specification non-deterministic.
Generality — allow acceptable alternative versions
The obvious fix for the non-determinism is to say which index you get. Saying it like this, however, is a bad example:
/**
* Examine ar[0], ar[1], ... in turn and
* return the index of the
* first one that is equal to x, if any,
* else return -1
*/
public int search(int[] ar, int x) {…}It is restrictive enough, but it over-commits: it describes how the method walks the array. A forward-scanning implementation goes with it (see the warning below before trusting this listing):
public int search(int[] ar, int x) {
int found = -1;
for (int i = 0; i < ar.length; i++) {
if (ar[i] == x) {
found = i;
}
}
return found;
}The consequence of the over-committed wording shows when the loop is run the other way:
public int search(int[] ar, int x) {
int found = -1;
for (int i = ar.length-1; i >= 0; i--) {
if (ar[i] == x) {
found = i;
}
}
return found;
}Scanning backwards and keeping the last match found is the smallest matching index — the answer the spec asks for — but the specification said ar[0], ar[1], ... in turn, so this version does not satisfy the specification. A perfectly good implementation has been outlawed by wording that was never about the outcome.
Even if you think that is the most natural way to do something, that doesn’t mean it should be part of the specification.
Specs should describe what happens, not how.
Rewritten to talk about the result only, the specification now accepts the backward implementation:
/**
* Return smallest index (i) of ar such that
* ar[i] == x, if any,
* else return -1
*/
public int search(int[] ar, int x) {…}The backward scan above returns the smallest index, so it satisfies the rewritten spec. The forward scan from earlier does not:
for (int i = 0; i < ar.length; i++) {
if (ar[i] == x) { found = i; }
}
return found;That loop overwrites found on every match, so it returns the largest matching index, not the smallest — and not the first one either, which is what the earlier spec asked for. On ar = [1,3,4,2,3,5] with x = 3 it returns 4 where both specs want 1. The forward and backward listings only agree when x occurs at most once. A forward scan that satisfies the spec has to stop at the first match:
for (int i = 0; i < ar.length; i++) {
if (ar[i] == x) { return i; }
}
return -1;Clarity
- A specification should facilitate communication between people.
- Two ways in which communication could fail:
- the reader doesn’t understand;
- the reader only thinks they understand.
- Clarity can be improved by being as concise as possible. Long specs are:
- more likely to contain errors/contradictions,
- less likely to be read properly,
- more likely to be misunderstood.
- Redundancy may help — but be clear that it is redundant, by using e.g. “e.g.” or “i.e.”.
Four specs to judge
Four one-line specifications. The question for each is whether it is a good specification.
/**
* Sorts the given array.
*/
public void sort(int[] ar) {...}/**
* Calculate x to the power of two with Math.pow.
*/
public int square(int x) {...}/**
* Returns the list of ResourceContainers stored by this instance.
*/
public List<ResourceContainer> getResources() {...}/**
* Calculate the nth value of the fibonacci sequence.
*/
public long fib(int n) {...}Applying the three criteria (restrictive, general, clear):
sort— under-restrictive. Ascending or descending? In place, or is the return ofvoidsupposed to imply in place? What about equal elements?square— over-general in one direction and over-specific in another: it namesMath.pow, which is a how, exactly the generality failure above; and it never says what happens on overflow.getResources— the mutability trap from java-mutability. Is the returnedListthe instance’s own list, so that the caller can add to it, or a copy? Restrictiveness: the spec’s silence permits either, so no caller can safely do anything with it.fib— under-restrictive on the domain and on the indexing convention. Isfib(0)0 or 1? What happens for negativen, or for annwhose answer overflowslong?
Formality
Specifications of software range in formality:
- informal — e.g. normal comments;
- semi-formal — structured English documentation, e.g. using Javadoc tags;
- formal — mathematical constraints, e.g. using Java syntax for boolean expressions.
Here is the same method specified three times, once at each level.
Informal:
/**
* Withdraws an amount from this account and
* returns how much is left.
*/
public int withdraw(int amount) {...}This leaves three things open: what happens when amount is negative, what happens when amount is bigger than the balance, and whether the balance is changed when there is a failure.
Semi-formal — structured English, one tag per obligation:
/**
* Withdraw an amount from this account.
*
* @param amount the amount to withdraw, must be a positive integer.
* @return the new balance after the withdrawal.
* @throws IllegalArgumentException if the amount is negative.
* @throws InsufficientFundsException if the amount is greater than the current balance.
*/
public int withdraw(int amount) {...}Formal — boolean expressions in Java syntax, with \old(...) naming the value an expression had before the call:
/**
* Withdraws an amount from this account.
*
* @require amount >= 0
* @require amount <= getBalance()
* @ensure getBalance() == \old(getBalance()) - amount
*/
public int withdraw(int amount) {...}There is no @throws in the formal version. The failure cases have not been forgotten: they have been moved into the caller’s obligations. The next section covers this.
Contracts
Specifications can be written using contracts:
/**
* [Description of method's behaviour]
*
* @require [Precondition]
* @ensure [Postcondition]
*/- If the code calling the method satisfies the precondition, then the method guarantees to satisfy the postcondition.
- If the code calling the method does not satisfy the precondition, then the method guarantees nothing — any behaviour is allowed.
Programming with contracts
\result names the returned value inside a postcondition:
/**
* Withdraws an amount from this account.
*
* @require amount >= 0
* @require amount <= getBalance()
* @ensure getBalance == \old(getBalance()) - amount
* @ensure \result == getBalance()
*/
public int withdraw(int amount) {
// no need to check the conditions
}int balance = myAccount.withdraw(amt);In the first @ensure, getBalance is written without the parentheses it has in the formal specification above.
It is up to the calling code to make sure it fulfils its side of the contract, i.e. 0 <= amt <= myAccount.getBalance().
The method body carries no validation at all, and the call site carries no error handling — the postcondition is unconditional, so balance is always meaningful.
Programming without contracts
The same method written defensively instead, with the failure folded into the return value:
/**
* Withdraw an amount from this account.
*
* @param amount The amount to withdraw.
* @return The balance of this account after
* the withdrawal successfully occurs,
* or -1 if it fails.
*/
public int withdraw(int amount) {
if (amount < 0) {
return -1;
}
if (balance < amount) {
return -1;
}
}int balance = myAccount.withdraw(amt);
If(balance == -1) {
...
}The method body shows only the two checks; the success path is left out. The call site writes If with a capital where Java needs if.
The cost is visible on both sides: the method now checks twice on every call, and every call site has to branch on a sentinel. It also re-introduces exactly the restrictiveness problem from search — -1 has to mean both “a balance” and “it failed”.
Defensive programming
Definition (Defensive Programming) Explicitly checking for invalid inputs and bad situations, ensuring the software does not behave dangerously regardless of input.
Sooner or later someone will call the method without checking the precondition. Particularly when dealing with external input sources or when guarding critical resources, it may be better to be defensive outside the wall and use contracts inside it.
Figure 17: Defensive outside the wall, contracts inside it: validate defensively where untrusted input crosses into the system, and rely on contracts for the internal calls behind that boundary, so the check happens once rather than at every hop. The gate box is the findMax method worked through below.
Worked example: findMax
The starting point, with no specification and no checks:
public int findMax(int[] numbers) {
int max = Integer.MIN_VALUE;
for (int i = 0; i < numbers.length-1; i++) {
if (numbers[i] > max) {
max = numbers[i];
}
}
return max;
}Documented, and with the defensive check added:
/**
* Finds the maximum value in the given array of integers.
*
* @param numbers An array of integers from which the maximum value is to be found.
* @return The maximum value in the array.
* @throws IllegalArgumentException if the array is null or empty.
*
* @requires numbers != null && numbers.length > 0
* - The array must not be null.
* - The array must contain at least one element.
*
* @ensures
* - The method returns the maximum value found in the array.
*
*/
public int findMax(int[] numbers) {
if (numbers == null || numbers.length == 0) {
throw new IllegalArgumentException("Array must not be null or empty.");
}
int max = Integer.MIN_VALUE;
for (int i = 0; i < numbers.length; i++) {
if (numbers[i] > max) {
max = numbers[i];
}
}
return max;
}This version writes the precondition down as @requires, promises an exception in @throws for callers who break it anyway, and then checks it in the body — belt and braces, which is the whole point of being defensive at a boundary. Without the check, a null array throws NullPointerException and an empty array silently returns Integer.MIN_VALUE as if that were a real maximum.
The first version loops i < numbers.length-1 and the documented version loops i < numbers.length. The first version therefore never examines the last element, so findMax(new int[]{1, 2, 9}) returns 2. No specification was attached to the first version, so nothing about it was wrong according to its spec, because it did not have one.
Further reading
Key takeaways
- A specification describes the contract between a method and its client.
- It explains what the method does, not how it is implemented.
- A good specification clearly states:
- Preconditions — conditions that must be true before the method is called;
- Postconditions — conditions that will be true after the method finishes successfully;
- Side effects — any additional changes the method makes to the system.
- Clear specifications make code easier to understand, use, and maintain.