Search
Join ACM

Computing Applications

Advertisement

Research and Advances

A practical method for constructing LR (k) processors

A practical method for constructing LR(k) processors is developed. These processors are capable of recognizing and parsing an input during a single no-backup scan in a number of steps equal to the length of the input plus the number of steps in its derivation. The technique presented here is based on the original method described by Knuth, but decreases both the effort required to construct the processor and the size of the processor produced. This procedure involves partitioning the given grammar into a number of smaller parts. If an LR(k) processor can be constructed for each part (using Knuth's algorithm) and if certain conditions relating these individual processors are satisfied, then an LR(k) processor for the entire grammar can be constructed for them. Using this procedure, an LR(1) parser for ALGOL has been obtained.
Research and Advances

APAREL—A parse-request language

APAREL is described: this language is an extension to an algorithmic language (PL/I) that provides the pattern-matching capabilities normally found only in special purpose languages such as SNOBOL4 and TMG. This capability is provided through parse-requests stated in a BNF-like format. These parse-requests form their own programming language with special sequencing rules. Upon successfully completing a parse-request, an associated piece of PL/I code is executed. This code has available for use, as normal PL/I strings, the various pieces (at all levels) of the parse. It also has available, as normal PL/I variables, the information concerning which of the various alternatives were successful. Convenient facilities for multiple input-output streams, the initiation of sequences of parse-requests as a subroutine, and parse-time semantic checks are also included. APAREL has proven convenient in building a powerful SYNTAX and FUNCTION macro system, an algebraic language preprocessor debugging system, an on-line command parser, a translator for Dataless Programming, and as a general string manipulator.
and
Research and Advances

Synchronization in a parallel-accessed data base

The following problem is considered: Given a data base which can be manipulated simultaneously by more than one process, what are the rules for synchronization which will maximize the amount of parallel activity allowed. It is assumed that the data base can be represented as a graph. An example of such a data base is a hierarchy of directories for an on-line file system. Methods for synchronization of processes are examined; their validity is discussed and their performance compared.
and
Research and Advances

An interactive graphical display monitor in a batch-processing environment with remote entry

A graphic monitor program is described. It was developed at Carnegie-Mellon University for the CDC G21 computer, which is a general purpose, batch-processing system with remote entry. The existing G21 system and the graphics hardware are described. The graphic monitor is a resident auxiliary monitor which provides comprehensive managerial capability over the graphical system in response to commands from the human user. It also will respond to commands from a user program through a similar interface, where routine calls take the place of manual actions. Thus the human and program can interact on a symmetrical and equal basis through the medium of the graphic monitor. The choices made in designing the graphic monitor, given the constraints of the existing hardware and computer system, are discussed. The structure of the monitor program and the human and program interfaces are described. There is also a transient swapping version with a small resident part, and provision for swapped used submonitors.
, , and
Research and Advances

An axiomatic basis for computer programming

In this paper an attempt is made to explore the logical foundations of computer programming by use of techniques which were first applied in the study of geometry and have later been extended to other branches of mathematics. This involves the elucidation of sets of axioms and rules of inference which can be used in proofs of the properties of computer programs. Examples are given of such axioms and rules, and a formal proof of a simple theorem is displayed. Finally, it is argued that important advantage, both theoretical and practical, may follow from a pursuance of these topics.
Research and Advances

A modular computer sharing systems

An alternative approach to the design and organization of a general purpose interactive multiterminal computing system is presented. The system organization described is a conceptually simple arrangement of a bank of interchangeable computers, each of which is a memory/proputor pair, that are assigned to process terminal jobs as they arrive. One of the computers serves as the master or control computer and supervises the collection and distribution of messages from and to the remote terminals. In the simplest form there is a disk drive for each connected terminal. A crosspoint switching network allows any such disk drive to be connected to any computer in the bank, under control of the control computer. Thus, while each active terminal user “occupies” a dedicated disk drive, he may share the computer with many other terminal users in a simple manner. The ratio of users to computers is dependent on both the size and power of the machines used and the computation requirements of the particular mix of users. This system organization is inherently a simpler and therefore more reliable approach to time-sharing computers and has the potential of a highly available system at relatively low cost. Economic configurations are possible for a range of systems sizes that span at least one order of magnitude. Finally, problem programs developed by remote terminal users can be run on a dedicated batch system if compatible computers are used.
, , , and
Research and Advances

A new method for determining linear precedence functions for precedence grammars

The precedence relations of a precedence grammar can be precisely described by a two-dimensional precedence matrix. Often the information in the matrix can be represented more concisely by a pair of vectors, called linear precedence functions. A new algorithm is presented for obtaining the linear precedence functions when given the precedence matrix; this algorithm is shown to possess several computational adavantages.
Research and Advances

An ambiguity in the description of ALGOL 60

When Algorithm 355 [Comm. ACM 12 (Oct. 1969), 562] was originally submitted to the Algorithms Department it contained a construct which pointed up an ambiguity in the description of ALGOL 60 [Revised Report on the Algorithmic Language ALGOL 60, Comm. ACM 6 (Jan. 1963), 1-17]. This ambiguity was not mentioned by Donald Knuth [The Remaining Trouble Spots in ALGOL 60, Comm. ACM 10 (Oct. 1967), 611-618].
Research and Advances

A comment on optimal tree structures

In Y.N. Patt's paper “Variable Length Tree Structures Having Minimum Average Search Time” [Comm. ACM 12 (Feb. 1969)], the tree structures obtained are not actually optimal with respect to the two-dimensional chaining devised by Sussenguth in his 1963 paper. This note points out that the result can be described as “optimal” only under the constraint—which Patt implicity assumes—that no key be allowed to prefix another.
Research and Advances

Loader standardization for overlay programs

The overlay capability is described for four of the third generation computer systems: CDC-6000, GE-635, IBM-360, and UNIVAC-1108. A critique of the first three sytems is based on actual experience with a large overlaid trajectory simulation program; a short history and description of this program is presented. A standardization of minimum capabilities for loaders is recommended so that programs which must operate under more than one computer system may be easily converted and maintained. A proposal that overlay software incorporates a memory occupation specification concept instead of the conventional tree structure is delineated. This concept provides more efficient and cost-effective utilization of the memory as well as increasd flexibility in program structure.
Research and Advances

A base for a mobile programming system

An algorithm for a macro processor which has been used as the base of an implementation, by bootstrapping, of processors for programming languages is described. This algorithm can be easily implemented on contemporary computing machines. Experience with programming languages whose implementation is based on this algorithm indicates that such a language can be transferred to a new machine in less than one man-week without using the old machine.
and
Research and Advances

On multiprogramming, machine coding, and computer organization

The author feels that the interrupt feature which is available in most modern computers is a potent source of programming pitfalls and errors, and that it therefore may heavily contribute to the unreliability of programs making use of it. A programming scheme is presented which avoids the concept of the interrupt and permits the specification of concurrent (or pseudoconcurrent) activities in a supposedly more perspicuous manner. It is intended to serve as a basis for the construction of operating systems, which are prime examples of programs with concurrent activities. The scheme includes a set of basic instructions for the generation, termination, and synchronization of parallel processes. A set of routines representing these instructions and thereby simulating a hypothetical machine organization has been implemented and tested on the IBM System/360. Two programs using these instructions, written in PL360, are presented.
Research and Advances

Compact list representation: definition, garbage collection, and system implementation

Compact lists are stored sequentially in memory, rather than chained with pointers. Since this is not always convenient, the Swym system permits a list to be chained, compact, or any combination of the two. A description is given of that list representation and the operators implemented (most are similar to those of LISP 1.5). The system garbage collector attempts to make all lists compact; it relocates and rearranges all of list storage using temporary storage. This unique list-compacting garbage collection algorithm is presented in detail. Several classes of the macros used to implement the system are described. Finally, consideration is given to those design factors essential to the success of a plex processing system implementation.
Research and Advances

The teachable language comprehender: a simulation program and theory of language

The Teachable Language Comprehender (TLC) is a program designed to be capable of being taught to “comprehend” English text. When text which the program has not seen before is input to it, it comprehends that text by correctly relating each (explicit or implicit) assertion of the new text to a large memory. This memory is a “semantic network” representing factual assertions about the world. The program also creates copies of the parts of its memory which have been found to relate to the new text, adapting and combining these copies to represent the meaning of the new text. By this means, the meaning of all text the program successfully comprehends is encoded into the same format as that of the memory. In this form it can be added into the memory. Both factual assertions for the memory and the capabilities for correctly relating text to the memory's prior content are to be taught to the program as they are needed. TLC presently contains a relatively small number of examples of such assertions and capabilities, but within the system, notations for expressing either of these are provided. Thus the program now corresponds to a general process for comprehending language, and it provides a methodology for adding the additional information this process requires to actually comprehend text of any particular kind. The memory structure and comprehension process of TLC allow new factual assertions and capabilities for relating text to such stored assertions to generalize automatically. That is, once such an assertion or capability is put into the system, it becomes available to help comprehend a great many other sentences in the future. Thus the addition of a single factual assertion or linguistic capability will often provide a large increment in TLC's effective knowledge of the world and in its overall ability to comprehend text. The program's strategy is presented as a general theory of
Research and Advances

The MAD definition facility

One of the first definition facilities for higher level languages is described. Users of the language can define new operators and/or data types into the MAD language, so that their use appears as if they were predefined. Information is given on how one writes definitions, as well as on much of the motivation behind the form in which definitions are written. Some conclusions are drawn about future definitional facilities.
, , and
Research and Advances

A program for the syntactic analysis of English sentences

A program is described which produces syntactic analyses of English sentences with respect to a transformational grammar. The main features of the analyzer are that it uses only a limited dictionary of English words and that it pursues all analysis paths simultaneously while processing the sentence from left to right. The form of representation used for the dictionary and the grammar is indicated and an outline account is given of the analysis procedure. Techniques for keeping the size of the analysis record within reasonable limits and for avoiding the need for dynamic application of certain transformational rules are described. A number of examples of output produced by the program are given. The output includes timing information.
, , and
Research and Advances

Computing capabilities at Argentine and Chilean universities

The author reports on a trip to universities in Argentina and Chile during November 1968, describing university conditions and computing activities. As elsewhere, these universities are experiencing student discontent with the status quo and the solutions they are attempting contrast: Argentina is excluding students from participating in university government; Chile is allowing such participation. University computing service and academic activities are limited. The number of computers is small and so is the capacity, none larger than an IBM 360/40; with some exception, computing science academic programs are rare. This situation is by no means attributable to those responsible for computing developments, who strive for excellence; rather the “system” is hard to overcome. Universities, especially those with strong European traditions, adapt slowly to new academic resources and disciplines; superimposed are the severe technological and economic constraints of the developing nation. Consequently, in the absence of conscious government emphasis on strengthening computing capabilities, future progress may be retarded.
Research and Advances

Automatic contour map

Some methods for contour mapping by means of a digital plotter are dicussed, and a new method is presented that is simple enough to be implemented by programs with a rather small number of instructions (about 120 FORTRAN IV instructions are required). Comparisons with some methods proposed by other authors are also performed. A FORTRAN IV program implementing the proposed method is availabel at the Istituto di Elettrotecnica ed Elettronica, Politecnico di Milano.
and

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