'Integrated Data Store' of General Electric." (Climenson, 1966, p. 125).

5.28 "This work has led to the definition of FILER (File Information Language Executive Routine), the formalization of a calculus of operations with specific relevance to problems of file organization." (Hughes Dynamics, 1964, p. 1.3).

5.29 "Apart from languages at the implementation or procedural level, a number of user-oriented systems employ list-structured data as a basic mechanism. Bernstein & Slojkowski describe a system called Program Management System (PMS), which stores data in a two-level file structure. Associated with each file is a file name, a list of pointers to its subfiles, and a list of pointers to other files." (Minker and Sable, 1967, p. 126).

5.30 "The long-range objectives are:

"1. To define some of the characteristics of large files, and to develop the structure for a large file of heterogeneous scientific and technical information including chemical structure representations, with particular attention to the necessity for:

a. Manipulating information which is in some cases formatted and in others completely amorphous.

b. Making provision for inclusion of certain kinds of information when it exists, and for later filling of gaps when the information is not available at the time of file initiation.

c. Creating a multi-level file of information so that provision may be made for the inclusion of general information, as well as the addition of various levels of specificity as required by the user, either simply because the additional levels of specificity exist and might be useful at a later date or because there is a user requirement for that degree of specificity. d. Examining the inter-structuring of files that are part of the larger files but which may be geographically separated. "2. To provide list-processing capability in the file structure in order to:

a. Maintain flexibility in the file.
b. Provide for an efficient
updating.

c. Permit

means of

additions to files, both in classes existing already in the system and in the entry of new classes of information.

d. Free the system from the constraints of fixed-length and formatted files.

e. Permit aggregations of data from files that are geographically separated.

"3. To investigate the techniques of file manipulation in order to provide systems of subfiles, special files, desirable redundancy in exchange for multiple access to information, and the necessary keying or cross

referencing facility required for such a system of multi-level, multi-subject files. This work must take into account also the planning and development of several kinds of computer programs which are required for file maintenance

"4. To

determine the kind of organization of information which will most readily permit questioning of the file by different groups of questioners who have varied (and varying) requirements for the kinds of information contained in the file, and who have, furthermore, requirements for for different degrees of specificity in the information they are seeking." (Anderson et al., 1966, pp. 2-4).

5.31 "Fossum & Kaskey examine different kinds of file organization and investigate the potential of a list ordered file' for economizing on the work-load on a computer when carrying out a search. The data base used is the terms assigned to a number of DDC documents, using the DDC thesaurus. The relevance of this study for this chapter is the analysis of word associations, and the objective of the analysis is, in effect, to permit a certain amount of precoordination of terms, in order to reduce the amount of processing necessary in the retrieval operation. The means to achieving this objective is the determination of the mutual exclusiveness of terms. Unlike the rigorous intellectual marshalling of terms in facet analysis, the procedure here is to determine mutual exclusiveness on the basis of whether or not terms appear together in the indexing of individual documents. The attempt to develop an economic list-organized file, the specific purpose of the work reported here, is abortive, but the technique of handling terms in this way remains an intriguing possibility as a machine aid to the generation of schedules for faceted classification schemes." (Sharp, 1967, p. 102).

5.32 "The fundamental importance of data structures may be illustrated by considering the problem of designing a single language that would be the preferred language either for a purely arithmetic job or for a job in symbol manipulation. Attempts to produce such a language have been disappointing. The difficulty is that the data structures required for efficient implementation in the two cases are entirely different. Perhaps we should recognize this difficulty as a fundamental one, and abandon the quest for an omnibus language which will be all things to all men." (Wilkes, 1968, p. 5).

5.33 "Historically primary preoccupation with three classes of data structures (real-complex scalars and arrays, alphanumeric strings and files, and symbolic lists) have led to three major language developments; exemplified-but not exhaustively defined-by ALGOL, COBOL, and LISP, respectively. A major concern of procedural language designers is the reconcilization of these diverse

data types and their transformations with one language." (Perlis, 1965, p. 189).

"Studies in artificial intelligence call for powerful list-processing techniques, and involve such operations as the placing of items on lists, the searching of lists for items according to specified keys, and so on. Languages in which such operations can be easily specified are indicated. The pioneer language in this regard was IPL developed by Newell, Simon and Shaw." (Wilkes, 1964, p. F 1-3).

5.34 "Early list processing languages were invented in order to carry out specific projects of a non-numerical nature. The sequence of languages called IPL . . . Started out in order to provide satisfactory methods of organizing information for work in theorem proving and problem solving, a field in which the amount of storage needed is very variable and unpredictable, and in which the structure of the lists carries important information. LISP . . was developed partly for the use of a project called the 'Advice Taker' which was intended to operate in a complex way on English statements about situations. A language called FLPL.. which was embedded in FORTRAN was produced to write programs for proving theorems in geometry. COMIT . . was devised for language research." (Foster, 1967, p. 3).

5.35 "Furthermore, since a list is itself an ordered set of items which may themselves be lists, there is no limit to the complexity of the structures that can be built up except the total memory space available. Also, there is no restriction to the number of lists on which an item can appear." (Hormann, 1960, p. 14).

"List structures have, as their fundamental property, the substitution rule that allows any symbol in a list to be substituted by a list structure. The natural control procedure for such rules is recu[r]sion: the use of rules whose definition contains calls on itself." (Perlis, 1965, p. 189).

5.36 "List structures allow dynamic storage allocation for units of data larger than can be stored in a single computer word. Normally blocks of consecutive storage cells are allocated for data sets prior to program execution based on estimates of the maximum size of these sets. If the sizes of data sets are variable or unknown, wasteful amounts of storage must be assigned to guard against program failure caused by overflow at some block of assigned storage. Faced with this problem, Newell, Shaw, and Simon organized information in memory into an associative list structure format." (Fuller, 1963, p. 5). "Since the order relation among items is determined only by links, this relation can be changed simply by changing the links without moving the items physically, thus allowing simple and quick changes of organization of memory content. Processes such as insertion and deletion of items in a list become very simple." (Hormann, 1960, p. 13). 5.37 For example, "list processing is relatively new; none of the forms for the components of list

languages has as yet been established as 'standard' even in an informal sense." (Raphael, 1966, p. 67).

"The concept of list processing, or chaining, has been used as a technique for the manipulation of logical data strings for many years and has been formalized as a language for handling data in computer storage. List processing has also been utilized with limited success for the control of data in directaccess storage devices. In general, when list structures are used for external data control, only a subset of the possible data structures is implemented, and the logical and physical relationships are approached as a single entity. Thus, the many ventures into this area are highly individualized, resulting in duplication and incompatibility." (Henry, 1969, p. 2).

5.38 "List processing is a convenient mode of description for many of the more interesting and provocative areas of computer application, but the available languages- such as IPL-V, COMIT, LISP, SIMSCRIPT-require a level of programmer sophistication that makes them almost prohibitive for normal classroom use." (Conway et al., 1965, p. 215).

5.39 "While the list processing languages make it possible to handle reasonably complicated data structures, the programmer is nevertheless faced with a number of difficult problems as soon as he attempts to use such languages in practice . . . it becomes necessary to fit the given data structures into what often turns out to be an unnatural format . . . At the very least, this type of data organization wastes a great deal of storage space . . . Furthermore, the inefficient space allocation also results in extremely slow execution times for the object programs." (Salton, 1966, p. 205).

"The user of list-processing languages is frequently plagued by the lack of memory space. Sophisticated means of 'garbage collection' have become important to circumvent memory space limitations; however, they constitute mostly a palliative that seldom satisfies the user's appetite for extra space." (Cohen, 1967, p. 82).

"In their relation to machines the list processing languages are burdensome, first because the data structures involved may be represented only through explicit links, and second because the free growth and cancellation of structures requires a troublesome administration of the storage." (Naur, 1965, p. 197).

"Powerful software schemes (e.g., the list processing languages) have been developed to deal with the problem of treating scattered data as a contiguous string, but they pay a very heavy price in memory overhead (in some schemes over three-fourths of the available memory is required to handle the addressing mechanisms) and in the processing time required to perform the address arithmetic.

"An alternative solution is proposed here which involves the addition of a small Associative Memory

(AM) to the addressing machinery of the computer (or peripheral direct access storage device). As will be shown, this hardware modification will permit scattered data to appear contiguous, with only a token overhead cost in memory and processing time." (Fischler and Reiter, 1969, p. 381).

5.40 "The process of item deletion involves the elimination of an existing item in the file. This task is complicated by the fact that after deletion, linkage information must be modified if the system is to operate properly. This can be accomplished in two ways. In the first case the item can be physically deleted and each list associated with the item can be searched and the associated link deleted. Alternatively, the specified item can be flagged in the control section. Then during retrieval flagged items are ignored." (Prywes, 1965, p. 20).

"There are several penalties paid for obtaining the flexibility of a memory organized into a list structure. One of these is the requirement for additional memory bits to store appropriate linking addresses. A far more serious penalty is the time required to retrieve symbols from lists and for operations required to add symbols to lists, reorder lists, delete symbols from lists, erase lists, transfer lists to and from bulk storage, and manipulate push-down registers. These tasks are taken out of the hands of the programmer by various listprocessing languages, but they still must be performed by the machine." (Fuller, 1963, p. 12). 5.41 "Most list-processing languages languages have suffered from their inability to deal directly with complex data structure and/or from their inability to perform the complete range of programming language operations upon the data list structures. (Lawson, 1967, p. 358).

5.42"... In many cases, especially among the list-oriented languages, they simply have not geared themselves to the large amounts of data and data processing required in this special field." (Simmons, 1966, p. 214).

"The reason list processing has yet to acquire universal popularity in non-numeric data processing is that, while these mechanics are easy in the list processing language, they can be very time-consuming when performed by a computer, so much so that the economics of use of present-day list processing languages in most information retrieval applications is questionable. Because of the saving in programming time that is possible, however, we may anticipate future hardware and software developments that will enable these methods to be made practical." (Meadow, 1967, pp. 200-201.)

"This suggests that a conventional linked list structure is inadequate for representing map (or picture) structure. Alternative forms might be an associative memory or a more general linked element structure." (Pfaltz et al., 1968, p. 369).

5.43 "It must be said also that numeric information is often awkward to store in terms of list struc

tures, and arithmetic procedures may be correspondingly difficult to perform." (Salton, 1966, p. 208).

"The well-known list structure languages such as LISP were not designed for graphics and are not very efficient or easy to use for such multidimensional problems. They are well suited for processing strings of text but break down when two-way associations between list elements are the rule rather than the exception." (Roberts, 1965, p. 212).

5.44 "The list processing section of the compiler should make it possible to handle variable length data structures, in such a way that each data item may be associated with a variable number of list pointers, as specified by a special parameter. (Salton, 1966, p. 209).

5.45 "It might . . . be useful to think about a general graph and tree manipulator, capable of performing most of the common transformations on abstract graphs and trees." (Salton, 1966, p. 209).

"The value of a generalized file processing system is directly related to the variety of file structures it can accommodate. With most existing systems, the user is limited to structures having the form of hierarchies or trees. For many problems, such structures are either not adequate or not efficient; instead, these problems require structures of the form of graphs, of which the tree is a special case. Examples of problems of this type are network and scheduling problems, computer graphic problems, and information retrieval problems." (McGee, 1968, p. F68).

"Most complex data structures can be adequately represented as directed graphs. A directed graph is defined informally as a set of labeled points or nodes, and a set of directed line segments or arcs connecting pairs of nodes. An arc running from node x to node y denotes that the entities represented by x and y are related in some way, e.g., x is superior to y, or x precedes y. If x and y bear multiple relationships to each other, they may be connected by multiple arcs, each arc being labeled with the relation being represented." (McGee, 1968, p. F68).

5.46 "Since Rover has more features that are common to IPLs than any other language, it may be said to be a member of the IPL family. Some additional features are present in Rover which attempt to provide a more powerful tool for synthesizing complex processes....

"The original design of IPL memory structure has only DLs [down links] which, by themselves can form lists and achieve a great flexibility. We are introducing ULs [up links] here in order to give greater flexibility and to overcome some of the difficulties encountered by having only DLs. . . .'

"Since the order relation among items is determined only by links, this relation can be changed simply by changing the links without moving the items physically, thus allowing simple and quick changes of organization of of memory content.

Processes such as insertion and deletion of items in a list become very simple. .

"Another disadvantage is the loss of ability to compute addresses. Since the order relation is introduced to a set of items only by extending 'adjacency' defined by links, the table look-up' feature is lost.

"A part of the seemingly lost feature is regained, and furthermore, an added feature is gained by introducing 'side links' which are extension of ULS and DLs. . . .

"The first item on a list. uses its UL to store the name of the list [the location of the cell that contains the name of the first item on the list]. The last item of a list contains the name of the first item as its DL as well as the 'end bit' description. "This internal convention gives a list the effect of being a ring; having reached to the end item, the processor has an access to the first item as well as the name of the list without backtracking." (Hormann, 1960, pp. 2, 13, 15-16, 21).

5.47 "The Association-Storing Processor (ASP) consists of a language designed to simplify the programming of non-arithmetic problems, together with a number of radically new machine organizations designed to implement this language. These machine organizations are capable of highspeed parallel processing, and take advantage of the low cost of memory and logic offered by large scale integration (LSI).

"The ASP concept has been developed specifically for applications having one or more of the following characteristics:

(1) The data bases are complex in organization and may vary dynamically in both organization and content.

a

(2) The associated processes involve complex combinations of simple retrieval operations. (3) The problem definitions themselves may change, often dramatically, during the life of the system." (Savitt et al., 1967, p. 87). 5.48 "Sketchpad's topological file uses special ring structure that permits storage structure rearrangement with a minimum of searching. The use of redundant interconnecting blocks in its list structure gives it the appearance of being ordered more like a tree. This allows fast forward and backward searches for subgroups. The structure used insures that at most two steps must be taken to find either the header block or the previous element." (Coggan, 1967, p. 6).

5.49 "If some connection is deleted, it is not sufficient to just remove the line from the display file. That line represents an association between two elements and may constrain the movement of the elements, the distance between them and their deletion, as well as their external properties (e.g., electrical, program flow, etc.). Thus, each line or other picture element must be attached to an undetermined number of graphical elements

and constraints in such a way as to facilitate the processing of these associations." (Roberts, 1965, p. 211).

..

"A block of elements collects many ties together and thus allows the multi-dimensional associations required for graphical data structures A block is formed from a sequence of registers of any length and contains a blockhead identifier at the top, a group of ring elements and any number of data registers . . . Blocks are used to represent items or entities and the rings form associations between blocks." (Roberts, 1965, pp. 212-213).

"There are two operators for moving around classes, one to go through all members of a class (arrows leaving this item), and one to find all the classes an item belongs to (arrows pointing at this item)." (Roberts, 1965, p. 214).

"Before a new free block is added to the free lists, the block just after it in memory is examined and if it is free also, then the two blocks are merged into one larger free block. This merging technique makes the allocation of variable length blocks almost as efficient as the allocation of fixed length blocks." (Roberts, 1965, p. 213).

5.50 "In the current DEACON work, data is organized into ring structures. These structures are similar in many respects to the plex structures defined by Ross and used by Sutherland in Sketchpad, and are an extension of the notion of list structure." (Thompson, 1966, pp. 354-355).

5.51 "SLIP was the first embedding of a listprocessing capability within a higher level language and has a formative ring structure. The idea of rings was crystallized by Sutherland and Roberts and used with data systems designed primarily for graphics and computer-aided design. Roberts has also developed a language to refer to rings (Class Oriented Ring Associative Language: CORAL). In such languages, the associations are built into the structure by allowing blocks of information to be threaded by rings which carry the associations between the blocks of data. This is illustrated

where 'JOHN's' 'parent of' ring goes through 'NUB C' and 'NUB A', which in turn reference 'Edith' and 'Arnold' respectively. Thus John is the parent of both Edith and Arnold. A similar structure has been implemented with PL/1 by Dodd. The duality of certain relationships, such as: 'defined by' and 'defines' or 'to the left of' and 'to the right of, etc., led to the need for a connector block, here illustrated by the three NUBS. In essence, the NUB represents a two-way switch for transferring out of one ring and into another. The subroutines or macros pass along the ring until they arrive at a NUB. They 'switch' it, and pass into the other ring, passing along the second ring (and others as found) picking up information until they return to the original NUB and re-enter the first ring. This allows answers to questions such as 'Who is the mother of Arnold?' as well as 'Who is the son of Mary?' One of the major disadvantages of these structures occurs on adding a new, not previously anticipated,

association. The operation either is impossible, requiring a complete re-compilation, or else clumsy, patching on additional blocks . . . and requiring sophisticated garbage collectors. A recent survey by Gray describes these and similar structures.' (Ash and Sibley, 1968, p. 145).

5.52 "An interesting variation on the basic list processing technique was described by Cheydleur in 1963. In this technique, a datum is stored just once in memory, but provision is made for many pointers both to and away from a given element. Data redundancy of normal list processing is eliminated at the expense of addressing redundancy. The address bookkeeping becomes quite complex, but it is interesting to note that Cheydleur's concept is applicable to cells of varying sizes. He suggests methods for partitioning strings of symbols so that there is a reasonable distribution of pointers throughout the store. That is, if it can be predicted that the co-occurrence of individual letters or words will be of high frequency, these co-occurrences would be stored in the same cell. Since the storage space taken by pointers competes with data storage requirements, methods for balancing cell size and pointer distribution are quite important." (Climenson, 1966, p. 114).

5.53. "Ring structures are adequate for storing a wide range of richly interrelated data that is pertinent to such functions as intelligence analysis, management planning, and decision making. Typical of these functions are resource allocation problems, in which the pertinent data is an inventory of the resources, their characteristics, and their interrelations. This type of data is specifiable in ring structures." (Craig et al., 1966, p. 366).

5.54 "APL was conceived at the General Motors Research Laboratories to satisfy the need for convenient data association and data handling techniques in a high-level language. Standing for ASSOCIATIVE PROGRAMMING LANGUAGE, it is designed to be embedded in PL/1 as an aid to the user dealing with data structures in which associations are expressed." (Dodd, 1966, p. 677).

5.55 "The principal tool used by this system is the Associative Structure Package (ASP7) implemented by W. A. Newman for the PDP7. It is used to build data structures whose associative properties are expressed using rings, where a ring is a series of addresses in words so that the first points to the next, and so on until the last points back to the first. The first pointer is specially marked and is called a ringstart. The ringstart may point to itself; i.e., the ring may be null." (Pankhurst, 1968, p. 410).

5.56 "On-line interaction introduces into the language picture the possibility of 'conversation'. This possibility, together with the need to bring online languages abreast of conventional programming languages, opens an inviting field to research and development." (Licklider, 1965, p. 124).

We note also the following: "On-line Programming Systems put the raw power of a computer at

the immediate disposal of a human user. Evidence of today's great interest in on-line programming systems is that more and more of them are being used." (Sutherland, 1965, p. 9).

"The on-line nature of time-sharing permits direct man-machine communication in languages that are beginning to approach natural language, at a pace approaching normal human conversation, and in some applications, at graded difficulty levels appropriate to the skill and experience of the user." (Sackman, 1968, p. 1).

"To improve all our on-line systems, we need more and better languages of communication between the man and the machine which are 'natural' in the sense that they are easy to use and fit the task. Why can't I write mathematical equations which look like mathematical equations and have the machine accept, compile and perform them? Why can't I describe network problems to the computer by means of the picture showing the network? Why can't I, in filter design, place poles and zeros on the complex plane? The answer in each case is: I can in principle, but not in practice. As yet, the techniques which let me do these things are not widely used." (Sutherland, 1965, pp. 11-12).

5.57 "Overhead computation can be thought of as degrading the effective operating rate of the processor as seen by the user." (Scherr, 1965, p. 28).

5.58 Examples include, but are not limited to, the following: "With each computation there is associated a set of information to which it requires a high density (in time) of effective reference. The membership of this working set of information varies dynamically during the course of the computation." (Dennis and Van Horn, 1965, p. 11).

"Various problem areas make different demands for data structures and for syntax. The argument is not to restrict specialization to transliteration. It is to avoid unnecessary diversity and to achieve necessary diversity by specializing in the various directions at as high a point on the scale as possible and thus by handling the bulk of the languageimplementation process in a uniform way with common facilities." (Licklider, 1965, p. 181).

"Most writers of papers on on-line applications of time-shared systems are universal in their agreement on the importance of interactive languages. They also seem to concur that such languages will differ substantially from the programming languages now in existence, such as FORTRAN, ALGOL, and IPL-V. The difference is primarily due to the new kinds of operations made possible by the remote console through which communication between man and computer takes place." (Davis, 1966, p. 229).

"In programming as well as in hardware design and system organization, time sharing calls for new departures. Perhaps the most significant is the one referred to by the term 're-entrant programs'. When many computer programs are currently active, it is likely that several of them are doing