Browse Prior Art Database

ON THE PROBLEM OF UNIFORM REFERENCES TO DATA STRUCTURES

IP.com Disclosure Number: IPCOM000128881D
Original Publication Date: 1975-Dec-31
Included in the Prior Art Database: 2005-Sep-20
Document File: 22 page(s) / 64K

Publishing Venue

Software Patent Institute

Related People

CHARLES M. GESCHKE: AUTHOR [+4]

Abstract

If a programmer needs to represent a table which associates a sum of money with a name for all the checking accounts in some bank branch office, he must first decide what operations are germane to an account table. Adding an amount to someone's account (e.g., increase John Smith's account by $5.03), subtracting an amount from an account (possibly with a check against overdrawing), closing an account (deleting the entry in the table for John Smith), and opening a new account (e.g., making a new entry in the table for Jane Doe with an initial balance of $0.00) are one possible set. Once such a set of logical operations on the account table are known, the programmer can make decisions on how to represent one in the computer. Any specific way of implementing an account table will have to provide storage and storage management for the table itself as well as concrete operations corresponding to the logical operations on an account table. To distinguish between the notion of an account table and the specific way in which it is implemented in the computer, we will refer to the former as an abstract data structure (or simply an abstraction) and to the latter as a representation of it. For instance, representing an account table as two arrays, one containing strings (the names associated with the accounts) and the other containing numbers (the funds in the accounts) would mean that the concrete counterpart of making a withdrawal involves looking up an account name in the first array and then subtracting the amount from the corresponding entry in the, numbers array. One would also have to specify what is to be done if the name cannot be found in the array of names or if there are not sufficient funds in the account to cover the withdrawal, but these considerations are issues about any representation of the abstract structure and not just about this implementation. Other considerations, however, may well be properties of a particular representation and not intrinsic to the abstract structure. A good illustration of a constraint imposed by the concrete form of an abstraction is provided by the above representation for an account table. Since we need to be able to open new accounts, and since arrays typically have a fixed number of entries, we may be unable to open a new account if the names array is full. We will have more to say about this situation later; for the moment, it points out that we might want to change the representation for an account table because we found drawbacks in the one chosen. Such modifications and the situations which prompt them are a common occurrence in all large software systems. In fact, a large softwaresystem may be viewed as a set of abstract data structures along with control programs which use them to some common end. The data represents the knowledge which is available for action, and the control programs are strategies which are driven by it. Compilers for programming languages, airline reservation systems, control systems for petroleum refining and operating systems all have this flavor, if one is willing to accept people at computer terminals and chemical reactions as data structures with certain logical operations which can be invoked from the software system.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 6% of the total text.

Page 1 of 22

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

ON THE PROBLEM OF UNIFORM REFERENCES TO DATA STRUCTURES

BY CHARLES M. GESCHKE AND JAMES G. MITCHELL

CSL 75-1 JANUARY 1975

The cost of a change to a large software system is often primarily a function of the size of the system rather than the complexity of the change. One reason for this is that programs which access some given data structure must operate on it using notations which are determined by its exact representation. Thus, changing how it is implemented may necessitate changes to the programs which access it. This paper develops a programming language notation and semantic interpretations which allow a program to operate on a data object in a manner which is dependent only on its logical or abstract properties and independent of its underlying concrete representation.

Index Terms - abstract data types, uniform references, Simula 67, data description, extensible languages, compilation, systems programming language, structured values, generic functions, sparse arrays.

XEROX PALO ALTO RESEARCH CENTER

3180 PORTER DRIVE/PALO ALTO/CALIFORNIA 94304

Introduction:

If a programmer needs to represent a table which associates a sum of money with a name for all the checking accounts in some bank branch office, he must first decide what operations are germane to an account table. Adding an amount to someone's account (e.g., increase John Smith's account by $5.03), subtracting an amount from an account (possibly with a check against overdrawing), closing an account (deleting the entry in the table for John Smith), and opening a new account (e.g., making a new entry in the table for Jane Doe with an initial balance of $0.00) are one possible set. Once such a set of logical operations on the account table are known, the programmer can make decisions on how to represent one in the computer.

Any specific way of implementing an account table will have to provide storage and storage management for the table itself as well as concrete operations corresponding to the logical operations on an account table. To distinguish between the notion of an account table and the specific way in which it is implemented in the computer, we will refer to the former as an abstract data structure (or simply an abstraction) and to the latter as a representation of it. For instance, representing an account table as two arrays, one containing strings (the names associated with the accounts) and the other containing numbers (the funds in the accounts) would mean that the concrete counterpart of making a withdrawal involves looking up an account name in the first array and then subtracting the amount from the corresponding entry in the, numbers array. One would also have to specify what is to be done if the name cannot be found in the array of names or if there are not sufficient funds in the account to cover the withdrawal, but these considerations are issues about any representation of the abstract st...