Recursive data structures |
| |
Authors: | C A R Hoare |
| |
Affiliation: | (1) Department of Computer Science, The Queen's University of Belfast, Belfast, Northern Ireland |
| |
Abstract: | The power and convenience of a programming language may be enhanced for certain applications by permitting treelike data structures to be defined by recursion. This paper suggests a pleasing notation by which such structures can be declared and processed; it gives the axioms which specify their properties, and suggests an efficient implementation method. It shows how a recursive data structure may be used to represent another data type, for example, a set. It then discusses two ways in which significant gains in efficiency can be made by selective updating of structures, and gives the relevant proof rules and hints for implementation. The examples show that a certain range of applications in symbol manipulation can be efficiently programmed without introducing the low-level concept of a reference into a high-level programming language.The work on this paper was supported in part by National Science Foundation under grant number GJ 36473X and ARPA Research Contract DAHC 15-73-0435. |
| |
Keywords: | Data structures recursive data structures axiomatic proof rules programming language design programming language features programming language implementation data representation symbol manipulation references (abolition of) pointers (abolition of) dynamic storage allocation |
本文献已被 SpringerLink 等数据库收录! |