MTS 8: LISP and SLIP in MTS
June 1976
Data types more complex than simple lists are also needed. A list
structure consists of a main list and a hierarchy of sublists. The
elements on the main list, and also on its sublists, are either data or
names of sublists. In the cases of self-referencing by a list or
cross-referencing between two lists, special care must be taken, of
course, to avoid an infinite loop in processing.
Rings and ring structures are analogous to lists and list structures,
respectively. However, in rings and ring structures a link connects the
last and first cells. This is why the term circular list is also used.
The first cell of every ring must be marked; otherwise, the processing
of elements would again go on indefinitely. The information structures
in SLIP are of this type. Distinction can be made as to whether one- or
two-directional pointers connect neighboring elements. The latter
arrangement, also used by SLIP, offers certain processing advantages at
the price of an extra link field in every node.
Data representations present problems of external (user’s) and
internal (inside the computer) representation. The solution to the
problems of external representation is, of course, idiosyncratic to the
language and will not be discussed here. Higher-level and more recent
languages tend to be more convenient for the user.
Depending on the amount of information stored in each cell and on the
word length of the machine on which the list processing language is
implemented one, two, or sometimes a higher varying number of computer
words are used for a cell. The lists need not contain the actual
information but may contain only links that point to a centralized data
table. The referencing to data can be direct or manifold indirect
(pointer to pointer to ... pointer to data). If a list contains data
of different modes, special markers are needed to indicate the type of
information in each cell.
Description Lists contribute to the power of SLIP. These lists
consist of a sequence of attribute-value pairs and can provide further
information about lists. Suppose, for example, a list structure
describes the current position on a chessboard. It has 64 sublists, one
for each square. Each sublist has a Description List with attributes:
occupancy status (the possible values are the 32 men and "empty"), your
own men defending the square (the value is a list of men, possibly
empty), opponent’s men attacking the square (the value is as before),
etc. As we can see, in general the value can be symbolic or numeric, a
single unit of data or a list of data. Also, a Description List itself
can have a Description List and so on.
If a list or list structure is copied or erased (i.e., returned to
Available Space List), its Description Lists undergo the same treatment.
An elegant and often very important list-processing technique
involves the use of recursive computations. A recursive subroutine is
one that calls itself. The input parameters of the subroutine called
later normally depend on the intermediate results of the same subroutine
114 SLIP

MTS 8: LISP and SLIP in MTS
June 1976
called earlier. Since these parameters all can contribute to the
overall final result, they have to be preserved on push-down stacks.
An example should clarify the idea. Instead of referring to the
hackneyed recursive computation of the factorial function N!, let us
consider the following.
Suppose there is a subroutine R, which simplifies symbolic formulae.
It carries out the addition/subtraction of identical terms; performs the
multiplication/division of numeric coefficients; reduces A⁰ to 1, A+0 to
A, A*0 to 0, A*1 to A; gives warning messages in cases of 0/0 and
infinity/infinity, etc. We call R for a complex, heavily parenthesized
expression. (For the sake of explanation, let us forget that the
computer representation of formulae is usually in a parenthesis-free,
so-called Polish notation. The technique, however, is basically the
same in any form of representation.) So, R first simplifies the
expression as if one single symbol were inside the outermost pair of
parentheses. R then turns to treat the expression therein by calling
itself again. As it goes further and further inside, peeling off pairs
of parentheses, it calls itself again and again. Finally, the parenthe-
ses disappear and further simplifications may have to be done. R has to
substitute the last result into the next to last, this result into the
one before that, and so on until it arrives back at the highest level of
expression. The intermediate results or, rather, pointers to the
intermediate results, are popped off a stack whenever they are needed.
Although most, if not all, recursive computations can be transformed
into iterative ones, recursion is always elegant and often more
efficient.
The last topic to be discussed in this section is the problem of
memory management. We saw earlier that the dynamic memory allocation
scheme enables the system to use only the currently necessary amount of
storage area. It is obvious, however, that during the execution of the
program many cells, lists, and list structures may no longer be needed.
We would soon run out of even the largest memories available today if
somehow the storage areas occupied by unnecessary information were not
returned to Available Space List. This process is called garbage
collection and is of extreme importance.
We can distinguish between three methods of memory management as far
as garbage collection is concerned. First, it can be completely under
the programmer’s control, for example, IPL. See Newell, et al. (1) and
Sammet (2).
The SLIP System uses a second type of garbage collection. In SLIP
one list may have several superlists. There is, therefore, a so-called
reference counter at the head of every list that indicates the number of
times that list is referred to by other "live" data structures. Every
time a list is erased the reference counters of its sublists are
decreased by one. If a reference counter reaches zero, that sublist is
also returned to Available Space List. Self-referencing and cross-
SLIP 115