Associative Programming

a set of procedures for solving informational-logical problems based on the programmed realization of associative connections between data stored in the memory of digital computers. The branch of programming for digital computers is known in foreign literature under the designations “list processing of data,” “modular method of organization of data,” “method of chained addressing,” or “method of control words.” Associative programming is used in the logical processing of information concerning diverse items—whose composition and quantity are altered in the process of solution—when it is impossible beforehand to determine the volumes of data of the diverse forms and to carry out the exact allocation of the memory volume.

For problems which are solved by means of associative programming, it is characteristic to have a large amount of data and frequent use of procedures for the retrieval or classification of items according to their attributes and the inclusion and exclusion of items from distinct groups (lists) of the information being processed.

Lists in associative programming are any groups of data which are associated in terms of certain attributes. In the memory of the digital computer are organized either sequential lists, by means of location of data in cells with sequentially increasing addresses, or chain lists, by means of the association of data by linkage addresses. The linkage address is stored jointly with a member of the list and indicates the location of the subsequent member of the given list. In this case, the members of lists can be located arbitrarily in the memory, and certain of them can indicate branching to so-called sublists. The aggregate of the list with branching sublists is called a list structure.

The basic facilities of associative programming are the use of linkage addresses for the construction of lists of various forms which link items with common attributes, the use of list structures for the representation of hierarchical systems of data organization, the use of the so-called push-down lists for the temporary storage of data in a specific order and the restoration of them in reverse order, and the organization of storage in the form of a linked list of cells providing for flexibility and completeness in the use of the entire storage capacity and excluding the necessity of detailed preliminary allocation.

The idea of linked addressing of lists belongs to the American computer scientists Newell, Simon, and Shaw, who developed in detail techniques for the construction and transformation of chained lists. Ordinarily, in the processing of data concerning a certain set of items, these data are distributed among different lists, whereupon the data concerning the same item can be found simultaneously in several lists. In order to avoid frequent repetition of all the information concerning a given item in different lists, a specific region in the machine’s memory is set aside, in which all the information concerning items is allocated by sequential sections (so-called entries); to each item there corresponds an individual position (one entry) with its address. In the construction of each chained list by a programmer, one cell—called the locator of the list—is set aside beforehand; it contains the address of the first member in the list, the number of members in the list, and other data concerning the list. The virtue of the chain mode of list organization is the ease of including new members and eliminating unnecessary members in any location in the list without the displacement of all the remaining members. Modifications of the chain technique of list construction are the cluster and modular techniques.

In the cluster technique, the members of one list are arranged in succession in consecutive cells of the memory. In this case, only the addresses of the entries of items which are members of the given list—and certain additional attributes—are indicated in the list words. Because the composition of lists is variable, the given variant is realized not in the form of continuous sequences of cells which pertain to one list, but rather in the form of a cluster of the members of one list. Within the cluster, the members are distributed in succession, and the linkage between clusters is realized by linkage addresses.

The modular technique of construction of lists is used for the formation of multilist structures. In modular lists, it is possible to make jumps from each member of the list not only to one following member but also to many other members—that is, every member is a node of intersection of many lists. In this case all the list words which represent the same object in different lists are allocated in succession in the machine’s memory.

In associative programming it is convenient to use certain special algorithmic languages (for example, LISP 1,5; IPL-V) or special subsets of universal algorithmic languages (such as PL-1, ALGEM, and ALGOL-COBOL). Sometimes associative programming is realized in the code of a specific machine by utilizing certain special methods.

The use of associative programming permits considerable speeding up of retrieval and processing of data in large blocks and provides for convenient and compact representation of complex algorithms for the solution of informational-logical problems such as the planning of production and material-technical supplying, retrieval of scientific-technical information, and the retrieval of reference data on various machines, instruments, and such.