Immutability, Spelled Out

01 — the shape

Three files and no build system

Python declared its architecture in import lines and OCaml in dune stanzas. Java declares almost nothing: the compiler is handed every source file at once and works out the rest from the names.

  Tests.java       ──┐
                     ├──>  PQueue.java   the queue: four TODOs
  MazeSolver.java  ──┘

The same shape as the other two: one structure, two clients, and no dependency between the clients. What differs is that nothing records it. javac *.java compiles the directory; the class named on the java command line supplies main. For three files that is a virtue. It is also why a Java project of any size acquires Maven or Gradle, and why the OCaml lab needed only two lines of dune to say the same thing.

02 — four keywords

One idea, said four times

The lecture asked why private and final. This file is the answer at full length: four independent mechanisms, each closing one route back to mutability.

public final class PQueue<T> {
    private record Node<T>(T head, Node<T> tail) {}
    private final Node<T> front;
    private final Node<T> back;
    private PQueue(Node<T> front, Node<T> back) { ... }
}

• final class. No subclass, so no override can reintroduce a mutable field or break the invariant behind the class's back.
• private final fields. private keeps clients out; final keeps the class itself out, after construction. The two are genuinely different guarantees, and both are needed.
• record nodes. A record's components are implicitly final and it has no setters, so a cons cell is immutable by construction rather than by discipline. This is the one place where modern Java says in a single word what the other three keywords say the long way.
• A private constructor. No client can assemble a queue directly, so every queue in the program has passed through make — which is what makes the invariant hold everywhere rather than merely usually.

03 — the shared empty

One empty queue, and a cast we sign for

This is the most interesting file in the lab, and it is six lines long.

private static final PQueue<?> EMPTY = new PQueue<>(null, null);

@SuppressWarnings("unchecked")
public static <T> PQueue<T> empty() {
    return (PQueue<T>) EMPTY;
}

There is exactly one empty queue in a running program, and every caller receives the same object. That is safe for precisely one reason: no operation can modify it. An ephemeral queue could not do this — each caller would need a fresh new, because each caller would be about to change it. The lecture made this point with two lines of an interface file, create : unit -> 'a t against empty : 'a t; here it is the same point, in the implementation.

04 — returning two things

No tuples, and no option

A persistent dequeue must return the element and the new version. Each language solves that with what it has.

public record Dequeued<T>(T value, PQueue<T> rest) {}

public Dequeued<T> dequeue() { ... }

Java has no tuple type, so returning two things means declaring a type for the occasion. Records make that cheap — one line — and arguably clearer than a tuple, because the components are named. MazeSolver does the same thing again for its frontier, with record Taken(Pos value, Frontier rest).

The second difference is sharper. OCaml returns ('a * 'a t) option, so the empty case is in the type and a caller cannot reach the value without handling it. Java throws NoSuchElementException, which is in the documentation and in nothing that the compiler checks. Both decisions are defensible; only one of them is enforced.

05 — the frontier

An interface, and two records that implement it

The search never names a queue or a stack. Java expresses that with the mechanism every student here already knows.

interface Frontier {
    boolean  isEmpty();
    Frontier put(Pos p);
    Taken    take();
    record Taken(Pos value, Frontier rest) {}
}

record QueueFrontier(PQueue<Pos> q) implements Frontier { ... }

record StackFrontier(Pos head, StackFrontier tail) implements Frontier { ... }

Three languages, three ways to say same interface, two implementations: Python gathers five functions into a SimpleNamespace and nothing checks that they exist; OCaml uses a record of functions whose second type parameter is the frontier itself, so the search is polymorphic in it; Java declares an interface and dispatches dynamically. Java's is the version that needs no explanation in this room — which is exactly why it is worth noticing that the other two achieved the same separation without it.

The highlighted line repays a second look. StackFrontier is a record whose tail is another StackFrontier: the frontier is its own cons cell, so the persistent stack needs no separate class and no queue behind it. Its put is one new, and its take returns the two components it already has. That is why --dfs produces a complete search before any of the four TODOs is written.

06 — run it

Two commands

javac *.java
java Tests
java MazeSolver ../mazes/medium.txt
java MazeSolver ../mazes/medium.txt --dfs

javac *.java compiles all three files; java Tests runs the tests and java MazeSolver the search. There is no build directory and nothing to clean beyond the .class files left beside the sources.

Part E is homework, and it is the third time through the same specification. The value is no longer in working out the algorithm — that was settled on paper before Part A — but in noticing what this language checks, what it merely permits, and what is left to us to guarantee. The half-page reflection asks precisely that.