Metadata Card

• Prerequisites: Chapter 1 (Software Construction Foundations)
• Estimated Time: 45 minutes
• Core Difficulty: Foundation-building
• Completion Milestone: Be able to design complete ADTs, understand representation independence and invariants

Your Progress

You've learned how to build a forge—static checking ensures the iron doesn't shatter, defensive programming ensures the fire doesn't burn you, assertions ensure the hammer never misses. But a forge that just throws iron in mindlessly is inefficient. You need to organize your workspace.

The City of Artisans has a rule: "separate what the outside world sees from how it's built inside." The blueprint shows the interface—the function, the connections. The internal construction is your own business. Your Task

Abstract Data Types (ADTs). You have data and you have operations on that data. ADT thinking requires you to separate the specification (what does this type do?) from the implementation (how does it do it?). Behind this separation lie two key concepts: representation independence (the implementation can change without affecting users of the type) and invariants (certain conditions must always be true about the internal state).

Chapter tiers

• Required reading: ADT concept, specification vs implementation
• Selective: Representation independence, representation exposure
• Advanced: Invariant maintenance, abstraction barrier

This chapter won't require you to master

• Category theory and algebraic data types
• Dependent types

---

Breaking Ground · Tracing the Source

The City of Artisans' core rule: any workshop's internal processing technique (how you quench, how you hammer) is the workshop's own business. Customers only need to know the interface: what parts you need to give it, and what parts it will return.

ADTs enforce this boundary in code. A well-designed ADT:

// Interface — what the outside world sees
public interface PlayerRepository {
    Player findById(PlayerId id);
    void save(Player player);
    void delete(PlayerId id);
}

The implementation could use PostgreSQL, MySQL, or a plain text file—the caller doesn't know and doesn't care. That's representation independence.

First Layer: Defining ADTs

An Abstract Data Type consists of:

1. A set of values — what data the type can hold
2. A set of operations — what you can do with the data
3. A set of invariants — conditions that always hold across all operations

Here's a Score ADT:

public class Score {
    private final int value;

    public Score(int value) {
        if (value < 0 || value > 999999) {
            throw new IllegalArgumentException("Score must be 0-999999");
        }
        this.value = value;
    }

    public Score add(Score other) {
        return new Score(this.value + other.value);
    }

    public int getValue() { return value; }
    // No setter — Score is immutable
}

Invariants:

• value is always between 0 and 999999
• After add(), the result is a valid Score
• Score is immutable — once created, it cannot change

Second Layer: Representing Complex State

An ADT's responsibility is to maintain its invariants. Let's look at a Match:

public class Match {
    private final String id;
    private final Player playerA;
    private final Player playerB;
    private int scoreA;
    private int scoreB;
    private MatchStatus status;
    private String winner;
    private final List<ScoreEvent> history = new ArrayList<>();

    public Match(String id, Player playerA, Player playerB) {
        this.id = id;
        this.playerA = playerA;
        this.playerB = playerB;
        this.scoreA = 0;
        this.scoreB = 0;
        this.status = MatchStatus.IN_PROGRESS;
    }

    public void recordScore(Player player, int points) {
        if (status != MatchStatus.IN_PROGRESS) {
            throw new IllegalStateException("Match is not in progress");
        }

        if (player.equals(playerA)) {
            scoreA += points;
        } else if (player.equals(playerB)) {
            scoreB += points;
        } else {
            throw new IllegalArgumentException("Player not in this match");
        }

        history.add(new ScoreEvent(player, points, Instant.now()));
    }

    public void finish() {
        this.status = MatchStatus.FINISHED;
        if (scoreA > scoreB) this.winner = playerA.getId();
        else if (scoreB > scoreA) this.winner = playerB.getId();
    }

    // Representation independence: internal data structure can change
    // without affecting callers
}

The ADT protects its internal state. You can't set winner directly—you must call finish() which handles the logic correctly.

Third Layer: Representation Exposure

What if someone gets direct access to your internal representation?

// BAD — representation exposure
public class BadMatch {
    public List<Round> rounds; // Directly accessible!

    public void addRound(Round round) {
        this.rounds.add(round);
    }
}

// Somewhere else:
BadMatch match = new BadMatch();
match.rounds.clear(); // Invariant violated — no rounds at all!
match.addRound(new Round(null, null)); // null values inside!

Solution: defensive copying.

public class GoodMatch {
    private final List<Round> rounds = new ArrayList<>();

    public void addRound(Round round) {
        if (round == null) throw new IllegalArgumentException();
        this.rounds.add(round);
    }

    public List<Round> getRounds() {
        return new ArrayList<>(rounds); // Defensive copy
    }
}

Fourth Layer: Abstraction Barrier

Operations on ADTs should form a clean layered structure:

Layer 0 (Internal): raw data structures
Layer 1 (ADT internal): operations that maintain invariants
Layer 2 (ADT public): operations available to callers
Layer 3 (Client code): code that uses the ADT

The barrier is between Layer 2 and Layer 3. Callers at Layer 3 should never need to know what happens at Layers 0-1.

public class Tournament {
    private final Map<String, Match> matches = new HashMap<>();

    // Abstraction barrier: caller doesn't know about Map<String, Match>
    public Match getMatch(String matchId) {
        return matches.get(matchId);
    }

    public void addMatch(Match match) {
        if (matches.containsKey(match.getId())) {
            throw new IllegalArgumentException("Match already exists");
        }
        matches.put(match.getId(), match);
    }
}

Fifth Layer: Immutability as Invariant Protection

The strongest invariant: no one can change this object at all after creation.

public final class Player {
    private final String id;
    private final String name;
    private final int level;

    public Player(String id, String name, int level) {
        this.id = id;
        this.name = name;
        this.level = level;
    }

    // Only getters — no setters
    public String getId() { return id; }
    public String getName() { return name; }
    public int getLevel() { return level; }
}

Immutability eliminates entire categories of bugs: no accidental state mutation, no thread-safety issues (immutable objects are naturally thread-safe), no hidden side effects.

The trade-off: immutability can be less efficient for frequent updates. Every change creates a new object. In practice, for value objects like Score, PlayerId, RoundResult, immutability is the standard.

Sixth Layer: Summary of ADT Design Principles

1. Gather all operations on the data — cohesive set, complete but not bloated
2. Define the specification before implementation — test the interface, not the internals
3. Maintain invariants — the ADT is responsible for its own correctness
4. Don't expose representation — no public fields, no return of mutable internals
5. Prefer immutability — for value objects, make them immutable
6. Keep the abstraction barrier — callers should never need to peek inside

---

Common Pitfalls

Pitfall 1: Anemic domain models. Classes with only getters/setters and no behavior. That's not an ADT—it's a struct. Operations should belong to the ADT, not live in a separate Service class that manipulates the data from outside.

Pitfall 2: Exposing mutable internals. Returning List<Player> directly from a class that owns that list. Callers can now modify the list, breaking invariants. Always defensive copy, or return unmodifiable views.

Pitfall 3: Leaky abstractions. "This method takes a String id, but the format is 'user-YYYYMMDD-NNNNN'." If callers need to know implementation details of the ID format, it's a leaky abstraction.

Pitfall 4: Creating ADTs for everything. Not every int needs to be wrapped in a Score. Not every String needs a PlayerName. Start with primitives, promote to ADT when invariants emerge.

---

Passing Challenges

• Warm up: Find a class you maintain that has public fields or mutable getters. Refactor it to protect its representation.
• Challenge: Design an ADT for "Tournament Bracket." It must support: add match, update winner, get current bracket state. Define the invariants, write the interface first, then implement.
• Observe: Find an open-source library's README or docs that advertise "immutable objects." Look at the source code — how do they ensure immutability? Do they make defensive copies everywhere?

---

Traveler's Notes

Abstract Data Types are the second measuring tool in the artisan's kit. After ensuring correctness-of-construction, ADTs ensure correctness-of-organization. You separate specification from implementation, protect invariants, and build an abstraction barrier that makes your code easier to reason about, easier to test, and easier to change.

---

Preview of Next Chapter

You know how to build a safe forge and how to organize raw materials. But which forge should you build? What kind of parts does the customer actually need? That's the next skill: understanding requirements before building. Next: Requirements Analysis & Architecture Design.