August 1972 - Vol. 15 No. 8

A design philosophy for developing a sophisticated utility program is illustrated by the actual design and implementation of a text editor. A versatile data structure is employed so that only a small number of programmed subroutines are necessary for all types of data manipulation. Such a data structure is described, and its merits are illustrated by the ease with which powerful extensions can be implemented in terms of a few basic editing functions.

The development of the research project in microprogramming and emulation at State University of New York at Buffalo consisted of three phases: the evaluation of various possible machines to support this research; the decision to purchase one such machine, which appears to be superior to the others considered; and the organization and definition of goals for each group in the project. Each of these phases is reported, with emphasis placed on the early results achieved in this research.

This paper is concerned with certain aspects of contention for main memory resources in a multiprogrammed computer system operating under demand paging. In the model presented, the number of page-frames of main memory allocated to a problem program varies in time. These changes in memory configuration are represented explicitly in the model, CPU requirements and page exception characteristics of program material being described statistically. Expressions for the distribution of the number of page-frames allocated to an executing program, the long run expected fraction of a program's execution time in a given number of page-frames, and the average execution interval of the multi-programmed load are obtained. It is pointed out heuristically and demonstrated numerically that an increase is obtainable in the average execution interval of the multiprogrammed load over that resulting from equal fixed partitioning of main memory.

With reference to the article by H. T. Gladwin [1], (Comm.) it should be noted that the technique described is a limited subset of techniques known for many years, particularly to programmers for machines lacking an integer multiply instruction, CDC 6000 PPU's for example. It is easier to present and implement more generally applicable techniques, such as full decomposition into “runs” of 0's and 1's to yield representation as: ∑Li=0(2m(i) - 2n(i)) which may be further compressed by replacing such terms as -2m+1 + 2m by -2m. In decomposing numbers from the right on a CDC 6000 in particular, special techniques are possible [2]. Finally, Gladwin failed to credit the CDC RUN compilers, in use for over six years on the very machines he discussed, for doing a large number of constant multiplies by shifts and adds (subroutine SHM in overlay RUN1).

In [1] van Wijngaarden presented a rather remarkable technique for rewriting ALGOL 60 programs to eliminate all labels. The purpose of this note is to point out that the rewriting would also eliminate the use of array returning (procedure returning, label returning, etc.) procedures had they been legal constructs of ALGOL 60. Hence, the many languages which allow such things to be returned as procedure values are not such large extensions of ALGOL 60 as one might think [2, 3, 4, 5].

Harada [1] has given a method of generating rosary permutations, and of associating an integer with each such permutation in a one-to-one manner. In this note we show that both these ends can be achieved more easily than by Harada's method.

We assume a directed graph whose nodes are labeled by integers between 1 and n. The arcs of this graph correspond to the flow of control between blocks of a computer program. The initial node of this graph (corresponding to the entry point of the program) is labeled by the integer 1. For optimizing the object code generated by a compiler, the relationship of immediate predominator has been used by Lowry and Medlock [3]. We say that node i predominates node k if every path from node 1 to node k passes through (i.e. both into and out of) node i. Node j is an immediate predominator of node k if node j predominates node k and if every other node i which predominates node k also predominates node j. It can easily be proved that if k ≠ 1 and node k is reachable from node 1t hen node k has exactly one immediate predominator. In case k = 1, or node k is not reachable from node 1, the immediate predominator of node k is undefined, and the value 0 will be given by the procedure PREDOMINATOR.