Search
Join ACM

Theory

Advertisement

Research and Advances Mar 1 1964

Polyphase sorting with overlapped rewind

A variation of the polyphase merge technique of sorting is described which permits one tape at a time to be rewound while the merge is continued on the remaining tapes. The result is the overlapping of a major portion of the rewind time. The technique should be considered whenever a sort is written to operate on five or more tapes that cannot be read backwards. The savings of the overlap method appear to increase as the number of available tapes is increased.
Research and Advances Mar 1 1964

Tests on a computer method for constructing school timetables

A previously proposed computer method for constructing timetables, based on an iteration involving Boolean matrices, is described. In limited tests the method has successfully produced timetables on every trial. References are given which relate the timetable problem to theorems on matrices of zeros and ones, and to theorems on bipartite graphs. Some problems of applying the method to constructing timetables in real situations are noted.
and
Research and Advances Mar 1 1964

FORTRAN subroutines for time series data reduction

For several years the author has been concerned with time series data reduction of guided missile data derived from tracking, telemetry and static test instrumentation. The data, which is acquired from many sources and comes in a great variety of formats and coding systems, must commonly be manipulated in a number of general ways before the calculation of functions specific to guided missile analysis is possible. The costs of programming many special purpose data reduction programs and the development time consumed in preparing and checking out these programs have strongly indicated the need for independent, general-purpose computer program modules or subroutines for data reduction. The philosophy arrived at by the author, is almost identical with that described in a recent publication by Healy and Bogert, and in a note by Bennet, but these individual module specifications are concerned with continuous functions, whereas the referenced article deals with spectral analysis.
Research and Advances Feb 1 1964

Some effects of the 6600 computer on language structures

The problem of compiling efficient 6600 codes prompted the development of an intermediate language reflecting the structure of the machine, that is more easily manipulated in improving object program efficiency. The subject of this paper is the intermediate language and methods of manipulating it. Compilations of a series of arithmetic statements are discussed. It is assumed that all functions and exponentials have been removed from these statements, and replaced by simple variables. For purposes of simplicity the treatment of subscripts is ignored. A simplified 6600 structure is presented to illustrate the compiling method. Several assumptions are made for purposes of simplification, although there are cases in which the assumptions are violated in the actual machine.
, , and
Research and Advances Feb 1 1964

A format language

One of the most primitive parts of a formula language is its specification of input-output actions within the framework of the language. While the specification is intrinsically more complex, say, than the evaluation of an arithmetic expression, most of the difficulties associated with input-output specification arise from the fact that the desired operations have not been properly defined using the framework of a programming language. Indeed, the complexity largely disappears when a programming language is constructed to specify input-output actions. The point to be made here is that the definition of an appropriate programming language makes more rational and simpler all three phases of the input-output programming cycle: (i) source program construction, (ii) object program construction, (iii) object program execution.
Research and Advances Feb 1 1964

Summary remarks

The topics began with discussion of almost exclusively syntactic analysis and methods. Beginning with context-free phrase-structure languages, we considered limitations thereof to remove generative syntactic ambiguities (Floyd), and extensions thereto to introduce more context-dependence (Rose). As the conference proceeded we ran through a spectrum of considerations in which the expressions in the languages considered were examined less and less as meaningless objects (the formal, or purely syntactic approach, as in the paper by Steel) and required more and more meaningful interpretations. In other words, we became more and more involved with semantic considerations. It is clear, then, that applications of the study of mechanical languages to programming must involve semantic questions; ADD must mean something more than the concatenation of three (not two) characters. The papers beyond Session 1 were therefore discussing the mechanization of semantics, but in only one case did we hear about the formalization (and hence mechanization) of the specification of the semantics of a language (McCarthy).
Research and Advances Feb 1 1964

On context and ambiguity in parsing

This note is by way of commentary on the notions of “bounded context” of Floyd [1] and “structural connections” of Irons [2], as these notions relate to as yet unpublished researches growing out of the development of the author's Algorithmic Theory of Language [3, 4]. In the closing paragraphs of [3], the author made comments concerning further developments of the theory which would include “context dependence” and “resolution of apparent syntactic ambiguities.” The work on parsing reported here was carried out in early September, 1962 (an earlier version in March, 1962), but has not been polished or reduced to final form because, for the purpose of the total theory, parsing should not be considered separately, and the complexities of the proper treatment of the “precedence string” (which relates to semantic structure as distinct from syntactic structure of parsing) have not yet been satisfactorily resolved.
Research and Advances Feb 1 1964

“Structural connections” in formal languages

This paper defines the concept of “structural connection” in a mechanical language in an attempt to classify various formal languages according to the complexity of parsing structures on strings in the languages. Languages discussed vary in complexity from those with essentially no structure at all to languages which are self-defining. The relationship between some existing recognition techniques for several language classes is examined, as well as implications of language structure on the complexity of automatic recognizers.
Research and Advances Feb 1 1964

Bounded context syntactic analysis

Certain phase structure grammars define languages in which the phrasehood and structure of a substring of a sentence may be determined by consideration of only a bounded context of the substring. It is possible to determine, for any specified bound on the number of contextual characters considered, whether a given grammar is such a bounded context grammar. Such grammars are free from syntactic ambiguity. Syntactic analysis of sentences in a bounded context language may be performed by a standard process and requires a number of operations proportional to the length of sentence analyzed. Bounded context grammars form models for most languages used in computer programming, and many methods of syntactic analysis, including analysis by operator precedence, are special cases of bounded context analysis.
Research and Advances Feb 1 1964

A general business-oriented language based on decision expressions

The structure of a digital computer programming language which covers a wide class of business and file processing applications is presented. Such a structure, based on identifying and incorporating into a compiler the aspects common to all processes of such class, permits writing extremely compact programs, even for comparatively complex applications, in terms of tables of control expressions which express only information characteristic of the particular application. Furthermore, local changes of a process (e.g. changes affecting only one of the output files involved) can be effected by local modifications in the program (e.g. modification of only one entry of the tables). This structure also allows for inexpensive preparation of loading-speed compilers which translate the source programs into efficient machine codes. The approach adopted here departs from conventional mechanical language design philosophies. It stresses the structural analysis of the class of processes to be represented in the languages, as opposed to emphasizing formal (i.e., contents-independent) syntactical definitions. It relies exclusively on nonprocedural representation of processes as sets (tables) of relations between data and results (there are no control statements such as GO TO, etc.), instead of using procedure descriptions (which are one-to-one translations of flowcharts). Here an invariant pattern of procedure is identified as characteristic of the class of all batch file processes.

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More