122 ABSTRACT DATA TYPES $6.1 establish the theoretical basis for the entire method,the consequences of the ideas introduced in this chapter will be felt throughout the rest of this book. There is more.As we will see at chapter end,these consequences actually extend beyond the study of software proper,yielding a few principles of intellectual investigation which one may perhaps apply to other disciplines. 6.1 CRITERIA To obtain proper descriptions of objects,we need a method satisfying three conditions: The descriptions should be precise and unambiguous. They should be complete-or at least as complete as we want them in each case (we may decide to leave some details out). They should not be overspecifying. The last point is what makes the answer non-trivial.It is after all easy to be precise, unambiguous and complete if we "spill the beans"by giving out all the details of the objects'representation.But this is usually too much information for the authors of software elements that need to access the objects. This observation is close to the comments that led to the notion of information "Information Hid- hiding.The concern there was that by providing a module's source code (or,more ing".page 51. generally,implementation-related elements)as the primary source of information for the authors of software elements that rely on that module,we may drown them in a flood of details,prevent them from concentrating on their own job,and hamper prospects of smooth evolution.Here the danger is the same if we let modules use a certain data structure on the basis of information that pertains to the structure's representation rather than to its essential properties. 6.2 IMPLEMENTATION VARIATIONS To understand better why the need for abstract data descriptions is so crucial,let us explore further the potential consequences of using physical representation as the basis for describing objects. A well-known and convenient example is the description of stack objects.A stack object serves to pile up and retrieve other objects in a last-in,first-out ("LIFO")manner, the latest inserted element being the first one to be retrieved.The stack is a ubiquitous structure in computing science and in many software systems;the typical compiler or interpreter,for example,is peppered with stacks of many kinds. Stacks,it must be said,are also ubiquitous in didactic presentations of abstract data types, so much so that Edsger Dijkstra is said to have once quipped that"abstract data types are a remarkable theory,whose purpose is to describe stacks".Fair enough.But the notion of abstract data type applies to so many more advanced cases in the rest of this book that I do not feel ashamed of starting with this staple example.It is the simplest I know which includes about every important idea about abstract data types.122 ABSTRACT DATA TYPES §6.1 establish the theoretical basis for the entire method, the consequences of the ideas introduced in this chapter will be felt throughout the rest of this book. There is more. As we will see at chapter end, these consequences actually extend beyond the study of software proper, yielding a few principles of intellectual investigation which one may perhaps apply to other disciplines. 6.1 CRITERIA To obtain proper descriptions of objects, we need a method satisfying three conditions: • The descriptions should be precise and unambiguous. • They should be complete — or at least as complete as we want them in each case (we may decide to leave some details out). • They should not be overspecifying. The last point is what makes the answer non-trivial. It is after all easy to be precise, unambiguous and complete if we “spill the beans” by giving out all the details of the objects’ representation. But this is usually too much information for the authors of software elements that need to access the objects. This observation is close to the comments that led to the notion of information hiding. The concern there was that by providing a module’s source code (or, more generally, implementation-related elements) as the primary source of information for the authors of software elements that rely on that module, we may drown them in a flood of details, prevent them from concentrating on their own job, and hamper prospects of smooth evolution. Here the danger is the same if we let modules use a certain data structure on the basis of information that pertains to the structure’s representation rather than to its essential properties. 6.2 IMPLEMENTATION VARIATIONS To understand better why the need for abstract data descriptions is so crucial, let us explore further the potential consequences of using physical representation as the basis for describing objects. A well-known and convenient example is the description of stack objects. A stack object serves to pile up and retrieve other objects in a last-in, first-out (“LIFO”) manner, the latest inserted element being the first one to be retrieved. The stack is a ubiquitous structure in computing science and in many software systems; the typical compiler or interpreter, for example, is peppered with stacks of many kinds. Stacks, it must be said, are also ubiquitous in didactic presentations of abstract data types, so much so that Edsger Dijkstra is said to have once quipped that “abstract data types are a remarkable theory, whose purpose is to describe stacks”. Fair enough. But the notion of abstract data type applies to so many more advanced cases in the rest of this book that I do not feel ashamed of starting with this staple example. It is the simplest I know which includes about every important idea about abstract data types. “Information Hid￾ing”, page 51