ABSRTACT DATA TYPES

In any programming language, there are several data types that are available for programmers use ( such as integers, floating point numbers, strings, or characters). Many applications needs more complicated structures of data, that can be added on a program to program basis; hence, the notion of data abstraction.

A data type cosists of a set of values or elements ( its domain) along with 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 this is done, 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: need to describe the operators' functionality ( or semantics). There are several ways to give semantics: a) giving texual description of the behaviour; b) operational specification; and c) algebriac specification. **** couple of sentenses will be added on items a) , b) with the indication that algebraic specification will be discussed in details******

ALGEBRAIC SPECIFICATIONS OF ADTS:

In giving the algebraic specification of some ADT, the process is divided into two parts: syntax and semantics. The syntax description is often referred to as the signature of the algebra, and each "auxiliary" data type used to give this signature is called a sort. Concepts will be illustrated via an ADT will call it STACK. We have ( for the moment) a general intuitive idea about what we mean by a STACK and what kind of operations is needed in applications for this data type. These operations (or some of it) are: push, pop, top, empty, and newstack. The syntax gives a description of each one of these operations as the way we normally describe functions that takes some elements from some domain, and maps it to some element of some domain. For example syntax for STACK may be given as follows:

    syntax (for STACK)

    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 sorts of this algebra.
2) The intended meaning for these operators are as follows:
   newstack: takes nothing as argument and it returns an empty STACK.
   push: takes some STACK S and an INTEGER I, and returns a STACK S1
         with I the top element; the rest of the elements are S.
   pop: takes a STACK S, removes its top element.
   top: takes a STACK S, it 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, the question of implementation is not under consideration.

So far, we have only an intuitive idea about the domain of the type STACK. Using the operators defined above, we may give a precise description Among the operators mentioned above, we identify the least number of them necessary to be able to construct all possible STACK(s) that could come up. These set of operators are called constructors for the type. So, for our type STACK, we can intuitively see that the operators sewstack and push are the constructors for STACK. In other words, any element of a STACK type can be build using only operations consisting of newstack and push. Now, we have a precise way to describe the domain of the type STACK.

In semantics, we describe the meaning of the operators in terms of how they interact with one another. That will give rise to a set of equations referred to as the axioms. For example, axioms for STACK may be given as follows:

   AXIOMS

   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

NOTES:
1) S is an arbitrary element of type STACK, and I is an INTEGER.
2) These set of equations seems to capture our intuitive notion of
   what we mean by type STACK. What we have here is an unbounded 
   stacks. If we like our stack(s) to be bounded, another function
   must be added to reflect this notion. This will be a "hidden
   function" normally not exported to the user. This example will
   be given latter.
3) At this stage, questions concerning implementation is not an issue.
   All what we need at this stage is a desciption of operators, and
   how they interact with each other.
4) Domain of STACK can be descriped in terms of constructors ( newstack
   and push), by means of what may called the normal lemma of the
   type STACK, as follows:
    For every S in STACK either:
    a) S=newstack or,
    b) there exists some S1 in STACK and integer I such that
       S=push(S,I).

DEVELOPING ALGEBRAIC AXIOMS:

In this part, we give a systematic way enabling us to develope our set of axioms in such a way making them "sufficiantly complete". Notions will be discussed using an example for the data type SET.

What we have at the moment is a general notion about the type SET ( a collection of some elements, integers-say). We also have an idea about the possible use of this type, hence, we can decide what kind of operations are needed. So , our first step is to:

1) Determine Functionality:

Thinking about the data type and its possible use, we can determine what operations are needed to create instances of the data type, modify these instances, and operations that obtain values from the data type. For example:

* need to creat new SET: this is done by having an operation, that will be called newset.

* need to add elements to a set: thus need an operation, will call it add.

* need to delete an element from a set: thus need an operation, call it delete.

* need to check to see if some given element is a member of a given set: another operation called member must be used.

* need to verify if a set is empty: another operation, empty, is needed.

* need to count how many elements a given set contains: a function (will name it ) size will be used.

Do we need any more operations? That depends on the way we intend to use the type we are building. It may be useful (or needed) to add other operations on SET, like union, intersection ...etc. Wiil keep things simple, we identify our operations as:

newset, add, delete, member, empty, and size.

2) Write Signature:

At this step, we write the signatures. Remember, signatures is writting the operators mentioned above the way we express mathematical functions. Using INTEGERS and BOOLEAN as sorts, 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

3) Choose Constructors:

Among the operators mentioned above, we can (intuitively) see that newset and add are the constructors for this ADT. Any set in SET can be constructed, only, using these two operators.

4) Writing Axioms:

In writing axioms, we only need to consider the composition of each nonconstructor operator with each constructor operator. Thus, we only consider:

      delete(newswt,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

************
     Will add the following:
     1. Sone notes about term equality.
     2. Some more examples: bounded stack; bags; queues
     3. Put it into final form using HTML.

     Any questions or comments, let me know.  Ibrahim Salama
**************