# July 1970 - Vol. 13 No. 7

## Features

An interactive command generating facility

A facility to permit conversationally controlled tasks to be executed in a noninteractive environment is proposed. A means by which programs can generate interactive time-sharing commands and receive the corresponding output response is presented. The commands will be invoked as if they had been typed at a console keyboard. It is argued that this facility will help overcome some of the current limitations in man-computer communication.
A set of functions to accomplish the above which could be embedded into any string processing language is suggested, and necessary information pertinent to implementation of the facility on existing time-sharing systems is given.

Conversational access to a 2048-word machine

LAP6 is an on-line system running on a 2048-word LINC which provides full facilities for text editing, automatic filing and file maintenance, and program preparation and assembly. It focuses on the preparation and editing of continuously displayed 23,040-character text strings (manuscripts) which can be positioned anywhere by the user and edited by simply adding and deleting lines as though working directly on an elastic scroll. Other features are available through a uniform command set which itself can be augmented by the user.
The machine, although small, aids program design by providing display scope and premarked randomly addressable LINC tapes as standard items, in an environment similar to that of a sophisticated terminal. The tapes are logically similar to a disk. Priority was given to the design of efficient tape algorithms to minimize the limitations of the small memory. Techniques developed for handling scroll editing, filing, and the layered system structure are outlined.
LAP6 is used by about 2000 people in 11 countries. Its design was strongly influenced by performance criteria established in interviews held with the LINC users themselves during the specification period.

The mobile programming system: STAGE2

STAGE2 is the second level of a bootstrap sequence which is easily implemented on any computer. It is a flexible, powerful macro processor designed specifically as a tool for constructing machine-independent software. In this paper the features provided by STAGE2 are summarized, and the implementation techniques which have made it possible to have STAGE2 running on a new machine with less than one man-week of effort are discussed. The approach has been successful on over 15 machines of widely varying characteristics.

Space/time trade-offs in hash coding with allowable errors

In this paper trade-offs among certain computational factors in hash coding are analyzed. The paradigm problem considered is that of testing a series of messages one-by-one for membership in a given set of messages. Two new hash-coding methods are examined and compared with a particular conventional hash-coding method. The computational factors considered are the size of the hash area (space), the time required to identify a message as a nonmember of the given set (reject time), and an allowable error frequency.
The new methods are intended to reduce the amount of space required to contain the hash-coded information from that associated with conventional methods. The reduction in space is accomplished by exploiting the possibility that a small fraction of errors of commission may be tolerable in some applications, in particular, applications in which a large amount of data is involved and a core resident hash area is consequently not feasible using conventional methods.
In such applications, it is envisaged that overall performance could be improved by using a smaller core resident hash area in conjunction with the new methods and, when necessary, by using some secondary and perhaps time-consuming test to “catch” the small fraction of errors associated with the new methods. An example is discussed which illustrates possible areas of application for the new methods.
Analysis of the paradigm problem demonstrates that allowing a small number of test messages to be falsely identified as members of the given set will permit a much smaller hash area to be used without increasing reject time.

File structures using hashing functions

A general method of file structuring is proposed which uses a hashing function to define tree structure. Two types of such trees are examined, and their relation to trees studied in the past is explained. Results for the probability distributions of path lengths are derived and illustrated.

Algorithm and bound for the greatest common divisor of n integers

A new version of the Euclidean algorithm for finding the greatest common divisor of n integers ai and multipliers xi such that gcd = x1 a1 + ··· + xn an is presented. The number of arithmetic operations and the number of storage locations are linear in n. A theorem of Lamé that gives a bound for the number of iterations of the Euclidean algorithm for two integers is extended to the case of n integers. An algorithm to construct a minimal set of multipliers is presented. A Fortran program for the algorithm appears as Comm. ACM Algorithm 386.

A comment on axiomatic approaches to programming

Reference is made to the paper by C. A. R. Hoare [1] which discusses the fundamentals of an axiomatic approach to computer programming. One advantage for an axiomatic system proposed by Hoare is that an axiomatic description of computer programs would allow the application of deductive inference to formally and conclusively prove that a computer program performs the computation the designer intended. The purpose of this short communication is to discuss the relationship between Hoare's concepts and an approach in a book by Wymore [2].