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 organiza

tion and content. (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 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,

а

uses

a

a

essentially the same thing at the same time. Whenever that is the case, efficiency in use of memory space would be gained if the several programs shared a common subprogram.” (Licklider, 1965,

p. 26).

a

a

5.59 "In artificial intelligence problems, this process (code, run & see, code] must often be prolonged beyond the debugging phase. It is important for the programmer to experiment with the working program, making alterations and seeing the effects of the changes. Only in this way can he evaluate it or extend it to cover more general cases." (Teitelman, 1966, p. 2).

“This appears to be the best way to use a truly interactive man-machine facility-i.e., not as a device for rapidly debugging a code representing a fully thought out solution to a problem, but rather as an aid for the exploration of problem solving strategies." (Weizenbaum, 1966, p. 42).

“If computers are to render frequent and intensive service to many people engaged in creative endeavors (i.e., working on new problems, not merely resolving old ones), an effective compromise between programming and ad hoc programming is required.” (Licklider, 1965, p. 181).

5.60 “Programs very likely to contain errors must be run but must not be permitted to interfere with the execution of other concurrent computations. Moreover, it is an extremely difficult task to determine when a program is completely free of errors. Thus, in a large operational computer system in which evolution of function is required, it is unlikely that the large amount of programming involved is at any time completely free from errors, and the possibility of system collapse through software failure is perpetually present. It is becoming clear that protection mechanisms are essential to any multiprogrammed computer system to reduce the chance of such failure producing catastrophic shutdown of a system.” (Dennis, 1965, p. 590).

5.61 “The functional language makes no reference to the specific subject matter of the problem ... The program must be organized to separate its general problem-solving procedures from the application of these to a specific task.” (Newell and Simon, 1959, p. 22).

“There has been a shift away from a concern with difficulty and toward a concern with generality. This means both a concern that the problem solver accept a general language for the problem statement, and that the internal representation be very general." (Newell, 1965, p. 17).

5.62 For example, "Multilang is a problemoriented language that translates the user's statement of the problem into requests for relevant programs and data in the system's memory. The language was designed specifically to assist in problem-solving and, in so doing, to 'accumulate knowledge'. For example, it may not recognize the term 'eligible voter', but it can be told that an eligible voter is a thing that is ‘human', ‘age over 21' and

either 'born in the U.S.' or 'naturalized'. If these terms have been previously defined, the computer can find an answer to the question; additionally, the next time it is asked about eligible voters, it will know what is meant.” (Carr and Prywes, 1965, pp. 88-89).

5.63 “Each user, and each user's program, must be restricted so that he and it can never access (read, write, or execute) unauthorized portions of the high-speed store, or of the auxiliary store. This is necessary (1) for privacy reasons, (2) to prevent a defective program from damaging the supervisor or another user's program, and (3) to make the operation of a defective program independent of the state of the rest in store.” (Samuel, 1965, p. 10).

, p. . 5.64 "The TRAC (Text Reckoning And Compiling) language system is a user language for control of the computer and storage parts of a reactive typewriter system.” (Mooers, 1966, p. 215).

“A solution to this problem is to use a machineindependent computer language, designed to operate with a reactive typewriter, to operate the local computer. With this method, the computer acts in place of the human controller to gain access to remote computer systems. This approach is possible only with an extremely versatile language, such as the TRAC language. ... It is relatively easy to describe in TRAC the set of actions which must be taken in order to make the remote computer perform and bring forth the desired files." (Fox et al., 1966, p. 161).

5.65 "The basic property of symbolic languages is that they can make use in a text of a set of local symbols, whose meaning and form must be declared within the text (as in ALGOL) or is to be deduced by the context (as simple variables in FORTRAN).' (Caracciolo di Forino, 1965, p. 227). However, wit is . . . regrettable from the standpoint of the emerging real-time systems that languages like COBOL are so heavily oriented toward processing of sequential tape file data." (Head, 1963, p. 40).

5.66 Some other recent examples include LECOM, LS, LISP II, CORAL, and TREET, characterized briefly as follows:

“The compiler language, called LECOM, is a version of COMIT, and is especially designed for small (8K) computers. The microcategorization program was written in LECOM, and assigns an appropriate syntactic category to each word of an input sentence." (Reed and Hillman, 1966, p. 1).

"Bell Telephone Laboratories' Low-Level Linked List Language (L6, pronounced ‘L-six') contains many of the facilities which underlie such list processors as IPL, LISP, COMIT and SNOBOL, but it permits the user to get much closer to machine code in order to write faster-running programs, to use storage more efficiently and to build a wider variety of linked data structures." (Knowlton, 1966, p. 616).

"L6 ... is presently being used for a variety of purposes, including information retrieval, simu

a simplified syntax and vocabulary. Examination of several query languages, for example, COLINGO and GIS, reveals a general (and natural) dependence on, and adaptation of, the rules of formal logic. However, even with English words for logical operations, relations, and object names, formal query languages have been a less-than-ideal solution to the man-machine communication problem. Except for the simplest queries, punctuating a nested Boolean logical statement can be tricky and can lead to errors. Furthermore, syntactic problems aside, a common difficulty arises when the user does not know the legal names of the data for which he is searching or the structural relationships among the data items in the data base, which may make one formulation of his query very difficult and expensive to answer whereas a slightly altered one may be simple to answer.” (Minker and Sable, 1967, p. 136).

“The possibility of user-guided natural-language programming offers a promise of bridging the manmachine communication gap that is today's greatest obstacle to wider enjoyment of the services of the computer.” (Halpern, 1966, p. 649).

"Such a language would be largely built by the users themselves, the processor being designed to facilitate the admission of new functions and notation of any time. The user of such a system would begin by studying not a manual of a programming language, but a comparatively few pages outlining what the computer must be told about the location and format of data, the options it offers in output media and format, the functions already available in the system, and the way in which further functions and notation may be introduced. He would then describe the procedure he desired in terms natural to himself.” (Halpern, 1967, p. 143).

5.72 “Further investigation is required in searching and maintaining relationships represented by graph structures, as in 'fact retrieval' systems. Problems in which parts of the graph exist in one store while other parts are in another store must be investigated, particularly when one breaks a link in the graphs. The coding of data and of relations also needs much work.” (Minker and Sable, 1967, p. 151).

5.73 “This program package has been used in the analysis of several multivariate data bases, including sociological questionnaires, projective test responses, and a sociopolitical study of Colombia. It is anticipated that the program will also prove useful in pattern recognition, concept learning, medical diagnosis, and so on." (Press and Rogers, 1967, p. 39).

5.74 “The execution of programs at different installations whose total auxiliary storage capacities are made up of different amounts of random access storage media with different access characteristics can be facilitated by the organization of the auxiliary storage devices into a multilevel storage hierarchy and the application of level changing." (Morenoff and McLean, 1967, p. 1).

5.75 “A systems problem that has received considerable attention is how to determine which data should be in computer memory and which should be in the various members of the mass storage hierarchy." (Bonn, 1966, p. 1865).

“The key requirement in multiprogramming systems is that information structures be represented in a hardware-independent form until the moment of execution, rather than being converted to a hardware-dependent form at load time. This requirement leads directly to the concept of hardwareindependent virtual address spaces, and to the concept of virtual processors which are linked to physical computer resources through address mapping tables." (Wegner, 1967, p. 135).

5.76 “With respect to the central processing unit, the major compromise of future needs with present economy is the limitation on addressing capacity." (Brooks, 1965, p. 90).

“Other major problems of large capacity memories are related to the tremendous amount of electronic circuitry required for addressing and sensing.” (Kohn, 1965, p. 132).

5.77 For example, "the problem of assigning locations in name space for procedures that may be referenced by several system functions and may perhaps share references to other procedures, is not widely recognized and leads to severe complications when implementation is attempted in the context of conventional memory addressing.” (Dennis and Glaser, 1965, p. 6).

5.78 “A particularly troublesome phenomenon, thrashing, may seriously interfere with the performance of paged memory systems, reducing computing giants (Multics, IBM System 360, and others not necessarily excepted) to computing dwarfs. The term thrashing denotes excessive overhead and severe performance degradation or collapse caused by too much paging. Thrashing inevitably turns a shortage of memory space into a surplus of processor time." (Denning, 1968, p. 915).

5.79 “... Global weather prediction. Here a three-dimensional grid covering the entire world must be stepped along through relatively short periods of simulated time to produce a forecast in a reasonable amount of time. This type of problem with its demand for increased speed in processing large arrays of data illustrates the applicability of a computer designed specifically for array processing.” (Senzig and Smith, 1965, p. 117).

“Most engineering data is best represented in the computer in array form. To achieve optimum capability and remove the restrictions presently associated with normal FORTRAN DIMENSIONed array storage, arrays should be dynamically allocated. Dynamic allocation of data achieves the following: “1. Arrays are allocated space at execution

time rather than at compilation time. They are only allocated the amount of space needed for the problem being solved. The