Search
Join ACM

Software Engineering and Programming Languages

Advertisement

Research and Advances

The Dilogarithm function of a real argument [S22]

The dilogarithm function [1-3], defined by Li2(x) = - ∫x0 (1/z) ln (1 - z) dz, (1) occurs in several different applications in physics and engineering, ranging from quantum electrodynamics, to network analysis, to the thermodynamics of ideal ferromagnets, to the structure of polymers. A new function subroutine is developed which computes the dilogarithm function of a real argument to an accuracy of a few parts in 1015. This program was designed to be included in the usual package of library subprograms relied upon by most users. It employs an alternative computational approach to a previously published algorithm [4].
and
Research and Advances

The algorithm sequential access method: an alternative to index sequential

A requirement of many computer file processing systems is the ability to access data stored on a direct access storage device (DASD) both sequentially and randomly. A popular method which provides both types of access is the index sequential organization. The purpose of this study is to propose and analyze a file organization method which should be appropriate for the same type of environment as index sequential but would be more efficient at the two types of access. This proposed method is designated the Algorithm Sequential Access Method (ASAM).
and
Research and Advances

A reply to gentleman and Marovich

Gentleman and Marovich in their short communication [Comm. ACM 17, 5 (May 1974) 276-277] make the claim that for FORTRAN “… the language definitions require that subprograms can be separately compiled…,” citing the ANSI FORTRAN standard X3.9-1966 as their authority.
Research and Advances

Matrix reduction—an efficient method

The paper describes an efficient method for reduction of the binary matrices which arise in some school time-tabling problems. It is a development of that described by John Lions. It has been generalized and adapted to fit into the complete timetabling process; to use a more compact data representation and more efficient processing techniques; to take fuller advantage of possible available previous knowledge about the matrix. And it is designed as a structured program, which can readily be coded by the reader in the high level or low level programming language of his choice. Practical tests of the method have shown it to be a good basis for a realistic timetabling algorithm.
and
Research and Advances

A system for typesetting mathematics

This paper describes the design and implementation of a system for typesetting mathematics. The language has been designed to be easy to learn and to use by people (for example, secretaries and mathematical typists) who know neither mathematics nor typesetting. Experience indicates that the language can be learned in an hour or so, for it has few rules and fewer exceptions. For typical expressions, the size and font changes, positioning, line drawing, and the like necessary to print according to mathematical conventions are all done automatically. For example, the input sum from i=0 to infinity x sub i = pi over 2 produces ∑∞i=0xi = &pgr;/2 The syntax of the language is specified by a small context-free grammar; a compiler-compiler is used to make a compiler that translates this language into typesetting commands. Output may be produced on either a phototypesetter or on a terminal with forward and reverse half-line motions. The system interfaces directly with text formatting programs, so mixtures of text and mathematics may be handled simply. This paper was typeset by the authors using the system described.
and
Research and Advances

On a solution to the cigarette smoker’s problem (without conditional statements)

This report discusses a problem first introduced by Patil, who has claimed that the cigarette smoker's problem cannot be solved using the P and V operations introduced by Dijkstra unless conditional statements are used. An examination of Patil's proof shows that he has established this claim only under strong restrictions on the use of P and V. These restrictions eliminate programming techniques used by Dijkstra and others since the first introduction of the semaphore concept. This paper contains a solution to the problem. It also discusses the need for the generalized operators suggested by Patil.
Research and Advances

Glypnir—a programming language for Illiac IV

GLYPNIR is one of the earliest existing languages designed for programming the Illiac IV computer. The syntax of the language is based on ALGOL 60, but has been extended to allow the programmer explicitly to specify the parallelism of his algorithm in terms of 64-word vectors. This paper describes the characteristics, goals, and philosophy of the language, and discusses some of the problems associated with parallel computer architectures.
, , , and
Research and Advances

Anaysis of interleaved memory systems using blockage buffers

A model of interleaved memory systems is presented, and the analysis of the model by Monte Carlo simulation is discussed. The simulations investigate the performance of various system structures, i.e. schemes for sending instruction and data requests to the memory system. Performance is measured by determining the distribution of the number of memory modules in operation during a memory cycle. An important observation from these investigations is that separately grouping instruction and data requests for memory can substantially increase the average number of memory modules in operation during a memory cycle. Results of the simulations and an analytical study are displayed for various system structures.
and
Research and Advances

The new math of computer programming

Structured programming has proved to be an important methodology for systematic program design and development. Structured programs are identified as compound function expressions in the algebra of functions. The algebraic properties of these function expressions permit the reformulation (expansion as well as reduction) of a nested subexpression independently of its environment, thus modeling what is known as stepwise program refinement as well as program execution. Finally, structured programming is characterized in terms of the selection and solution of certain elementary equations defined in the algebra of functions. These solutions can be given in general formulas, each involving a single parameter, which display the entire freedom available in creating correct structured programs.
Research and Advances

Storage-efficient representation of decimal data

Usually n decimal digits are represented by 4n bits in computers. Actually, two BCD digits can be compressed optimally and reversibly into 7 bits, and three digits into 10 bits, by a very simple algorithm based on the fixed-length combination of two variable field-length encodings. In over half of the cases the compressed code results from the conventional BCD code by simple removal of redundant 0 bits. A long decimal message can be subdivided into three-digit blocks, and separately compressed; the result differs from the asymptotic minimum length by only 0.34 percent. The hardware requirement is small, and the mappings can be done manually.
and
Research and Advances

Computer programming as an art

When Communications of the ACM began publication in 1959, the members of ACM's Editorial Board made the following remark as they described the purposes of ACM's periodicals [2]: “If computer programming is to become an important part of computer research and development, a transition of programming from an art to a disciplined science must be effected.” Such a goal has been a continually recurring theme during the ensuing years; for example, we read in 1970 of the “first steps toward transforming the art of programming into a science” [26]. Meanwhile we have actually succeeded in making our discipline a science, and in a remarkably simple way: merely by deciding to call it “computer science.”
Research and Advances

A heuristic approach to inductive inference in fact retrieval systems

Heuristic procedures are presented which have been developed to perform inferences by generalizing from available information. The procedures make use of a similarity structure which is imposed on the data base using nonnumerical clustering algorithms. They are implemented in a model fact retrieval system which uses a formal query language and a property-list data structure. A program of experiments is described wherein the procedures are used with test data bases which are altered by deleting part of the data and by purposely introducing false data. It is found that the system can infer the correct response under a variety of conditions involving incomplete and inconsistent data.
Research and Advances

An analytic model of the HASP execution task monitor

The HASP Execution Task Monitor periodically rearranges the OS/360 dispatching chain to give tasks preemptive execution priority in inverse order to that of their cpu utilization history. The effect is to keep the I/O bound tasks active and to prevent cpu bound tasks from locking out other tasks. This paper develops a simple model of the Execution Task Monitor and employs it to study the effectiveness of the monitor in improving system performance. A modified strategy for monitor control is investigated for the case of task execution in a memory heirarchy of varying speeds.
Research and Advances

Arguments for a moratorium on the construction of a community information utility

In this article the author urges a prudent and decentralized approach to the question of the design and desirability of computerized community information utilities. Before accepting the inevitability and desirability of this or any technology, we should: (1) be sure of the feasibility (internally and externally) of what is proposed; (2) project and perhaps wait for changes in complementary techniques; (3) evaluate current and projected supplementary techniques; (4) establish the existence of demand for what is proposed; (5) take steps to involve a representative group of ultimate users in systems design, and (6) carefully think through possible side effects on man and his world view. Current proposals for community information utilities are examined in this framework, and the conclusion is drawn that society is not yet in a position to justify either the construction of an information utility in a prototype community or the acceptance of a policy in favor of its widespread implementation.
Research and Advances

Self-stabilizing systems in spite of distributed control

The synchronization task between loosely coupled cyclic sequential processes (as can be distinguished in, for instance, operating systems) can be viewed as keeping the relation “the system is in a legitimate state” invariant. As a result, each individual process step that could possibly cause violation of that relation has to be preceded by a test deciding whether the process in question is allowed to proceed or has to be delayed. The resulting design is readily—and quite systematically—implemented if the different processes can be granted mutually exclusive access to a common store in which “the current system state” is recorded.
Research and Advances

A method for composing simple traditional music by computer

A method is described for composing musical rounds by computer. This method uses some music theory plus additional heuristics. Fundamental to the method is a set of productions together with sets of applicability rules and weight rules which operate on the productions deciding when and to what extent they are available for use. Several rounds generated by the computer implementation of the method are presented. Generally, the resultant music sounds mediocre to the professional although usually pleasing to the layman. It appears that full-blown music theory is not needed for rounds—all the hardware required for structural levels is not necessary for these pieces. The author has tried to address both musicians and computer scientists.

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 Involved

Communications 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