Abstract Data Types

• What does the word "abstract" mean?
• Where have we heard of this term before?
• How does it apply in the context of Computer Science?

Our definition

An Abstract Data Type (ADT) is a theoretical concept that:

• Separates Interface from Implementation
• Promotes maximum information hiding
• Conforms to the principle of least priviledge

In other words, an ADT gives the user what he needs and nothing more.
Note: In this context the term "user" is another programmer or software engineer.

Separating Interface from Implementation

A practical, real world example

Do you really understand how your car works? Unless you're a mechanic or automotive engineer, that answer is most likely "no". Why would you? Do you need to know?

How many people could drive to work in the morning if they had to pop the hood, whip out a screwdriver, adjust the carburator to the proper fuel/air mixture for a cold motor under the prevailing weather conditions, pull the throttle cable, make the contact to send current to the starter motor, etc ... all just to start the car. The point is, to start a car you only need to understand how to insert and turn the key and possibly step on the gas pedal (or in newer models, just push the button). These are part of your interface with the car. What's under the hood is the implementation. The fact that they're separated, i.e. the interface can be understood in isolation from the implementation, is what allows naive, mechanically inadept people to drive cars.

Whether you realized before or not, you're already familiar with the concept. Think about any time you've ever used a function in C or C++ that you did not write yourself. For example, if you used the cos function from the cmath library, you were interested in the interface only (in this case the function's prototype), and probably never got to see the implementation (the function's definition) since cos was already compiled and stored in a library.

If you are properly documenting your code through strategic comments as described in the Coding Standards, then you are providing a level of abstraction to someone reading your code. The strategic comment is analogous to an interface,and the code following it is the implementation. To understand what that part of the code is doing, one only needs to look at the comment. The code itself is for anyone concerned with how the task is being accomplished.

Another way to understand interface versus implementation is to think of what versus how.

An Analogue to Software Development Steps

This concept is largely analogous to our first two Software Development Steps. Consider the following:

Data Structure

A data structure:

• is a specific implementation of an ADT
• is a way of organizing data so that it can be used effectively (not necessarily efficiently)
• will have defined methods for user interaction
  
  At a minimum, a data structure will have methods for:
  • Creation
  • Deletion
  But those aren't very useful by themselves, so we also need methods to:
  • Get data in / Input / Write
  • Get data out / Output / Read

A poor abstraction

Consider the perfectly valid example of modular programming below (taken from Lab01), and observe where it falls short of our ideals of separation of interface and implementation.

The doublelist module.

#ifndef _DOUBLELIST_
#define _DOUBLELIST_

/* List Node type.  A list is a pointer to a node */
class DoubleNode {
public:
  double data;
  DoubleNode* next;
};

/* add2front(val,L) adds val to the front of list L */
void add2front(double val, DoubleNode* &L);

/* deletelist(L) deletes the nodes of the list L */
void deletelist(DoubleNode *L);

#endif

#include "doublelist.h"

void add2front(double val, DoubleNode* &L) {
  DoubleNode *T = new DoubleNode;
  T->data = val;
  T->next = L;
  L = T;
}

void deletelist(DoubleNode *L) {
  while(L != 0) {
    DoubleNode *T = L;
    L = L->next;
    delete T;
  }
}

Notice that the doublelist module (which itself defines a DoubleNode class), falls short of our ideals of separation of interface and implementation. Why? What's missing? The developer of this module did not provide a way for the user to get any data out of a list once it's been stored. The module requires that the user understand the implementation enough to get the data out of the list by following all the next pointers for each DoubleNode in the list.

YouTube explanations of ADTs

Here are a few short videos to help solidify the concept of an ADT.
https://www.youtube.com/watch?v=HcxqzYsiJ3k
https://www.youtube.com/watch?v=y5yRJIc2TCo
https://www.youtube.com/watch?v=2USMAwcRWHE