areas as graphical communication, on-line problem solving, multiple access and multiprocessor control systems, simulation, and on-line instrumentation.

We are concerned here, then, with generalpurpose language and compatibility requirements; with special-purpose requirements such as problem-oriented programs, list-processing and other techniques for non-numeric data processing; with special problem areas such as very large programs and the requirements of multiple-access and multiprogrammed systems; with hierarchies of programming languages, and with the increasing interdependence of software and hardware considerations.

5.1.1. Problems of Very Large Programs and of Program Documentation

In terms of continuing R & D concern, we note first the problems of handling very large programs, defined as those that demand many times the available main storage capacity and that are sufficiently complex in structure to require more than ten independent programmers to work on them.5.3 An obvious requirement is to develop efficient techniques for segmentation: "When many programmers are involved, there is the problem of factoring the system into appropriate subtasks. At the present time this is an art rather than a science, and very few people are good at its practice, because of the inability to find useful algorithms for estimating the size and degree of difficulty of programming tasks." (Steel, 1965, p. 234). The questions of automatic segmentation, although recognized as critical and difficult problems, have therefore been raised.5.4

In particular, the checkout of very large programs presents special problems.* For example, 'another practical problem, which is now beginning to loom very large indeed and offers little prospect of a satisfactory solution, is that of checking the correctness of a large program." (Gill, 1965, p. 203). Further, "the error reporting rate from a program system of several million instructions is sufficient to occupy a staff larger than most computing installations possess." (Steel, 1965, p. 233).

Other specific requirements in the programming problem areas include improved provision for adequate program documentation and related controls.5.5 For example, Pravikoff (1965) presents cogent arguments for the improved documentation for programs generally. Mills (1967) points to the special documentation problems in multiple access systems where users are less and less apt to be trained programmers.5.6 Dennis (1968) points to the present high costs of large-scale programming efforts as due to inadequate documentation that prevents taking advantage of programming already achieved,5.7 while Kay (1969) considers the advan

*See also Section 7.1 of this report, on debugging problems generally.

tages of on-line documentation systems.5.8 Thus the area of program documentation requires further study and concern.

A related difficulty is that of inadequate means for translation between machine languages, although some progress has been made.5.9 An intriguing possibility deserving further investigation has been raised by Burge (1966, p. 60) as follows: "Presented here is a problem and a framework for its solution. The problem is as follows: Can we get a computer program to scan a library of programs, detect common parts of patterns, extract them, and re-program the library so that these common parts are shared?"

Another current question of R & D concern with respect to programming problems is of the generality with which a given language system can or cannot cope with a wide variety of system configurations and reconfigurations over time.5.10 The questions of development of more effective common-purpose or general-purpose languages involve very real problems of mutually exclusive features and of choices as between a number of means of achieving certain desirable built-in features.5.11

Areas of continuing R & D concern in programming language developments reflect, first, the need for increasing generality, universality, and compatibility (these objectives are followed in general-purpose language construction and standardization, on the one hand, and by increasing recognition of the needs for hierarchies of language, on the other); secondly, the special requirements of multiple-access, multiprogrammed, multiprocessor, and parallel processing systems; thirdly, requirements for problem-oriented and other special-purpose languages, and finally, needs for continuing advances in hardware-software balances and in fundamental programming theory.

5.1.2. General-Purpose Programming Requirements The presently indicated transition from exclusively batch or job-shop operation to on-line, multiple access system management 5.12 sharply aggravates the problems of programming language requirements in a number of different ways. First, there are very real difficulties in translating from programming languages and concepts geared to sole occupancy and use of system facilities to those required in the multiple-access, and multiprogrammed, much less the multiprocessor and network environment.5.13

As Brooks (1965) points out: "Today's excitement centers chiefly around (1) multiprogramming for time-sharing, (2) multiple-computer systems using a few computers for ultra-reliability, and (3) multiple-computer systems using a highly parallel structure for specialized efficiency on highly structured problems. "5.14 In all of these cases, moreover, the R & D requirements are typically

aggravated by a persistent tendency to underestimate the difficulties of effective problem solution.5.15

An obvious first common-purpose requirement is for truly efficient supervisory, accounting, and monitoring control programs 5.16 that will effectively allocate and dynamically reallocate system resources, that will be secure from either inadvertent or malicious interference, and that will be flexible enough to accommodate to changing clientele needs, often with new and unprecented applications.5.17

Also in the area of general-purpose programming requirements are the various emerging programs for generalized file or data base management, maintenance, and use.5.18 The first requirement, here, is for reconciliation of variable input, file storage, and output formats, together with flexible means for dupe checking on input, combinatorial selection, and output reformatting.5.19 Closely related are the questions of the so-called "formatted file systems."

5.20

A first approach to such general-purpose programming systems was undoubtedly that of the Univac B-O or Flow-Matic system developed in the mid-1950's.5.21 More recent examples include General Electric's GECOS III (General Comprehensive Operating Supervisor III) 5.22 and Integrated Data Store concepts; 5.23 the TDMS (TimeShared Data Management System) at System Development Corporation 5.24 and GIS (Generalized Information System) of IBM.5.25 Heiner and Leishman (1966) describe a generalized program for record selection and tabulation allowing variable parameters for sort requirements, selection criteria, and output formats.5.26

In 1965, comparative operation of file management was demonstrated by different systems including COLINGO (Mitre Corporation), Mark III (Informatics, Inc.), BEST (National Cash Register), Integrated Data Store (G.E.), and an on-line management system of Bolt, Beranek, and Newman, Inc.5 5.27 It was concluded that: “All of these systems were able to accomplish the processing required, but their approaches varied considerably, particularly in the file structures chosen for the application, executive control procedures, and level of language used in specifying the processing to be performed." (Climenson, 1966, p. 125).

In addition, we may note the examples of a file organization executive system, 5.28 a program management system involving a two-level file.5.29 and a file organization scheme developed for handling various types of chemical information.5.30 Another documentation application involving a list-ordered file is provided by Fossum and Kaskey (1966) with respect to word and indexing term associations for DDC (Defense Documentation Center) documents.5.31

In the area of common-purpose languages, also, there is need to reconcile the differing requirements with respect to different classes of data structures,5.32 from those of numerical

analysis processing through those of alphanumeric file management to those of list and multi-list processing.5.33 List structures have been noted in several of the file management systems mentioned and it is to be noted further that: "Linked indexes and self-defining entries are an extension of list processing techniques." (Bonn, 1966, p. 1869). For non-numeric data processing applications, in general, symbol string manipulation, list processing and related programming techniques have been of particular concern.5.34

While many advantages of list-processing techniques have been noted, a number of disadvantages are also reported. Among the major advantages are the recursive nature of list processing languages 5.35 and adaptability to dynamic memory allocation and reallocation.5.36 Also, languages of this type are "well suited to symbol manipulation, which means that it is possible to talk about the names of variables, and perform computations which produce them" (Teitelman, 1966, p. 29), and "by means of list structures . . . a three-dimensional spatial network can be modeled in computer memory." (Strom, 1965, p. 112).

Typical disadvantages to be noted include lack of standardization,5.37 degree of programming sophistication required,5.38 and wastage of storage space.5.39 Major difficulties are often encountered in updating and item deletion operations 5.40 and in dealing with complex data structures.5.41 We may ask also to what extent the available list-processing and symbol manipulation programming languages are adequate for current application needs? 5.42 To what extent are they useful for the investigation of further needs? In particular, it is noted that "unfortunately, while these languages seem in many ways directly tailored to the information retrieval work, they are also in other respects very awkward to use in practice." (Salton, 1966, p. 207).

are

List-processing languages and structures particularly clumsy, moreover, for multiply interrelated and cross-associated data.5.43 Short of truly large-scale associative memories, effective compromises are needed as between list structures, including multilist programming languages, and file organizations that will provide economy of both storage and access.5.44

Beyond list processing procedures there are trees, directed graphs, rings, and other more complex associative schemes.5.45 A relatively early example is that of "Rover" with "up links" and "side links" as well as "down links".5.46 Savitt et al., 1967, describe a language, ASP (Association-Storing Processor), that has been designed to simplify the programming of nonnumeric problems, together with machine organizations capable of high-speed parallel processing.5.47

Ring structure language systems are represented by Sketchpad developments 5.48 and the work of Roberts at M.I.T. for graphical data processing 5.49 and by systems for use in question-answering

and similar systems, such as Project DEACON.5.50 Still other associative structure developments are discussed for example, by Ash and Sibley (1968), 5.51 Climenson (1966), 5.52 Craig et al., (1966), 5.53 Dodd (1966), 5.54 and Pankhurst (1968),5.55

There are certainly those who need far more generalized multipurpose languages and, with equivalent force, those who advocate specialized, man-oriented, and special-purpose languages. A specific current design problem has to do with an appropriate compromise between these apparently contradictory comments. A future R & D requirement is to seek more effective solutions. Thus Licklider insists upon the need to bring on-line "conversational" languages more nearly abreast with the more conventional programming languages as an R & D challenge. 5.56

5.1.3. Problem-Oriented and Multiple-Access Language Requirements

Increasing needs for advanced special-purpose program language developments have been recognized for the areas of man-machine interactive problem-solving and computer-aided instruction applications, graphical manipulation operations, and simulation applications, among others. It is noted in particular that "their power [that of problem-oriented languages] in the extension of computing lies in the fact that the expert knowlledge of skilled analysts in particular fields can be incorporated into the programs, together with a language which is native to the field, or nearly so, and can thereby break down the barriers of economics, of lack of familiarity with the computer, and of time." (Harder, 1968, p. 235).

Important requirements in programming languages reflect, predictably, those of multipleaccess and time-shared systems involving a suitable hierarchy of languages so that the relatively unsophisticated user may converse freely with the machine without interference to other users or to the control and monitor programs and yet also draw upon common-use programs and data. The effective use of such systems in turn demands extremely tight and sophisticated programming to keep "overhead" to a minimum 5.57 and to provide dynamic program and data location and relocation. Relatively recent developments in this area are discussed by Bauer, Davis, Dennis and Van Horn, Licklider, Clippinger, Opler, and Scherr among others.5.58 Bauer (1965, p. 23) suggests in particular that: "Entirely new languages are needed to allow flexible and powerful use of the computer from remote stations."

Multiple-access systems and networks obviously require R & D efforts in the development of language systems "optimized for remote-on-line use" (Huskey, 1965, p. 142). Opler points out, first, that "for the most difficult areas - telecommunication, process control, monitors, etc.real-time languages have provided little assistance,"

and, secondly, that "the task of developing a complete new real-time language would be interesting and challenging since it would require reconsideration of the conventional procedure and data defining statements from the viewpoint of the real-time requirements." (Opler, 1966, p. 197).

Further, on-line problem-solving applications require dynamic and flexible programming capabilities.5.59 Experimentation with the working program should be permitted with due regard for system protection and control.5.60 Generalized problemsolving capabilities should be available in the language system without necessary regard to specific applications.5.61 Such programs should be extensively self-organizing, self-modifying, and capable of adaptation or tentative "learning." 5.62

Then it is to be noted that languages for on-line use should be relatively immune to inadvertent user errors.5.63 Teitelman comments, for example, that "in languages of this type, FORTRAN, COMIT, MAD, etc., it is difficult to write programs that construct or modify procedures because the communication between procedures is so deeply embedded in the machine instruction coding, that it is very difficult to locate entrances, exits, essential variables, etc." (1966, p. 28).

In language systems such as TRAC,5.64 the powerfulness is largely buried in specific machine processors for this language-the user is freed from learning a number of arbitrary exceptions, he is not able to "clobber" the underlying processor by inadvertent goofs, he is able iteratively to name and rename strings and procedures he wishes to use largely in terms of his own convenience, and he is able to make use of the language and system with minimal training or prior experience.

Related problems affect the design of specialpurpose languages ("the design of special-purpose languages is advancing rapidly, but it has a long way to go," Licklider, 1965, p. 66), the interaction of executive and console languages ("wherever remote consoles are used, we find the users enthusiastic. However, they always hasten to add that there is much to learn about the design of executives and processors for console languages,' (Wagner and Granholm, 1965, p. 287), the provision of adequate debugging aids ("the creation of large programming systems using remote facilities requires a number of debugging aids which range in complexity from compilers to simple register contents request routines." Perlis, 1965, p. 229), and the development of effective modularity in programs and compilers ("it will be necessary for the software to be modular to the greatest extent possible because it will need to work up to the next level of software." Clippinger, 1965, p. 211).

In connection with the latter requirement Lock discusses the desirability of an incremental compiler which is characterized by its ability "to compile each statement independently, so that any local change in a statement calls only for the re

compilation of the statement, not the complete program." (1965, p. 462).

Time-sharing or time-slicing options and graphical communication possibilities cast new light not only upon the problem-oriented but also upon the useroriented languages and improved possibilities for man-machine communication and interaction. Effective compromises between the system design, the programmer, and the client have not yet been met, even although the demands of modern systems are increasing in complexity.

The problems of effective programming and utilization reach back beyond specific routines, specific languages, and specific equipment. They are involved in all the many questions of systems planning, systems managment and systems design. For example, in time-shared operations, "considerably greater attention should be focused on questions of economy in deciding on the tradeoff between hardware and software, in using storage hierarchies, and in determining the kind of service which the timesharing user should be offered." (Adams, 1965, p. 488). Finally, the critical problems reach farther back than the potentialities of hardware, software and systems planning combined, to fundamental question of why, how, and when we should look to machines for substantial aid to human decisionmaking and problem-solving processes.

"An analysis of the various requirements that a programming language must satisfy (to be known both by the job-originator and the job-executor and to be capable of expressing both what the first wants to be done and what the second is capable of doing) involves basic researches on the linguistic nature of programming languages." (Caracciolo di Forino, 1965, p. 224).

5.1.4. Heirarchies of Languages and Programming

Theory

Direct machine-language encoding and programming was the first and obvious approach to both numeric and non-numeric data processing problems. In both areas, forms of communication with the machine that are more congenial to the human user have been developed, as formal "programming languages" (FORTRAN, ALGOL, COBOL, and the like).5.65 In addition, special program languages to facilitate either problemsolving and question-answering systems, or textual data processing, or both; (such as list-processing techniques, IPL-V, LISP, COMIT, SNOBOL, more recently TRAC, and others) 5.66 have been developed. More and more, however, it is beginning to be recognized that hierarchies of language are essential to present and foreseeable progress.5.67 Burkhardt (1965, p. 3) lists a spectrum of programming languages on the basis of the "declarative freedom' available to the user, from absolute machine languages with none, to "declarative languages" which provide a description of the problem and freedom of both procedure and solu

tion. Certainly, for the future, "the entire spectrum of language from binary machine code to the great natural languages will be involved in man's interaction with procognitive systems." (Licklider, 1965, p. 104).

In the area of desired hierarchies of languages, we note such corroborating opinions as those of Salton who asks for compiling systems capable of handling a variety of high-level languages, specifically including list processing and string manipulations 5.68 and of Licklider who points out that in each of many subfields of science and technology there are specific individual problems of terminology, sets of frequently used operations, data structures, and formulas, indicating a very real need for many different user-oriented languages.5.69 However, in his 1966 review, the first ACM Turing Lecture, Perlis concludes: "Programmers should never be satisfied with languages which permit them to program everything, but to program nothing of interest easily. Our progress, then, is measured by the balance we achieve between efficiency and generality." (1967, p. 9).

Moreover, even in a single system, it may be necessary not only to reconcile but to combine the contradictory advantages and disadvantages of differing levels of programming language in various ways. Thus Salton states "it is possible to recognize five main process types which must be dealt with in an automatic information system: string manipulation and text processing methods, vector and matrix operations, abstract tree and list structure manipulations, arithmetic operations, and finally sorting and editing operations." (Salton, 1966, p. 205). A second complicating factor relates to the still unusually fluid situation with respect to hardware developments, logical design, and the increasing interdependence of hardware-software factors in the consideration of future system and network design possibilities.

Beyond the investigation, development, and experimental application of advanced programming languages for specific types of application such as graphical data processing, simulation, or on-line question-answering and problem-solving systems, study is needed of fundamental problems of programming theory.5.70 For example Halpern notes the increasingly wide gulf between research and practice in the design of programming languages." (1967, p. 141), while Alt emphasizes that "we do not yet have a good theory of computer languages, and we are nowhere near the limit of the concepts which can be expressed in such languages." (1964, p. B.2-1).

66

66

There is also to be noted in the current state of the art in the computer and information sciences an increasing concern for the relationships between formal modelling techniques, generally, the questions of formal languages, and the development. of powerful, general-purpose programming languages.5.71 Karush emphasizes that "the development of an integrated language of mathematical

and computer operations is part of a more general problem associated with the automation of control functions. This is the problem of formalism which embraces both mathematical representations of systems and representations of the processes of actual execution of systems, by computer or otherwise." (1963, p. 81).

A similar concern is expressed by Gelernter: "Just as manipulation of numbers in arithmetic is the fundamental mode of operation in contemporary computers, manipulation of symbols in formal systems is likely to be the fundamental operating mode of the more sophisticated problem solving computers of the future. It seems clear that while the problems of greatest concern to lay society will be, for the most part, not completely formalizable, they will have to be expressed in some sort of formal system before they can be dealt with by machine." (1960, p. 275).

High-order relational schemes both in languages and in memory structures will thus be required.5.72 For example, "the incorporation in procedural programming languages of notations for describing data structures such as arrays, files, and trees, and the provision to use these structures recursively together with indications of the scope of definition, will help greatly with the storage allocation problem and assist the programmer organizationally. . ." (Barton, 1963, p. 176). In this connection, Press and Rogers (1967) have described the IDEA (Inductive Data Exploration and Analysis) program package for the detection of inherent structure in multivariate data.5.73

We note also that "even in the more regular domain of formal and programming languages, many unsolved practical and theoretical problems remain. For example, the matter of recovery from error in the course of compilation remains in a quasi-mystical experimental state, although some early results, applicable only to the simplest of languages suggest that further formal study of this problem could be worth while." (Oettinger, 1965, p. 16).

Requirements for continuing research and development activities in the area of computing and programming theory are increasingly seen as directly related to needs for more effective multiaccess time-sharing, multi-programmed, and multiprocessor systems. It can be foreseen that "Organizational generality is an attribute of underrated importance. The correct functioning of on-line systems imposes requirements that have been met ad hoc by current designs. Future system designs must acknowledge the basic nature of the problems and provide general approaches to their resolution." (Dennis and Glaser, 1965, p. 5).

What are some of the difficulties that can be foreseen with respect to the further development of hierarchies of systems? Scarrott suggests that "the problems of designing and using multilevel storage systems are in a real sense central

to the design of computing systems" (1965, p. 137), and Burkhardt warns: "As long as actual computers are not well understood there will not be much hope for very successful development of useful universal processors." (1965, p. 12).

5.2. Processor and Storage System Design Considerations

In the area of information processing systems themselves, current trends have been marked not only by new extensions to the repertoires of system configurations available for the large, high-cost, high-speed processors but also by a continuing tendency to the development of computer system "families." Increasing attention is being given to both "upward" and "downward" compatibility - that is, to means by which programs operable on a large system may also operate on a smaller, slower, or less expensive member of the same family, and vice versa.

Increasing attention has also been given to providing adjuncts to existing and proposed systems which will give them better adapatability to timesharing and on-line multiple-access requirements. Similarly, the requirements for handling a variety of input sensing modalities and for processing more than one input channel in an effectually simultaneous operation clearly indicate needs for continuing research and development efforts in the design and use of parallel processing techtime-shared niques, multiprocessor networks, multiple access scheduling and multiprogramming. Hierarchies of languages are implied as we have seen, ranging from those in which the remote console user speaks to the machine system in a relatively natural language (constrained to a greater or lesser degree) to those required for the highly sophisticated executive control, scheduling, file protection, accounting, monitoring, and monitoring instrumentation programs.

Tie-in to various communication links, generally, should include remote consoles, closed circuit TV, facsimile, voice quality circuits, and the like, with capability for real-time processing. Message security protection facilities are often required, including encoding and decoding. Access to error detection and error correction mechanisms are also necessary.

Overall system design requirements indicate also the necessary exploitation of new hardware technologies, new storage media, associative-memory procedures for file and data bank organization and management, the use of dynamic reallocations of space and access to both programs and files or data banks in multiple-access systems, protective and fail-safe measures, and the development of hierarchies of languages of access and usage, hierarchies of stored data files, and hierarchies of systems. 5.74

Many of the above factors are discussed in other sections of this report or in other reports in this series. Here, we will consider briefly some of the