Page images

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,





[ocr errors]
[ocr errors]

association. The operation either is impossible, the immediate disposal of a human user. Evidence requiring a complete re-compilation, or else clumsy, of today's great interest in on-line programming patching on additional blocks . . . and requiring systems is that more and more of them are being sophisticated garbage collectors. A recent survey

used." (Sutherland, 1965, p. 9). by Gray describes these and similar structures. "The on-line nature of time-sharing permits direct Ash and Sibley, 1968, p. 145).

man-machine communication in languages that are 5.52 An interesting variation on the basic list beginning to approach natural language, at a pace processing technique was described by Cheydleur approaching normal human conversation, and in in 1963. In this technique, a datum is stored just some applications, at graded difficulty levels approonce in memory, but provision is made for many priate to the skill and experience of the user. pointers both to and away from a given element. (Sackman, 1968, p. 1). Data redundancy of normal list processing is elim- “To improve all our on-line systems, we need inated at the expense of addressing redundancy. more and better languages of communication The address bookkeeping becomes quite complex, between the man and the machine which are but it is interesting to note that Cheydleur's concept ‘natural in the sense that they are easy to use and is applicable to cells of varying sizes. He suggests fit the task. Why can't I write mathematical equamethods for partitioning strings of symbols so that tions which look like mathematical equations and there is a reasonable distribution of pointers through- have the machine accept, compile and perform out the store. That is, if it can be predicted that the them? Why can't I describe network problems to co-occurrence of individual letters or words will be the computer by means of the picture showing the of high frequency, these co-occurrences would be network? Why can't I, in filter design, place poles stored in the same cell. Since the storage space and zeros on the complex plane? The answer in taken by pointers competes with data storage each case is: I can in principle, but not in practice. requirements, methods for balancing cell size and As yet, the techniques which let me do these things pointer distribution are quite important." (Climen- are not widely used.” (Sutherland, 1965, pp. 11-12). son, 1966, p. 114).

5.57 “Overhead computation can be thought of 5.53. “Ring structures are adequate for storing

as degrading the effective operating rate of the a wide range of richly interrelated data that is pertinent to such functions as intelligence analysis,

processor as seen by the user.” (Scherr, 1965, p. 28). management planning, and decision making. Typi. 5.58 Examples include, but are not limited to, cal of these functions are resource allocation prob- the following: "With each computation there is lems, in which the pertinent data is an inventory of

associated a set of information to which it requires the resources, their characteristics, and their inter- a high density (in time) of effective reference. relations. This type of data is specifiable in ring The membership of this working set of informastructures." (Craig et al., 1966,

tion varies dynamically during the course of the 5.54 “APL was conceived at the General Motors computation.” (Dennis and Van Horn, 1965, p. 11). Research Laboratories to satisfy the need for con- “Various problem areas make different demands venient data association and data handling tech- for data structures and for syntax. The argument niques in a high-level language. Standing for is not to restrict specialization to transliteration. ASSOCIATIVE PROGRAMMING LANGUAGE, it It is to avoid unnecessary diversity and to achieve is designed to be embedded in PL/1 as an aid to the necessary diversity by specializing in the various user dealing with data structures in which associa- directions at as high a point on the scale as possible tions are expressed." (Dodd, 1966, p. 677).

and thus by handling the bulk of the language5.55 “The principal tool used by this system is implementation process in a uniform way with the Associative Structure Package (ASP7) imple- common facilities.” (Licklider, 1965, p. 181). mented by W. A. Newman for the PDP7. It is used "Most writers of papers on on-line applications to build data structures whose associative proper- of time-shared systems are universal in their agreeties are expressed using rings, where a ring is a ment on the importance of interactive languages. series of addresses in words so that the first points They also seem to concur that such languages will to the next, and so on until the last points back to differ substantially from the programming languages the first. The first pointer is specially marked and now in existence, such as FORTRAN, ALGOL, and is called a ringstart. The ringstart may point to IPL-V. The difference is primarily due to the new itself; i.e., the ring may be null." (Pankhurst, 1968, kinds of operations made possible by the remote p. 410).

console through which communication between 5.56 "On-line interaction introduces into the

man and computer takes place.” (Davis, 1966, language picture the possibility of conversation'. This possibility, together with the need to bring on- “In programming as well as in hardware design line languages abreast of conventional programming and system organization, time sharing calls for new languages, opens an inviting field to research and departures. Perhaps the most significant is the development." (Licklider, 1965, p. 124).

one referred to by the term ‘re-entrant programs'. We note also the following: On-line Program- When many computer programs are currently ming Systems put the raw power of a computer at active, it is likely that several of them are doing

p. 366).

p. 229).

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).



[ocr errors]

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

[ocr errors]
[ocr errors]

lation of digital circuits, and automatic drawing of pendence for transition to other computers, and flowcharts and other graphical output.” (Knowlton, otherwise for compatibility with hardware .. 1966, p. 617).

[and] better documentation (compatibility among "The most important features of Lsix which programs and different programmers). (Burkdistinguish it from other list processors such as hardt, 1965, p. 4). IPL, LISP, COMIT and SNOBOL are the availa- “The user needs to employ data structures and bility of several sizes of storage blocks and a flexible processes that he defined in the past, or that were means of specifying within them fields containing defined by colleagues, and he needs to refresh his data or pointers to other blocks. Data structures understanding of those objects. The language must are built by appropriating blocks of various sizes, therefore have associated with it a metalanguage defining fields (simultaneously in all blocks) and and a retrieval system. If there is more than one filling these fields with data and pointers to other working language, the metalanguage should be blocks. Available blocks are of lengths 2n machine common to all the languages of the system.” (Lickwords where n is an integer in the range 0–7. The

lider, 1965, p. 185). user may define up to 36 fields in blocks, which “The over-all language will be a system because have as names single letters or digits. Thus the D all the sublanguages will fall within the scope of one field may be defined as bits 5 through 17 of the metalanguage. Knowing one sublanguage will make first word of any block. Any field which is long it easier to learn another. Some sublanguages will enough to store an address may contain a pointer

be subsets of others.” (Licklider, 1965, p. 126). to another block. The contents of a field are inter- 5.68 “The most immediate need is for a general preted according to the context in which they are compiling system capable of implementing a used." (Housden, 1969, p. 15).

variety of higher-level languages, including in “LISP 2 is a new programming language designed particular, string manipulations, list processing facilfor use in problems that require manipulation of ities, and complete arithmetic capabilities." (Salton, highly complex data structures as well as lengthy 1966, p. 208). arithmetic operations. Presently implemented 5.69 Licklider, 1965, p. 119. on the AN/FSQ-32V computer at the System "It will be absolutely necessary, if an effective Development Corporation ... A particularly

procognitive system is ever to be achieved, to have important part of the program library is a group excellent languages with which to control processing of programs for bootstrapping LISP 2 onto a

and application of the body of knowledge. There new machine. (Bootstrapping is the standard must be at least one (and preferably there should be method for creating a LISP 2 system on a new only one) general, procedure-oriented language for machine). The bootstrapping capability is suffici

use by specialists. There must be a large number of ently powerful so that the new machine requires no convenient, compatible field-oriented languages for resident programs other than the standard monitor the substantive users." (Licklider, 1965, p. 67). system and a binary loader.” (Abrahams et al.,

5.70 “There is, in fact, an applied scientific 1966, pp. 661-662). "This list structure processing system and

lag in the study of computer programmers and language being developed at Lincoln is called

computer programming-a widening and critical

lag that threatens the industry and the profession CORAL (Class Oriented Ring Association Lan

with the great waste that inevitably accompanies guage). The language consists of a set of operators for building, modifying, and manipulating a list

the absence of systematic and established methods

and findings and their substitution by anecdotal structure as well as a set of algebraic and conditional forms." (Roberts, 1965, p. 212).

opinion, vested interests, and provincialism.



(Sackman et al., 1968, p. 3). "TREET is a general-purpose list processing system written for the IBM 7030 computer at

“Work on programming languages will continue

to provide a basis for studies on languages in genthe MITRE Corporation. All programs in TREET are coded as functions. A function normally has

eral, on the concept of grammar, on the relation

between actions, objects and words, essence a unique value (which may be an arbitrarliy complex

of imperative and declarative sentences, etc. list structure), a unique name, and operates with

Unfortunately we do not know yet how to achieve a zero or more arguments." (Bennett et al., 1965,

definition of programming languages that covers pp. 452-453).

both their syntactic and pragmatic aspects. To this 5.67 “The growing importance of the family

goal a first step may be the thorough study of special concept accentuates the need for levels of soft- languages, such as programming languages for ware. These levels of software will be geared to

machine tools, and simulation languages." (Caracconfiguration size instead of family member.

ciolo di Forino, 1965, p. 6). In other words, the determining factor will be the 5.71 “As Levien & Maron point out, and Bobrow amount of memory and the number of peripheral analyzes in detail, natural language is much too units associated ..." (Clippinger, 1965, p. 210). syntactically complex and semantically ambiguous

“The advantages of high-level programming to be efficient for man-machine communication. An languages . . . [include] higher machine inde- alternative is to develop formalized languages with

on the

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

« PreviousContinue »