bluuebunny/crossref_metadata_2025_split huggingface dataset:
Regulation management and logic programming
Authors: Koster Alexis , Parker D. Stott 
Published: November 2006

AbstractRegulations are pervasive in information systems. They manifest themselves as design rules, integrity constraints, deadlines, conventions, information disclosure requirements, policies, procedures, contracts, taxes, quotas and other statutes. Managing regulations is difficult. Regulations are complex, change frequently and rest on models of the real world that involve unusual vocabulary if not unusual concepts. Consequently, checking compliance with regulations is tedious and error‐prone.Logic programming appears to provide a good framework for developing regulation management systems. Besides permitting arbitrary regulations to be modelled, it offers rapidity and ease of development, readability, incremental modifiability, extensibility and portability. These features are not provided by existing DP programming tools, database managers or conventional expert‐system shells.This paper investigates the application of logic programming in a significant regulation management application: Workers' Compensation Insurance premium auditing. The insurance premium computation rules for the State of California were encoded as a large Prolog program. This application illustrates specific strengths and weaknesses of logic programming and Prolog in dealing with large‐scale real‐world regulations.
A structure for efficient update, incremental redisplay and undo in graphical editors
Authors: Dannenberg Roger B. 
Published: November 2006

AbstractThe design of a graphical editor requires a solution to a number of problems, including how to (1) support incremental redisplay, (2) control the granularity of display updates, (3) provide efficient access and modification to the underlying data structure, (4) handle multiple views of the same data and (5) support Undo operations. It is most important that these problems be solved without sacrificing program modularity. A new data structure, called an ItemList, provides a solution to these problems. ItemLists maintain both multiple views and multiple versions of data to simplify Undo operations and to support incremental display updates. The implementation of ItemLists is described and the use of ItemLists to create graphical editors is presented.
Structured dataflow analysis for arrays and its use in an optimizing compiler
Authors: Gross Thomas , Steenkiste Peter 
Published: November 2006

AbstractWe extend the well‐known interval analysis method so that it can be used to gather global flow information for individual array elements. Data dependences between all array accesses in different basic blocks, different iterations of the same loop, and across different loops are computed and represented as labelled arcs in a program flow graph. This approach results in a uniform treatment of scalars and arrays in the compiler and builds a systematic basis from which the compiler can perform numerous global optimizations.This global dataflow analysis is performed as a separate phase in the compiler. This phase only gathers the global relationships between different accesses to a variable, yet the use of this information is left to the code generator. This organization substantially simplifies the engineering of an optimizing compiler and separates the back end of the compiler (e.g. code generator and register allocator) from the flow analysis part.The global dataflow analysis algorithm described in this paper has been implemented and used in an optimizing compiler for a processor with deep pipelines. This paper describes the algorithm and its compact implementation and evaluates it, both with respect to the accuracy of the information and to the compile‐time cost of obtaining and using it.
Experience with distributed Smalltalk
Authors: Bennett John K. 
Published: November 2006

AbstractDistributed Smalltalk (DS) is an implementation of Smalltalk that supports the interaction of many Smalltalk users on many machines. It provides communication and interaction among remote Smalltalk users, direct access to remote objects, and a degree of object sharing among users. The distributed aspects of the system are largely user transparent. Many of the major design issues and implementation decisions associated with Distributed Smalltalk have previously been reported. This paper concentrates on the impact of those decisions and describes how DS is used to build distributed applications. Three example applications are described: remote file access, animated distributed objects, and offloading a compute‐intensive task to a non‐Smalltalk host. Based on our experience with DS, we present an evaluation of its design and implementation.
Extending mutation testing to find environmental bugs
Authors: Spafford Eugene H. 
Published: November 2006

AbstractEnvironmental bugs are bugs caused by limitations of precision or capacity in the environment of a piece of software. These bugs may be difficult to activate and even more difficult to find.This paper reports on an extension to traditional mutation testing that enables testing specifically for environmental bugs involving integer arithmetic. This method is both simple and effective, and provides some insight into other possible extensions of the mutation‐testing methodology that can be used to expose environmental bugs.
Conversion of simulation processes to pascal constructs
Authors: Malloy Brian , Soffa Mary Lou 
Published: November 2006

AbstractAlthough the expressive power of retentive control is widely accepted, languages possessing such control forms are not always available. In this paper, we present an implementation technique to extend a recursive language to one containing simulation processes. In particular, we report on the design of a preprocessor that translates SimCal, a language that combines Pascal and the process abstraction of Simula, into Pascal. The translation is done automatically by the preprocessor without additional information from the user. The preprocessor has been implemented for a microcomputer using Turbo Pascal, which is also used as the target language. SimCal has been found to be useful for teaching simulation and for programming simulation applications.
Selecting a hashing algorithm
Authors: McKenzie B. J. , Harries R. , Bell T. 
Published: November 2006

AbstractHashing is so commonly used in computing that one might expect hash functions to be well understood, and that choosing a suitable function should not be difficult. The results of investigations into the performance of some widely used hashing algorithms are presented and it is shown that some of these algorithms are far from optimal. Recommendations are made for choosing a hashing algorithm and measuring its performance.
A system for adaptive disk rearrangement
Authors: Vongsathorn Paul , Carson Scott D. 
Published: November 2006

AbstractThe speed of mass storage devices has a significant impact on the performance of computer systems. The speed that is realized on a particular mass storage device, however, depends heavily on how that device is used. Operating systems, such as the UNIXUNIX is a trademark of AT&T Bell Laboratories.time‐sharing system, use layout policies and head‐scheduling disciplines that are designed to work well on average.Numerous studies have shown that disk access patterns exhibit a high degree of locality. Further, studies have shown that these access patterns do not necessarily correspond to the usage patterns anticipated by the system's designers, and that head scheduling is used infrequently enough that it has limited effect. This paper describes the design, implementation, and use of a disk subsystem that adaptively corrects the disparity between expected access patterns and actual access patterns by reorganizing disk data. A representative experiment that demonstrates the resulting performance improvement is presented.
Programming abstract data types, iterators and generic modules in C
Authors: Iannello Giulio 
Published: November 2006

AbstractA programming discipline to write abstract data types, iterators and generic modules using the C language is proposed. Program examples are presented making use of features of the ANSI standard for C.The discipline supports object‐oriented development by allowing the programmer to implement abstractions through modules with well‐defined interfaces. To use the abstractions, the programmer is not required to be aware of how they are implemented.
A tool to minimize the time costs of parallel computations through optimal processing power allocation
Authors: Qin Bin , Sholl Howard A. , Ammar Reda A. 
Published: November 2006

AbstractIn this paper, we present a software system, OPAS (Optimal Allocation System), that incorporates the optimal allocation policy in the analysis of the time‐cost behaviour of parallel computations. OPAS assumes that the underlying system which supports the executions of parallel computations has a finite number of processors, that all the processors have the same speed and that the communication is achieved through a shared memory. OPAS defines the time cost as a function of the input, the algorithm, the data structure, the processor speed, the number of processors and the processing power allocation. In analysing the time cost of a computation, OPAS first uses the optimal allocation policy that we developed previously to determine the amount of processing power each node receives and then derives the computation's time cost. OPAS can evaluate different time‐cost behaviours, such as the minimum time cost, the maximum time cost, the average time cost and the time‐cost variance. It can also determine the speed‐up and efficiency, and plot the time‐cost curve and time‐cost distribution.
TMS: A free‐form text‐management system
Authors: Amur Rekha , Mohan K. Ananda , Ramaswami M. D. 
Published: November 2006

AbstractTMS (Text Management System) is a database management system that supports an access method based on both select and search queries. TMS provides support for variable‐length records with pointer fields within the relation. Pointers can be used to support not only text but data from any media, such as graphics and images. An inverted index based on the variable‐length record structure is used for speedy retrieval of records based on keywords. In this paper, the variable length record management of TMS and the keyword‐based retrieval mechanism are described.
Proxies: A software structure for accommodating heterogeneity
Authors: Notkin David 
Published: November 2006

AbstractHandling heterogeneity in computer systems without decreasing user productivity and without increasing development costs demands special software structures. This paper presents a flexible software structure that has been used to construct heterogeneous remote procedure call, naming, electronic mail, filing and remote computation services. This structure captures the heterogeneous aspects of a service in a set of abstract interfaces. Clients of the service are built in terms of the abstract interfaces, but one of multiple implementations of those interfaces, called proxies, is dynamically selected to satisfy the demands of heterogeneity.
A symbolic debugger for real‐time embedded Ada software
Authors: Lyttle Dan , Ford Ray 
Published: November 2006

AbstractRockwell's Ada symbolic debugging system (ASDS) is designed especially for use in debugging and testing embedded system software. ASDS uses a combination of software and special hardware to support unobtrusive monitoring, breakpoint and display facilities that can be applied during the development of an embedded system and during the ‘downstream’ stages of the embedded system life cycle associated with production and field unit testing. The ASDS software kernel executes on a stand‐alone monitor processor with modest computational power (e.g. a personal computer), connected to the embedded target system via a target interface that allows the monitor to observe transactions on the target bus in real‐time. The use of a monitor processor with modest power limits the degree of ‘high level’ monitoring support—though ASDS can detect the execution of a particular line of source code or access to a particular variable it contains no facilities for monitoring interactions between high‐level dynamic objects such as tasks. However, the modest power required for the monitor also reduces its costs, with the result that ASDS debugging and test stations have been readily available to engineers working on system development, in production and in the field. Our description of the ASDS design and implementation focuses on its practical solutions to the problems associated with building and maintaining a symbolic debugging system to support embedded system development.
Code compaction for parallel architectures
Authors: Anantha Kasi , Long Fred 
Published: November 2006

AbstractThere are two principal methods used to exploit the parallelism available on a parallel machine: the program to be executed can be optimized by hand, or the program can be automatically converted to parallel machine code by a compiler. The first method usually derives parallelism at the procedure level; a parallel program is written in a high‐level language and typically has various modules executing in parallel. By contrast, the compiler methodically transforms the program into parallel code using various transformations, such as code movement. The automatic conversion of a program to parallel code is called compaction or parallelization. This paper describes the evolution of a new compaction program and presents a new algorithm for determining legal code movements. A simulator of the target architecture was used to estimate the execution times of a sample suite of programs before and after compaction. The results verify that substantial advantages arise from applying this compaction technique.
Experiences of designing a sophisticated network monitor
Authors: Sudama Ram , Chiu Dah‐Ming 
Published: November 2006

AbstractThis paper describes the design of a network monitor that captures connections information in a network. The real‐time performance requirement makes the design significantly more challenging than that of a simple monitor that only counts packet types. Although we developed the monitor for DECnet, most of the lessons we learned are protocol‐independent and are thus applicable to designing such a monitor for a different protocol. In addition to reviewing the functionality, we report a first‐cut performance evaluation of the monitor software. We also describe some of our early experiences in using the monitor and review some current applications of the monitor in the areas of network configuration planning and performance management.
Message passing in concurrent C: Synchronous versus asynchronous
Authors: Gehani N. H. 
Published: November 2006

AbstractMessage‐passing facilities used for interprocess communication fall into two categories: asynchronous and synchronous. Most concurrent programming languages support either synchronous or asynchronous message passing, but not both. Although these two kinds of message passing are equivalent because each can be implemented in terms of the other, programmers seem to have a strong preference for one or the other. Concurrent C is a parallel superset of C that initially provided only synchronous message‐passing facilities. Some users and potential users of Concurrent C indicated a strong preference for asynchronous message‐passing facilities. In response to this feedback, we eventually extended Concurrent C with asynchronous message passing.The issue of synchronous message passing versus asynchronous message passing has been much discussed in the context of operating systems but not in the context of programming languages. In this paper, I will explain the decision to add asynchronous message passing to Concurrent C. I will first summarize and review the pros and cons of synchronous and asynchronous message passing. I will then compare four versions of an example written using synchronous and asynchronous message passing, discuss some details about implementing synchronous and asynchronous message passing facilities, examine the costs involved in using these facilities, and present some experimental results.
Field experiments with local software quality metrics
Authors: Binder L. H. , Poore J. H. 
Published: November 2006

AbstractThe theory for local software quality metrics that appeared in Software‐Practice and Experience in November has been tested in field experiments. Data collected in the experiments and the results are presented here. The theory prescribed two activities, one for articulating rule sets for quality and the other for deriving a statistical metric. The process of deriving the statistical metric has been reduced to easy practice. Effective articulation of rule sets is still under study.
Squinting at power series
Authors: McIlroy M. Douglas 
Published: November 2006

AbstractData streams are an ideal vehicle for handling power series. Stream implementations can be read off directly from simple recursive equations that define operations such as multiplication, substitution, exponentiation and reversion of series. The bookkeeping that bedevils these algorithms when they are expressed in traditional languages is completely hidden when they are expressed in stream terms. Communicating processes are the key to the simplicity of the algorithms. Working versions are presented in newsqueak, the language of Pike's ‘squint’ system; their effectiveness depends critically on the stream protocol.
A node‐positioning algorithm for general trees
Authors: Walker John Q. 
Published: November 2006

AbstractDrawing a tree consists of two stages: determining the position of each node, and actually rendering the individuals nodes and interconnecting branches. The algorithm described in this paper is concerned with the first stage: given a list of nodes, an indication of the hierarchical relationship among them, and their shape and size, where should each node be positioned for optimal aesthetic effect?This algorithm determines the positions of the nodes for any arbitrary general tree. It is the most desirable positioning with respect to certain widely‐accepted heuristics. The positioning, specified in x, y co‐ordinates, minimizes the width of the tree. In a general tree, there is no limit on the number of offspring per node; this contrasts with binary and ternary trees, for example, which are trees with a limit of two and three offspring per node. This algorithm operates in time O(N), where N is the number of nodes in the tree.Previously, most tree drawings have been positioned by the sure hand of a human graphic designer. Many computer‐generated positionings have been either trivial or contained irregularities. Earlier work by Wetherell and Shannon1 and Tilford,2 upon which this algorithm builds, failed to position the interior nodes of some trees correctly. The algorithm presented here correctly positions a tree's node using only two passes. It also handles several practical considerations: alternative orientations of the tree, variable node sizes and out‐of‐bounds conditions. Radack,3 also building on Tilford's work, has solved this same problem with a different algorithm which makes four passes.
Optimization techniques for parallel processing
Authors: Ebenstein Samuel E. , McDermott Tracy L. 
Published: November 2006

AbstractTechniques for optimization on a parallel architecture are presented, and are applied to a proprietary simulation code. Software tools available on most UNIX systems are used extensively in these techniques. Methods for determining where to partition an application for maximum benefit from parallelism are discussed, along with a way for determining what portion of the application has been parallelized. Finally, an algorithm is given which can be used to predict the effect on computation time of adding additional processors.
Live text
Authors: Fraser Christopher W. , Krishnamurthy Balachander 
Published: November 2006

AbstractThis paper describes software that allows the user to edit the output of several common software tools and to cause the changes to be written back to the input files. For example, it is possible to edit the output of a spelling checker and have the changes propagated back to the source files. This technique makes some corrections simpler and more direct. A trial implementation is embedded in Emacs.
Program monitoring and analysis: Software structures and architectural support
Authors: Charlton C. C. , Leng P. H. , Wilkinson D. M. 
Published: November 2006

AbstractThe ability to monitor the progress of a program in execution is useful in program testing and debugging, and for performance analysis and profiling. Systems to support this activity should ideally be high‐level‐language based, but progress in implementing them has been limited by the lack of suitable hardware support. In this paper we derive software structures to support a generalized system of execution monitoring, and define a set of architectural primitives sufficient to support these structures. Simple and efficient means of implementing these primitives within the machine architecture are described.
Object‐oriented programming applied to a prototype workstation
Authors: Kuhl Frederick S. 
Published: November 2006

AbstractObject‐oriented programming has been applied to the development of a prototype workstation to be used in airport traffic control towers. Objective‐C was used because it supports objects, classes and inheritance, and it allows easy access to system services. A number of design practices emerged as helpful in the course of development, some of which have been reported elsewhere. The notion of a framework of co‐operating classes as a paradigm of design was especially helpful. Comparisons with the size and rate of code production of an earlier, similar workstation programmed in C indicate an advantage to object‐oriented programming.
The implementation of Pro Test: A Prolog debugger for a refined box model
Authors: Schleiermacher A. , Winkler J. F. H. 
Published: November 2006

AbstractWe describe some aspects of the implementation of a Prolog debugger for a refined box model in which attempted unifications can also be observed. Our implementation of the ProTest debugger is based on a meta‐interpreter for Prolog. We start with an existing meta‐interpreter for Byrd's box model (four‐port debugger) and we transform it into one for the refined box model (ten‐port debugger). To explain the transformation we show several versions of the meta‐interpreter. In these versions we use the technique of changing the database to implement the cut, but another possibility is also explained briefly. A simple notation for typing is used to make Prolog programs more readable. In an appendix we give a listing of a simple prototype of the extended meta‐interpreter.
Incremental register reallocation
Authors: Bivens Mary P. , Soffa Mary Lou 
Published: November 2006

AbstractCurrent compiler technology performs extensive code transformations either to parallelize code or to perform optimizations that reduce space or time. The cost of the analyses for these transformations is high and is further magnified when edits are made, forcing complete recompilation. By extending the concept of incremental compilation to include fine‐grained, high‐quality target code generation, we develop techniques that reuse the information created by an optimizing compiler to incorporate program edits efficiently into optimized target code. Our techniques include developing models of register usage for both local and global register allocation schemes and algorithms for incrementally updating these structures in response to an editing change. Based on these changes, the target code is updated. As graph colouring is a widely accepted register allocation scheme, we present techniques to rebuild and recolour interference graphs incrementally. Results from experiments that compare the performance of the incremental target code generator with its non‐incremental counterpart are reported, showing a saving when incorporating changes incrementally.