MTS 8: LISP and SLIP in MTS
June 1976
(1) Access the kth element (1kn).
(2) Insert a new element before or after the kth.
(3) Delete the kth element.
(4) Concatenate (i.e., chain together) two or more simple lists.
(5) Split a list into two or more lists.
(6) Make a copy of a list in terms of its contents and structure.
(7) Count the number of elements on a list.
(8) Sort the elements according to some criterion; for example, in
ascending order of the integers in a given field of the
elements.
(9) Search for an element that has a particular value.
Special reference is usually made either to the first (top) or the
last (bottom) element (i.e., when k=1 or k=n). There is even a
particular terminology dealing with list processing: inserting a new
element to the top is called pushing down the list, and deleting an
element from the top is called popping up the list. Although these
terms are completely acceptable in automata theory, they may be
misleading in programming, as we will see later, since the elements
below the top element do not in fact change location.
To achieve ease and flexibility in the above-mentioned nine basic
operations, the usual sequential structure of the memory, as in FORTRAN,
must be given up. In other words, elements that are consecutive
logically on the list may not be consecutive geometrically in the
computer hardware memory. Nothing is novel about this. For example,
when we store the elements of a two-dimensional array column-wise, the
row-wise neighboring elements are no longer adjacent in the essentially
one-dimensional memory. However, if we know the location of the first
element, the dimensions of the array, and the so-called mapping function
(i.e., the algorithm of storing the array), we can easily determine the
geometrical location of any element. Some similar arrangement is needed
in the case of lists, and the solution is provided by links or, using
another term, by pointers. A part of the space representing the list
element is occupied by the name of the next element. This name field
links with, or points to, the neighboring element, which in fact may be
in any part of memory.
Let us now consider one more concept, that of the Available Space
List for free storage, before seeing how the nine basic operations are
carried out. The Available Space List is essentially a reservoir of
free space from which we draw when a new cell is needed and to which we
return cells no longer needed, in order not to run out of free space too
soon. Similarly, the SLIP system can automatically draw cells from or
return cells to this reservoir. This dynamic memory allocation enables
us to omit specifying in advance how long a list is going to be. In
fact, we can create, change the size of, and erase lists during
execution time.
The importance of the Available Space List cannot be overemphasized,
particularly in nonnumeric computations.
112 SLIP

MTS 8: LISP and SLIP in MTS
June 1976
Generally, dynamic memory management becomes indispensable whenever
data are interrelated in a complex manner, and especially when process-
ing causes data to be dynamically reorganized in an unpredictable way as
part of the solution to the problem.
Many of the problems that require these facilities are partly or
wholly symbol-manipulating in nature, such as projects in artificial
intelligence, analysis and synthesis of natural languages, computer
graphics, simulation of cognitive processes, information retrieval, etc.
However, the study of many numerically oriented problem areas is also
greatly helped by list-processing techniques. The representation and
manipulation of sparse matrices is an obvious example of this case.
The initial objection to using list-processing languages was based on
the apparent waste of memory space occupied by pointers. As we can see,
in the problem of sparse matrices, just the opposite is often true.
There are, of course, other arguments in favor of list-processing
languages.
Let us now turn back to the basic list processes. Operations 2 to 5
amount to managing the relative linkings of certain cells. The name of
the top cell is always contained in a special word, the symbolic name of
which is FAVSLC. We can say the word points to the top of Available
Space List.
We can now discuss the rest of the basic operations.
(1) Accessing the kth element consists of going along the links and
increasing a counter of the elements passed by until k is
reached.
(2) Described above.
(3) Described above.
(4) Concatenating two lists amounts to simply overwriting the
end-of-list symbol of the first list with the name of the top
cell of the second list.
(5) Splitting a list into two is the opposite of the above process.
The symbolic name of the new list is identified by SLIP with the
name of its top cell and is output in a standard manner.
(6) Copying a list is straightforward. The name of the new list is
usually output according to some convention. The name is output
also when a new empty list is created. A single cell with an
empty symbol field and no link is considered an empty list.
(7) Counting the elements of a list consists of going down the list
via the linking pointers, always adding one to a counter until
the end-of-list symbol is encountered.
(8) Sorting consists of systematically comparing "keys" and manipu-
lating the link fields whenever necessary.
(9) Searching for a special element on a list is accomplished again
by a sequence of comparisons. The result can be either a simple
yes/no answer concerning the success of the search, or the name
of the matching element when found. In case of failure, a
special symbol, such as zero, is output.
SLIP 113