MTS 8: LISP and SLIP in MTS
June 1976
referencing lists obviously require special attention; otherwise they
would never be erased, or infinite processing loops could develop. The
programmer may, therefore, override the control role of the counters and
return to Available Space List, or keep alive, any list.
The third technique is completely automatic, relieving the programmer
of all housekeeping duties. The LISP system lets the program run until
almost all free space is exhausted. Two phases of garbage collection
are then called into action. In the first phase, all those lists are
marked that can be accessed from (i.e., named by) other lists. The
nonaccessible data are returned to Available Space List in the second
phase, and the marks are eliminated so that another cycle of garbage
collection can take place at a later stage.
Obviously, this is a very time-consuming method. It excludes the
possibility of using the language in "real time." With most large-scale
projects, the frequency of garbage collection goes up rapidly as the
program progresses, and the number of liberated cells per action
diminishes at the same time. To stop nonsensical oscillations of this
kind, the programmer can prespecify in some systems the termination of
the run if a garbage collection cycle results in less than a certain
number of cells being returned to Available Space List.
Conventions ___________
The basic element of SLIP is a SLIP-cell. Each such cell is divided
into two parts. The first part, the linkword, is occupied with linking
and bookkeeping information useful in linking each cell with its
relatives as required by SLIP. The second part occupying the second
half of the cell is a datum. This datum contains the user’s informa-
tion. A datum may be any bit configuration such as integer, real,
character strings, etc. A datum may also have the value of a SLIP-name
which is the name of a list. It is in this manner that a list becomes a
sublist of another list.
Every list has one cell, the Header, which is equivalent to the "name
of that list." This Header cell’s space is completely devoted to
information regarding the state of the list. No space in this cell is
available for the user. However the user, through SLIP functions, has
access to this information; one may inquire if the list is empty, i.e.,
there is a Header but no other cells are attached to the Header.
Each SLIP cell has as a name an INTEGER value specifying its location
in the SLIP memory. In this description, CADR refers to this name or
cell address.
Even in the original version of SLIP it was necessary to provide two
names for certain functions to be compatible with FORTRAN and to prevent
undesirable conversions. This problem is further aggravated in this
116 SLIP