Abstraction and ADTs --- Some Help for Assignment 2

What does it mean to define an ADT?

To define an ADT is to specify (1) some objects and (2) a collection of operations that can be performed on those objects.

Although for this assignment, you will eventually use your ADT definition as the basis for some OOT code, the ADT definition itself is much more general than that. It expresses a concept or idea for how objects of its kind can be manipulated. That idea may be made real by building a computer program, or a physical object. Or it may never be made real at all -- an ADT can merely exist in your head.

Examples of ADTs

Three examples are:

The ordered set ADT, defined on slides 2 and 3 of a handout.
The stack ADT, defined on slide 266
The queue ADT, defined on slide 276

How to think about your ADT -- an analogy

Have you ever played Monopoly, Trivial Pursuit, or any other non-computer game that comes in a box? Imagine that you work for a company that produces such games. You have just come up with a great idea for a new game about labyrinths. So far, the idea exists only in your imagination. You want to show the game to your boss, and you'd like the design department to build a version of the game. There are many decisions to be made, like:

Should the tiles be made out of cardboard, plastic, wood?
How will the tiles be made so that they can slide against each other in the required way? Perhaps they'll have grooves in their sides, or maybe there will be a base underneath with tracks in it.
Will the player pieces be small plastic people, or some sort of abstract shape? What will they be made of?
What exactly will the pictures on the tiles look like? They will have to somehow represent straight, cross, and elbow shapes, but will they be paths through plumbing pipes, or along a road, or just abstract looking?

The design people are the experts on graphic design and working with materials, so you are going to leave all such decisions up to them. However, you need to convey to them two sorts of information:

What objects are part of the game.
That is, when someone buys the game and dumps out the contents of the box, what stuff will fall out? (Tiles, prize pieces, and so on.)
What kinds of manipulations of these objects are possible.
That is, what can one do to the tiles etc? (slide the spare tile in, and so on.)

You will write down specifications for the above in plain English. Your specifications should be very clear, unambiguous, and complete. (Imagine that you will be out of the country for a month exactly when they are going to build your game, so they won't be able to ask you for clarifications.)

Your specifications definitely should not say anything about grooves in wood, or pictures of plumbing pipes. This is true even if you expect the designers will choose wood with pictures of plumbing pipes. They are simply separate issues. Neither should your specifications say anything about pointers, modules, subprograms, or anything at all to do with a program, whether or not you plan later to write a program based on your ADT.

General form to use on assignment 2

You ADT definition should have this form:

   Game Data (or whatever your choose to call your ADT) consists of
   the following objects:
       -   [ List the objects here, and specify any properties
       -     that they must have.  Include only essential properties -- 
       -     you don't want to tie things down unnecessarily.  Don't
       -     talk about what the objects can do, just what they are. ]
   The operations that one can perform on Game Data are:
       -   [ List the operations here.  Specify exactly what each one should
       -     do.  You will have to refer to information that flows to and 
       -     from the operation.  
       -     For example, when we defined the Retrieve operation for ordered
       -     sets, we said "Given an integer i ... returns the element of rank 
             i in the ordered set. ]

Your definition must be specific (and clear and unambiguous) enough that, from only your definition, one could implement the ADT. That is, one could:

define a data structure to represent each object
define a subprogram to perform each operation

To do this, it should not be necessary to know anything other than what's written in your ADT definition.

What's left for the main program to do?

Some students imagine that the ADT will define, and the corresponding module will implement, everything about the game. Hence that there will be nothing left for the main program to do, other than to call some exported routine like GameData.playGame that plays an entire round of the game. (Sort of like how Simulate.run does an entire simulation.)

This is not correct. Your ADT should defined only the objects involved in Labyrinth, and how they can be manipulated. Specifying how the game is played, using these objects and operations, is the not the job of the ADT. (After all, those same objects and operations could be used to create a game with different rules, perhaps a cooperative game in which the two players work together rather than against eacy other.) So your ADT should not include an operation for playing a game. And your corresponding module should not include a subprogram for playing a game. Playing a game is the job of the main program.

By the way, when I talk about the "main program" I mean the code outside of the module. It will be big enough that you will want to break it down into subprograms.

Abstraction in general

When trying to understand the concept of abstraction, it helps to think about precisely what the word "abstract" means. My Webster's dictionary defines several senses of the word that are relevant to how we use it in computer science.

As an adjective, it can mean "considered apart from concrete existence". This certainly applies to the notion of an Abstract Data Type; it is a concept quite separate from any concrete existence that we might create, say, with a program.

As a noun, it can mean "A statement summarizing the important points of a given text"; "the concentrated essence of a larger whole." In other words, an "abstract" ignores the small details. Modules certainly allow us to ignore the small details to do with how things are implemented. Subprograms do the same thing, on a smaller scale. For example, in the assignment hints we suggest that you include this function in your module:

    % tileTypeAt
    %----------------------------------------------------------------
    % Return the type of the tile at location (row, col).
    function tileTypeAt (row : int, col : int) : tileType

Once you've written it, you "abstract away from" the details of the data structure and act as if it's accessible directly by row and column number. You can probably come up with a number of subprograms that provide convenient abstractions like this for you.

Abstraction is one of the most important concepts in computer science. Abstraction makes it possible to manage the complexity of large programs.

Back to the csc148 home page