Reading 12: Abstract Data Types

Abstract data types are an instance of a general principle in software engineering, which goes by many names with slightly different shades of meaning. Here are some of the names that are used for this idea:

• Abstraction. Omitting or hiding low-level details with a simpler, higher-level idea.
• Modularity. Dividing a system into components or modules, each of which can be designed, implemented, tested, reasoned about, and reused separately from the rest of the system.
• Encapsulation. Building a wall around a module (a hard shell or capsule) so that the module is responsible for its own internal behavior, and bugs in other parts of the system can’t damage its integrity.
• Information hiding. Hiding details of a module’s implementation from the rest of the system, so that those details can be changed later without changing the rest of the system.
• Separation of concerns. Making a feature (or “concern”) the responsibility of a single module, rather than spreading it across multiple modules.

As a software engineer, you should know these terms, because you will run into them frequently. The fundamental purpose of all of these ideas is to help achieve the three important properties that we care about in 6.031: safety from bugs, ease of understanding, and readiness for change.

We have in fact already encountered some of these ideas in previous classes, in the context of writing methods that take inputs and produce outputs:

• Abstraction: A spec is an abstraction in that the client only has to understand its preconditions and postconditions to use it, not the full internal behavior of the implementation.
• Modularity: Unit testing and specs help make methods into modules.
• Encapsulation: The local variables of a method are encapsulated, since only the method itself can use or modify them. Contrast with global variables, which are quite the opposite, or local variables pointing to mutable objects that have aliases, which also threaten encapsulation.
• Information hiding: A spec uses information-hiding to leave the implementer some freedom in how the method is implemented.
• Separation of concerns: A spec is coherent if it is responsible for just one concern.

Starting with today’s class, we’re going to move beyond abstractions for methods, and look at abstractions for data as well. But we’ll see that methods will still play a crucial role in how we describe data abstraction.

User-defined types

Types, whether built-in or user-defined, can be classified as mutable or immutable. The objects of a mutable type can be changed: that is, they provide operations which when executed cause the results of other operations on the same object to give different results. So Date is mutable, because you can call setMonth and observe the change with the getMonth operation. But String is immutable, because its operations create new String objects rather than changing existing ones. Sometimes a type will be provided in two forms, a mutable and an immutable form. StringBuilder, for example, is a mutable version of String (although the two are certainly not the same Java type, and are not interchangeable).

The operations of an abstract type are classified as follows:

• Creators create new objects of the type. A creator may take an object as an argument, but not an object of the type being constructed.
• Producers create new objects from old objects of the type. The concat method of String, for example, is a producer: it takes two strings and produces a new one representing their concatenation.
• Observers take objects of the abstract type and return objects of a different type. The size method of List, for example, returns an int.
• Mutators change objects. The add method of List, for example, mutates a list by adding an element to the end.

We can summarize these distinctions schematically like this (explanation to follow):

• creator : t* → T
• producer : T+, t* → T
• observer : T+, t* → t
• mutator : T+, t* → void | t | T

These show informally the shape of the signatures of operations in the various classes. Each T is the abstract type itself; each t is some other type. The + marker indicates that the type may occur one or more times in that part of the signature, and the * marker indicates that it occurs zero or more times. | indicates or. For example, a producer may take two values of the abstract type T, like String.concat() does:

• concat : String × String → String

Some observers take zero arguments of other types t, such as:

• size : List → int

… and others take several:

• regionMatches : String × boolean × int × String × int × int → boolean

Mutators are often signaled by a void return type. A method that returns void must be called for some kind of side-effect, since it doesn’t otherwise return anything. But not all mutators return void. For example, Set.add() returns a boolean that indicates whether the set was actually changed. In Java’s graphical user interface toolkit, Component.add() returns the object itself, so that multiple add() calls can be chained together.

Abstract data type examples

The essential idea here is that an abstract data type is defined by its operations.

The set of operations for a type T, along with their specifications, fully characterize what we mean by T. So, for example, when we talk about the List type, what we mean is not a linked list or an array or any other specific data structure for representing a list. Instead we mean a set of opaque values – the possible objects that can have List type – that satisfy the specifications of all the operations of List: get(), size(), etc.

The values of an abstract type are opaque in the sense that a client can’t examine the data stored inside them, except as permitted by operations. Expanding our metaphor of a specification firewall, you might picture values of an abstract type as hard shells, hiding not just the implementation of an individual function, but of a set of related functions (the operations of the type) and the data they share (the private fields stored inside values of the type).

Designing an abstract type involves choosing good operations and determining how they should behave. Here are a few rules of thumb.

It’s better to have a few, simple operations that can be combined in powerful ways, rather than lots of complex operations.

Each operation should have a well-defined purpose, and should have a coherent behavior rather than a panoply of special cases. We probably shouldn’t add a sum operation to List, for example. It might help clients who work with lists of integers, but what about lists of strings? Or nested lists? All these special cases would make sum a hard operation to understand and use.

The set of operations should be adequate in the sense that there must be enough to do the kinds of computations clients are likely to want to do. A good test is to check that every property of an object of the type can be extracted. For example, if there were no get operation, we would not be able to find out what the elements of a list are. Basic information should not be inordinately difficult to obtain. For example, the size method is not strictly necessary for List, because we could apply get on increasing indices until we get a failure, but this is inefficient and inconvenient.

The type may be generic: a list or a set, or a graph, for example. Or it may be domain-specific: a street map, an employee database, a phone book, etc. But it should not mix generic and domain-specific features. A Deck type intended to represent a sequence of playing cards shouldn’t have a generic add method that accepts arbitrary objects like integers or strings. Conversely, it wouldn’t make sense to put a domain-specific method like dealCards into the generic type List.

Critically, a good abstract data type should be representation independent. This means that the use of an abstract type is independent of its representation (the actual data structure or data fields used to implement it), so that changes in representation have no effect on code outside the abstract type itself. For example, the operations offered by List are independent of whether the list is represented as a linked list or as an array.

You won’t be able to change the representation of an ADT at all unless its operations are fully specified with preconditions and postconditions, so that clients know what to depend on, and you know what you can safely change.

Example: different representations for strings

/** MyString represents an immutable sequence of characters. */
public class MyString { 

    //////////////////// Example of a creator operation ///////////////
    /** @param b a boolean value
     *  @return string representation of b, either "true" or "false" */
    public static MyString valueOf(boolean b) { ... }

    //////////////////// Examples of observer operations ///////////////
    /** @return number of characters in this string */
    public int length() { ... }

    /** @param i character position (requires 0 <= i < string length)
     *  @return character at position i */
    public char charAt(int i) { ... }

    //////////////////// Example of a producer operation ///////////////    
    /** Get the substring between start (inclusive) and end (exclusive).
     *  @param start starting index
     *  @param end ending index.  Requires 0 <= start <= end <= string length.
     *  @return string consisting of charAt(start)...charAt(end-1) */
    public MyString substring(int start, int end) { ... }
}

MyString s = MyString.valueOf(true);
assertEquals(4, s.length());
assertEquals('t', s.charAt(0));
assertEquals('r', s.charAt(1));
assertEquals('u', s.charAt(2));
assertEquals('e', s.charAt(3));

private char[] a;

public static MyString valueOf(boolean b) {
    MyString s = new MyString();
    s.a = b ? new char[] { 't', 'r', 'u', 'e' } 
            : new char[] { 'f', 'a', 'l', 's', 'e' };
    return s;
}

public int length() {
    return a.length;
}

public char charAt(int i) {
    return a[i];
}

public MyString substring(int start, int end) {
    MyString that = new MyString();
    that.a = new char[end - start];
    System.arraycopy(this.a, start, that.a, 0, end - start);
    return that;
}

private char[] a;
private int start;
private int end;

public static MyString valueOf(boolean b) {
    MyString s = new MyString();
    s.a = b ? new char[] { 't', 'r', 'u', 'e' } 
            : new char[] { 'f', 'a', 'l', 's', 'e' };
    s.start = 0;
    s.end = s.a.length;
    return s;
}

public int length() {
    return end - start;
}

public char charAt(int i) {
  return a[start + i];
}

public MyString substring(int start, int end) {
    MyString that = new MyString();
    that.a = this.a;
    that.start = this.start + start;
    that.end = this.start + end;
    return that;
}

/**
 * Represents a family that lives in a household together.
 * A family always has at least one person in it.
 * Families are mutable.
 */
class Family {
    // the people in the family, sorted from oldest to youngest, with no duplicates.
    public List<Person> people;

    /**
     * @return a list containing all the members of the family, with no duplicates.
     */
    public List<Person> getMembers() {
        return people;
    }
}

void client1(Family f) {
    // get youngest person in the family
    Person baby = f.people.get(f.people.size()-1);
    ...
}

/**
 * Represents a family that lives in a household together.
 * A family always has at least one person in it.
 * Families are mutable.
 */
class Family {
    // the people in the family
    public Set<Person> people;

    /**
     * @return a list containing all the members of the family, with no duplicates.
     */
    public List<Person> getMembers() {
        return new ArrayList<>(people);
    }
}

/**
 * Represents a family that lives in a
 * household together. A family always
 * has at least one person in it.
 * Families are mutable. */
class Family {
    // the people in the family,
    // sorted from oldest to youngest,
    // with no duplicates.
    public List<Person> people;

    /** @return a list containing all
     *  the members of the family,
     *  with no duplicates. */
    public List<Person> getMembers() {
        return people;
    }
}

/**
 * Represents a family that lives in a
 * household together. A family always
 * has at least one person in it.
 * Families are mutable. */
class Family {
    // the people in the family
    public Set<Person> people;


    /**
     * @return a list containing all
     * the members of the family,
     * with no duplicates. */
    public List<Person> getMembers() {
        return new ArrayList<>(people);
    }
}

void client2(Family f) {
    // get size of the family
    int familySize = f.people.size();
    ...
}

/**
 * Represents a family that lives in a
 * household together. A family always
 * has at least one person in it.
 * Families are mutable. */
class Family {
    // the people in the family,
    // sorted from oldest to youngest,
    // with no duplicates.
    public List<Person> people;

    /** @return a list containing all
     *  the members of the family,
     *  with no duplicates. */
    public List<Person> getMembers() {
        return people;
    }
}

/**
 * Represents a family that lives in a
 * household together. A family always
 * has at least one person in it.
 * Families are mutable. */
class Family {
    // the people in the family
    public Set<Person> people;


    /**
     * @return a list containing all
     * the members of the family,
     * with no duplicates. */
    public List<Person> getMembers() {
        return new ArrayList<>(people);
    }
}

void client3(Family f) {
    // get any person in the family
    Person anybody = f.getMembers().get(0);
    ...
}

/**
 * Represents a family that lives in a household together.
 * A family always has at least one person in it.
 * Families are mutable.
 */

public class Family {

    // the people in the family, sorted from oldest to youngest, with no duplicates.

    private List<Person> people;

    /**
     * @return a list containing all the members of the family, with no duplicates.
     */

    public List<Person> getMembers() {

        return people;

    }
}

Let’s summarize some of the general ideas we’ve discussed in this reading, which are applicable in general to programming in any language, and their specific realization using Java language features. The point is that there are several ways to do it, and it’s important to both understand the big idea, like a creator operation, and different ways to achieve that idea in practice.

There are three items in this table that haven’t yet been discussed in this reading:

1. Defining an abstract data type using an interface. We’ve seen List and ArrayList as an example, and we’ll discuss interfaces in a future reading.
2. Defining an abstract data type using an enumeration (enum). Enums are ideal for ADTs that have a small fixed set of values, like the days of the week Monday, Tuesday, etc. We’ll discuss enumerations in a future reading.
3. Using a constant object as a creator operation. This pattern is commonly seen in immutable types, where the simplest or emptiest value of the type is simply a public constant, and producers are used to build up more complex values from it.

We build a test suite for an abstract data type by creating tests for each of its operations. These tests inevitably interact with each other. The only way to test creators, producers, and mutators is by calling observers on the objects that result, and likewise, the only way to test observers is by creating objects for them to observe.

Here’s how we might partition the input spaces of the four operations in our MyString type:

// testing strategy for each operation of MyString:
//
// valueOf():
//    true, false
// length(): 
//    string len = 0, 1, n
//    string = produced by valueOf(), produced by substring()
// charAt(): 
//    string len = 1, n
//    i = 0, middle, len-1
//    string = produced by valueOf(), produced by substring()
// substring():
//    string len = 0, 1, n
//    start = 0, middle, len
//    end = 0, middle, len
//    end-start = 0, n
//    string = produced by valueOf(), produced by substring()

Then a compact test suite that covers all these partitions might look like:

@Test public void testValueOfTrue() {
    MyString s = MyString.valueOf(true);
    assertEquals(4, s.length());
    assertEquals('t', s.charAt(0));
    assertEquals('r', s.charAt(1));
    assertEquals('u', s.charAt(2));
    assertEquals('e', s.charAt(3));
}

@Test public void testValueOfFalse() {
    MyString s = MyString.valueOf(false);
    assertEquals(5, s.length());
    assertEquals('f', s.charAt(0));
    assertEquals('a', s.charAt(1));
    assertEquals('l', s.charAt(2));
    assertEquals('s', s.charAt(3));
    assertEquals('e', s.charAt(4));
}

@Test public void testEndSubstring() {
    MyString s = MyString.valueOf(true).substring(2, 4);
    assertEquals(2, s.length());
    assertEquals('u', s.charAt(0));
    assertEquals('e', s.charAt(1));
}

@Test public void testMiddleSubstring() {
    MyString s = MyString.valueOf(false).substring(1, 2);
    assertEquals(1, s.length());
    assertEquals('a', s.charAt(0));
}

@Test public void testSubstringIsWholeString() {
    MyString s = MyString.valueOf(false).substring(0, 5);
    assertEquals(5, s.length());
    assertEquals('f', s.charAt(0));
    assertEquals('a', s.charAt(1));
    assertEquals('l', s.charAt(2));
    assertEquals('s', s.charAt(3));
    assertEquals('e', s.charAt(4));
}

@Test public void testSubstringOfEmptySubstring() {
    MyString s = MyString.valueOf(false).substring(1, 1).substring(0, 0);
    assertEquals(0, s.length());
}

Try to match each test case to the partitions it covers.

Notice that each test case typically calls a few operations that make or modify objects of the type (creators, producers, mutators) and some operations that inspect objects of the type (observers). As a result, each test case covers parts of several operations.

/** Immutable datatype representing a student's progress through school. */
class Student {

    /** make a freshman */
    public Student() { ... }

    /** @return a student promoted to the next year, i.e.
           freshman returns a sophomore, 
           sophomore returns a junior,
           junior returns a senior,
           senior returns an alum,
           alum stays an alum and can't be promoted further. */   
    public Student promote() { ... }

    /** @return number of years of school completed, i.e.
           0 for a freshman, 4 for an alum */
    public int getYears() { ... }

}

• Abstract data types are characterized by their operations.
• Operations can be classified into creators, producers, observers, and mutators.
• An ADT’s specification is its set of operations and their specs.
• A good ADT is simple, coherent, adequate, and representation-independent.
• An ADT is tested by generating tests for each of its operations, but using the creators, producers, mutators, and observers together in the same tests.

These ideas connect to our three key properties of good software as follows:

• Safe from bugs. A good ADT offers a well-defined contract for a data type, so that clients know what to expect from the data type, and implementers have well-defined freedom to vary.

• Easy to understand. A good ADT hides its implementation behind a set of simple operations, so that programmers using the ADT only need to understand the operations, not the details of the implementation.

• Ready for change. Representation independence allows the implementation of an abstract data type to change without requiring changes from its clients.