Recursive Data Structures

The power and convenience of a programming language may be enhanced for certain applications by permitting data structures to be defined by recursion. The 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. It is shown by examples that a certain range of applications can be efficiently programmed, without introducing the low-level concept of a reference into a high-level programming language.