December 1982 - Vol. 25 No. 12
Features
Software engineering for the Cobol environment
In a attempt to improve the productivity of their 70 development staff, Skandinaviska Enskilda Banken has built an integrated set of manual and automatic tools for the implementation of Cobol programs. It was possible to use a number of modern programming techniques, including software engineering methods, in a Cobol environment. The project required 31 person-months; the aims, current status, and initial results are reported.
On the emulation of flowcharts by decision tables
Any flowchart can be emulated by a decision table, whose complexity depends on that of the flowchart. It may be necessary, however, to introduce a new control variable with associated tests and sets or to permit changes in execution sequences provided action-test independence holds. Two measures of decision table complexity are discussed and interrelated. Finally, conditions and procedures for reducing complexity are presented.
An effective way to represent quadtrees
A quadtree may be represented without pointers by encoding each black node with a quaternary integer whose digits reflect successive quadrant subdivisions. We refer to the sorted array of black nodes as the “linear quadtree” and show that it introduces a saving of at least 66 percent of the computer storage required by regular quadtrees. Some algorithms using linear quadtrees are presented, namely, (i) encoding a pixel from a 2n × 2>n array (or screen) into its quaternary code; (ii) finding adjacent nodes; (iii) determining the color of a node; (iv) superposing two images. It is shown that algorithms (i)-(iii) can be executed in logarithmic time, while superposition can be carried out in linear time with respect to the total number of black nodes. The paper also shows that the dynamic capability of a quadtree can be effectively simulated.
Implementations for coalesced hashing
The coalesced hashing method is one of the faster searching methods known today. This paper is a practical study of coalesced hashing for use by those who intend to implement or further study the algorithm. Techniques are developed for tuning an important parameter that relates the sizes of the address region and the cellar in order to optimize the average running times of different implementations. A value for the parameter is reported that works well in most cases. Detailed graphs explain how the parameter can be tuned further to meet specific needs. The resulting tuned algorithm outperforms several well-known methods including standard coalesced hashing, separate (or direct) chaining, linear probing, and double hashing. A variety of related methods are also analyzed including deletion algorithms, a new and improved insertion strategy called varied-insertion, and applications to external searching on secondary storage devices.
A critique of the foundations of Hoare style programming logics
Much recent discussion in computing journals has been devoted to arguments about the feasibility and usefulness of formal verification methods. Too little attention has been given to precise criticism of specific proposed systems for reasoning about programs. Whether such systems are to be used for formal verification, by hand or automatically, or as a rigorous foundation for informal reasoning, it is essential that they be logically sound. Several popular rules in the Hoare language are, in fact, not sound. These rules have been accepted because they have not been subjected to sufficiently strong standards of correctness. This paper attempts to clarify the different technical definitions of correctness of a logic, to show that only the strongest of these definitions is acceptable for Hoare logic, and to correct some of the unsound rules that have appeared in the literature. The corrected rules are given merely to show that it is possible to do so. Convenient and elegant rules for reasoning about certain programming constructs will probably require a more flexible notation than Hoare's.
A hash code method for detecting and correcting spelling errors
The most common spelling errors are one extra letter, one missing letter, one wrong letter, or the transposition of two letters. Deletion, exchange, and rotation operators are defined which detect and “mend” such spelling errors and thus permit retrieval despite the errors. These three operators essentially delete a letter of a word, exchange two adjacent letters, and rotate a word cyclically. Moreover, the operators can be used in conjunction with hashing, thus permitting very fast retrieval. Results of experiments run on large databases in Hebrew and in English are briefly indicated.
A comment on English neologisms and programming language keywords
The choice of keywords in the design of programming languages is compared to the formation of neologisms, or new words, in natural languages. Examination of keywords in high-level programming languages shows that they are formed using mechanisms analogous to those observed in English. The use of mirror words as closing keywords is a conspicuous exceptions.
This is a comment on “File Archival Techniques Using Data Compression” by Michael Pechura [Communications, Sept. 1982, p. 605]. We approached the data compression problem with the aim of maximizing the saving in archival storage over all files for which archival storage was necessary. We also wanted a routine which was reasonably economic in use of system resource.
