November 1972 - Vol. 15 No. 11

The constructs of a simple programming language are introduced and described informally in terms of values and side-effects. A translator is defined which translates the language into flowcharts for a simple machine. The action of the machine in executing a flowchart is defined. A proof is constructed that the effect of translating and executing any program can be expressed solely in terms of the value and side-effect of the program. During the course of constructing the proof, formal definitions of the concepts of value and side-effect are derived in order to make the proof rigorous. Correctness of the implementation involves checking that the definitions derived in the step above are an acceptable formalization of the informal description given in the first step.

Two new algorithms for deriving optimal and near-optimal flowcharts from limited entry decision tables are presented. Both take into account rule frequencies and the time needed to test conditions. One of the algorithms, called the optimum-finding algorithm, leads to a flowchart which truly minimizes execution time for a decision table in which simple rules are already contracted to complex rules. The other one, called the optimum-approaching algorithm, requires many fewer calculations but does not necessarily produce the optimum flowchart. The algorithms are first derived for treating decision tables not containing an ELSE-rule, but the optimum-approaching algorithm is shown to be equally valid for tables including such a rule. Both algorithms are compared with existing ones and are applied to a somewhat large decision table derived from a real case. From this comparison two conclusions are drawn. (1) The optimum-approaching algorithm will usually lead to better results than comparable existing ones and will not require more, but usually less, computation time. (2) In general, the greater computation effort needed for applying the optimum-finding algorithm will not be justified by the small reduction in execution time obtained.

In list processing there is typically a growing demand for space during program execution. This paper examines the practical implications of this growth within a virtual memory computer system, proposes two new garbage collection techniques for virtual memory systems, and compares them with traditional methods by discussion and by simulation.

A method for generating values of continuous symmetric random variables that is relatively fast, requires essentially no computer memory, and is easy to use is developed. The method, which uses a uniform zero-one random number source, is based on the inverse function of the lambda distribution of Tukey. Since it approximates many of the continuous theoretical distributions and empirical distributions frequently used in simulations, the method should be useful to simulation practitioners.

In an earlier paper by Lum, Yuen, and Dodd [1] experimental results comparing six commonly used key-to-address transformation techniques were presented. One transformation in that study referred to as “Lin's method” is an elaborate technique based on radix transformation. Andrew Lin has since pointed out to the authors that his method of transformation [2] consists of not just a radix transformation algorithm but also the specific ways the values of p and q are chosen as well as hardware implementation to carry out the steps of this transformation in an efficient manner. Since our study was intended for general radix transformations rather than Lin's specific implementation, we think it is more appropriate to change the label of that transformation in [1] from “Lin's method” to “generalized radix transformation method” and we use this term here.

This note concerns the recent paper by Hu [2] dealing with doubly-chained trees of the type introduced by Sussenguth [9]. In the second part of the paper, Hu deals with the problem of constructing an optimum weighted doubly-chained tree, under the standard assumption that no key is allowed to prefix another, as found, for example, in Patt [6]. He states that for the weights and elements of Figure 1, the optimum doubly-chained tree with all nodes reachable in less than five steps is the one shown in Figure 2. This tree is obtained from the optimal binary tree constructed in Hu and Tan [3], using the technique found in Knuth [5]. But the doubly-chained tree constructed by this method comes from an artificially restricted class of doubly-chained trees, and is thus not optimal in the sense usually defined in the literature [6-9] and described below. This fact is recognized by Hu [1], but was not explicitly stated in the paper in question.

E.W. Dijkstra [1] presented an algorithm whereby N mainly independent computers, with a common data store as their sole means of communication, could contend for exclusive control of any given resource (storage, I/O, etc.). To use the resource, a computer had to gain access to the “critical section” of the algorithm, within which one and only one computer at a time could be executing.

J.A. Moorer's “Music and Computer Composition” [1] was a distressing communication. While I realize that musical expertise is probably beyond the realm of the editorial staff, I must object to both the naiveté and faulty reasoning on the musical side of this article. In a nutshell, Moorer presents us with many paragraphs of philosophical meanderings to back up a few results which are, by his own admission, inadequate. From this he concludes, “It is also hoped that this experiment may help dispel doubts that musical composition is ‘sacred’ and unreachable by mechanical methods.” From any serious musical point of view, such a conclusion is almost vacuous.