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.
http://i.stanford.edu/pub/cstr/reports/cs/tr/68/113/CS-TR-68-113.pdf