Abstract data type
An Abstract Data Type ( ADT) is a composite of data along with the definition of all valid operations that access it.
- 3.2.1 Mathematics and axiomatic method
- 3.2.2 Mathematics and algebraic method
- 3.2.3 Informal method ( Java)
- 3.2.4 Specification of a functional programming language ( Haskell )
Description
Since access is made only on the specified operations, the data is encapsulated to the outside.
An ADT describes what the operations do (semantics ), but not how they do it ( implementation). Even the concept of ADTs can specify different and an ADT are listed in various ways, for example by pseudocode or by a mathematical description. More modern programming languages support, however, targeted the creation of ADTs.
Object-oriented programming languages support through their Class concept, the creation of ADTs, since data and operations are bound to the data protection and the permitted operations can be defined. Some modular programming languages like Ada or Modula-2 support also targeted the creation of ADTs. In general, it is possible to define an ADT, by definition of the data and the signatures of the operations, while the semantics is described as the comment text.
Specifications
An abstract data type can be specified by different specifications. A specification consists of a signature and a semantics, the meaning and interaction of operations sets.
Mathematically it is the specification of a term algebra by signature, producers and axioms. Hence the first type of specification that mathematically - axiomatic.
Another possibility is the mathematical- algebraic specification that only in the specification of the semantics differs from the axiomatic. The substantive meaning of the operations is defined here by mathematical means, matrices, vectors, sequences, etc..
There are also special forms, such as the informal method of specification - by specifying an interface of a programming language, such as Java interfaces or the implementation of the data type in a functional programming language like Haskell - what's to an effort at first contradictory, data type, regardless of to make an implementation. The implementation in a functional programming language, however, serves as a specification for ADTs that will eventually be implemented in procedural or object oriented languages. The advantage of this specification is that the same can be tested whether the specification is useful, what is possible with the other options, especially the axiomatic, not readily available.
Example
The following are the ADT stack memory ( stack, works on the last-in, first-out principle) and queue (queue, works on the first-in- first-out principle) defined in the mentioned four specifications.
Signature
Mathematics and axiomatic and algebraic method
STACK ( defined herein ) ELEMENT ( an undefined here ADT, the stack works ) BOOL empty stack: STACK → (creates an empty stack) isStackEmpty: STACK → BOOL ( ask if the stack is empty ) push: STACK → STACK ELEMENT × ( grabs an item on top of the stack) pop: STACK → STACK ( removes the top element and returns the new stack back ) top: STACK → ELEMENT ( returns the top element without removing it ) QUEUE ELEMENT BOOL empty queue: → QUEUE isQueueEmpty: QUEUE → BOOL enqueue: ELEMENT × → QUEUE QUEUE ( adds an element at the bottom ) dequeue: QUEUE QUEUE → ( removed the front element ) head: QUEUE ELEMENT → ( returns the front element without removing it ) Informal method ( Java)
Public interface IStack
Data stack e = e | S e ( Stack s) isStackEmpty :: Stack a → Bool push :: e → e → Stack Stack s pop :: Stack Stack → e e top :: Stack e → e data queue e = e | Q (queue e) e isQueueEmpty :: Queue e → Bool enqueue :: e → e → Queue Queue e dequeue :: Queue Queue e → e head :: Queue e → e semantics
Even on closer inspection of the (identical) signatures no differences between the data types can be seen. Only with the definition of the semantics there are differences.
Mathematics and axiomatic method
X: ELEMENT s: STACK isStackEmpty ( empty stack () ) = TRUE isStackEmpty ( push ( x, s )) = FALSE pop ( empty stack () ) = ERROR pop ( push ( x, s) ) = s top ( empty stack () ) = ERROR top ( push ( x, s) ) = x push ( top ( s ), pop ( s ) ) = s if s is not empty x: ELEMENT q: QUEUE isQueueEmpty ( empty queue () ) = TRUE isQueueEmpty ( enqueue (x, q )) = FALSE head ( empty queue () ) = ERROR head ( enqueue (x, q) ) = IF isQueueEmpty (q ) THEN x ELSE head (q ) dequeue ( queue empty ()) = ERROR dequeue ( enqueue (x, q) ) = IF isQueueEmpty (q ) THEN q ELSE enqueue (x, dequeue (q ) ) Mathematics and algebraic method
ELEMENT SETS = E ( set of elements ) STACK = S = FUNCTIONS empty stack = isStackEmpty (S) = push ( s, x ) = if = If top ( S) = if = If pop ( S) = if = If = If ELEMENT SETS = E ( set of elements ) QUEUE = Q = FUNCTIONS empty queue = isQueueEmpty (Q ) = enqueue (Q, x) = if = If head (S) = if = If dequeue (S) = if = If = If Informal method ( Java)
Semantics: by specifying a precondition and effect / result of the method ( in object-oriented programming usually eliminates the need to specify as a condition the existence of the data structure, since the method is bound to an object that already exists).
Public interface IStack
Empty stack = E isStackEmpty e = True isStackEmpty (S x xs ) = False push xs = e S e xs pop ( S x xs ) = xs top ( S x xs ) = x empty queue = E isQueueEmpty e = True isQueueEmpty (Q xs x) = False enqueue e xs xs = Q e dequeue E = E dequeue (Q (E) x ) = E dequeue ( Q ( ys y) x ) = x enqueue ( dequeue (Q ys y)) head E = error "Queue is empty. " head (Q (E) x ) = x head ( Q ( ys y) x) = head (Q ys y) Desired properties
To strive towards properties of a well- programmed ADT and usually also a well-specified data structure are:
- Universality ( implementation independence ): The once designed and implemented ADT can be included in any program and used there ( eg in the form of a unit ).
- Precise description ( precise specification ): The interface between implementation and application must be clearly and completely.
- Simplicity ( simplicity ): When using the internal implementation of the ADT is not interested in the ADT takes its representation and management in memory itself
- Encapsulation ( encapsulation ): The interface should be construed as a hermetic border. The user should know very well what an ADT does, but not how he does it.
- Snugness ( integrity ): The user can not intervene in the internal structure of the data. The danger of inadvertently delete data or modify and to commit programming error is thus significantly reduced.
- Modularity ( modularity ): The modular principle allows clear and thus secure programming and simple replacement of parts of the program. When troubleshooting, individual modules can be considered a very isolated. Many improvements can be taken over ADTs later without the slightest change in all ambient or application programs.
If object-oriented programming, these properties can be very easily satisfied because the object-oriented paradigm naturally supports the creation of ADTs. Another way to create ADTs ( also in conjunction with object-oriented programming) are generic types.