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

MTS 8: LISP and SLIP in MTS
June 1976
version and consequently additional functions are provided to shelter
the user from this nonproductive concern.
It is preferred, as a matter of style, to speak of cell names rather
than machine addresses of cells. The particular conversion from cell
name to machine address ought not to be a user’s concern. However, we
are at the mercy of our wish to remain as compatible as possible with
the tradition of SLIP and thus we retain previously defined mnemonics
emphasizing the machine address of a word or cell. We have, however,
added functions to make the user’s lot comfortable.
However, now particular attention must be paid to the mode declara-
tion of functions to insure compatibility with FORTRAN IV and its
implicit mode conversion policies. To assist the user, a complete
tabulation of the policy is provided as is a complete tabulation of the
proper mode declaration for functions; see the subsection "Summary of
360 SLIP Functions and Subroutines."
FUNDAMENTAL SLIP OPERATIONS ___________________________
For a readable introduction to the principles of list processing, and
SLIP in particular, see Findler, et al. (4).
The data structures of the Symmetric List Processor (SLIP) consist of
bidirectional rings. Each element is connected by pointers to both its
left and right neighbors. (Sometimes we will use the synonymous terms
above and below instead of left and right respectively.) Also, the last _____ _____ ____ _____
cell points back to the beginning of a ring.
In the following discussion we will use the more customary terms list ____
and list structure rather than ring and ring structure, since no ____ _________ ____ ____ _________
misunderstanding can arise from this substitution.
SLIP Data Elements __________________
The first word of a SLIP cell, the linkword, contains the list-
linking information and is not directly needed by the user. The second
word of a SLIP-cell contains some datum.
The DATUM field is one word or 32 bits long. It may contain anything
which can be represented by 32 bits.
The cell name of the Header is called the name of the list. If more ____
than one FORTRAN word has the list name, the list is said to have
several aliases. If two aliases are established for a list that does _______
not imply that it has been referenced twice.
SLIP 117