May 1974 - Vol. 17 No. 5
Features
Reduction of compilation costs through language contraction
Programming languages tailored to particular groups of users can often be constructed by removing unwanted features from a general purpose language. This paper describes the use of simulation techniques to predict the savings in compilation cost achievable by such an approach. The results suggest a function which describes the effect of changes in the power of a language on the compilation cost of an algorithm expressed in that language: when features not actually used by the algorithm are removed from the language, the cost of compiling the algorithm decreases moderately, but when features that are needed are removed, the compilation cost increases sharply.
The treatment of data types in EL1
In constructing a general purpose programming language, a key issue is providing a sufficient set of data types and associated operations in a manner that permits both natural problem-oriented notation and efficient implementation. The EL1 language contains a number of features specifically designed to simultaneously satisfy both requirements. The resulting treatment of data types includes provision for programmer-defined data types and generaic routines, programmer control over type conversion, and very flexible data type behavior, in a context that allows efficient compiled code and compact data representation.
Order-n correction for regular languages
A method is presented for calculating a string B, belonging to a given regular language L, which is “nearest” (in number of edit operations) to a given input string &agr;. B is viewed as a reasonable “correction” for the possibly erroneous string &agr;, where &agr; was originally intended to be a string of L. The calculation of B by the method presented requires time proportional to |&agr;|, the number of characters in &agr;. The method should find applications in information retrieval, artificial intelligence, and spelling correction systems.
On the distributions of significant digits and roundoff errors
Generalized logarithmic law is derived for the distribution of the first t significant digits of a random digital integer. This result is then used to determine the distribution of the roundoff errors in floating-point operations, which is a mixture of uniform and reciprocal distributions.
A design for a number theory package with an optimized trial division routine
A number theory package is described which uses doubly linked list structures for storing multiprecise integers. The package has been coded in IBM's Basic Assembly Language and makes heavy use of the macro language and conditional assembly. An optimally coded trial division routine is also described which can be used to determine the unique factorization of large integers.
More on algorithms that reveal properties of floating point arithmetic units
In the interests of producing portable mathematical software, it is highly desirable for a program to be able directly to obtain fundamental properties of the environment in which it is to run. The installer would then not be obliged to change appropriate magic constants in the source code, and the user would not have to provide information he may very well not understand. Until the standard definitions of programming languages are changed to require builtin functions that provide this information [1, 3], we will have to resort to writing routines that discover it.
A model for masking rotational latency by dynamic disk allocation
This paper presents the background and algorithms for masking the rotational latency of a disk or drum. It discusses the anticipatory input and output of blocks of data to buffer and primary memories for a mono-programmed computer system. A basic permutation algorithm and several variations are given. Because of the anticipatory nature of the I/O scheduling, these algorithms are restricted to classes of programs with predictable behavior. While the methods are not restricted to numerical computations, matrix and partial differential equation methods are typical examples of their use. It is shown that latency may be masked using a small amount of buffer memory. The methods discussed are independent of the overall size of the data base being considered.
