Software Engineering and Programming Languages
Advertisement
Some realities of data administration
Little information exists on the practice of data administration, i.e., the management of data as an enterprise resource. A survey of data administrators at predominantly large enterprises was conducted to determine the extent of the existence of data administration and to assess its effectiveness as implemented. New insight into the realities of data administration, including its real-world objectives and perceived effectiveness, is presented.
Spelling correction in user interfaces
The feasibility of providing a spelling corrector as a part of interactive user interfaces is demonstrated. The issues involved in using spelling correction in a user interface are examined, and a simple correction algorithm is described. The results of an experiment in which the corrector is incorporated into a heavily used interactive program are described. More than one quarter of the errors made by users during the experiment were corrected using the simple mechanisms presented here. From this we have concluded that there are considerable benefits and few obstacles to providing a spelling corrector in almost any interactive user interface.
Managing application program maintenance expenditures
Program maintenance represents a major portion of the total expenditures on application programs. Despite the attention this subject has received in the MIS literature, new guidelines to action in this area remain of great interest to practitioners. A large number of variables thought to be determinants of application program maintenance expenditure have been studied through the inspection of application portfolios and personal interviews with top computer executives and systems development personnel. Based on the results, recommendations are made on how to reduce application program maintenance expenditures.
Estimating file access time of floppy disks
Small computers often use floppy disks for storage. Since such disks are significantly slower than hard disks, the response time of a given application program is due predominantly to the time required to access data in files. Access time is dependent on three factors: hardware (disk drive and interface), the operating system in use, and the patterns of file access of application programs. A simple-to-use method of predicting access times with good accuracy is presented. The method makes use of simple calibration experiments that provide information related to the hardware and operating system characteristics of the system in use. This is combined with patterns of file access information for a given application program to predict access time for that program. Actual examples for several small computer systems are presented.
A quadtree medial axis transform
As printed
Quadtree skeletons are exact representations of the image and
are used because they are observed to yield space efficiently and a
decreased sensitivity to shifts in contrast with the quadtree. The
QMAT can be used as the underlying representation when solving most
problems that can be solved by using a quadtree. An algorithm is
presented for the computation of the QMAT of a given quadtree by
only examining each BLACK node's adjacent and abutting
neighbors.
Corrected Abstract (published as corrigendum in CACM 27, 2
(February 1984) p. 151)
The skeletal and medial axis transform concepts used in
traditional image processing representations are adapted to the
quadtree representation. The result is the definition of of a new
data structure termed the Quadtree Medial Axis Transform (QMAT). A
QMAT results in a partition of the image into a set of nondisjoint
squares having sides whose lengths are sums of powers of 2 rather
than, as is the case with quadtrees, a set of disjoint squares
having sides of lengths which are powers of 2. The motivation is
not to study skeletons for the usual purpose of obtainings
approximations of the image. Instead, quadtree skeletons are exact
representations of the image and are used because they are observed
to yield space efficiency and a decreased sensitvity to shifts in
contrast with the quadtree. The QMAT can be used as the underlying
representation when solving most problems that can be solved by
using a quadtree. An algorithm is presented for the computation of
the QMAT of a given quadtree by only examining each BLACK node's
adjacent and abutting neighbors. Analysis of the algorithm reveals
an average execution time proportional to the complexity of the
image, i.e., the number of BLACK blocks.
A practical tool kit for making portable compilers
The Amsterdam Compiler Kit is an integrated collection of programs designed to simplify the task of producing portable (cross) compilers and interpreters. For each language to be compiled, a program (called a front end) must be written to translate the source program into a common intermediate code. This intermediate code can be optimized and then either directly interpreted or translated to the assembly language of the desired target machine. The paper describes the various pieces of the tool kit in some detail, as well as discussing the overall strategy.
A simple database language for personal computers
A simple database language for personal computers has been implemented by selecting a subset of the ANS MUMPS language and enhancing it so as to meet the requirements of microcomputer end-users who are unfamiliar with computers. This database language is named Micro MUMPS. Its database is based on a modified prefix B-tree having parameters for adjusting its data organization according to the requirements of space and time efficiency. Experience with Micro MUMPS has demonstrated a remarkable reduction in programming time.
A diagnosis of beginning programmers’ misconceptions of BASIC programming statements
In the process of learning a computer language, beginning programmers may develop mental models for the language. A mental model refers to the user's conception of the “invisible” information processing that occurs inside the computer between input and output. In this study, 30 undergraduate students learned BASIC through a self-paced, mastery manual and simultaneously had hands-on access to an Apple II computer. After instruction, the students were tested on their mental models for the execution of each of nine BASIC statements. The results show that beginning programmers—although able to perform adequately on mastery tests in program generation—possessed a wide range of misconceptions concerning the statements they had learned. This paper catalogs beginning programmers' conceptions of “what goes on inside the computer” for each of nine BASIC statements.
The fifth generation project — a trip report
As part of Japan's effort to become a leader in the computer industry, the Institute for New Generation Computer Technology has launched a revolutionary ten-year plan for the development of large computer systems which will be applicable to knowledge information processing systems. These Fifth Generation computers will be built around the concepts of logic programming. In order to refute the accusation that Japan exploits knowledge from abroad without contributing any of its own, this project will stimulate original research and will make its results available to the international research community.
An empirical study of insertion and deletion in binary search trees
This paper describes an experiment on the effect of insertions and deletions on the path length of unbalanced binary search trees. Repeatedly inserting and deleting nodes in a random binary tree yields a tree that is no longer random. The expected internal path length differs when different deletion algorithms are used. Previous empirical studies indicated that expected internal path length tends to decrease after repeated insertions and asymmetric deletions. This study shows that performing a larger number of insertions and asymmetric deletions actually increases the expected internal path length, and that for sufficiently large trees, the expected internal path length becomes worse than that of a random tree. With a symmetric deletion algorithm, however, the experiments indicate that performing a large number of insertions and deletions decreases the expected internal path length, and that the expected internal path length remains better than that of a random tree.
A generalized control structure and its formal definition
A new programming language control structure as well as an improved approach to a formal definition of programming languages are presented. The control structure can replace both iteration and conditional structures. Because it is a semantic generalization of those structures, a single statement using the new control structure can implement the functions of loops, conditionals, and also programs that would require several conventional constructs. As a consequence of this increased capability, it is possible to write algorithms that are simpler, more efficient, and more clearly correct than those that can be written with earlier structured-programming control structures. In order to provide a precise definition of the new constructs, a new version of relational semantics, called LD-relations is presented. An algebra of these relations is developed and used to define the meaning of the new constructs. A short discussion of program development and the history of control structures is included.
The economics of designing generalized software
The choice of the attributes to be incorporated in a generalized software package is a complex design task, much like the choice of the characteristics of the basic model and the options to be offered when a new automobile is being designed. Some empirical evidence available suggests that the choices made by generalized software designers are not always well founded; for example, some functions included in the software are hardly, if ever, used, while functions that would be used extensively are not available. To assist the designer, we formulate a market model showing the interactions between the producers (designers) of generalized software and the consumers (users) of generalized software. The model provides insight into those factors that affect the demand for a package and the variables to be considered in a profit-maximizing decision.
Audit considerations in distributed processing systems
Applications of distributed processing networks are proliferating rapidly. It is expected that by the year 2000, distributed networks will be one of the most significant developments to evolve from the computer revolution.
Distributed networks are unique in that they bring together concepts of communication, engineering, and computing. From an audit standpoint, the complexities involved in control design and testing are challenging. The auditor needs to be knowledgeable concerning these complexities in order to apply the proper audit tools, particularly since some of these tools are in need of improvement or development. This paper provides a summary of important areas of audit concern in distributed processing systems.
A second look at bloom filters
This note deals with a paper by Gremillion demonstrating the simulation approach to the design of a Bloom filter. It is shown that an analytical approach can yield insights into competing filter design and give expected values for the goodness-of-hash transformations not available with simulation. On the other hand, simulation gives insight into what can be expected with available hash transformation not available from an analytic approach.
Precision averaging for real-time analysis
An analysis of the computation of the arithmetic mean using only single-precision fixed-point arithmetic is presented. This is done to ease the timing constraints common to many on-line applications. Others have introduced several averaging algorithms in floating-point arithmetic for use in inferential statistics. In this paper, these algorithms are evaluated with respect to their feasibility as fixed-point methods in the context of real-time analysis. Modifications of these algorithms are presented, and previously unpublished ones are introduced in the interest of avoiding overflow (necessary) and minimizing truncation errors (highly desirable). All algorithms presented are tested for speed and accuracy on several sets of data, including their own “worst case.” The applicability of each algorithm is discussed with respect to some of the basic functions that real-time programs must perform.
Natural command names and initial learning: a study of text-editing terms
In the first of two studies of “naturalness” in command names, computer-naive typists composed instructions to “someone else” for correcting a sample text. There was great variety in their task-descriptive lexicon and a lack of correspondence between both their vocabulary and their underlying conceptions of the editing operations and those of some computerized text editors. In the second study, computer-naive typists spent two hours learning minimal text-editing systems that varied in several ways. Lexical naturalness (frequency of use in Study 1) made little difference in their performance. By contrast, having different, rather than the same names for operations requiring different syntax greatly reduced difficulty. It is concluded that the design of user-compatible commands involves deeper issues than are captured by the slogan “naturalness.” However, there are limitations to our observations. Only initial learning of a small set of commands was at issue and generalizations to other situations will require further testing.
A hierarchical data structure for multidimensional digital images
A tree data structure for representing multidimensional digital binary images is described. The method is based on recursive subdivision of the d-dimensional space into 2d hyperoctants. An algorithm for constructing the tree of a d-dimensional binary image from the trees of its (d - 1 )-dimensional cross sections is given. The computational advantages of the data structure and the algorithm are demonstrated both theoretically and in application to a three-dimensional reconstruction of a human brain.
Flowcharts versus program design languages: an experimental comparison
An experiment was performed to assess the relative merits of program design languages (PDLs) and flowcharts as techniques for the development and documentation of detailed designs for computer programs. The use of a PDL by a software designer, for the development and description of a detailed program design, produced better results than did the use of flowcharts. Specifically, the designs appeared to be of significantly better quality, involving more algorithmic or procedural detail, than those produced using flowcharts. In addition, flowchart designs exhibited considerably more abbreviation and other space-saving practices than did PDL designs, with a possible adverse effect on their readability. When equivalent, highly readable designs were presented to subjects in both PDL and flowchart form, no pattern of short-term or long-term differences in comprehension of the design was observed. No significant differences were detected in the quality or other properties of programs written as implementations of the designs. Subjective ratings indicated a mild preference for PDLs. Overall, the results suggest that software design performance and designer-programmer communication might be significantly improved by the adoption of informal PDLs rather than flowcharts as a standard documentation method for detailed computer program designs.
A general purpose data entry program
Simulations constitute an important family of computer applications in science and engineering. To perform each simulation run, it is usually necessary to provide extensive data specifying the parameters of the simulation as well as data which support the calculation models involved. We have designed a program and a file structure that provides a method for convenient data entry, and creates and edits data files according to specifications contained in a separate file that serves as a template. By providing different templates, the same program can be made to serve numerous applications. The structure of the data files allows a degree of flexibility difficult to achieve using conventional database systems.
Shape the Future of Computing
ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.
Get InvolvedCommunications of the ACM (CACM) is now a fully Open Access publication.
By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.
Learn More