Hi. One of my units for Uni is centred on Data Structures (in Java). It discusses Abstract Data Types (ADTs). The meaning of an ADT seem to vary between lecture slides and the text book, even though the lecture slides are derived from the text book. The text book says that an Abstract Data Type has a set of values and operations, and that: "data representation plays no part in the characterization of an ADT. Of course, the ADT must have a data representation, but it is private." Then, in the lecture slides, a java interface class is used to illustrate a possible "contract" for a Stack class. So on one hand I'm being told that an ADT must have a private data representation, and on the other hand an interface (which cannot contain mutable data members) is an ADT. This frustrates me, because if I was to walk into an exam and be asked "What is an ADT?", I wouldn't know. I thought that an ADT would be an interface, but apparently it can be a concrete class as well... so I'm curious what an ADT really is? Cheers.

Quote:Original post by nolsen01
As I understand it, an ADT is a a data type that isn't necessarily defined by a concrete instance.

These data types may have private members associated with them, and an interface to manipulate (mutators, accessors) those private members, but they aren't defined by what private members they have or how their interface is implemented.

they are defined only by their behavior.

ie, a stack is a first in, first out data structure

Thusly, a stack is defined by its behavior, not by what kind of data it holds, or what methods are available to use it.

Hope that helped.

Hmmm... not really the kind of answer I was looking for. I'm curious to know the concise, universal meaning of an abstract data type.

The lecture slides say that a Set, String, etc is an ADT.. but they are concrete instances.

I do agree with you, but it's still too fuzzy to put into a sentence. (Note I'm not looking for exam answers, I'm just trying to find a definition that is widely agreed upon).

An abstract data type is not a language-level concept. It's not even an object-oriented concept. Therefore, attempting to describe it in terms of "interface", "class" or other similar language-level building blocks is bound to fail.

An abstract data type is a language-independent data type, defined not by its implementation in any particular language but rather by the theoretical operations it supports.

For instance, if you say that a stack allows pushing and popping values, where popping yields the last value pushed but not yet popped, as well as querying whether the stack is empty or not, then you have described the Stack ADT.

On the other hand, if you were to write:

interface Stack<E> {   void Push(E);  E Pop();  boolean Empty();}

Then your code would not be an ADT, it would be a representation of that ADT in the Java programming language, just like this other one:

class Stack<E>{  public Stack(Stack<E> pop, E top) { this.pop = pop ; this.top = top ; }  public final Stack<E> pop;  public final E top;}

In practice, Java provides several implementations of various ADTs (such as lists or dictionaries) which are called "Abstract Data Types" because it's shorter than "Java Standard Library Representations of Abstract Data Type", but this is a derived meaning, not a primary one.

Ok cheers for that guys... gives me more of an understanding of the true meaning and how I can now word my understanding of it.

Edit: The text I'm reading says that an ADT is also the values that comprise it... read:

Quote:An ADT is characterized by:
- a set of values
- a set of operations [...]

what do you think about that statement?

Quote:Original post by Mybowlcut
Edit: The text I'm reading says that an ADT is also the values that comprise it... read:

Quote:An ADT is characterized by:
- a set of values
- a set of operations [...]

what do you think about that statement?

This statement is a bit confusing, because "a set of values" could be taken to mean different things.

A mathematical definition of an Abstract Data Type is that it is first and foremost a Type. A type is a set of values (every value in that set is said to be "of that type") with several operations that either transform a value into another or map every value to an element of another set.

If you were looking for the mathematical definition of a stack over set E, then you would define it as the set S and operations (PUSH,POP,TOP,SIZE) such that:

• Set S contains a single element, called ∅, such that SIZE(∅) = 0.
  
• For every element s ∈ S, e ∈ E, there is a single s' = PUSH(s,e) ∈ S.
  
• For every such s', the following are well-defined: POP(s') = s, TOP(s') = e and SIZE(s') = 1 + SIZE(s).

This would be the complete mathematical definition of a stack as an ADT. It is said to be abstract because the actual nature of S is not specified, only its properties.

The other possible meaning of set is that every implementation of the ADT contains values, which is again quite correct—for any but the most trivial ADT (the singleton) you need to represent state, and state is represented with values.

One source of confusion is the traditional description of abstract data types as parametric types: for example not simply completing implementations of a "queue" but a "queue of T" ADT whose different possible implementations can be adapted to, and works in the same way for, any payload type T.

Strings are an unusual ADT in that they have a specific content (characters) and specific uses that imply easy but specialized operations (e.g. anything involving Unicode databases, such as lexicographical sorting), whole categories of sophisticated algorithms (e.g. search of substrings), peculiar performance issues (e.g. optimizing for large or small sizes or for common characters).

The contents of strings are not specified—in formal theory, a string over an alphabet A is the Kleene closure of that alphabet (with the appropriate operators defined over it). So, you could define a string of 3D vertices if you wanted (and this often happens in computational topology programs, for instance).