Abstract Data Types (ADT)

A data type consists of a set of values or elements, called its domain, and a set of operators acting on that domain. The domain may be defined either by enumeration, if finite, or by specifying a rule describing its elements.

Once the domain is defined, we need to specify the operations. Two steps are involved here. First, we enumerate operators names, identifying what type of values they both operate on and also return. This step is referred to as prescribing the syntax. Second, we need to describe the operators' functionality, or semantics. There are several ways to give semantics:

• giving textual description of the behavior
• operational specification
• algebriac specification

On the other hand, operational specification gives a description of the ADT at hand in terms of another, primitive type with well-defined mathematical properties. For example, we may describe the ADT set in terms of sequences, which is in this case a well-defined type. In what follows, we concentrate on algebriac specification.

Algebraic Specification

We have, for the moment, a general intuitive idea about what we mean by a STACK and what kinds of operations are needed in applications for this data type. These operations are: push, pop, top, empty, and newstack.

The syntax gives a description of each one of these operations in the same way we normally describe functions: take some elements from a domain and map them to some element of a domain.

For example, syntax for STACK may be given as follows:

  newstack:                 ------->  STACK

  push    : STACK x INTEGER --------> STACK

  pop     : STACK           --------> STACK

  top     : STACK           --------> INTEGER U 
                                      {undefined}

  empty   : STACK           --------> BOOLEAN

NOTES:

1. INTEGER and BOOLEAN are the types of this algebra.
   
2. The intended meaning for these operators are as follows:
   • newstack: takes nothing as its argument and returns an empty STACK.
   • push: takes some STACK S and an INTEGER I, and returns a STACK S1 with top element I and the rest of its elements are from S.
   • pop: takes a STACK S and removes its top element.
   • top: takes a STACK S, returns the top element of S. If S is empty, it returns undefined.
   • empty: takes a STACK S, decides if it is empty.
3. At this stage, implementation is not considered.

For our type STACK, we can see that the operators newstack and push are the constructors for STACK. In other words, any element of a STACK type can be built using only operations consisting of newstack and push. Now we have a precise way to describe the domain of the type STACK.

1. pop(newstack) = newstack
2. pop(push(S,I)) = S
3. top(newstack) = undefined
4. top(push(S,I)) = I
5. empty(newstack) = true
6. empty(push(S,I))= false

1. S is an arbitrary element of type STACK, and I is an INTEGER.
2. At this stage, questions concerning implementation are not an issue. All we need at this stage is a desciption of operators, and how they interact with each other.
3. The domain of STACK can be described in terms of constructors (newstack and push), by means of what may be called the normal lemma of the type STACK, as follows:

   For every STACK S, either:
   a) S = newstack or,
   b) there exists some S1 and I such that S = push(S1,I).

Developing Algebraic Axia

To create our axia, we must:

1. Determine Functionality
2. Write Signatures
3. Choose Constructors
4. Write Axia

Our first step is to determine functionality. Thinking about the data type and its possible use, we determine what operations are needed to create instances of the data type, modify these instances, and obtain values from the data type.

For example, we need to:

• create a new SET. This is done by having an operation called newset.
• add elements to a set. Thus, we need an operation called add.
• delete an element from a set. Thus, we need an operation called delete.
• check to see if some given element is a member of a set. Another operation called member must be used.
• verify if a set is empty. This requires the operation empty.
• count how many elements a set contains. The function size will be used.

Using INTEGERS and BOOLEAN as types, we have:

 newset:               --------> SET

 add   : SET x INTEGER --------> SET

 delete: SET x INTEGER --------> SET

 member: SET x INTEGER --------> BOOLEAN

 empty : SET           --------> BOOLEAN

 size  : SET           --------> INTEGER

Finally, we write the axia. We only need to consider the composition of each non-constructor operator from some combination of constructor operators. Thus, we only consider:

• delete(newset,I)
• delete(add(S,I),J)
• member(newset,I)
• member(add(S,I),J)
• empty(newset)
• empty(add(S,I))
• size(newset)
• size(add(S,I))

1. delete(newset,I) = newset
2. delete(add(S,I),J) = S if I=J else add(delete(S,J),I)
3. member(newset,I) = false
4. member(add(S,I),J) = true if I=J else member(S,J)
5. empty(newset) = true
6. empty(add(S,I)) = false
7. size(newset) = 0
8. size(add(S,I)) = size(S)+1 if I is not in S else size(S)

In the implementation process we will be faced with an issue concerning term equality. That is, what is meant by stating that two things are equal? For example, to state that two sets are equal, it means they have the same elements (regardless of the order in which they appear). This "equality function" must be defined in order for us to check the correctness of our implementation for the axia.

Previous Topic

Next Topic