bluuebunny/crossref_metadata_2025_split huggingface dataset:
Modularity of computer languages
Authors: Beech David 
Published: November 2006

AbstractAccepting the coexistence of a variety of computer languages as a fact of life, this paper seeks to make a virtue of necessity by proposing a modular framework within which these languages can be used. Examples of the types of languages considered are command languages, programming languages, data manipulation and definition languages, data communication languages and text editor languages.Aspects of syntactic modularity and semantic modularity are distinguished, and some answers to difficult questions are suggested, leading to a proposal for specific RUN and EXECUTE constructs that should be made widely available. Discussion is mainly at the level of the visible and conceptual concerns of the end user and the system architect, but the actual implementation of interconnection mechanisms is not totally ignored.A tutorial outline is offered as an indication of how the underlying ideas might be introduced to non‐specialists, and might even become a part of elementary education.
A machine‐independent approach to microprogram synthesis
Authors: Mezzalama M. , Prinetto P. 
Published: November 2006

AbstractThe paper addresses the problem of automating microprogram generation, starting from a high‐level language (namely from a subset of PL/1). The microprogram synthesis process is structured in four steps in a highly hierarchical way; each step may be viewed as an independent process which uses formal representations for both data (i.e. the input program) and machine specifications. The translation system is based on a microcode model built on a formal definition of microoperations, microinstruction semantics, and relationships among microinstructions.
The design and implementation of a code generation tool
Authors: Akin T. Allen , Leblanc Richard J. 
Published: November 2006

AbstractA practical approach to the development of a high‐quality, re‐usable code generator is described in this paper. This code generator produces code for the Prime 64V mode architecture, but the methodology used is generally applicable to the construction of compilers for most architectures. The code generator accepts a tree‐structured intermediate form, linearized and represented as a file of integers. This intermediate form uses high‐level operators, minimizing work by compiler front‐ends that use it and providing a number of advantages in the code generation process. The output of the code generator is assembly language. This tool was found to considerably extend the capabilities of students in a graduate compiler class and has been used in the construction of Pascal and C compilers.
A costing model for software conversions
Authors: Wolberg John R. 
Published: November 2006

AbstractIn this paper a cost model for software conversion projects is developed. The model is based upon three variable parameters: L (thousands of lines of source code), N (the total number of programs being converted) and E (the conversion software inefficiency). All other parameters included in the model are constant coefficients which can vary from one type of conversion to another.An analysis of the resulting model yields four major conclusions: (1) There is an optimum investment that should be made in conversion software for each conversion project. (2) As the total number of lines to be converted increases, it is cost‐effective to increase the investment in conversion software. (3) If conversion software is reused for a second project, it is worthwhile to invest additional effort (and/or funds) in upgrading the software. (4) As the size of the conversion increases the cost per line decreases to a lower limit.
A file server for a network of low cost personal microcomputers
Authors: Dellar Carl N. R. 
Published: November 2006

AbstractThis paper describes a file server which was specifically designed to be the file store for a number of personal microcomputers attached to a local area network. In particular these personal machines (clients) have a very limited amount of memory with which to interface to the file server. The filing system supports an hierarchical directory structure with a simple capability‐like protection mechanism. Both the operations and communication protocol supported by the file server are chosen to make a client computer's interface code simple. Special attention is given to speeding up certain frequently used processor‐bound operations. Various aspects of the implementation are discussed, together with some suggested improvements.
The flat file system FFG: A database system consisting of primitives
Authors: Comer Ouglas 
Published: November 2006

AbstractFfg is a simple database system that consists of a set of many independent programs, called primitives, each of which performs a single operation. The user composes primitives by connecting the output of one to the input of the next to achieve a computation. Because they are independent, primitives are easily modified or replaced, and one can add programs to the set of primitives. Unlike the strongly typed interconnections provided by many languages, interconnections of ffg primitives are not type‐checked. The implementation ffg is also novel because ffg primitives are constructed out of lower level primitives instead of conventional programs. The selection of primitives, the type checking mechanism and the implementation are discussed.
A semi‐incremental garbage collection algorithm
Authors: Hughes R. J. M. 
Published: November 2006

AbstractLisp is restricted in application because of d the unpredictable delays introduced by garbage collection. Incremental garbage collectors eliminate the delays, but are less efficient overall. We present a semi‐incremental algorithm that reduces the delays and is, moreover more efficient than the mark‐scan algorithm from which it is derived. The mark‐scan algorithm is explained it consists of a mark phase followed by a sweep phase. The sweep phase can be performed incrementally, but the mark phase cannot. If this modification is made, our semi‐incremental algorithm is derived. Using the new algorithm the delay on garbage collection is proportional to the amount of heap actually in use, not the size of the heap. Allocating a cell takes a variable amount of time, depending on the proportion of the heap in use. Comparing the number of operations in the old and new algorithms, we see that the new algorithm is more efficient. The new algorithm was used as part of a Lisp implementation on an LSI‐11/03 and found to behave well.
Fast approximate string matching
Authors: Owolabi O. , McGregor D. R. 
Published: November 2006

AbstractApproximate string matching is an important operation in information systems because an input string is often an inexact match to the strings already stored. Commonly known accurate methods are computationally expensive as they compare the input string to every entry in the stored dictionary. This paper describes a two‐stage process. The first uses a very compact n‐gram table to preselect sets of roughly similar strings. The second stage compares these with the input string using an accurate method to give an accurately matched set of strings. A new similarity measure based on the Levenshtein metric is defined for this comparison. The resulting method is both computationally fast and storage‐efficient.
Process‐graph analyser: A front‐end tool for VHDL behavioural synthesis
Authors: Bhasker J. 
Published: November 2006

AbstractA front‐end of an electronic CAD synthesis system is described. The synthesis system accepts a behavioural description of a digital system design written in VHSIC Hardware Description Language (VHDL) and produces the physical hardware, at the register transfer level, needed for realizing the specified behaviour. The synthesis system comprises three major subsystems: process‐graph analyser, design representation and the MIMOLA synthesis system. The process‐graph analyser is an optimization and parallelization tool. We show how optimizing techniques used for compilers are adapted to perform a similar optimization function for hardware synthesis. We present techniques that extend the parallelization of the sequential programs concept for doing control state partitioning. The technique is new because of the unique synthesis model that MIMOLA uses. Finally, we show how to integrate these concepts using a suitable intermediate behavioural representation called the process graph.
A simple row‐replacement method
Authors: Miller Webb , Myers Eugene W. 
Published: November 2006

AbstractUpdating a video screen involves row replacement, i.e, the task of updating an existing screen row to produce the desired row. In many environments, screen operations require transmitting characters to the terminal by a process that is painfully slow compared to computing speeds. Thus, it is worth while to compute a minimal set of row updating commands, as long as the time to do so does not outweigh the savings in character transmission time. This paper presents a simple and practical algorithm for optimal row replacement and describes experience with its use in a screen editor.
Compiler support for floating‐point computation
Authors: Farnum Charles 
Published: November 2006

AbstractPredictability is a basic requirement for compilers of floating‐point code—it must be possible to determine the exact floating‐point operations that will be executed for a particular source‐level construction. Experience shows that many compilers fail to provide predictability, either because of an inadequate understanding of its importance or from an attempt to produce locally better code. Predictability can be attained through careful attention to code generation and a knowledge of the common pitfalls. Most language standards do not completely define the precision of floating‐point operations, and so a good compiler must also make a good choice in assigning precisions of subexpression computation. Choosing the widest precision that will be used in the expression usually gives the best trade‐off between efficiency and accuracy. Finally, certain optimizations are particularly useful for floating‐point and should be included in a compiler aimed at scientific computation. But predictability is more important than efficiency; obtaining incorrect answers fast helps no one.
PRESTO: A system for object‐oriented parallel programming
Authors: Bershad Brian N. , Lazowska Edward D. , Levy Henry M. 
Published: November 2006

AbstractPRESTO is a programming system for writing object‐oriented parallel programs in a multiprocessor environment. PRESTO provides the programmer with a set of pre‐defined object types that simplify the construction of parallel programs. Examples of PRESTO objects are threads, which provide fine‐grained control over a program's execution, and synchronization objects, which allow simultaneously executing threads to co‐ordinate their activities.The goals of PRESTO are to provide a programming environment that makes it easy to express concurrent algorithms, to do so efficiently, and to do so in a manner that invites extensions and modifications. The first two goals, which are the focus of this paper, allow a programmer to use parallelism in a way that is naturally suited to the problem at hand, rather than being constrained by the limitations of a particular underlying kernel or hardware architecture. The third goal is touched upon but not emphasized in this paper.PRESTO is written in C++; it currently runs on the Sequent shared‐memory multiprocessor on top of the Dynix operating system. In this paper we describe the system model, its applicability to parallel programming, experiences with the initial implementation, and some early performance measurements.
Dragonmail: An exercise in distributed computing
Authors: Peterson Larry L. 
Published: November 2006

AbstractA conversation‐based message system groups related messages into conversations and orders messages within conversations according to the context in which they were submitted. This paper describes the implementation of a comprehensive conversation‐based message system, called Dragonmail, that extends an earlier prototype in two ways. First, it integrates conversations with conventional memo‐based mail in a way that preserves the semantics of the conversation abstraction. Secondly, it provides for the distribution of software components across multiple hosts to support remote interfaces.
Garbage collection in an uncooperative environment
Authors: Boehm Hans‐Juergen , Weiser Mark 
Published: November 2006

AbstractWe describe a technique for storage allocation and garbage collection in the absence of significant co‐operation from the code using the allocator. This limits garbage collection overhead to the time actually required for garbage collection. In particular, application programs that rarely or never make use of the collector no longer encounter a substantial performance penalty. This approach greatly simplifies the implementation of languages supporting garbage collection. It further allows conventional compilers to be used with a garbage collector, either as the primary means of storage reclamation, or as a debugging tool.Our approach has two potential disadvantages. First, some garbage may fail to be reclaimed. Secondly, we use a ‘stop and collect’ approach, thus making the strategy unsuitable for applications with severe real‐time constraints. We argue that the first problem is, to some extent, inherent in any garbage collection system. Furthermore, based on our experience, it is usually not significant in practice. In spite of the second problem, we have had favourable experiences with interactive applications, including some that use a heap of several megabytes.
Profiling prolog programs
Authors: Debray Saumya K. 
Published: November 2006

AbstractProfilers play an important role in the development of efficient programs. Profiling techniques developed for traditional languages are inadequate for logic programming languages, for a number of reasons: first, the flow of control in logic programming languages, involving back‐tracking and failure, is significantly more complex than in traditional languages; secondly, the time taken by a unification operation, the principal primitive operation of such languages, cannot be predicted statically because it depends on the size of the input; and finally, programs may change at run‐time because clauses may be added or deleted using primitives such as assert and retract. This paper describes a simple profiler for Prolog. The ideas outlined here may be used either to implement a simple interactive profiler, or integrated into Prolog compilers.
Index preparation and processing
Authors: Chen Pehong , Harrison Michael A. 
Published: November 2006

AbstractIndex preparation is a tedious and time‐consuming task. This paper indicates how the indexing process can be automated in a way that is largely independent of a specific typesetting system and independent of the format being used. Fundamental issues related to this process are identified and analysed. Specifically, we develop a framework for placing index commands in the document. In addition, the design of a general‐purpose index processor that transforms a raw index into an alphabetized version is described. The resulting system has proved very useful and effective in producing indexes for several books, technical reports and manuals. A comparison of our system with indexing facilities available from a variety of other document preparation environments is given.
Indx and findphrases, a system for generating indexes for ditroff documents
Authors: Abe Kris K. , Berry Daniel M. 
Published: November 2006

AbstractCreating back‐of‐the‐book indexes is a difficult task involving intelligent and clerical processes. Programs have generally not achieved the level of intelligence required to perform the intelligent process of selecting terms for the index. Semi‐automatic indexing programs perform the clerical process of preparing entries once the terms have been selected. The programs do not provide assistance in term determination and most require flooding the text with indexing commands. indx differs from other semi‐automatic indexing programs mainly because it does not require the insertion of indexing commands into the text to be indexed. The method by which indx assists in the creation of an index is introduced and compared with the characteristics of the other programs. This method includes the use of a program that aids the term determination process. The design, implementation, and application of indx are presented. Areas in which indx may be improved or enhanced are identified. An index of this paper created with indx is included as an example.
Portrep: A portable repeated string finder
Authors: Jones Leslie P. , Gassie Edward W. , Radhakrishnan Sridhar 
Published: November 2006

AbstractIn recent years, several authors have presented algorithms that locate instances of a given string, or set of strings, within a text. Recently, authors have given less consideration to the complementary problem of processing a text to find out what strings appear in the text, without any preconceived notion of what strings might be present. A system called PATRICIA, which was developed two decades ago, is an implementation of a solution to this problem. The design of PATRICIA is very tightly bound to the assumptions that individual string elements are bits and that the user of the system can provide complete lists of starting and stopping places for strings. This paper presents an approach that drops these assumptions. Our method allows different definitions of indivisible string elements for different applications, and the only information the user provides for the determination of the beginning and ends of strings is a specification of a maximum length for output strings.This paper also describes a portable C implementation of the method, called PORTREP. The primary data structure of PORTREP is a trie represented as a ternary tree. PORTREP has a method for eliminating redundancy from the output, and it can function with a bounded number of nodes by employing a heuristic process that reuses seldom‐visited nodes. Theoretical analysis and empirical studies, reported here, give confidence in the efficiency of the algorithms. PORTREP has the ability to form the basis for a variety of text‐analysis applications, and this paper considers one such application, automatic document indexing.
The performance of the Amoeba distributed operating system
Authors: Van Renesse Robbert , Van Staveren Hans , Tanenbaum Andrew S. 
Published: November 2006

AbstractAmoeba is a capability‐based distributed operating system designed for high‐performance interactions between clients and servers using the well‐known RPC model. The paper starts out by describing the architecture of the Amoeba system, which is typified by specialized components such as workstations, several services, a processor pool, and gateways that connect other Amoeba systems transparently over wide‐area networks. Next the RPC interface is described. The paper presents performance measurements of the Amoeba RPC on unloaded and loaded systems. The time to perform the simplest RPC between two user processes has been measured to be 1‐4 ms. Compared to SUN 3/50's RPC, Amoeba has one ninth of the delay, and over three times the throughput. Finally we describe the Amoeba file server. The Amoeba file server is so fast that it is limited by the communication bandwidth. To the best of our knowledge this is the fastest file server yet reported in the literature for this class of hardware.
Improved string searching
Authors: Baeza‐Yates Ricardo A. 
Published: November 2006

AbstractWe show that it is possible to improve the average time of the Boyer‐Moore string matching algorithm using more space. This is accomplished by applying a transformation that virtually increases the size of the alphabet in use. The improvement is such that for long patterns it is possible to obtain an algorithm more than 50 per cent faster than the original one. We include experimental results on random and English text. Some improvements for searching on English text are also discussed.
User‐adaptable prettyprinting
Authors: Blaschek G. , Sametinger J. 
Published: November 2006

AbstractThis paper presents a prettyprinter for high‐level languages that can be adapted to the personal preferences of an individual user or to particular project conventions. The customization of the prettyprinter is done by means of a user profile with a set of parameters. The available parameters have been chosen with respect to minimality of the user interface and reasonable flexibility. The paper includes a complete list of all parameters with examples. The prettyprinter is fairly portable; it consists of a language‐independent back end and a front end that is created by a compiler generator from a formal description of the language to be processed. Currently, Modula‐2 and Pascal versions of the prettyprinter have been implemented.
The Elmwood multiprocessor operating system
Authors: Leblanc Thomas J. , Mellor‐Crummey John M. , Gafter Neal M. , Crowl Lawrence A. , Dibble Peter C. 
Published: November 2006

AbstractElmwood is an object‐oriented, multiprocessor operating system designed and implemented during a graduate seminar. It consists of a minimal kernel and a collection of user‐implemented services. The kernel provides two major abstractions:objects, which consist of code and data, and processes, which represent asynchronous activity. Objects, like programs, are passive. To operate on an abstraction or to request a service, processes invoke anentry proceduredefined by the corresponding object. Objects implement their own protection and synchronization policies using minimal kernel mechanisms. We describe the Elmwood kernel interface, an implementation on the BBN Butterfly parallel processor, and our experiences in developing a multiprocessor operating system under rigid time constraints. These experiences illustrate several general lessons regarding kernel design and trade‐offs for implementation expedience.
Complexity measurement of a graphical programming language
Authors: Henry Sallie , Goff Roger 
Published: November 2006

AbstractFor many years the software engineering community has been attacking the software reliability problem on two fronts. First via design methodologies, languages and tools as a pre‐check on complexity and secondly by measuring the complexity of produced software as a post‐check. This research attempts to unify the approach to creating reliable software by providing the ability to measure the complexity of a design prior to its implementation.We have successfully defined and applied software metrics to graphical designs in an effort to predict software complexity early in the software life cycle. Metric values from the graphical design are input to predictor equations, provided in this paper, to give metric values for the resultant source code.
A selection algorithm with a practical upper bound on expected number of comparisons
Authors: Park Jong Soo , Kim Myunghwan 
Published: November 2006

AbstractA selection algorithm to find the Irth smallest element of a elements is presented. The algorithm mainly consists of the partition procedure and an improved method to choose a partitioning element. The algorithm estimates the partitioning element from a small sample so that the icth element is contained in the smaller partition between two partitions resulting from partitioning. The partitioning element is determined by using estimation of the cumulative frequency distribution in the theory of non‐parametric statistics. The expected number of comparisons is found to be n + min(k, n‐k) + O(n2/3) through experimental tests where the sample size is approximately n2/3. The experimental results show that the performance of the algorithm is improved, compared to the two known selection algorithms, particularly when the selection index is near to the median.