March 1966 - Vol. 9 No. 3

March 1966 issue cover image

Features

Research and Advances

Programming semantics for multiprogrammed computations

The semantics are defined for a number of meta-instructions which perform operations essential to the writing of programs in multiprogrammed computer systems. These meta-instructions relate to parallel processing, protecting of separate computations, program debugging, and the sharing among users of memory segments and other computing objects, the names of which are hierarchically structured. The language sophistication contemplated is midway between an assembly language and an advanced algebraic language.
Research and Advances

The structure of programming languages

The following are identified as major components of every programming language: (1) the elementary program statement, (2) mechanisms for linking elementary statements together, (3) the means by which a program can obtain data inputs. Several alternative forms of each of these components are described, compared and evaluated. Many examples, frequently from list processing languages, illustrate the forms described. Elementary program statements usually take the form of commands, requirements, or implicit specifications. A command is an imperative statement that commands the action to be taken. A requirement describes the effect to be achieved without saying anything about the actions to be taken. An implicit specification is similar to a requirement, but the programmer must understand what actions will be taken to achieve the desired effect. Subroutines may be entered explicitly, by execute call, or by function composition. Explicitly called subroutines generally require special linkage conventions. An execute subroutine call is syntactically indistinguishable from a basic instruction of the programming language. Function composition is a convenient alternative to the explicit call. The three principal ways of getting inputs for routines are (1) by referring to the data itself, (2) by referring to the data by a “name”, and (3) by referring to it implicitly by means of variables or functions. Names are useful entry points into permanent data structures, but can be error-causing distractions in other contexts. The author discusses advantages, disadvantages, and factors influencing the choice of a form of component for a language. He concludes by suggesting the evolution of programming languages toward one which will permit all
Research and Advances

The next 700 programming languages

A family of unimplemented computing languages is described that is intended to span differences of application area by a unified framework. This framework dictates the rules about the uses of user-coined names, and the conventions about characterizing functional relationships. Within this framework the design of a specific language splits into two independent parts. One is the choice of written appearances of programs (or more generally, their physical representation). The other is the choice of the abstract entities (such as numbers, character-strings, list of them, functional relations among them) that can be referred to in the language. The system is biased towards “expressions” rather than “statements.” It includes a nonprocedural (purely functional) subsystem that aims to expand the class of users' needs that can be met by a single print-instruction, without sacrificing the important properties that make conventional right-hand-side expressions easy to construct and understand.
Research and Advances

Syntax-directed interpretation of classes of pictures

A descriptive scheme for classes of pictures based on labeling techniques using parallel processing algorithms was proposed by the author some years ago. Since then much work has been done in applying this to bubble chamber pictures. The parallel processing simulator, originally written for an IBM 7094 system, has now been rewritten for a CDC 3600 system. This paper describes briefly the structure of syntactic descriptive models by considering their specific application to bubble chamber pictures. How the description generated in this phase can be embedded in a larger “conversation” program is explained by means of a certain specific example that has been worked out. A partial generative grammar for “handwritten” English letters is given, as are also a few computer-generated outputs using this grammar and the parallel processing simulator mentioned earlier.
Research and Advances

A graphical service system with variable syntax

Man-machine interaction in many fields of endeavor should be greatly facilitated in the near future through the use of interactive graphical languages. To provide a variety of display scope communication procedures, a Graphic Service System which functions as a generalized graphical language translator, is being developed to aid the definition as well as the use of new graphical languages.
Research and Advances

Program translation viewed as a general data processing problem

Efficiency dictates that the overall effectiveness of a compiler be increased by all means available. For a compiler to have a substantial useful life it needs a clear logical structure, reliability and sound data processing techniques. A compiler must be based on fixed conventions to preserve efficiency and reliability; empty options and default conventions violate this dictum. Use of structure to associate various parts of a program and economy of features promote clarity and reliability.
Research and Advances

An ALGOL compiler: construction and use in relation to an elaborate operating system

An ALGOL translator has been prepared and integrated into the IBSYS Operating System. Assembly and “go” features of IBSYS permit immediate execution with optional listings, decks and debugging information. Using the chain feature of IBSYS, links written in MAP or FORTRAN as well as ALGOL may be called by the ALGOL main program. In addition, procedures coded in MAP may be included in any ALGOL program. Although assembly plus loading time exceeds compilation time, the total time is satisfactory and the user gets ease and facility which are fully compensating.
Research and Advances

More on extensible machines

One of the most salient characteristics of extensible machines (EM) is the facility for providing system control over program-to-program and program-to-data linkage (e.g., address connection.) It is the intent of this paper to expand and clarify the remarks concerning program-to-program and program-to-data linkage that were embodied in the authors' previous paper on the EM concepts, and to, finally, trace the employment of linkage mechanisms through various levels of programming languages.
Research and Advances

Multilevel operating systems

The basic software for all newer computers is built on the well-established need for standard operating systems. This implies that all applications—no matter how large, complex or time consuming—must operate under (or, more precisely, on top of) the standard system. Large applications require supervisory monitors which handle problems similar to those of the operating systems, but at a different level. Sometimes, still a third or even a fourth such level is required or desirable. This leads naturally to the concept of multilevel systems—similar vertically, but different horizontally. Proper division of responsibility between levels leads to greater efficiency and less logical complexity, while actually enhancing capability.
Research and Advances

Evolution of the meta-assembly program

A generalized assembler called a “meta-assembler” is described. The meta-assembler is defined and factors which contributed to its evolution are presented. How a meta-assembler is made to function as an assembly program is described. Finally, the implication of meta-assemblers on compiler design is discussed.
Research and Advances

Requirements for real-time languages

Real-time languages have different requirements from other programming languages because of the special nature of their applications, the environment in which their object programs are executed and the environment in which they may be compiled. It may not be the language extensions that ultimately advance developments in the field. Progress may be made by attacking the special compiling and executing system problems that must be solved.
Research and Advances

Online programming

When the transition has been made from offline to online programming, there are a number of changes in the working conditions noted. These changes in the environment make necessary corresponding changes in the processes related to producing and checking out programs. In the main, it is not the programming language itself which must be changed to provide a facility for the online user; it is the system surrounding the programming language. In this paper the online environment and its effect on programming are discussed.
Research and Advances

Data manipulation and programming problems in automatic information retrieval

Automatic information retrieval programs require the manipulation of a variety of different data structures, including linear text, sparse matrices, and tree or list structures. The main data manipulations to be performed in automatic information systems are first briefly reviewed. A variety of data representations which have been used to describe structured information are then examined, and the characteristics of various processing languages are outlined in the light of the procedures requiring implementation. Advantages and disadvantages of these programming languages for the retrieval application are examined, and suggestions are made for the design of programming facilities to aid in information retrieval.
Research and Advances

Storage and retrieval of aspects of meaning in directed graph structures

An experimental system that uses LISP to make a conceptual dictionary is described. The dictionary associates with each English word the syntactic information, definitional material, and references to the contexts in which it has been used to define other words. Such relations as class inclusion, possession, and active or passive actions are used as definitional material. The resulting structure serves as a powerful vehicle for research on the logic of question answering. Examples of methods of inputting information and answering simple English questions are given. An important conclusion is that, although LISP and other list processing languages are ideally suited for producing complex associative structures, they are inadequate vehicles for language processing on any large scale—at least until they can use auxiliary memory as a continuous extension of core memory.
Research and Advances

TRAC, a procedure-describing language for the reactive typewriter

A description of the TRAC (Text Reckoning And Compiling) language and processing algorithm is given. The TRAC language was developed as the basis of a software package for the reactive typewriter. In the TRAC language, one can write procedures for accepting, naming and storing any character string from the typewriter; for modifying any string in any way; for treating any string at any time as an executable procedure, or as a name, or as text; and for printing out any string. The TRAC language is based upon an extension and generalization to character strings of the programming concept of the “macro.” Through the ability of TRAC to accept and store definitions of procedures, the capabilities of the language can be indefinitely extended. TRAC can handle iterative and recursive procedures, and can deal with character strings, integers and Boolean vector variables.
Research and Advances

Some preliminary remarks on theoretical pragmatics

The term pragmatics has been used, as is well known, by Morris and Carnap to denote that branch of semiotics which deals with the relation between a language and its users. As such I don't like the term very much. But one might also define it to be that branch which deals with the relation between languages and actions or processes. This seems more appropriate to me. In any case, whatever the definition, there is a basic connection between programming languages and pragmatics, as pointed out by Gorn. I devoted a paragraph to this subject in my talk at the IFIP Congress 1965 entitled “Linguistic Problems in Programming Theory.”
Research and Advances

The use of English as a programming language

The purpose of this talk is to make a personal plea, backed up by some practical comments, for the use of English or anyone else's natural language as a programming language. This seems to be a suitable subject for the conference, since whatever definition of pragmatics is decided upon, it certainly seems to be tied in with the users of any programming language and what the language means to them.
Research and Advances

Microprogramming, emulators and programming languages

The problem we have been concerned with is that of converting language to action—or intellectual energy to mechanical energy. The medium that we use for this purpose is language and therefore we are preoccupied with the subject of language. In the areas of language investigation we have concentrated first on formalizing syntax and then on semantics. I believe semantics has received an unfair share of the energy of too many people—mainly misdirected to trying to reduce semantics to an algebraic manipulation of symbols, without enough attention to reality. By reality I mean the devices or mechanisms which are going to use these symbols. We have been overly concerned with what the symbols mean to one class of users, namely, the human or the senders of the symbols, without sufficient concern about the receivers of the symbols, in this case the machines.
Research and Advances

Advanced programming and the aims of standardization

Some of the most advanced programming techniques have emerged either because of the complete lack of coordinated standards, or because there was too rigid standardization and too soon, whether it was planned that way or not. The standardization that was lacking, or too rigid, was in programming techniques, programming languages, programming terminology, equipment techniques, available equipment, and specification and documentation methods for equipment, programs, languages, and problems to be solved. For example, common programming languages developed because of the lack of standardized equipment or languages for their use.

Recent Issues

  1. November 2024 CACM cover
    November 2024 Vol. 67 No. 11
  2. October 2024 CACM cover
    October 2024 Vol. 67 No. 10
  3. September 2024 CACM cover
    September 2024 Vol. 67 No. 9
  4. August 2024 CACM cover
    August 2024 Vol. 67 No. 8