Reading 10: Abstract Data Types

In this reading, we look at a powerful idea: abstract data types. This idea enables us to separate how we use a data structure in a program from the particular form of the data structure itself.

Abstract data types address a particularly dangerous problem: clients making assumptions about the type’s internal representation. We’ll see why this is dangerous and how it can be avoided. We’ll also discuss the classification of operations, and some principles of good design for abstract data types.

Access control in Java

You should already have read: Controlling Access to Members of a Class in the Java Tutorials.

reading exercises

The following questions use the code below. Study it first, then answer the questions.

 class Wallet < private int amount; public void loanTo(Wallet that) < // put all of this wallet's money into that wallet /*A*/ that.amount += this.amount; /*B*/ amount = 0; > public static void main(String[] args) < /*C*/ Wallet w = new Wallet(); /*D*/ w.amount = 100; /*E*/ w.loanTo(w); > > class Person < private Wallet w; public int getNetWorth() < /*F*/ return w.amount; > public boolean isBroke() < /*G*/ return Wallet.amount == 0; > >

Suppose the program has paused after running the line marked /*A*/ but before reaching /*B*/ . A partial snapshot diagram of its internal state is shown at the right, with numbered gray boxes as placeholders for you to fill in. What should each of those boxes be?

that.amount += this.amount;

The reference to this.amount would be prevented by Java because it uses this to access a private field. (missing answer)

The reference to that.amount would be prevented by Java because that.amount is a private field in a different object. (missing answer)

The reference to that.amount would be prevented by Java because it writes to a private field. (missing answer)

amount = 0;

The reference to amount would be prevented by Java because it doesn’t mention this . (missing answer)

Wallet w = new Wallet();

The call to the Wallet() constructor would be prevented by Java because there is no public Wallet() constructor declared. (missing answer)

w.amount = 100;

The access to w.amount would be prevented by Java because amount is private and main is not an instance method. (missing answer)

w.loanTo(w);

The call to loanTo() would be prevented by Java because this and that will be aliases to the same object. (missing answer)

return w.amount;

The reference to w.amount is allowed by Java because both w and amount are private variables. (missing answer)

The reference to w.amount is allowed by Java because amount is a primitive type, even though it’s private. (missing answer)

The reference to w.amount would be prevented by Java because amount is a private field in a different class. (missing answer)

return Wallet.amount == 0;

The reference to Wallet.amount is allowed by Java because Wallet has permission to access its own private field amount . (missing answer)

The reference to Wallet.amount is allowed by Java because amount is a static variable. (missing answer)

The reference to Wallet.amount would be prevented by Java because amount is a private field. (missing answer)

The reference to Wallet.amount would be prevented by Java because amount is an instance variable. (missing answer)

What abstraction means

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 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 good method spec is coherent, meaning 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

In the early days of computing, a programming language came with built-in types (such as integers, booleans, strings, etc.) and built-in functions, e.g., for input and output. Users could define their own functions: that’s how large programs were built.

A major advance in software development was the idea of abstract types: that one could design a programming language to allow user-defined types, too. This idea came out of the work of many researchers, notably Dahl, who invented the Simula language; Hoare, who developed many of the techniques we now use to reason about abstract types; and Parnas, who coined the term information hiding and first articulated the idea of organizing program modules around the secrets they encapsulated.

Here at MIT, Barbara Liskov and John Guttag did seminal work in the specification of abstract types, and in programming language support for them – and developed the original 6.170, the predecessor to 6.005, predecessor to 6.031. Barbara Liskov earned the Turing Award, computer science’s equivalent of the Nobel Prize, for her work on abstract types.

The key idea of data abstraction is that a type is characterized by the operations you can perform on it. A number is something you can add and multiply; a string is something you can concatenate and take substrings of; a boolean is something you can negate, and so on. In a sense, users could already define their own types in early programming languages: you could create a record type date, for example, with integer fields for day, month, and year. But what made abstract types new and different was the focus on operations: the user of the type would not need to worry about how its values were actually stored, in the same way that a programmer can ignore how the compiler actually stores integers. All that matters is the operations.

In Java, as in many modern programming languages, the separation between built-in types and user-defined types is a bit blurry. The classes in java.lang , such as Integer and Boolean , are built-in in the sense that the Java language specification requires them to exist and behave in a certain way, but they are defined using the same class/object abstraction as user-defined types. But Java complicates the issue by having primitive types that are not objects. The set of these types, such as int and boolean , cannot be extended by the user.

reading exercises

Consider an abstract data type Bool . The type has the following operations:

true : Bool
false : Bool

and : Bool × Bool → Bool
or : Bool × Bool → Bool
not : Bool → Bool

… where the first two operations construct the two values of the type, and the last three operations have the usual meanings of logical and, logical or, and logical not on those values.

Which of the following are possible ways that Bool might be implemented, and still be able to satisfy the specs of the operations? Choose all that apply.