bluuebunny/crossref_metadata_2025_split huggingface dataset:
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

AbstractIn 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

AbstractThe 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

AbstractMany 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

AbstractCode 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

AbstractWe 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

AbstractIn 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

AbstractLANSF 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

AbstractEmerald 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

AbstractWe 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

AbstractProgramming 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

AbstractThis 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

AbstractThis 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

AbstractThis 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

AbstractBy 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

AbstractThere 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

AbstractA 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

AbstractThis 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

AbstractSunday 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

AbstractThe 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

AbstractThis 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

AbstractAn 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

AbstractWe 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

AbstractThis 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.
Software reverse engineering: A case study
Authors: Byrne Eric J. 
Published: November 2006

AbstractThis paper presents lessons learned from an experiment to reverse engineer a program. A reverse engineering process was used as part of a project to develop an Ada implementation of a Fortran program and upgrade the existing documentation. To accomplish this, design information was extracted from the Fortran source code and entered into a software development environment. The extracted design information was used to implement a new version of the program written in Ada. This experiment revealed issues about recovering design information, such as, separating design details from implementation details, dealing with incomplete or erroneous information, traceability of information between implementation and recovered design, and re‐engineering. The reverse engineering process used to recover the design, and the experience gained during the study are reported.