Software Engineering and Programming Languages
Advertisement
Reciprocal hashing: a method for generating minimal perfect hashing functions
A method is presented for building minimal perfect hash functions, i.e., functions which allow single probe retrieval from minimally sized tables of identifier sets. A proof of existence for minimal perfect hash functions of a special type (reciprocal type) is given. Two algorithms for determining hash functions of reciprocal type are presented and their practical limitations are discussed. Further, some application results are given and compared with those of earlier approaches for perfect hashing.
A two-list synchronization procedure for discrete event simulation
The traditional mechanism for maintaining a list of pending events in a discrete event simulation is the simple linked list. However, in large scale simulations this list often becomes cumbersome to maintain since the number of pending events may become quite large. As a result, the execution time required by the simple linked list is often a significant portion of total simulation time. Several papers have been published suggesting improved synchronization procedures. The most efficient procedures reported are the time-indexed procedure and the two-level procedure. Both methodologies are much more efficient than simple linked lists; however, neither has been adopted by a general purpose simulation language. Further, both procedures require external parameter definition, which is a major handicap to their adoption by a general purpose language. This paper introduces a new sychronization procedure, the two-list procedure, which is much faster than simple linked lists for large pending event files. This procedure was designed for implementation in Fortran, and properly implemented it is transparent to the user. Thus it is ideal for adoption by general purpose simulation languages.
A generalized user interface for applications programs
A general method for using disk files (instead of a more conventional parameter-passing mechanism) to transfer control information from a user interface to a set of related applications programs is described. This technique effectively moves much of the user interface, including command decoding and limited parameter checking, from the applications programs to a table-driven executive.
Microcomputers as remote nodes of a distributed system
A time-sharing system may be extended into a general-purpose distributed computing facility through the use of remote microcomputer systems. In such an extension the microcomputer system is not merely a remote terminal but a complete computer system. It becomes part of an integrated network of computers, each with significant local computational power with access to host system data resources. The implementation described emphasizes ease-of-use by minimizing any differences between local and remote data use.
Problems in application software maintenance
The problems of application software maintenance in 487 data processing organizations were surveyed. Factor analysis resulted in the identification of six problem factors: user knowledge, programmer effectiveness, product quality, programmer time availability, machine requirements, and system reliability. User knowledge accounted for about 60 percent of the common problem variance, providing new evidence of the importance of the user relationship for system success or failure. Problems of programmer effectiveness and product quality were greater for older and larger systems and where more effort was spent in corrective maintenance. Larger scale data processing environments were significantly associated with greater problems or programmer effectiveness, but with no other problem factor. Product quality was seen as a lesser problem when certain productivity techniques were used in development.
The evolution of user behavior in a computerized conferencing system
Data from 18-month operational trials of the EIES system indicate that the range of features considered valuable in a computer-based communication system increases with the amount of experience gained by using this medium of communication. Simple message systems alone are not likely to satisfy the communications needs of long term, regular users of computerized communications systems. Among the capabilities which long term, regular users find valuable are group conferences, notebooks for text composition, and self-defined commands.
Documentation for a model: a hierarchical approach
A set of documents and their organization according to functional requirements in order to produce information that will facilitate the use of models are described. The authors discuss the role of models in the policy process and of documentation in the assessment of such models.
Password authentication with insecure communication
A method of user password authentication is described which is secure even if an intruder can read the system's data, and can tamper with or eavesdrop on the communication between the user and the system. The method assumes a secure one-way encryption function and can be implemented with a microcomputer in the user's terminal.
A history and evaluation of System R
System R, an experimental database system, was constructed to demonstrate that the usability advantages of the relational data model can be realized in a system with the complete function and high performance required for everyday production use. This paper describes the three principal phases of the System R project and discusses some of the lessons learned from System R about the design of relational systems and database systems in general.
An experiment in high level language microprogramming and verification
The STRUM system was created to apply software engineering techniques to microprogramming. It provides the tools that allow the microprogrammer to use high level language, structured programming, and formal program verification to create emulations for a horizontally microprogrammed computer. This system is evaluated in two parts: (1) High level microprogramming language design and its use in structured microprogramming; and (2) Verification of a large microprogram. Both parts of this evaluation include experimental results. Part I includes a comparison of an emulation created using traditional techniques to the same emulation created using the STRUM system. Part II describes the formal verification of a 1700 line program that was immediately subjected to extensive testing. This work provides new results on the efficiency of high level microprogramming languages, the effectiveness of peephole optimization for microcode and the practicality of formal microprogram verification.
Low contention semaphores and ready lists
A method for reducing semaphore and ready-list contention in multiprocessor operating systems is described. Its correctness is established. Its performance is compared with conventional implementations. A ready list implemented as a ring network is proposed and evaluated.
Shuffle languages, Petri nets, and context-sensitive grammars
Flow expressions have been proposed as an extension of the regular expressions designed to model concurrency. We examine a simplification of these flow expressions which we call shuffle expressions. We introduce two types of machines to aid in recognizing shuffle languages and show that one such machine may be equivalent to a Petri Net. In addition, closure and containment properties of the related language classes are investigated, and we show that one machine type recognizes at least a restricted class of shuffle languages. Finally, grammars for all shuffle languages are generated, and the shuffle languages are shown to be context-sensitive.
On sharing secrets and Reed-Solomon codes
Shamir's scheme for sharing secrets is closely related to Reed-Solomon coding schemes. Decoding algorithms for Reed-Solomon codes provide extensions and generalizations of Shamir's method.
The Cornell program synthesizer: a syntax-directed programming environment
Programs are not text; they are hierarchical compositions of computational structures and should be edited, executed, and debugged in an environment that consistently acknowledges and reinforces this viewpoint. The Cornell Program Synthesizer demands a structural perspective at all stages of program development. Its separate features are unified by a common foundation: a grammar for the programming language. Its full-screen derivation-tree editor and syntax-directed diagnostic interpreter combine to make the Synthesizer a powerful and responsive interactive programming tool.
An abstract model of a processor is presented informally. The model can be used by itself to abstractly describe algorithms, or with a direct implementation to write and run programs, or as the foundation of a programming language. In the last case, a translator allows higher level descriptions of algorithms for the model.
Automatic extension of an ATN knowledge base
A computer program is described that acquires much of its knowledge from conversations among operators on Morse code radio networks. The system consists of a learning component and a language understander. The learning component extends a ‘core’ augmented transition network (ATN) knowledge base by generalizing from sentences taken from scripts of actual conversations. The extensions enable the understanding component to process a large number of sentences that are syntactically and semantically similar to the examples.
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