October 1969 - Vol. 12 No. 10
Features
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.
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.
A digital computer is considered, whose memory words are composed of N r-state devices plus two sign bits (two state devices). The choice of base &bgr; for the internal representation of floating-point numbers on such a computer is discussed. It is shown that in a certain sense &bgr; = r is best.
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.
The IITRAN programming language
The IITRAN language, developed to be used by students, and its important features are described. IITRAN is a procedure-oriented language with a one-level block structure and a variety of data types. Several novel and powerful features are included. A discussion of design principles to be followed in a student language is given.
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.
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].
In this note we point out how rational approximations which are best with respect to maximum logarithmic error can be computed by existing algorithms. Let y be a quantity that we wish to approximate and y be an approximation, then the logarithmic error is defined to be log (y/y). In a recent paper [3] it is shown that minimax logarithmic approximations are optimal for square root calculations, making the minimax logarithmic problem of practical interest. Suppose we wish to approximate a positive continuous function ƒ by a positive rational function R, then the logarithmic error at a point x is log (ƒ(x)) - log (R(x)). Our approximation problem is thus equivalent to ordinary approximation of a continuous function g = log (ƒ) by log (R). This is contained in the more general theory of approximation by ϕ(R), ϕ monotonic which appears in [1]. Computational procedures (based on the Remez algorithm) for the general problem are given in [2, 5]. These are easily adapted to the special case of logarithmic approximation and can readily be coded by modification of a standard rational Remez algorithm.
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.
Retrieval times for a packed direct access inverted file
This note extends the results obtained by Thomas C. Lowe [1] for the case where the list file is stored in packed form. The notation and terminology used were established by Lowe. In addition, we define F(j) = ∑j-1i=1 ƒ(i) and write [x] for the greatest integer not exceeding x.
