November 1963 - Vol. 6 No. 11

The need to determine minimum paths through a maze very often arises in such fields as traffic, transportation, communication and network studies. Computer analysis of these maze problems has been hampered in many cases due to the excessive size of the network under consideration. A technique has been developed to handle networks of very large magnitude by serially processing the network repetitively until only minimum paths remain.

An oft-mentioned advantage of ALGOL over FORTRAN is the recursion capability of the former. FORTRAN adherents often belittle this advantage by claiming that all recursive relations can be reduced to recurrence or iterative relations, or that no recursive relations exist which are worth coding as recursive relations. The question of the truth of this must be left unanswered here. It is hoped that the technique described below will draw the poison from the FORTRANers' wounds by allowing them to recurse to their complete satisfaction. There is an hereditary resemblance between this technique and the MAD (Michigan Algorithm Decoder) recursion technique.

An increasing number of computer programs are designed to accept and translate a symbolic, English-like language which facilitates communication between the user and the computer. A common feature of such programs is a pre-determined vocabulary of expressions for specifying the input to the program. This note describes a generalized technique for permitting flexible abbreviation of such expressions in order to further simplify the task of writing source programs.

During the past few years, research into so-called “Syntax Directed Compiler” and “Compiler Compiler” techniques [1, 2, 3, 4, 5, 6] has given hope that constructing computer programs for translating formal languages may not be as formidable a task as it once was. However, the glow of the researchers' glee has obscured to a certain extent some very perplexing problems in constructing practical translators for common programming languages. The automatic parsing algorithms indeed simplify compiler construction but contribute little to the production of “optimized” machine code, for example. An equally perplexing problem for many of these parsing algorithms has been what to do about syntactically incorrect object strings. It is common knowledge that most of the ALGOL or FORTRAN “programs” which a compiler sees are syntactically incorrect. All of the parsing algorithms detect the existence of such errors. Many have considerable difficulty pinpointing the location of the error, printing out diagnostic information, and recovering enough to move on to other correct parts of the object string. It is the author's opinion that those algorithms which do the best job of error recovery are those which are restricted to simpler forms of formal languages.

MADCAP is a programming language admitting subscripts, superscripts and certain forms of displayed formulas. The basic implementation of this language was described in a previous paper [MADCAP: A scientific compiler for a displayed formula textbook language, Comm. ACM 4 (Jan. 61), 31-36]. This paper discusses recent improvements in the language in three areas: complex display, logical control, and subprogramming. In the area of complex display, the most prominent improvements are a notation for integration and for the binomial coefficients. In the area of logical control the chief new feature is a notation for variably nested looping. The discussion of subprogramming is focused on MADCAP's notation for and use of “procedures.”

A major component of a bit-time computer simulation program is the Boolean compiler. The compiler accepts the Boolean functions representing the simulated computer's digital circuits, and generates corresponding sets of machine instructions which are subsequently executed on the “host” computer. Techniques are discussed for increasing the sophistication of the Boolean compiler so as to optimize bit-time computer simulation. The techniques are applicable to any general-purpose computer.

Detailed statistics are given on the length of maximal sorted strings which result from the first (internal sort) phase of a merge sort onto tapes. It is shown that the strings produced by an alternating method (i.e. one which produces ascending and descending strings alternately) tend to be only three-fourths as long as those in a method which produces only ascending strings, contrary to statements which have appeared previously in the literature. A slight modification of the read-backward polyphase merge algorithm is therefore suggested.

A series of clinical laboratory codes have been developed to accept and store urinalysis, blood chemistry, and hematology test results for automatic data processing. The codes, although constructed as part of a computerized hospital simulation, have been able to handle the results of every laboratory test that they have encountered. The unique feature of these codes is that they can accept conventionally recorded qualitative as well as quantitative test results. Consequently, clinical test results need not be arbitrarily stratified, standardized, or altered in any way to be coded. This paper describes how the codes were developed and presents a listing of the urinalysis codes. Five criteria used in developing the codes are outlined and the problem of multiple-synonymous terminology is discussed. A solution to the problem is described. Flexible, computer-produced, composite laboratory reports are also discussed, along with reproduction of such a report. The paper concludes that even though many problems remain unsolved, the next ten years could witness the emergence of a practical automated information system in the laboratory.

In the course of our work on the physical chemistry of histamine and related compounds, we have done extensive work involving potentiometric titration of systems of chelates of these ligands with various metallic ions, negative ions, and small molecules. The resulting data is used to calculate the stability constants in solution (1, 2, 3, 4). The mathematical calculations for a single titration require two to four hours when done on a desk calculator, even when the operator is experienced. This is a serious disadvantage of the technique. The more accurate methods of successive approximations and of simultaneous equations [2] are so time consuming that their routine use is impractical without the aid of a high speed computer.