2.1 ADT Specifications, Representation, and Invariants

An abstract data type (ADT) begins with a behavioral specification: it defines a set of possible values and the operations that callers can perform. Classes, interfaces, and structs are merely language tools used to implement this specification.

This section addresses four key questions:

• What constitutes an abstract value?
• What guarantees does each operation provide?
• How are internal fields mapped to abstract values?
• Which internal states are permanently disallowed?

Start with Abstract Values, Not Fields

Take rational numbers as an example. The caller cares about the mathematical value $p/q$, not about whether the object internally stores (1, 2), (2, 4), or a string.

We can begin by writing a public specification:

Type: Rational
Abstract value: any rational number

of(numerator, denominator)
  Precondition: numeric objects are non-null and denominator != 0
  Failure: null throws NullPointerException; zero denominator throws IllegalArgumentException
  Postcondition: returns the rational number corresponding to numerator / denominator

add(other)
  Precondition: other is non-null; otherwise NullPointerException
  Postcondition: returns this + other; neither operand is modified

numerator(), denominator()
  Postcondition: returns the reduced fraction, with denominator > 0

This specification makes no promises about field layout and requires no understanding of the reduction algorithm from the caller. This boundary enables implementation evolution without forcing callers to change their code.

Abstraction Functions and Representation Invariants

Implementers need two descriptions of the representation.

Abstraction Function (AF) explains how fields correspond to the abstract value:

AF(numerator, denominator) = numerator / denominator

Representation Invariant (RI) constrains the set of valid internal states:

numerator and denominator are non-null
denominator > 0
gcd(abs(numerator), denominator) = 1
numerator = 0 implies denominator = 1

The AF answers "what does it represent?", while the RI answers "which representations are allowed". These serve distinct purposes and should not be combined into a single statement like "the fields must be correct".

A Complete Immutable Implementation

Use the Java 21/Maven/JUnit environment from 1.1 and save this complete class as src/main/java/Rational.java. BigInteger avoids silent long overflow during cross-multiplication. The mathematical specification admits any rational number, but actual values remain bounded by the implementation and available memory. Multiplication and gcd costs grow with bit length; big integers are not constant-cost machine words.

import java.math.BigInteger;
import java.util.Objects;

public final class Rational {
    private final BigInteger numerator;
    private final BigInteger denominator;

    private Rational(BigInteger numerator, BigInteger denominator) {
        this.numerator = numerator;
        this.denominator = denominator;
        checkRep();
    }

    public static Rational of(long numerator, long denominator) {
        return of(BigInteger.valueOf(numerator), BigInteger.valueOf(denominator));
    }

    public static Rational of(BigInteger numerator, BigInteger denominator) {
        Objects.requireNonNull(numerator, "numerator");
        Objects.requireNonNull(denominator, "denominator");
        if (denominator.signum() == 0) {
            throw new IllegalArgumentException("denominator is zero");
        }

        if (numerator.signum() == 0) {
            return new Rational(BigInteger.ZERO, BigInteger.ONE);
        }

        BigInteger gcd = numerator.gcd(denominator);
        BigInteger n = numerator.divide(gcd);
        BigInteger d = denominator.divide(gcd);
        if (d.signum() < 0) {
            n = n.negate();
            d = d.negate();
        }
        return new Rational(n, d);
    }

    public Rational add(Rational other) {
        Objects.requireNonNull(other, "other");
        BigInteger n = numerator.multiply(other.denominator)
                .add(other.numerator.multiply(denominator));
        BigInteger d = denominator.multiply(other.denominator);
        return of(n, d);
    }

    public BigInteger numerator() {
        return numerator;
    }

    public BigInteger denominator() {
        return denominator;
    }

    private void checkRep() {
        assert denominator.signum() > 0;
        assert numerator.gcd(denominator).equals(BigInteger.ONE);
        assert numerator.signum() != 0 || denominator.equals(BigInteger.ONE);
    }

    @Override
    public boolean equals(Object obj) {
        return this == obj
                || obj instanceof Rational other
                && numerator.equals(other.numerator)
                && denominator.equals(other.denominator);
    }

    @Override
    public int hashCode() {
        return Objects.hash(numerator, denominator);
    }

    @Override
    public String toString() {
        return denominator.equals(BigInteger.ONE)
                ? numerator.toString()
                : numerator + "/" + denominator;
    }
}

All instances enter through a factory and undergo normalization before object creation. The object holds immutable BigInteger values and exposes no mutation path, so ordinary internal updates cannot break its representation invariant.

Responsibility Boundary of assert

A zero denominator is an external input error and must be rejected explicitly. checkRep() checks internal assumptions of the implementation, suitable for testing and debugging; Java assertions may be disabled and thus cannot serve as input validation for a public API.

Representation Independence Requires More Than an Interface

Representation independence means that as long as two implementations satisfy the same public specification, the caller should not depend on their internal representations.

This comparison concerns replacing the internals of the same public Rational type; it does not grant automatic cross-class equality to arbitrary Java implementations.

Suppose later we store unreduced (numerator, denominator) pairs with nonzero denominators and reduce them during access or comparison, while keeping hashCode consistent with value equality. As long as the public methods' results, exceptions, and observable side effects still conform to the specification, the calling code remains unchanged. Conversely, if a class implements an interface but the caller performs downcasting, reads specific fields, or checks the concrete type of the implementation, representation independence has been violated.

Use Contract Tests to Constrain Different Implementations

Save this as src/test/java/RationalTest.java and run mvn -Dtest=RationalTest -DenableAssertions=true test; it should discover and pass 5 tests. Enabling assertions activates checkRep, while public input checks must work even with assertions disabled. Test abstract behavior and public accessors:

import static org.junit.jupiter.api.Assertions.*;
import org.junit.jupiter.api.Test;

class RationalTest {
    @Test
    void normalizesEquivalentRepresentations() {
        assertEquals(Rational.of(1, 2), Rational.of(2, 4));
        assertEquals(Rational.of(-1, 2), Rational.of(1, -2));
        assertEquals(Rational.of(0, 1), Rational.of(0, -9));
    }

    @Test
    void exposesCanonicalComponentsAndMatchingHashes() {
        var value = Rational.of(2, -4);
        assertEquals(java.math.BigInteger.valueOf(-1), value.numerator());
        assertEquals(java.math.BigInteger.valueOf(2), value.denominator());
        assertEquals(Rational.of(-1, 2).hashCode(), value.hashCode());
    }

    @Test
    void rejectsInvalidInputs() {
        assertThrows(IllegalArgumentException.class, () -> Rational.of(0, 0));
        assertThrows(NullPointerException.class, () ->
            Rational.of(null, java.math.BigInteger.ONE));
        assertThrows(NullPointerException.class, () -> Rational.of(1, 2).add(null));
    }

    @Test
    void normalizesLongMinValueWithoutOverflow() {
        var value = Rational.of(1, Long.MIN_VALUE);
        assertEquals(java.math.BigInteger.valueOf(-1), value.numerator());
        assertEquals(java.math.BigInteger.ONE.shiftLeft(63), value.denominator());
    }

    @Test
    void additionPreservesValueAndOperands() {
        Rational left = Rational.of(1, 3);
        Rational right = Rational.of(1, 6);

        assertEquals(Rational.of(1, 2), left.add(right));
        assertEquals(Rational.of(1, 3), left);
        assertEquals(Rational.of(1, 6), right);
    }
}

If a test can only pass by reading private fields, it's likely verifying an implementation rather than the contract of the ADT.

Specification Design Checklist

When designing an ADT, answer the following questions in sequence:

1. What is the abstract value set?
2. Are the operations sufficient to fulfill the type's promised behavior?
3. Can the preconditions be improved by better types or factory constructs?
4. Does each operation modify itself, its parameters, or external state?
5. What exceptions are thrown on failure, and is the state preserved?
6. Can the Abstraction Function (AF) and Representation Invariant (RI) fully cover every field and construction path?

The next section addresses the three most common ways through which abstract boundaries are breached: mutability, representation leakage, and equality.

References

• MIT 6.102: Abstract Data Types
• Java SE 21: BigInteger
• Java SE 21: Object.equals and hashCode