Accession Number:

AD0772509

Title:

Recursive Data Structures

Descriptive Note:

Corporate Author:

STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1973-10-01

Pagination or Media Count:

35.0

Abstract:

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.

Subject Categories:

  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE