bluuebunny/crossref_metadata_2025 huggingface dataset:
VIFOR: A tool for software maintenance
Authors: Rajlich Vaclav , Damaskinos Nicholas , Linos Panagiotis , Khorshid Wafa
Published: November 2006

VIFOR is a software tool oriented towards maintenance of medium‐to‐large Fortran77 programs. With VIFOR, programs can be displayed and edited in two forms: as the code and as the graph. VIFOR also contains transformations in both directions, i.e. from code to graph and from graph to skeletons of code. Hence, it is suitable for re‐engineering and maintenance of existing code. Specially designed browsers implement the graphical interface. VIFOR contains a database that is based on a simple but effective data model of Fortran programs. The model contains only four entity classes and three relations, which makes the tool small, and easy to implement and use. A simple query language allows browsing through the database.
Regulation management and logic programming
Authors: Koster Alexis , Parker D. Stott
Published: November 2006

Regulations 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

The 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

We 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

Distributed 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

Environmental 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

Although 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

Hashing 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

The 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 UNIX

UNIX 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

A 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.
Code generation for a systolic computer
Authors: Lengauer Christian
Published: November 2006

An experiment of a mechanical code generation for a programmable systolic computer is reported. Two‐dimensional systolic arrays are automatically reduced to one dimension, and code is generated for the one‐dimensional processor array Warp. The technique is demonstrated with two examples: matrix multiplication and LU decomposition.
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

In 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

TMS (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

Handling 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.
Collaboration using roles
Authors: Bishop Matt
Published: November 2006

Segregation of roles into alternative accounts is a model which provides not only the ability to collaborate but also enables accurate accounting of resources consumed by collaborative projects, protects the resources and objects of such a project, and does not introduce new security vulnerabilities. The implementation presented here does not require users to remember additional passwords and provides a very simple consistent interface.
A symbolic debugger for real‐time embedded Ada software
Authors: Lyttle Dan , Ford Ray
Published: November 2006

Rockwell'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

There 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

This 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

Message‐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

The 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

Data 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

Drawing 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

Techniques 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

This 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

The 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

Object‐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.
Calendrical calculations
Authors: Dershowitz Nachum , Reingold Edward M.
Published: November 2006

A unified, algorithmic presentation is given for the Gregorian (current civil), ISO, Julian (old civil), Islamic (Moslem), and Hebrew (Jewish) calendars. Easy conversion among these calendars is a byproduct of the approach, as is the determination of secular and religious holidays.
The implementation of Pro Test: A Prolog debugger for a refined box model
Authors: Schleiermacher A. , Winkler J. F. H.
Published: November 2006

We 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

Current 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.
A virtual stack facility for mini‐computer and microcomputer implementation of the finite element method
Authors: Eldin A. Sharaf , Evans D. J.
Published: November 2006

In this paper, the efficient implementation of the finite element method on mini‐computers and microcomputers is considered. The main limitations of memory and address space are overcome and a software solution proposed with the use of a virtual stack facility which is implemented and tested. A new replacement algorithm for a virtual stack is presented and shown to be more efficient than other known implementations.
A graphical user interface server for unix
Authors: Hudson Scott E. , Mohamed Shamim P.
Published: November 2006

The UNIX operating system has attained widespread popularity because of its power, flexibility and elegance. However, the common user interfaces (shells) have been criticized as being cryptic and difficult to use, especially for novices. In this paper, we present a user interface server that can be used to provide a graphical shell for UNIX. This shell helps to overcome a number of difficulties faced by both novices and experts. Although it is largely intended to assist novices, it is also designed not to become a hindrance for expert users and does not sacrifice the basic power and flexibility of UNIX. The server is designed to augment rather than replace text‐based interfaces and can be used from a variety of different interactive programs in addition to shells.
Abstract execution: A technique for efficiently tracing programs
Authors: Larus James R.
Published: November 2006

Many areas of computer performance analysis require detailed traces of events that occur during a program's execution. Collecting traces is expensive. The additional code required to record events greatly slows a program's execution. In addition, the resulting trace files can grow unmanageably large. This paper describes a technique called abstract execution that alleviates both problems.

Abstract execution records a small set of events during the traced program's execution. These events serve as input to an abstract version of the program that generates a full trace by re‐executing selected portions of the original program. This process greatly reduces both the cost of tracing the original program and the size of the trace files. The cost of regenerating a trace is insignificant in comparison to the cost of applications that use it.

This paper also describes a system called AE that implements Abstract Execution. The paper contains measurements that demonstrate that AE can efficiently trace large programs.
Hard‐coding bottom‐up code generation tables to save time and space
Authors: Fraser Christopher W. , Henry Robert R.
Published: November 2006

Code generators based on bottom‐up rewrite systems (BURS) are automatically generated from machine‐description grammars. They produce locally optimal code for expression trees, but their tables are large and require compile‐time interpretation. This paper describes a program that compiles BURS tables into a combination of hard code and data. Hard‐coding exposed important opportunities for compression that were previously hidden in the tables, so the hard‐coded code generators are not just faster but also significantly smaller than their predecessors. A VAX code generator takes 21.4Kbytes and identifies optimal assembly code in about 50 VAX instructions per node.
A light‐weight UIMS
Authors: Read Robert L. , Smith Martin L.
Published: November 2006

We built a limited but successful user interface management system named HYPE which supports rapid interactive creation and organization of user interfaces for a large class of applications. HYPE is targeted at applications for which the user interface is only loosely coupled to the application. Examples of this class of application are ‘command line‐driven’ programs. Many applications in this class can be quickly given satisfactory direct‐manipulation interfaces with little or no reprogramming of the application. The programmer need only be familiar with HYPE, and not with the particular windowing system upon which it sits.

The appearance of the interface is specified interactively through the direct manipulation of interface components.

The behaviour of the interface is programmed with an interpreted procedural language which can send and receive messages and invoke system services. In particular, it can execute applications.

The structure of the interface is a tree of potentially‐visible objects which communicate with the user, the system, and each other through message passing. The tree structure facilitates grouping interfaces for related applications, or families of applications, into a single master interface.

Visual layout, tree‐building, behaviour assignment (programming) and execution of the interface all occur within HYPE, a conjunction that makes it a powerful prototyping tool.
A letter‐oriented perfect hashing scheme based upon sparse table compression
Authors: Chang Chin‐Chen , Wu Tzong‐Chen
Published: November 2006

In this paper, a new letter‐oriented perfect hashing scheme based on Ziegler's row displacement method is presented. A unique n‐tuple from a given set of static letter‐oriented key words can be extracted by a heuristic algorithm. Then the extracted distinct n‐tuples are associated with a 0/1 sparse matrix. Using a sparse matrix compression technique, a perfect hashing function on the key words is then constructed.
LANSF: A protocol modelling environment and its implementation
Authors: Gburzyński Paweł , Rudnicki Piotr
Published: November 2006

LANSF is a software package that was originally designed as a tool to investigate the behaviour of medium access control (MAC) level protocols. These protocols form an interesting class of distributed computations: timing of events is the key factor in them. The protocol definition language of LANSF is based on C, and protocols are specified (programmed) as collections of communicating, interrupt‐driven processes. These specifications are executable: an event‐driven emulator of MAC‐level communication phenomena forms the foundation of the implementation. Some tools for debugging, testing, and validation of protocol specifications are provided. We present key features of LANSF at the syntactic level, comment informally on the semantics of these features, and highlight some implementation issues. A complete example of a LANSF application is discussed in the Appendix.
Emerald: A general‐purpose programming language
Authors: Raj Rajendra K. , Tempero Ewan , Levy Henry M. , Black Andrew P. , Hutchinson Norman C. , Jul Eric
Published: November 2006

Emerald is a general‐purpose language with aspects of traditional object‐oriented languages, such as Smalltalk, and abstract data type languages, such as Modula‐2 and Ada. It is strongly typed with a non‐traditional object model and type system that emphasize abstract types, allow separation of typing and implementation, and provide the flexibility of polymorphism and subtyping with compile‐time checking. This paper describes the Emerald language and its programming methodology. We give examples that demonstrate Emerald's features, and compare and contrast the Emerald approach to programming with the approaches used in other similar languages.
Ytracc: A parse browser for yacc grammars
Authors: Furuta Richard , Stotts P. David , Ogata Jefferson
Published: November 2006

We describe a program for the display and exploration of complex, domain‐specific information: ytracc, an interactive grammar debugging tool for compiler writers. The ytracc system provides the designer of a yacc grammar a method of tracing a parser as it uses the grammar, ytracc captures the states of the parse as it is carried out. The captured parse can then be replayed forwards or backwards, step‐by‐step, or subtree‐by‐subtree, as defined by the non‐terminals of the grammar. The tool has been successfully used by students as an assistant in an advanced undergraduate compiler construction class, and we use the tool in our everyday work.
A scheme for little languages in interactive graphics
Authors: Beckman Brian
Published: November 2006

Programming environments for interactive graphics software typically have a multiplicity of tools and applications. Many of these programs contain ad hoc ‘little language’ interpreters1 that do many similar things in needlessly different ways. In particular, many little languages have, in addition to their special‐purpose constructs, vestigial support for ordinary programming, such as variables, loops and conditionals. If a single, standard programming language were the basis for all these little languages, they could have complete, coherent programming semantics; they could communicate with each other more easily; no design work for basic constructs would be needed; and interpreter implementation work would be saved. The approach of reusing and extending the same core language and interpreter for a variety of little languages is the extension language approach.

Scheme is proposed as a good choice for such a core language. Scheme is a simple, elegant, high‐level programming language. Extendable implementations are readily available in C source form. Example applications in Scheme from interactive graphics are presented that would be nearly impossible to code in a typical scripting language and very tedious to code in a lower‐level implementation language such as C.
A dataflow approach to event‐based debugging
Authors: Olsson Ronald A. , Crawford Richard H. , Ho W. Wilson
Published: November 2006

This paper describes a novel approach to event‐based debugging. The approach is based on a (coarsegrained) dataflow view of events: a high‐level event is recognized when an appropriate combination of lower‐level events on which it depends has occurred. Event recognition is controlled using familiar programming language constructs. This approach is more flexible and powerful than current ones. It allows arbitrary debugger language commands to be executed when attempting to form higher‐level events. It also allows users to specify event recognition in much the same way that they write programs.

This paper also describes a prototype, Dalek, that employs the dataflow approach for debugging sequential programs. Dalek demonstrates the feasibility and attractiveness of the dataflow approach. One important motivation for this work is that current sequential debugging tools are inadequate. Dalek contributes toward remedying such inadequacies by providing events and a powerful debugging language. Generalizing the dataflow approach so that it can aid in the debugging of concurrent programs is under investigation.
Module reuse by interface adaptation
Authors: Purtilo James M. , Atlee Joanne M.
Published: November 2006

This paper describes a language called Nimble that allows designers to declare how the actual parameters in a procedure call are to be transformed at run time. Normally, programmers must edit an application's source in order to adapt it for reuse in some new context where the interfaces fail to match exactly (e.g. the parameters may appear in a different order, data types may not exactly match, and some data may need to be either initialized or masked out when the reusable module is integrated within a new application.) But Nimble allows programmers to adapt the interfaces of existing software without having to operate on the source manually. As a result, existing software may be easily reused in a broader range of applications, and software libraries do not need to store many variants of a component that differ only in how the interfaces are used. Nimble has been implemented on a variety of Unix hosts, and is part of a broader reuse project at the University of Maryland. Our current system is suitable for use either in conjunction with existing module interconnection languages, or stand‐alone with C, Pascal and Ada source programs.
An experiment with inline substitution
Authors: Cooper Keith D. , Hall Mary W. , Torczon Linda
Published: November 2006

This paper describes an experiment undertaken to evaluate the effectiveness of inline substitution as a method of improving the running time of compiled code. Our particular interests are in the interaction between inline substitution and aggressive code optimization. To understand this relationship, we used commercially available FORTRAN optimizing compilers as the basis for our study. This paper reports on the effectiveness of the various compilers at optimizing the inlined code. We examine both the runtime performance of the resulting code and the compile‐time performance of the compilers. This work can be viewed as a study of the effectiveness of inlining in modern optimizers; alternatively, it can be viewed as one data point on the overall effectiveness of modern optimizing compilers. We discovered that, with optimizing FORTRAN compilers, (1) object‐code growth from inlining is substantially smaller than source‐code growth, (2) compile‐time growth from inlining is smaller than source‐code growth, and (3) the compilers we tested were not able to capitalize consistently on the opportunities presented by inlining.
Reflection mechanisms for combining prolog databases
Authors: Lamma Evelina , Mello Paola , Natali Antonio
Published: November 2006

By using practical examples, this paper outlines the power of reflection mechanisms for logic programming systems in the domain of knowledge structuring. In particular, it presents an extension of Prolog, where separate databases can be handled as first‐class objects. Different forms of database combination such as inheritance and dynamic context extension/contraction are specified and implemented in a dynamic and flexible way through reflection. The main aim is to broaden the application area of logic programming to encompass most of the paradigms needed by systems that use artificial intelligence techniques. Practical results presented in the paper show that logic programs that use reflection can be shorter, more readable and efficient than those using more conventional full meta‐interpretation techniques. Full meta‐interpretation, however, is more general than reflection.
The design of an operating system for a scalable parallel computing engine
Authors: Austin Paul , Murray Kevin , Wellings Andy
Published: November 2006

There are substantial benefits to be gained from building computing systems from a number of processors working in parallel. One of the frequently‐stated advantages of parallel and distributed systems is that they may be scaled to the needs of the user. This paper discusses some of the problems associated with designing a general‐purpose operating system for a scalable parallel computing engine and then describes the solutions adopted in our experimental parallel operating system.

We explain why a parallel computing engine composed of a collection of processors communicating through point‐to‐point links provides a suitable vehicle in which to realize the advantages of scaling. We then introduce a parallel‐processing abstraction which can be used as the basis of an operating system for such a computing engine. We consider how this abstraction can be implemented and retain the ability to scale. As a concrete example of the ideas presented here we describe our own experimental scalable parallel operating‐system project, concentrating on the Wisdom nucleus and the Sage file system. Finally, after introducing related work, we describe some of the lessons learnt from our own project.
Implementing dynamic minimal‐prefix tries
Authors: Dundas John A.
Published: November 2006

A modified trie‐searching algorithm and corresponding data structure are introduced which permit rapid search of a dictionary for a symbol or a valid abbreviation. The dictionary‐insertion algorithm automatically determines disambiguation points, where possible, for each symbol. The search operation will classify a symbol as one of the following: unknown (i.e. not a valid symbol), ambiguous (i.e. is a prefix of more than one valid symbol) or known. The search operation is performed in linear time proportional to the length of the input symbol, rather than the complexity of the trie. An example implementation is given in the C programming language.
An experimental investigation of distributed matrix multiplication techniques
Authors: Rees Stephen A. , Black James P.
Published: November 2006

This paper discusses the development and refinement of several distributed matrix multiplication algorithms. Our goal in this research has been to determine if successful distribution of this problem is possible within a loosely‐coupled environment. Our criteria for success are fast execution speed and, to a lesser extent, memory efficiency.

Our results indicate that, perhaps counter‐intuitively, it is possible to use distribution to improve the performance of dense matrix multiplication. The speed increase obtained ranges up to a factor of four, depending upon the algorithm and the process configuration used. Among the factors affecting performance are computational complexity, number and size of interprocess messages, and bookkeeping overhead. We conclude that this approach to matrix multiplication has potential. Furthermore, some of the principles discussed here may be usefully employed in the distribution of other algorithms of the same O(n3) computational complexity, such as LU decomposition (linear system solvers) and Cholesky factorization.
Experiments with a very fast substring search algorithm
Authors: Smith P. D.
Published: November 2006

Sunday devised string matching methods that are generally faster than the Boyer‐Moore algorithm. His fastest method used statistics of the language being scanned to determine the order in which character pairs are to be compared. In this paper the performances of similar, but language‐independent, algorithms are examined. Results comparable with language‐based algorithms can be achieved with an adaptive technique. In terms of character comparisons, a faster algorithm than Sunday's is constructed by using the larger of two pattern shifts.
Path testing of computer programs with loops using a tool for simple loop patterns
Authors: White Lee J. , Wiszniewski Bogdan
Published: November 2006

The purpose of this paper is to present a method for testing computer programs with iteration loops. Given such programs, we have shown that for classes of program paths, identified assequences of simple loop paths, there is a characterizing function called asimple loop pattern. The key idea of simple loop patterns is that these special functions form a base set which can represent any path computation in the given program. A software tool called SILOP has been developed to automatically generate these simple loop patterns, and each corresponding sequence of simple loop paths can be considered as a test case. The tester uses each test case, and with knowledge of the application program, can generate corresponding test data. This paper also presents a method for selecting the specific paths and test data to determine the simple loop pattern reliably. The tester can use this selection method to predict the number of tests required. In order to apply this selection method, the given program must be alinear computer program. The SILOP tool and this test selection method have been applied to commercial software; in this paper, this computational experience is reported and several examples are given to demonstrate the approach.
Operational definitions for system requirements as the basis of design automation
Authors: Lor Kar‐Wing Edward
Published: November 2006

This paper introduces formal definitions to system requirements as the basis of design automation. Semi‐formal requirements for real‐time systems are expressed in the form of system verification diagrams, and the graph model of behaviour represents the design, capturing three aspects of system behaviour—control, data and interpretation. The design model is consideredoperationalas an underlying token machine governs its actual behaviour. To achieve automatic design synthesis, the semantics of each construct in the requirement model have to be formally defined. These definitions constitute the core of a knowledge base in an automatic design synthesis tool.
A note on searching in a binary search tree
Authors: Andersson Arne
Published: November 2006

An algorithm for searching in a binary search tree using two‐way comparisons is presented. The number of comparisons required by this algorithm is only one more than when using three‐way comparisons. Since most high‐level programming languages do not supply three‐way comparisons, the number of comparisons used de facto is reduced by a factor of two. We give experimental results to indicate the speed‐up that may be achieved by the presented algorithm.
Graph drawing by force‐directed placement
Authors: Fruchterman Thomas M. J. , Reingold Edward M.
Published: November 2006

We present a modification of the spring‐embedder model of Eades [Congressus Numerantium, 42, 149–160, (1984)] for drawing undirected graphs with straight edges. Our heuristic strives for uniform edge lengths, and we develop it in analogy to forces in natural systems, for a simple, elegant, conceptually‐intuitive, and efficient algorithm.
A cached WORM file system
Authors: Quinlan Sean
Published: November 2006

This paper describes a general‐purpose file system that uses a write‐once‐read‐many (WORM) optical disk accessed via a magnetic disk cache. The cache enables blocks to be modified a number of times before they are written to the WORM and increases performance. Snapshots of the file system can be made at any time without limiting the users' access to files. These snapshots reside entirely on the WORM, are accessible to the user via a second read‐only file system, do not contain multiple copies of unchanged data, and can be used to rebuild the file system in the event that the disk cache is destroyed. The file system has been implemented as part of Plan 9, an experimental operating system under development at AT&T Bell Laboratories.