CSE 331: Subtyping practice

Question 1: Behavioral Subtyping: Counters

Compare public instance methods and class-wide promises, ignoring constructor signatures. Justify each answer outside the boxes. You may assume no arithmetic here ever overflows.

Part 1

Consider these classes:

/** A counter holding a nonnegative integer. */
class Counter {
    private int n = 0;
    /** @return the current value; changes nothing */
    public int value() { return n; }
    /** @modifies this
     *  @effects increases the value by exactly 1 */
    public void increment() { n++; }
}

/** A counter whose value stays between 0 and its fixed limit. */
class BoundedCounter {
    private int n = 0;
    private final int limit;
    /** @requires 0 <= limit
     *  @effects creates a counter with value 0 and this limit */
    BoundedCounter(int limit) { this.limit = limit; }
    /** @return the current value; changes nothing */
    public int value() { return n; }
    /** @requires value() < limit
     *  @modifies this
     *  @effects increases the value by exactly 1 */
    public void increment() {
        if (n == limit) throw new IllegalStateException();
        n++;
    }
}

Y if the first type is a behavioral subtype of the second
N if it is not

	Subtype?
a. Is `BoundedCounter` a behavioral subtype of `Counter`?

a. Is BoundedCounter a behavioral subtype of Counter?

Answer

Subtype?
N

No: BoundedCounter.increment has a stronger precondition.

Take a limit of 2 and a current value of 2.
Counter.increment() permits the call and promises a value of 3.
BoundedCounter.increment() requires a value below 2, so its specification makes no promise on this call. Its code throws.
The bound does not excuse rejecting a call that Counter permits.

The rule: a behavioral subtype keeps every promise.

Part 2

Compare this class with those in Part 1, using the same limit for the bounded and saturating counters. Calls outside @requires have unspecified behavior.

/** A counter whose value stays between 0 and its fixed limit. */
class SaturatingCounter {
    private int n = 0;
    private final int limit;
    /** @requires 0 <= limit
     *  @effects creates a counter with value 0 and this limit */
    SaturatingCounter(int limit) { this.limit = limit; }
    /** @return the current value; changes nothing */
    public int value() { return n; }
    /** @modifies this
     *  @effects increases the value by 1 if below the limit;
     *      otherwise leaves it unchanged */
    public void increment() { if (n < limit) n++; }
}

Y if the first type is a behavioral subtype of the second
N if it is not

	Subtype?
b. Is `SaturatingCounter` a behavioral subtype of `Counter`?
c. Is `SaturatingCounter` a behavioral subtype of `BoundedCounter`?
d. Is `BoundedCounter` a behavioral subtype of `SaturatingCounter`?

b. Is SaturatingCounter a behavioral subtype of Counter?

Answer

Subtype?
N

No: at the limit, increment breaks Counter's postcondition.

Take a limit of 2 and a current value of 2.
Both types permit a call to increment().
Counter promises a value of 3, while SaturatingCounter leaves it 2.
Returning normally is insufficient: the promised state change matters.

The rule: a behavioral subtype keeps every promise.

c. Is SaturatingCounter a behavioral subtype of BoundedCounter?

Answer

Subtype?
Y

Yes: it keeps every promise on calls that BoundedCounter permits.

Both types keep the value between 0 and the same fixed limit.
Both provide value() with the same specification.
BoundedCounter permits increment() only below the limit. On those calls, SaturatingCounter also increases the value by exactly 1.
SaturatingCounter additionally specifies behavior at the limit. Its weaker precondition does not break any promise of BoundedCounter.

The rule: a behavioral subtype keeps every promise.

d. Is BoundedCounter a behavioral subtype of SaturatingCounter?

Answer

Subtype?
N

No: BoundedCounter does not promise the required behavior at the limit.

With limit 2 and value 2, SaturatingCounter.increment() is permitted and promises to leave the value unchanged.
The same call violates BoundedCounter.increment()'s precondition.
That specification makes no promise there; its implementation throws.

The rule: a behavioral subtype keeps every promise.

Part 3

Finally, consider this class, together with Counter from Part 1:

/** A nonnegative counter that cannot change after construction. */
class ImmutableCounter {
    private final int n;
    /** @requires 0 <= initial
     *  @effects creates a counter with value initial */
    ImmutableCounter(int initial) { n = initial; }
    /** @return the current value; changes nothing */
    public int value() { return n; }
}

Y if the first type is a behavioral subtype of the second
N if it is not

	Subtype?
e. Is `Counter` a behavioral subtype of `ImmutableCounter`?
f. Is `ImmutableCounter` a behavioral subtype of `Counter`?

e. Is Counter a behavioral subtype of ImmutableCounter?

Answer

Subtype?
N

No: Counter breaks the class-wide immutability promise.

ImmutableCounter promises that its value cannot change after construction.
A Counter with value 0 changes to 1 when increment() is called.
A client relying on immutability could observe that change after another alias calls increment(), even if the client itself only calls value().
Merely providing the same observer is insufficient to keep the promise.

The rules: behavioral subtyping and immutable objects.

f. Is ImmutableCounter a behavioral subtype of Counter?

Answer

Subtype?
N

No: it lacks the increment() operation required by Counter.

A client of Counter may call both value() and increment().
ImmutableCounter provides only value().
Its stronger promise about stability cannot replace a required operation.

The rule: a behavioral subtype keeps every promise.

Question 2: Behavioral Subtyping: Worklists

Judge behavioral subtyping from the specifications. Clients use public methods only. Justify each answer outside the boxes. You may assume no arithmetic here ever overflows.

Part 1

Consider this interface and class:

/** A collection of integers, allowing duplicate occurrences. */
interface Worklist {
    /** @modifies this
     *  @effects adds one occurrence of x, preserving all others */
    void add(int x);
    /** @requires this is nonempty
     *  @modifies this
     *  @effects removes one occurrence
     *  @return the removed integer */
    int remove();
    /** @return the current number of occurrences; changes nothing */
    int size();
}

/** An initially empty sequence of integers. */
class QueueWorklist implements Worklist {
    protected final ArrayDeque<Integer> entries = new ArrayDeque<>();
    /** @modifies this
     *  @effects appends x at the back, preserving all other entries */
    public void add(int x) { entries.addLast(x); }
    /** @requires this is nonempty
     *  @modifies this
     *  @effects removes the front entry, preserving all others in order
     *  @return the removed integer */
    public int remove() { return entries.removeFirst(); }
    /** @return the current number of entries; changes nothing */
    public int size() { return entries.size(); }
}

Y if the first type is a behavioral subtype of the second
N if it is not

	Subtype?
a. Is `QueueWorklist` a behavioral subtype of `Worklist`?

a. Is QueueWorklist a behavioral subtype of Worklist?

Answer

Subtype?
Y

Yes: each queue operation satisfies the corresponding worklist promise.

add(x) adds one occurrence without removing any existing occurrence.
On a nonempty queue, remove() removes and returns its front entry. That entry is one of the occurrences Worklist permits removing.
size() reports the current number of occurrences without changing them.
Choosing a particular removal order strengthens the removal promise.

The rule: a behavioral subtype keeps every promise.

Part 2

This class inherits add, remove, and size from QueueWorklist:

/** An initially empty sequence; inherits add, remove, and size. */
class DequeWorklist extends QueueWorklist {
    /** @modifies this
     *  @effects inserts x at the front, preserving all other entries */
    public void addFirst(int x) { entries.addFirst(x); }
    /** @requires this is nonempty
     *  @modifies this
     *  @effects removes the back entry, preserving all others in order
     *  @return the removed integer */
    public int removeLast() { return entries.removeLast(); }
}

Y if the first type is a behavioral subtype of the second
N if it is not

	Subtype?
b. Is `DequeWorklist` a behavioral subtype of `QueueWorklist`?
c. Is `QueueWorklist` a behavioral subtype of `DequeWorklist`?

b. Is DequeWorklist a behavioral subtype of QueueWorklist?

Answer

Subtype?
Y

Yes: its additional operations preserve the shared operations' promises.

add, remove, and size retain their inherited specifications.
addFirst and removeLast leave an ordinary sequence of entries. The inherited methods still append at the back, remove at the front, and report the current size.
For example, after add(1); addFirst(2);, remove() returns 2. The queue contract promises the current front, not the earliest insertion across every possible method.

The rule: a behavioral subtype keeps every promise.

c. Is QueueWorklist a behavioral subtype of DequeWorklist?

Answer

Subtype?
N

No: it lacks operations required by DequeWorklist.

A client of DequeWorklist may call addFirst or removeLast.
QueueWorklist provides neither operation.
Agreement on add, remove, and size does not supply the missing methods.

The rule: a behavioral subtype keeps every promise.

Part 3

This class inherits remove and size from QueueWorklist:

/** An initially empty sequence; inherits remove and size. */
class CountingQueueWorklist extends QueueWorklist {
    private int added = 0;
    /** @modifies this
     *  @effects appends x at the back, preserving all other entries,
     *      and increases totalAdded() by 1 */
    public void add(int x) { super.add(x); added++; }
    /** @return the number of add calls since construction,
     *      including duplicates and entries later removed;
     *      changes nothing */
    public int totalAdded() { return added; }
}

Y if the first type is a behavioral subtype of the second
N if it is not

	Subtype?
d. Is `CountingQueueWorklist` a behavioral subtype of `QueueWorklist`?
e. Is `QueueWorklist` a behavioral subtype of `CountingQueueWorklist`?

d. Is CountingQueueWorklist a behavioral subtype of QueueWorklist?

Answer

Subtype?
Y

Yes: recording the history does not change the promised queue behavior.

add still appends exactly one entry at the back, preserving the others.
remove and size retain their inherited specifications.
The extra counter records successful additions without changing the entries. After add(1); add(1); remove();, size() is 1 and totalAdded() is 2.
QueueWorklist makes no promise forbidding this additional information.

The rule: a behavioral subtype keeps every promise.

e. Is QueueWorklist a behavioral subtype of CountingQueueWorklist?

Answer

Subtype?
N

No: it lacks the required totalAdded() operation.

A client of CountingQueueWorklist may ask how many additions have occurred.
QueueWorklist has no method with that specification.
size() cannot replace it: removing an entry reduces the size but does not reduce the historical addition count.

The rule: a behavioral subtype keeps every promise.

Part 4

Finally, consider this class. Its fixed blocklist contains -1 and 0.

/** An initially empty sequence; inherits remove and size. */
class BlocklistQueueWorklist extends QueueWorklist {
    private final Set<Integer> blocked = Set.of(-1, 0);
    /** @modifies this
     *  @effects if x is blocked, throws IllegalArgumentException
     *      and leaves this unchanged; otherwise appends x at the
     *      back, preserving all other entries */
    public void add(int x) {
        if (blocked.contains(x)) throw new IllegalArgumentException();
        super.add(x);
    }
}

Y if the first type is a behavioral subtype of the second
N if it is not

	Subtype?
f. Is `BlocklistQueueWorklist` a behavioral subtype of `QueueWorklist`?
g. Is `QueueWorklist` a behavioral subtype of `BlocklistQueueWorklist`?

f. Is BlocklistQueueWorklist a behavioral subtype of QueueWorklist?

Answer

Subtype?
N

No: it rejects an addition that QueueWorklist promises to perform.

Start with an empty queue and call add(0).
QueueWorklist has no precondition restricting the integer, so it promises to append 0 and return normally.
BlocklistQueueWorklist instead throws and leaves the queue empty.
The declared extends relationship does not make that behavior satisfy the superclass's specification.

The rule: a behavioral subtype keeps every promise.

g. Is QueueWorklist a behavioral subtype of BlocklistQueueWorklist?

Answer

Subtype?
N

No: accepting a blocked integer breaks the promised rejection behavior.

Start with an empty queue and call add(0).
BlocklistQueueWorklist specifies this call: it must throw IllegalArgumentException and leave the queue unchanged.
QueueWorklist instead appends 0 and returns normally.
This is a promised exception, not a precondition forbidding the call. Accepting more inputs does not preserve that promise.

The rule: a behavioral subtype keeps every promise.