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

this paper. Most of the computing world is still concerned with essentially numerical processes, either because the problems themselves are numerical or because nonnumerical problems have been appropriately arithmetized. The kinds of problems that the authors have been concerned with are essentially nonnumerical, and they have tried to cope with them without resort to arithmetic models. Hence the IPL's have not been designed with a view to carrying out arithmetic with great efficiency.

The basic aim, then, is to construct a powerful programming language for the class of problems concerned. Given the amount and kind of output desired from the computer, a reduction in the size and complexity of the specification (the program) that has to be written in order to secure this output is desired.

The goal is to reduce programming effort. This is not the same as reducing the computing effort required to produce the desired output from the specification. Programming feasibility must take precedence over computing economics; since it is not yet known how to write a program that will enable a computer to teach itself to play chess, it is premature to ask whether it would take such a computer one hour or one hundred hours to make a move. This is not meant as an apology, but as support for the contention that, in seeking to write programs for very large and complicated tasks, the overriding initial concerns must be to attain enough flexibility, abbreviation, and automation of the underlying computing processes to make programming feasible. And these concerns have to do with the power of the programming language rather than the efficiency of the system that executes the program.

In the next section a straightforward description of an IPL computer is begun. To put the details in a proper setting, the remainder of this section will be devoted to the basic devices that IPL-VI uses to achieve a measure of power and flexibility. These devices include: organization of memory into list structure, provision for breakouts, identity of data with program, two-stage interpretation, invariance of program during execution, provision for responsibility assignments, and centralized signalling of test results.

The most fundamental and characteristic feature of the IPL's is that they organize memory into list structures whose arrangement is independent of the actual physical geometry of the memory cells and which undergo continual change as computation proceeds. In all computing systems the topology of memory, the characteristics of hardware and program that determine what memory cells can be regarded as "next to" a given cell, plays a fundamental role in the organization of the information processing. This is obviously true for serial memories like tape; it is equally true from random access memories. In random access memories the topological structure is derived from the possibility of performing arithmetic operations on the memory addresses that make use of the numerical relations among these addresses. Thus, the cell with address 1435 is next to cell 1436 in the specific sense that the second can be reached from the first by adding one to the number in a counter.

In standard computers use is made of the static topology based on memory addresses to facilitate programming and computation. Index registers and relative addressing schemes, for example, make use of program arithmetic and depend for their efficacy upon an orderly matching of the arrangement of information in memory with the topology of the addressing system.

When memory is organized in a list structure, the relation between information storage and topology is reversed. The topology of memory is continually modified to adapt to the changing needs of organization of memory content. No arithmetic operations on memory addresses are permitted; the topology is built on a single, asymmetric, modifiable, ordinal relation between pairs of memory cells which is called adjacency. The system contains processes that make use of the adjacency relations in searching memory, and processes that change these relations at will inexpensively in the course of processing.

A list structure can be established in computer memory by associating with each word in memory an address that determines what word is adjacent to it, as far as all the operations of the computer are concerned. Memory space of an additional address associated with each word is given up, so that the adjacency relation can be changed as quickly as a word in memory can be changed. Having paid this price, however, many of the other basic features of IPL's are obtained almost without cost: unlimited hierarchies of subroutines; recursive definition of processes; variable numbers of operands for processes; and unlimited complexity of data structure, capable of being created and modified to any extent at execution time.

Languages require grammar-fixed structural features so that they can be interpreted. Grammar imposes constraints on what can be said, or said simply, in a language. However, the constraints created by fixed grammatical format can be alleviated at the cost of introducing an additional stage of processing by devices that allow one