152 Part 4 The instruction-set processor level: special-function processors

information, the actual transfer can be postponed to the most convenient point in the processing. The flexibility obtained by this device proves especially useful in dealing with the transmission of conditional information from subroutines to the routines that call upon them.

The machine that is described can profitably be viewed as a "control computer." It consists of a single control unit with access to a large random-access memory. This memory should contain 10⁵ words or more. If less than 10⁴ words are available in the primary memory, there will probably be too frequent occasions for transfer of information between primary and secondary storage to make the system profitable.

The operation of the computer is entirely nonarithmetic, there being no arithmetic unit. Since arithmetic processes are not used as the basis of control, as they are in standard computers, such a unit is inessential, although it would be highly desirable for the computer to have access to one if it is to be given arithmetic tasks. The computer is perfectly capable of proving theorems in logic or playing chess without an arithmetic adjunct.

The memory consists of cells containing words of fixed length. Each word is divided into two parts, a symbol and a link. The entire memory is organized into a list structure in the following way. The link is an address; if the link of a word a is the address of word b, then b is adjacent to a. That is, the link of a word in a simple list is the address of the next word in the list.

The symbol part of a word may also contain an address, and this may be the address of the first word of another list. As indicated earlier, the entire topology of the memory is determined by the links and by addresses located in the symbol parts of words. The links permit the creation of simple lists of symbols; the links and symbol parts together, the creation of branching list structures.

The topology of memory is modified by changing addresses in links and symbol parts, thereby changing adjacency relations among words. The modification of link addresses is handled directly by various list processes without the attention of the programmer. Hence, the memory can be viewed as consisting of symbol occurrences connected together by mechanisms or structure whose character need not be specified.

The basic unit of organization is the list, a set of words linked together in a particular order by means of their link parts, in the way previously explained. The address of the first word in the sequence is the name of the list. A special terminating symbol T, whose link is irrelevant, is in the last word on every list. A simple list is illustrated in Fig. 1; its name is L₁₀₀, and it contains two symbols, S₁ and S₂.

The symbols in a list may themselves designate the names of other lists. (The symbols themselves have a special format, so that they are not names of lists but designate the names in a manner that will be described.) Thus, a list may be a list of lists, and each of its sublists may be a list of lists.

An example of a list structure is shown in Fig. 2. The name of the list structure is the name of the main list, L₂₀₀. L₂₀₀ contains two sublists, L₃₀₀ and L₅₀₀, plus an item of information, I₄, that is not a name of a list. L₃₀₀ in its turn consists of item I₁ plus another sublist, L₄₀₀, while L₅₀₀ contains just information, and is not broken out further into sublists. Each of these lists terminates in a word that holds the symbol T.

A list uses a certain number of cells from memory. Which cells it uses is unimportant as long as the right linkages are set up. In executing programs that continually create new lists and destroy old ones, two requirements arise. When creating a list, cells in memory must be found that are not otherwise occupied and so are available for the new list. Conversely, when a list is destroyed (when it is no longer needed in the system) its cells become available for other uses, but something must be done to gain access to these available cells when they are needed.

The device used to accomplish these two logistic functions is the available space list. All cells that are available are linked together into the single long list. Whenever cells are needed, they are taken from the front of this available space list: whenever cells are made available, they are inserted on the front of the available space list just behind the fixed register that holds the link to the first available space. The operations of taking cells from the available space list and returning cells to the available space list involve, in each case, only changes of addresses in a pair of links.