bluuebunny/crossref_metadata_2025 huggingface dataset:
A communicating sequential process language and implementation
Authors: Roper T. J. , Barter C. J.
Published: November 2006

The design of a communicating sequential process language is presented, featuring a parallel command, communication by message passing and the use of the guarded command as a means of introducing and controlling non‐determinism. The language described here incorporates a number of new proposals regarding communications between sequential processes. The principal proposal is that messages are to be selected for reception by a receiving process solely on the basis of their type and arrival order within type; in particular, the identity of the sending process does not influence message reception. This results in a greater degree of parallelism and non‐determinism, which is useful to both the programmer and the language implementor. Also a hierarchichal composition regime is proposed, which gives communications significance to the organization of subprocess hierarchies; this promotes an independence of specification of program components through information hiding properties. The language implementation is described, and several aspects are of particular interest: the design of a process scheduler in a non‐deterministic situation leads to some interesting optimizations, as does the design of a message handler in the case where the communicating processes can access the same memory. Finally, example programs are given to illustrate some of the novel features of the language.
Cheap concurrent programming
Authors: Ben‐Ari Mordechai
Published: November 2006

A system for class exercise of concurrent programming is described. The system is very simple and easy to implement yet it can demonstrate the basic concepts of concurrent programming. A detailed description of the implementation is given to enable others to adapt the system with minimal effort.
Files in an interactive environment
Authors: Orgass Richard J.
Published: November 2006

A well designed file system can significantly simplify the design of and increase the reliability of interactive programs. A summary of the specifications of a convenient file system that is substantially independent of the host operating system and some experiences using the system are described.
Modular programming with Pascal
Authors: Steensgaard‐Madsen J.
Published: November 2006

A technique is presented by which the programming language Pascal as defined by the expected standard, can be used to write programs divided into modules containing mutually hidden information. The technique fits nicely with the programming by stepwise refinement methodology, combines top‐down and bottom‐up methods, and illustrates that stepwise refinement does not necessarily lead to simple tree‐like programs. Limitations for the application of the technique with Pascal are pointed out.
Sorting unsorted and partially sorted lists using the natural merge sort
Authors: Harris James D.
Published: November 2006

A version of the natural merge sort is shown to be an efficient method for both nearly sorted data and for random data. This method is compared with quickersort, 2‐way merge sort, and Cook and Kim's method for various sortedness ratios.
The practicality of text signatures for accelerating string searching
Authors: Tharp Alan L. , Tai Kuo‐Chung
Published: November 2006

This paper studies the use of text signatures in string searching. Text signatures are a coded representation of a unit of text formed by hashing substrings into bit positions which are, in turn, set to one. Then instead of searching an entire line of text exhaustively, the text signature may be examined first to determine if complete processing is warranted. A hashing function which minimizes the number of collisions in a signature is described. Experimental results for two signature lengths with both a text file and a program file are given. Analyses of the results and the utility and application of the method conclude the discussion.
The syntax of interactive command languages: A framework for design
Authors: Hardy I. Trotter
Published: November 2006

Various qualities of simple command languages, such as ease of use and flexibility, are defined in terms of syntax. Certain design attributes—namely style, structure and level of abstraction—are described for command languages, and these attributes are shown to strongly influence the defined qualities. Commands are designed for three functions to show how the design trade‐offs are made in light of the qualities and attributes discussed.
Real‐time checkout: The ‘source error first’ approach
Authors: Glass Robert L.
Published: November 2006

This paper proposes some improvements to the archaic methodologies currently used for checkout of real‐time software. The emphasis is placed on removing errors from the computer program source code in the host computer environment, and deferring target computer checkout until those errors have been largely removed. Specific tools and techniques to make this possible are described. This improvement is seen to be risk‐free and to reduce cost. It is, however, controversial.
Time token design methodology
Authors: Celko Joe
Published: November 2006

A program design methodology is proposed and an example is given using it for a small inventory system.

The method depends on viewing a problem in terms of tokens that carry date information. This date information gives the date of the creation, and exit of the token from the active system. The source of creation and the place of exit are also coded into the token.

The method is most useful in an environment that has time‐dependent, on‐line interactive processing.
Immediate turnround—an elusive goal
Authors: Newbury J. P.
Published: November 2006

This paper, inspired by the work of Larmouth,1 describes a job scheduler now in service on an ICL 1906A with the GEORGE 4 Operating System. The main goals were to apply a smooth control of machine usage, enabling users to run work at rates proportional to their shares without any sharp cut‐off; to maximize the amount of work achieving very fast turnround; to provide predictable turnround; to allow users some control over turnround; to eliminate cheating; to be easy to understand and use. An outline of our method is given together with a discussion of some of the practical and theoretical problems with this sort of approach.
Executing large graphics programs with a small computer
Authors: Van Tilborg Andrè M.
Published: November 2006

This article describes a simple graphics compiler which allows the owner of a personal computer system with a graphics display and access to a larger computer to execute large application programs remotely but still use his display as though the programs were running locally. Simple graphics primitives and the program structures used to implement them are discussed. The compiler includes a simple packet switching subsystem which allows display data to be transmitted over the telephone network.
Modularity of computer languages
Authors: Beech David
Published: November 2006

Accepting 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 robust distributed solution to the dining philosophers problem
Authors: Cargill T. A.
Published: November 2006

A distributed solution to Dijkstra's ‘Dining Philosophers’ problem is presented. There is no central synchronization mechanism and it is robust in that the impact of failures is local. The solution is amenable to implementation using a wide class of synchronization primitives. A concrete implementation is presented in Ada.
A machine‐independent approach to microprogram synthesis
Authors: Mezzalama M. , Prinetto P.
Published: November 2006

The 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

A 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

In 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

This 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

Ffg 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

Lisp 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

Approximate 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

A 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

Updating 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.
The programming language oberon
Authors: Wirth N.
Published: November 2006

This is the defining report of the programming language Oberon.
Compiler support for floating‐point computation
Authors: Farnum Charles
Published: November 2006

Predictability 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

PRESTO 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

A 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

We 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

Profilers 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

Index 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

Creating 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

In 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

Amoeba 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

We 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.
Using sentinels in insert sort
Authors: Thimbleby Harold
Published: November 2006

The inner loop of insert sort can be simplified by using a sentinel value. We suggest a way of avoiding the extra storage normally required for the sentinel, and a way of avoiding the prior, and possibly restrictive, choice of its value. Algorithms are given in Pascal.
User‐adaptable prettyprinting
Authors: Blaschek G. , Sametinger J.
Published: November 2006

This 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

Elmwood 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.
Generic parameters in Occam
Authors: Wilson G. A.
Published: November 2006

Simple extensions to Occam procedure parameter mechanisms are proposed that reduce some of the cumbersome nature of the language. The extensions are a GENERIC formal parameter type and associated TYPEOF construct and ISTYPE operator, and facility for a LIST of parameters. The features are illustrated using simple input/output procedures based on the equivalent Pascal procedures.
Complexity measurement of a graphical programming language
Authors: Henry Sallie , Goff Roger
Published: November 2006

For 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

A 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.
Parallel algorithm design for workstation clusters
Authors: Magee J. N. , Cheung S. C.
Published: November 2006

Clusters of workstations connected by local area networks are in common use in many organizations. The combined processing power of these clusters is rarely exploited owing to the lack of suitable parallel algorithms. The paper describes a parallel programming paradigm calledsupervisor‐worker, suitable for the workstation environment, which can be used to speed up the execution of a large class of existing sequential programs. Simple formulae are developed to predict the speed‐up of a parallel algorithm developed in this way. The predictions depend on two easily‐determined parameters of the sequential program and the characteristic communication cost of the workstation cluster. Consequently, it is possible to estimate the benefits of the parallel program before proceeding with detailed implementation. As an example, the parallel version of a travelling salesman program is developed and the measured speed‐up compared with the predicted speed‐up.
A syntax‐directed integrated programming environment for developing simd supercomputer software
Authors: Perrott R. H. , Lunney T. F.
Published: November 2006

The increasing availability and use of supercomputers has highlighted the need for better software development techniques and tools. Supercomputers have traditionally been extensively used by engineers and scientists whose preference for Fortran is well established and recognized. However, in the parallel environment offered by the latest configurations of supercomputers, more sophisticated languages and tools are required. The present experiment is concerned with devising a syntax‐directed integrated programming environment based on the language Actus, which enables a user to develop and debug programs before submitting them to an actual supercomputer. Actus is a high‐level, Pascal‐like language, with SIMD parallel processing features. It enables the user to ignore the idiosyncrasies of the chosen supercomputer by abstracting the parallel processing detail to a higher level. The editing, compilation and testing phases of program development are all integrated, providing a single consistent interface for all activities relating to program development.
Performance of lazy combinator graph reduction
Authors: Hartel Pieter H.
Published: November 2006

The performance of program‐derived combinator graph reduction is known to be superior to that of graph reduction based on a fixed set of standard combinators. The major advantage of program‐derived combinator reduction is that it uses less transient store than standard combinator reduction. We show on what activities a combinator reduction algorithm spends its execution time. Based on this analysis we show that it depends to a large extent on the application how much faster a program will run if program‐derived combinators are used instead of standard combinators. The analysis is based on experimental evidence obtained from a small bench‐mark of medium‐size functional programs. Performance gains of up to 11 x are reported for target architectures on which each memory reference consumes one unit of time. The results are valid for implementations of combinator graph reduction that use binary graphs.
A parallel implementation of the douglas‐peucker line simplification algorithm
Authors: Vaughan Jon , Whyatt Duncan , Brookes Graham
Published: November 2006

As parallel machines become more widely available, many existing algorithms are being converted to take advantage of the improved speed offered by such computers. However, the method by which the algorithm is distributed is crucial towards obtaining the speed‐ups required for many real‐time tasks. This paper presents three parallel implementations of the Douglas—Peucker line simplification algorithm on a Sequent Symmetry computer and compares the performance of each with the original sequential algorithm.
An approach to genuine dynamic linking
Authors: Ho W. Wilson , Olsson Ronald A.
Published: November 2006

This paper describes a new approach to dynamic link/unlink editing. The basis of this approach is a library of link editing functions that can add compiled object code to or remove such code from a process any time during its execution. Loading modules, searching libraries, resolving external references, and allocating storage for global and static data structures are all performed at run time. This approach provides the efficiency of native machine code execution along with the flexibility to modify a program during its execution, thereby making many new applications possible. This paper also describes three sample applications of these dynamic link editing functions: program customization, incremental program development, and support for debugging and testing. A prototype of this approach is implemented under UNIX as a library package called dld for the C programming language and is available for VAX, Sun 3 and SPARCstation machines.
Reactive C: An extension of C to program reactive systems
Authors: Boussinot Frédéric
Published: November 2006

Reactive systems are interactive programs that react continuously to sequences of activations coming from the external world. Reactive programming leads to a new programming style where one programs in terms of reactions to activations and reasons in a logic of instants. This paper describes an extension of the C programming language called RC (for ‘Reactive C’) to program reactive systems. The language RC is described, then some programming examples are given to illustrate the reactive approach. The main RC notions come directly from the Esterel synchronous programming language. Finally, the Esterel and RC languages are compared.
Utility servers in charlotte
Authors: Yang Cui‐Qing , Finkel Raphael
Published: November 2006

Most distributed operating systems are built with a kernel replicated in each machine that supports only basic interprocess communication (IPC) and process control. All other system services, such as memory management, file system, and name service, are distributed in a set of utility servers, which are ordinary processes (except perhaps for some privileges) residing at various machines. Design and implementation of such utility servers in distributed environments are far different from those in a centralized system.

This paper presents our experience in building utility servers in Charlotte, a message‐based distributed operating system running on a loosely‐coupled multicomputer. Utility services in Charlotte are provided by server squads. Each member in a squad covers services to its own community. The squad as a whole co‐operatively provides services to the entire system. These servers are designed with the goals of simplicity, efficiency and robustness. They are intended to support a multiprogramming system for the development of distributed algorithms and other distributed applications. We address several major issues in developing a utility server, including the server structure, the management of message buffers, deadlock, and the robustness of server processes. Several utility servers in the Charlotte system are discussed as real examples.
A modular fully‐lazy lambda lifter in Haskell
Authors: Jones Simon L. Peyton , Lester David
Published: November 2006

An important step in many compilers for functional languages is lambda lifting. In his thesis, Hughes showed that by doing lambda lifting in a particular way, a useful property called full laziness can be preserved. Full laziness has been seen as intertwined with lambda lifting ever since.

We show that, on the contrary, full laziness can be regarded as a completely separate process to lambda lifting, thus making it easy to use different lambda lifters following a full‐laziness transformation, or to use the full‐laziness transformation in compilers which do not require lambda lifting.

On the way, we present the complete code for our modular fully‐lazy lambda lifter, written in the HASKELL functional programming language.
A fortran language system for mutation‐based software testing
Authors: King K. N. , Offutt A. Jefferson
Published: November 2006

Mutation analysis is a powerful technique for testing software systems. The Mothra software testing project uses mutation analysis as the basis for an integrated software testing environment. Mutation analysis requires executing many slightly differing versions of the same program to evaluate the quality of the data used to test the program. The current version of Mothra includes a complete language system that translates a program to be tested into intermediate code so that it and its mutated versions can be executed by an interpreter.

In this paper, we discuss some of the unique requirements of a language system used in a mutation‐based testing environment. We then describe how these requirements affected the design and implementation of the Fortran 77 version of the Mothra system. We also describe the intermediate language used by Mothra and the features of the language system that are needed for software testing. The appendices contain a full description of the intermediate language and the mutation operators used by Mothra.

The design and implementation techniques that were developed for Mothra are applicable for constructing not just software testing systems, but any type of program analysis system or language system for a special‐purpose application. In particular, we discuss decisions made and techniques developed by the Mothra team that can be useful in such applications as debuggers, program measurement tools, software development environments and other types of program analysis systems.
Tlex
Authors: Kearns Steven M.
Published: November 2006

TLex is a pattern matching and parsing library for C++. In comparison to existing pattern matching tools, TLex sets a new standard for expressiveness when nearly optimal speed is required. It incorporates recent advances in regular expression technology that make it easier to write patterns and extract information from a successful match. An overview of TLex is presented, the pattern and parsing languages are described, and actual results of its use are discussed.
A methodology for constructing predicate transition net specifications
Authors: He Xudong , Lee John A. N.
Published: November 2006

In this paper, a methodology for constructing hierarchical and structured predicate transition net specifications is developed, which includes new systematic notation extensions for supporting various transformation techniques upon predicate transition nets and several rules for applying such transformation techniques. The levelling technique in data‐flow diagrams is adapted in the refinement and the abstraction techniques, and the state decomposition idea in state‐charts is employed in designing various label formulation operators. The methodology is illustrated through the specification of a lift system. The methodology can significantly reduce the constructing complexity and enhance the comprehensibility of large predicate transition net specifications.
A code generation interface for ANSI C
Authors: Fraser Christopher W. , Hanson David R.
Published: November 2006

1cc is a retargetable, production compiler for ANSI C; it has been ported to the VAX, Motorola 68020, SPARC, and MIPS R3000, and some versions have been in use for over a year and a half. It is smaller and faster than generally available alternatives, and its local code is comparable. This paper describes the interface between the target‐independent front end and the target‐dependent back ends. The interface consists of shared data structures, a few functions, and a dag language. While this approach couples the front and back ends tightly, it results in efficient, compact compilers. The interface is illustrated by detailing a code generator that emits naive VAX code.
Administrators and multiprocessor rendezvous mechanisms
Authors: Gentleman W. Morven , Shepard Terry , Thoreson Douglas V. P.
Published: November 2006

This paper discusses rendezvous on multiprocessors. Three different approaches are compared, represented by three specific systems: Ada, Harmony and BNR Pascal. All three permit tasks to run on multiple processors and use blocking communications primitives, but there are significant differences. For example, control over replying to messages out of sequence and over the allocation of tasks to processors is omitted in Ada, but is available in Harmony. The approach represented by BNR Pascal follows a middle road between Harmony and Ada: a low level protocol, invisible to the programmer, is used to ensure communications reliability, but the programmer is aware of when a rendezvous is remote. If performance considerations and verbosity and robustness are ignored, all three approaches are equivalent. To illustrate this equivalence, and to demonstrate clearly the complexity of the Ada rendezvous, an Ada rendezvous administrator written using Harmony is described. A second method of adapting Harmony to Ada is also presented, in which the Harmony primitives are modified to be closer to Ada. In practice, using Harmony primitives directly will usually result in better programs. It is argued that something very much like the rendezvous adminstrator is needed for any actual implementation of the Ada rendezvous.
User interface—application communication in the Chimera user interface management system
Authors: Wood Catherine A. , Gray Philip D.
Published: November 2006

Until quite recently, perhaps the least appreciated part of user interface management system (UIMS) architecture has been the interface to the application. A number of approaches to interface‐application communication have been attempted, but these have suffered as a result of being non‐programmable, unstructured and/or static. This paper presents the user‐interface‐application communication system developed for the Chimera UIMS, which attempts to address these problems. This system enables interprocess communication between user interface and application via an explicit, programmable UIMS component—an application linkage, which is structured, dynamic and reconfigurable at run‐time. The internal structure of the linkage is described, along with the mechanism for communication with dialogue control and application. An extensive example is developed in order to illustrate the communication process to and from the user via dialogue control and linkage to the application.
μC++: Concurrency in the object‐oriented language C++
Authors: Buhr P. A. , Ditchfield Glen , Stroobosscher R. A. , Younger B. M. , Zarnke C. R.
Published: November 2006

We present a design, including its motivation, for introducing concurrency into C++. The design work is based on a set of requirements and elementary execution properties that generate a corresponding set of programming language constructs needed to express concurrency. The new constructs continue to support object‐oriented facilities such as inheritance and code reuse. Features that allow flexibility in accepting and subsequently postponing servicing of requests are provided. Currently, a major portion of the design is implemented, supporting concurrent programs on shared‐memory uniprocessor and mulitprocessor computers.
Adding run‐time checking to the portable C compiler
Authors: Steffen Joseph L.
Published: November 2006

Run‐time checking of array subscripts and pointer bounds was added to the Portable C Compiler (PCC). Memory overwrite bugs are then caught as they happen instead of when the overwritten memory is used later in the program execution. The run‐time checking compiler is used both to find the true cause of a core dump and to eliminate run‐time errors as the cause of unexpected program behavior. On average, it takes about 40 percent longer to compile, the generated code is about three times larger, and it runs about ten times slower. This performance may seem slow, but it typically reduces days of debugging to less than an hour. The implementation described herein can be adapted to any C compiler as it describes how to generate run‐time checking code in a machine/compiler independent way by changing the intermediate expression trees. In four years of use it has found latent bugs and the cause of intermittent core dumps in programs used for many years by thousands of people.