15

Just browsing through Code Complete last night and I came across the explanation of abstract data types.

I must have read it 5 times, and the Wikipedia article doesn't help much either. So what I'm looking for is a simple explanation of exactly what is an Abstract Data Type? Any solid examples? In C# or VB?

I understand that String is supposed to be one, why is this? And why isn't Int32 one? Or is it?

Any pointers are much appreciated.

1

5 Answers 5

7

Objects are not ADTs (*). (So in C# String and Int32 are not ADTs.)

With that out of the way, an abstract data type "has a public name, a hidden representation, and operations to create, combine and observe values of the abstraction". (Quoting from the linked paper.)

(*) Briefly, Cook explains that:

  • Objects cannot inspect the hidden representation of other objects, unlike members of an ADT. That implies that values of an ADT may be implemented efficiently, even for operations that require inspection of multiple abstract values.
  • Objects behave like a characteristic function over the values of a type, rather than as an algebra. Objects use procedural abstraction rather than type abstraction
  • ADTs usually have a unique implementation in a program. When one's language has modules, it's possible to have multiple implementations of an ADT, but they can't usually interoperate.
4

An abstract data type is a theoretical concept (a collection of function signatures and rules) to describe the values that a type can have by defining how these values can be constructed and which constructions create the same values. For example, for integers, you can have:

Three signatures:

zero: INTEGER
successor(INTEGER): INTEGER
predecessor(INTEGER): INTEGER

And the following rules:

successor(predecessor(X)) = X
predecessor(successor(X)) = X

You can introduce addition, subtraction and any other operation by providing these rules.

ADTs are vehicle to understand types, similar to a Turing machine is used to understand computation.

There is a relationship between ADTs and data types in programming languages, more specifically classes in OO languages. But that is a complex relationship, as instances of classes in OO introduce the idea of 'object identity' which is not present in ADTs.

1

An abstract data type is defined by it's interface. I think a good example of this is the JDBC API. You look up a Datasource (an ADT), and you get a specific implementation of that datasource depending on what database type you want to access. You create Statements and work with ResultSets, which are also ADTs. The point is that the interface is defined, the implementation is not.

Why would you want this? Again with JDBC, it allows more portable code because since you use the interface to access the object, you don't need to worry about what kind of database you are accessing. That can be handled in exactly one place: where the datasource is defined. If you are using factories, the factory can return different objects based on the context of the data they contain, while allowing the code operating on those objects to remain the same.

Some reasons I see to use ADTs:

  • To keep from repeating yourself. If you only need to handle specifics in one place, changes are easier to do and track.
  • To provide a level of abstraction. ADTs allow you to think at a higher level. You can think of what to do rather than how to do it.
0

An Abstract Data Type (ADT) is any type whose internal implementation can change without affecting code that uses it. By "internal implementation", I mean that the interface (API, if you wish) for the ADT remains.

In that sense, the classic "internals-hiding" class implements an ADT, it would be possible to have a parallel implementation with different internal implementation, as long as the API remains unchanged.

-2

If you know Factory Design Pattern, It'll more understandable what is ADT.

Let us discuss it with the example, Let take a Pizza store, which has the regional branches in NY, Chicago, California, etc. The Head Office, which is in Washington defines how should a Pizza prepared and let the regional branches implements that on their own.

Here, Pizza is a ADT, and NYPizza, ChicagoPizza, CaliforniaPizza are subtypes.


Hope this helps to get the idea in a abstract way.

1
  • 1
    You are describing abstract classes but not abstract data types (e.g. why is List an abstract datatype, but not String?).
    – user40980
    Jul 3, 2015 at 13:08

Not the answer you're looking for? Browse other questions tagged or ask your own question.