Research and Advances

The problem of selecting a random sample of precisely n records from a tape film containing N records sometimes arises in data processing applications. If a means of obtaining a random sample of n integers r1, r2, … ,rn selected from the N integers 1, 2, … , N is available, the problem is theoretically simple. All that need be done is to then select the r1th, r2th, … , rnth records.

During the past few years a major portion of the work in computer applications has been concentrated in the two closely related fields of automatic programming and symbol manipulation. The results of this effort have been a wealth of new computer languages, a better understanding and definition of the basic principles and problems of symbol manipulation, and a growing body of algorithms and techniques for use in the applications.

The final result of prolonged computations will in general contain some errors. These errors are composed in part of computational round-off errors. This note points out one source of round-off error encountered in the IBM 709-7090 machines. An example is included which demonstrates the potential seriousness of this error and finally a means of coping with it is given. The notation used here is that used in [1].

In using ALGOL, or any other common language for communicating among computers with different input-output media, one or more human beings is normally present in the communication channel. In the otherwise convenient method of communication by published algorithms, at least three humans are directly involved: a typist to prepare the manuscript in reference or publication language, a typesetter, and a keypunch operator to prepare the program for the computer in its hardware language. In spite of checking by authors, proof readers, editors, and verifiers, this process is a noisy one, involving as it does not only copying a synthetic (and therefore unfamiliar) language, but also translation to and from the publication dialect. The number of minor typographical errors which have been detected and reported in published algorithms confirms this observation. Clearly some check of the accuracy with which an algorithm has been transmitted through this noisy channel would be desirable. The solution which we propose is directed particularly to ALGOL 60, but the same problems exist with other common languages, and the principles which we use could be readily adapted to them.

In the past Backus Normal Form (BNF) has been defined only informally; however, a formal recognition definition has been evolved.