Abstraction Functions and Rep Invariants

This is an easy-to-understand note for Reading 13: Abstraction Functions & Rep Invariants.

# Invariants [ɪn’veərɪənt] 不变量

Invariant: A property of a program that is always true, for every possible runtime state of the program.

Most important property of a good abstract data type is that it preserves its own invariants. That means the ADT is responsible for ensuring that its own invariants hold, instead of depending on good behavior from its clients.

Such as:

• Immutability

Contrast that with a string type that guarantees that it will be immutable only if its clients promise not to change it. Then you’d have to check all the places in the code where the string might be used.

## Immutability [i,mjuitə’biləti] 不变性

representation exposure: Code outside the class can modify the representation directly. It may threaten invariants and representation independence.

representation independence: The use of an abstract type is independent of its representation.

representation(rep): The actual data structure or data fields used to implement the class.

# Rep invariants and abstraction function

Consider the relationship between two spaces of values:

1. The space of representation values consists of the values of the actual implementation as a single object.
2. The space of abstract values consists of the values that the type is designed to support.

Commonly, a small network of objects is needed to implement the abstract values.

Note:

• Every abstract value is mapped to by(由……映射而来) some rep value.
• Some abstract values are mapped to by more than one rep value. There’s more than one way to represent an abstract value.
• Not all rep values are mapped. Some reps may have no meaning.

Abstract Function

AF : R → A

The function is surjective/onto(满射的), not necessary injective/one-to-one(单射的), and therefore not necessarily bijective(双射的), and often partial.

Rep Invariant that maps Rep values to Booleans

RI : R → boolean

For a rep value, RI® is true if and only if r is mapped by AF, aks, the rep is well-formed/meaningful.
RI is the subset of rep values on which AF is defined.

RI(“”) = true, RI(“abc”) = true, and RI(“bac”) = true, but RI(“abbc”) = false.

Note: rep invariant is different from invariant.

Even with the same type for the rep value space and the same rep invariant, we might still interpret the rep differently.

In summary, there are five things to remember:

• The abstract value space for the specification
• The rep value space for the implementation
• Deciding which rep values are legal, and the rep invariant is a function from rep values to boolean
• Interpreting reps as abstract values
• Writing these assumptions in your code

Checking the rep invariant

If your implementation asserts the RI at runtime, then you can catch bugs early.

Here’s a method for RatNum that tests its rep invariant:

Observer methods don’t normally need to call checkRep(), but it’s good defensive practice to do so anyway.

Calling checkRep() in every method means you’ll be more likely to catch rep invariant caused by rep exposure.

No null values in the rep

In MIT 6.031, the rep invariant implicitly includes x != null for every reference x in the rep that has object type.
checkRep() also checks for x != null. It may be checked when you check a string’s length, etc.

# Beneficent mutation

Beneficent mutation: The abstract value should never change. But the implementation is free to mutate a rep value as long as it continues to map to the same abstract value.

For example: A RatNum type whose rep has weaker rep invariant that doesn’t require the numerator and denominator to be stored in lowest terms.
We can first simplify the rational number when the user calls ‘toString()’. We mutate the rep even in an observer method.

# Documenting the AF, RI, and safety from rep exposure

Precise:

• RI: what makes the field values valid or not.
• AF: define how the concrete field values are interpreted.

rep exposure safety argument: A comment that examines each part of the rep, looks at the code that handles the part of the rep, and presents a reason why the code doesn’t expose the rep.

## What an ADT specification may talk about

ADT should only talk about things that are visible to the client.

# ADT invariants replace preconditions

ADT encapsulates and enforces properties that we would otherwise have to stipulate in a precondition.

use SortedSet<Character> set1 instead of

because the elaborate precondition is no better than directly using a good ADT.