Report Number: CS-TR-68-113
Institution: Stanford University, Department of Computer Science
Title: The impact of storage management on plex processing language implementation
Author: Hansen, Wildred J.
Date: July 1969
Abstract: A plex processing system is implemented within a set of environments whose relationships are vital to the system's time/space efficiency: Data Environment Stack Structures Data Structures Subroutine Environment Routine Linkage Variable Binding Storage Management Environment Memory Organization for Allocation Storage Control This paper discusses these environments and their relationships in detail. For each environment there is some discussion of alternative implementation techniques, the dependence of the implementation on the hardware, and the dependence of the environment on the language design. In particular, two language features are shown to affect substantially the environment design: variable length plexes and 'release' of active plexes. Storage management is complicated by the requirement for variable length plexes, but they can substantially reduce memory requirements. If inactive plexes are released, a garbage collector can be avoided; but considerable tedious programming may be required to maintain the status of each plex. Many plex processing systems store numbers in strange formats and compile arithmetic operations as subroutine calls, thus handicapping the computer on the only operations it does well. Careful coordination of the system environments can permit direct numeric computation, that is, a single instruction for each arithmetic operation. This paper considers with each environment, the requirements for direct numeric computation. To explore the techniques discussed, a collection of environments called Swym was implemented. This system permits variable length plexes and compact lists. The latter is a list representation requiring less space than chained lists because pointers to the elements are stored in consecutive words. In Swym, a list can be partly compact and partly chained. The garbage collector converts chained lists into compact lists when possible. Swym has careful provision for direct numeric computation, but no compiler has been built. To illustrate Swym, an interpreter was implemented for a small language similar to LISP 1.5. Details of Swym and the langauge are in a series of appendices.