While it is true that the specification supplies precise syntactic information about each operation of the abstract data type in that the type of each input parameter and the type of the result returned are clearly stated, the use of comments to describe the behaviour of the operations (that is ``what the operations do!''), poses problems. At best, use of natural language is an informal tool and at worst can often lead to an ambiguous and hazy description of the semantics of an abstract data type.
Another feature of the specification of Fig. 8.1 is that it provides a template that many implementations can fit. For example, in one implementation, the operation top might return the first natural number that was pushed onto the stack (and not the most recent value). Although this is at variance with the accepted behaviour of a stack, nevertheless the syntax of such an abstract data type is still specified by Fig. 8.1. A second implementation that fits the syntactic specification of Fig. 8.1 is the queue where now, push and pop are interpreted as operations which insert and remove a natural number from different ends of a queue. (This example featured in Exercise 8.3 above). Yet a third implementation which fits the specification is one whereby the operation push(s,n) now replaces the top-most element of the stack with the data value n.
On one level, the DEFINITION MODULE of Fig. 8.1 consists of nothing more than a collection of identifiers (names) for the data types and operations (Stack, BOOLEAN, CARDINAL and init, push, pop, top, isempty respectively). Any consistent renaming of these identifiers would still specify a stack and while using obscure names for the types and operations of Fig. 8.1 might appear to result in a less meaningful specification, the comparative clarity of the specification of Fig. 8.1 stems entirely from our familiarity with names such as push and pop. The use of such descriptive names does not endow the specification with a formal semantics.
Identifiers that appear in a DEFINITION MODULE (or package specification) therefore play a purely symbolic role (apart from BOOLEAN and CARDINAL which have an externally defined meaning) in the sense that they show us, for example, whether the values returned by the different operations are the same or not.
The following features emerge from this discussion :
This last point reinforces the need to provide a semantic specification which formally describes the behaviour of the operations of an abstract data type.
It is observations such as these which lead naturally to the use of algebras for specifying an abstract data type. Algebraic specifications are similar in structure to abstract data types. They consist of a set (or sets) of values called sorts (which are symbolic set names) together with a collection of operations, each of which is a mathematical function defined over the sorts. This is one reason for the choice of function procedures in Fig. 8.1 for our Modula-2 specification of a stack. A further reason for confining the operations of an algebraic specification to functions is that procedures, which are often used to implement the operations of an abstract data type, have no obvious mathematical counterpart.
Another desirable feature of an algebraic specification is that it too has a number of possible interpretations or models which are mathematical ``implementations'' of the specification. These ideas will be developed more fully later when we examine the role of algebras in the specification of abstract data types.