The engineering of data structures.

Abstraction in computer programming provides a means of reducing complexity by emphasising the significant information (program behaviour) whilst suppressing the immaterial (program implementation). This aids program construction, improves reliability and maintainability, and eases the application of formal correctness proofs. The importance of data abstraction in the specification, design and implementation of large systems raises the question as to whether such methods may be applied in the context of programming languages designed before the widespread use of abstraction techniques. The program structuring facilities available in FORTRAN 77 support a form of encapsulation for simple data structures. In light of this mechanism provided by the language, state-based specification was found to be most appropriate. A specification technique incorporating object-oriented techniques is particularly suitable and allows a library of object classes to be specified and then implemented in sequential FORTRAN 77. Refinement extends the object classes so as to provide the commonly occurring generators for use in iterative constructs. Therefore, the advantages of data abstraction methods may be obtained in an early procedural language such as FORTRAN 77. Data abstraction provides data independence : a change in the representation for a particular class of objects affects only the code that implements the associated operations. This allows parallel implementations to be considered, without changes to the original specification or to any user-code. The provision of such parallel data structures is required for the migration of sequential systems onto parallel distributed memory architectures. As an illustration of this approach a general 2P2-2P (for integer P≥3) search tree utilising a pipeline of processors in a distributed memory architecture is shown to provide a means of implementing the object classes. Variations in both the number of processors allocated to the pipeline and the value of P allows the optimal search structure for a given architecture to be determined. These structures are highly efficient leading to improvements in both throughput and response time as processors are added to the array. An efficient parallel implementation of object classes is therefore achieved within the tight interface provided by abstraction.