Is the understanding of abstract datatypes correct

abstractiondata structures

After reading lots of pages on various sites, I came to the conclusion that abstract datatype helps to separate the use of datastructure from its implementation. We can easily map the data into a datastructure by using an already available abstraction. And this abstraction is called ADT. Please tell me if I have understood this correctly. Also if you can give a small example, it will be very helpful. If you prefer to give any code in your example, C or Python would be helpful for me.

Addition: They are a very special implementation of data abstraction. What separates them from other instances of abstractions is that ADTs are theoretical constructs. Theoretical constructs that help map or represent data in a desired data structure. They have attributes or operations associated with them. These operations may be applied on the data that has been mapped into the ADT. How the data is actually stored inside the ADT or how the operations work are kept hidden.

EDIT: I had previously said, "ADT is like the blueprint of a datastructure". A few of the answers have explained why it's not. I didn't have a clear comprehension of what a 'blueprint' is and that was the reason for using the term. So, I've now removed it from my original text.

Best Answer

This is just a gist on the subject, I strongly suggest following the links herein.

"An abstract data type defines a class of abstract objects which is completely characterized by the operations available on those objects. This means that an abstract data type can be defined by defining the characterizing operations for that type." Liskov, Zilles: Programming with abstract data types

Given the informal definition above, the following pseudo-code can be seen as an ADT:

type stack;
stack stack_create();
void stack_push(stack, T);
T stack_pop(stack);

One point is that nothing is known about stack objects, except what can be inferred by the operations available for it -- in the case above, stack_create, stack_push and stack_pop. Every single bit of implementation and structure detail is left to the implementation side.

Now, take an OO/python class called Stack with the methods push and pop. 

class Stack:

    def __init__(self):
       ...
    def push(self, element):
       ...
    def pop(self):
       ...

If its clients know that there is a class called Stack and they have access to it, one way to see it is that the objects are characterized by the fact that they are instances of the class Stack whose structure contains push and pop fields -- regardless of the fact that they are callable. Clients also know that they can inherit from Stack to create something else and so on.

That is, much more is known/exposed to clients. Therefore, this Stack type is much less abstract than the previous one (it is exposed as a concrete structure with two fields, has a class with which you can do inheritance, etc). Consequently, one could argue this Stack type is not an Abstract Data Type conforming to the given definition. To be more strict, one would have to write something like this:

def create_stack():
   ...
def stack_push(stack, element):
   ...
def stack_pop(stack):
   ...

And here is a possible implementation of it (in the case below, if you already have the class above and just want to make it an ADT, it is just a wrapper):

def create_stack():
   retur Stack()
def stack_push(stack, element):
   return stack.push(element)
def stack_pop(stack):
   return stack.pop()

Now the client only knows the operations and their interfaces and use them (and only them) to infer what is the type "stack". From outside, nothing is known about the actual implementation and structure of a stack (unless they breach the abstraction by inspecting the structure of the result of create_stack).

Similarly, in C, you could mimic this by putting these function declarations on a .h header file (using a forward declaration standing as the stack type, or simply void*), and then, putting the struct definition and function implementations in the .c file.

Note on type systems: All the above, of course, are not in the context of languages with static type checking and good type systems -- such language may need to provide certain instruments to make reasonable ADTs possible. Furthermore, the way this theme is exposed in the paper cited above, "strong" type checking appears to be a matter of author preference alone; I did not see them being discussed or shown to be a requirement of ADTs -- the text actually seems to be careful in discussing type checking as something related but not essential. Plus, the explanation of a "C approach to ADT" (see above) was given by William Cook, the researcher who wrote Object-Oriented Programming Versus Abstract Data Types. [edit] On the other hand, Cook writes:

"Abstract data types depend upon a static type system to enforce type abstraction. It is not an accident that dynamic languages use objects instead of user-deļ¬ned abstract data types. Dynamic languages typically support built-in abstract data types for primitive types; the type abstraction here is enforced by the runtime system."

Related Topic