bluuebunny/crossref_metadata_2025 huggingface dataset:
An experiment with the interchangeability of processes and monitors
Authors: Stroustrup Bjarne
Published: November 2006

Two styles of operating system implementation based on the use of monitors and processes, respectively, are identified, and arguments for a basic equivalence of these systems despite large stylistic differences are presented. The ‘Lauer‐Needham Duality Hypothesis’ states that the two styles are equivalent, both in terms of ease of programming and in efficiency of the resulting systems. A domain for which the first part of this claim holds is outlined, and data affirming the essential equivalence of performance within that domain are presented. An operating system based on the Cambridge CAP system, called SIMOS, was simulated for a wide range of hardware configurations and job loads. SIMOS is written using a module concept that allows an individual module to be interpreted as a monitor in one run and as a process in another. Runs using a monitor to control access to some data can be compared with runs using a process to control access to the same data. The throughput and response time for the two styles of system were found to be identical in most cases. However, a degradation in response time occurred in a process‐based system when the job load and the low level scheduling policy were poorly matched.
A technique for subclassing and its implementation exploiting polymorphic procedures
Authors: Mancini Luigi V.
Published: November 2006

Since the introduction of Smalltalk, the object‐oriented approach towards the organization of data and programs has become popular. In this paper the possibilities of exploiting procedure‐oriented languages to allow an object‐oriented style of programming are analysed. Although the two approaches are apparently dissimilar, a family of procedure‐oriented languages is described which allows a high degree of freedom in programming and does not appear to restrain the programmer within the procedure‐oriented scheme. Popular languages of this family are ML and PS‐Algol. For such languages, a technique is developed which enables an efficient implementation of object‐oriented features, such as the subclassing form of inheritance provided by Smalltalk‐80 and Simula.
Edison‐N — an Edison implementation for a network of microcomputers
Authors: Dubnicki Cezary , Madey Jan , Wygla̧dała Wojciech
Published: November 2006

This paper describes an experimental implementation of the Edison programming language for a network of microcomputers based on the Z‐80 microprocessor. The resulting Edison‐N system allows parallel execution of concurrent processes. Its aim is to assist in teaching the principles of concurrent programming.
Structured FORTRAN preprocessors generating optimized output
Authors: Tsuji Tatsuo , Watanabe Katsumasa , Ikehata Atsushi
Published: November 2006

Usually a structured FORTRAN program is transformed into a standard FORTRAN program by means of a one‐pass preprocessor. In this case, several problems are caused by the many redundant continue and goto statements that a preprocessor generates. These problems include: (i) the generated FORTRAN program is not easy to read; (ii) the size of files to store the related programs becomes large; (iii) the total time increases for executing both the FORTRAN compiler and the output program itself.

This paper presents a new scheme for constructing a one‐pass preprocessor that generates the optimized FORTRAN code by suppressing the redundant statements. By employing this scheme we have constructed our own preprocessors for Westran (one of the Structured FORTRAN languages) and Ratfor and measured these against the traditional preprocessors for the Westran and Ratfor languages.

One of the results is as follows. The total time for users, namely ‘preprocessing time + FORTRAN compiling time’ is rather less than the traditional ones. This is due to the fact that to suppress the input/output of the redundant statements from/to files contributes to the decreasing of both preprocessing and compiling times, and this compensates completely the time‐overhead of the optimization process.
Inaccuracies in program profilers
Authors: Ponder Carl , Fateman Richard J.
Published: November 2006

Run‐time program profiling is a valuable tool in understanding software efficiency. Techniques for obtaining profiles make assumptions that may result in misleading data. In the paper we illustrate flaws in two profiling systems: the Unix ‘Gprof’ family (including the packages ‘monitor’, ‘prof’ and ‘profil’), and the TI Explorer metering package for Lisp.
A convenient way to incorporate semantic actions in two‐pass compiling schemes
Authors: Mössenböck H.
Published: November 2006

We present a simple method for connecting semantic actions to parsers. Although applicable to any kind of parser it is especially suited for LR parsers. The method is based on the idea of separating syntax analysis and semantic processing and executing semantic actions by procedures, similar to those of a recursive descent compiler. The procedures are driven by structural information about the source program, which is collected during parsing. The method is applicable to L‐attributed grammars. It can be incorporated easily into any existing parser.
Performance of multi‐tasking and synchronization mechanisms in the programming language SR
Authors: Atkins M. Stella , Olsson Ronald A.
Published: November 2006

High‐level language primitives for concurrent programming exist in languages such as Ada and Modula‐2. However, each of these languages provides only a single means for specifying multitasking and synchronization, essential in the implementation of concurrent systems. The SR language provides several mechanisms for specifying multi‐tasking and synchronization, so it can be used to explore the performance of various communication techniques.

This paper presents performance results for SR's multi‐tasking and synchronization mechanisms and discusses the effects of the generated code, the run‐time support and the hardware on these results. These results are compared with those for similar mechanisms in other languages, leading to some general conclusions about the performance of process communication primitives. These performance results can be used by programmers to make design choices that allow systems programs written in high‐level languages to meet real‐time performance specifications.
Independent testing of compiler phases using a test case generator
Authors: Homer William , Schooler Richard
Published: November 2006

Since a compiler phase depends on previous phases for input, it can be difficult to do timely independent unit testing of some phases. This can make integration more difficult and reduce overall quality. A test case generator has been used to circumvent this problem by providing an independent source of phase test inputs. Using a context‐free grammar augmented with contextsensitive constructs, a test case generator can generate intermediate language graphs in textual form.
Circular programs and self‐referential structures
Authors: Allison Lloyd
Published: November 2006

A circular program creates a data structure whose computation depends upon itself or refers to itself. The technique is used to implement the classic data structures circular and doubly‐linked lists, threaded trees and queues, in a functional programming language. These structures are normally thought to require updateable variables found in imperative languages. For example, a functional program to perform the breadth‐first traversal of a tree is given. Some of the examples result in circular data structures when evaluated. Some examples are particularly space‐efficient by avoiding the creation of intermediate temporary structures which would otherwise later become garbage. Lastly, the technique can be applied in an imperative language to give an elegant program.
Q'Nial: A portable interpreter for the nested interactive array language, Nial
Authors: Jenkins M. A.
Published: November 2006

The Q'Nial interpreter combines ideas from APL and Lisp implementations to provide a rich programming environment that supports several paradigms of programming. The interpreter is structured to reflect the division of Nial semantics into levels corresponding to zero‐, first‐and second‐order objects. The paper describes the design of the interpreter, discusses constraints imposed by the desire to achieve portability and comments on what has been learned in building an interpreter in this style.
The design and implementation of a version server for computer‐aided design data
Authors: Gedye David , Katz Randy H.
Published: November 2006

The Version Server is a system for managing the versions and configurations of design descriptions as they change over time. In this paper we focus on the design and implementation of such a system, which we have built at U.C. Berkeley. The data model supported and the browser application are introduced to illustrate the system's user and application interface. The design decisions and details of the internal architecture are described and the system's performance is evaluated. For structure‐oriented queries, such as ‘traverse an entire chip's design hierarchy’, the Version Server is about five times as fast as comparable design management systems that store their design objects as files in a hierarchical file system.
GMB: A tool for manipulating and animating graph data structures
Authors: Jablonowski David , Guarna Vincent A.
Published: November 2006

This paper describes a tool graph originally developed for the Faust environment. Faust is a scientific program development environment being implemented at the Center for Supercomputing Research and Development at the University of Illinois at Urbana‐Champaign. The graph tool comprises two major components: the Graph Manager that implements an abstract graph data type, and the Graph Browser that handles the details of displaying a subgraph of a graph created through the Graph Manager. The Graph Browser displays graph views, where a graph view is a subgraph of its parent graph. The concept of graph views is analogous to the concept of views in the traditional database sense. Several graph views may simultaneously exist for a single parent graph, where each view's subgraph depends on the context of the application requesting the view. Goals of the graph tool, GMB, included providing an abstract graph data type for general use and animating graphs efficiently.
A practical algorithm for evaluating database queries
Authors: De Vet John H. M.
Published: November 2006

This paper describes an algorithm for evaluating database queries represented as expressions in a logical language. Such a database query expression can be evaluated efficiently by focusing on the variable dependencies. The algorithm recursively computes the values of subexpressions to evaluate the input expression, but it avoids re‐evaluation of those subexpressions whose values are not affected by new variable assignments. The input expression is internally structured as a directed acyclic graph. Two additional techniques to improve efficiency of the evaluation are discussed: transformations of the input expression and special primitive database operations. Finally, its implementation in the natural language question‐answering system SPICOS is described.
Program tools for algorithm animation
Authors: Krishnamoorthy Mukkai S. , Swaminathan Ramesh
Published: November 2006

This paper proposes graphics primitives for constructing programs for algorithm animation. Our experiments show that these primitives can reduce program development time. Future directions of the current research is also discussed.
Semantic extension possibilities in the proposed new fortran
Authors: Schonfelder J. L.
Published: November 2006

The next revision of the standard Fortran language, commonly referred to as Fortran 8x, has now been published, at least in draft form. It is therefore possible for some of its new features to be investigated and the type of programming that can be expected when implementations appear to be explored. This paper looks at the scope provided by the proposed new features for 'semantic extension' of the language. The capability is illustrated by way of example code which could provide an extended‐precision numeric facility if implemented. The new linguistic constructs that permit this type of approach to software provision are described as they are used.
The Joyce language report
Authors: Hansen Per Brinch
Published: November 2006

This paper defines a programming language for distributed processing called Joyce. Joyce is based on CSP and Pascal. A Joyce program defines concurrent agents which communicate through synchronous channels. The agents may be recursive.
Allocation without locking
Authors: Appel Andrew W.
Published: November 2006

In a programming environment with both concurrency and automatic garbage collection, the allocation and initialization of a new record is a sensitive matter: if it is interrupted half‐way through, the allocating process may be in a state that the garbage collector cannot understand. In particular, the collector will not know which words of the new record have been initialized and which are meaningless (and unsafe to traverse).

For this reason, parallel implementations usually use a locking or semaphore mechanism to ensure that allocation is an atomic operation. The locking significantly adds to the cost of allocation. This paper shows how allocation can run extremely quickly even in a multi‐thread environment: open‐coded, without locking.
The parser generating system PGS
Authors: Klein E. , Martin M.
Published: November 2006

PGS is a parser generating system accepting LALR(1) and related grammars in extended BNF notation and producing parsers based on table‐driven stack automata. To enable syntax‐directed translation, semantic actions can be attached to rules of the input grammar. An attribution mechanism allows the transfer of information between rules. The generated parsers have an automatic error recovery which can be tailored to satisfy specific needs of the language to be accepted. PGS generates parsers written in Pascal, Modula‐2, C or Ada. Compared with existing systems, e.g. YACC1, a parser generated by PGS is twice as fast and the parse tables require 25 per cent less storage. This paper gives a survey of algorithms involved in the generator and the generated parsers, and compares them with algorithms used in other systems. In detail, it compares several parse‐table representations and their implications for space and time efficiency of the generated parsers.
Efficient generation of lexical analysers
Authors: Grosch J.
Published: November 2006

General tools for the automatic generation of lexical analysers such as LEX1 convert a specification consisting of a set of regular expressions into a deterministic finite automaton. The main algorithms involved are subset construction, state minimization and table compression. Even if these algorithms do not show their worst‐case time behaviour they are still quite expensive. This paper shows how to solve the problem in linear time for practical cases, thus resulting in a significant speed‐up. The idea is to combine the automaton introduced by Aho and Corasick2 with the direct computation of an efficient table representation. Besides the algorithm we present experimental results of the scanner generator Rex3 which uses this technique.
Converting a portable Pascal p‐code interpreter to a code generator
Authors: Schneider Victor
Published: November 2006

This is a technical note that assumes reader familiarity with Pagan's paper on converting scaled down Pascal p‐code programming language interpreters into simple compilers.1 This note discusses the extension of Pagan's methods to a full‐scale Pascal‐to‐C translator. In order to make procedure calls and typed function calls work properly for such a translator, it was found necessary to add type information to one of the p‐code calling instructions (and alter the Pascal‐to‐p‐code translator accordingly). A table of execution times for Pagan's ‘50 primes’ bench‐mark program shows the improvements obtained as a result of successive refinements in the Pascal‐to‐C translator, until the present version that uses C ‘register variables’ for integer arithmetic.2 Programs compiled using this system can also be linked into C programs as functions or procedures and can be debugged using standard C debuggers.
Vertical migration of numerical routines in software and microcode
Authors: Charlton C. C. , Leng P. H. , Little J.
Published: November 2006

Vertical migration is a widely acknowledged technique for improving the performance of critical sections of code. Migration may be to the assembly‐language level or, for machines with writable control store, into microcode. The former is easier to implement and allows a degree of portability, albeit limited, of the target routines, although performance gains may not be as great as those resulting from migration into microcode. The latter however, requires considerable programming effort and the size of available control store may well place restrictions upon the amount of code which can be migrated to this level. Given the task of improving the performance of a large software base, full migration is rarely practical, so time must be spent determining the best migration strategy for a ‘target set’ of critical routines.

In this paper, we report on work to improve, by vertical migration, the performance of the bask linear algebra subroutines of the FORTRAN NAG library. We identify a number of different migration strategies based upon the availability of two migration levels and report on the performance gains achieved by applying each of these strategies; various conditions under which each strategy may be most appropriate have thus been identified. In particular, this work shows how, by careful selection of just a small number of target routines, resulting performance gains can not only be significant for each individual routine, but also for the whole software system.
Building a real‐time kernel: First steps in validating a pure process/ADT model
Authors: Callison H. Rebecca , Shaw Alan C.
Published: November 2006

A model based on simple, unadorned processes and abstract data types has been proposed for the design and implementation of real‐time systems. We describe our generally successful experiences in using this model for the construction of a real‐time operating system kernel containing services for process control, synchronization, time and input‐output. Our work and results focus on the usefulness of the scheme for designing modules at hardware/software interfaces, for predicting deterministic timing behaviour, and for software development.
The design and implementation of a high‐level language converter
Authors: Moynihan Vincent D. , Wallis Peter J. L.
Published: November 2006

There is now a good understanding of problems encountered in the design, implementation and use of a high‐level language converter. These general issues are illustrated in terms of an account of the design and implementation of one particular converter, which converts programs from Pascal‐SC (a Pascal dialect) to Ada. A specific aim of the presentation is to provide guidance for those contemplating future language conversion projects.
An implementation of distributed shared memory
Authors: Ramachandran Umakishore , Khalidi M. Yousef A.
Published: November 2006

Shared memory is a simple yet powerful paradigm for structuring systems. Recently, there has been an interest in extending this paradigm to non‐shared memory architectures as well. For example, the virtual address spaces for all objects in a distributed object‐based system could be viewed as constituting a globaldistributed shared memory. We propose a set of primitives for managing distributed shared memory. We present an implementation of these primitives in the context of an object‐based operating system as well as on top of Unix.
Reverse engineering: Algorithms for program graph production
Authors: Cimitile Aniello , de Carlini Ugo
Published: November 2006

The paper proposes an algebraic representation of program modules, calledF(p), and illustrates the algorithms that useF(p)to generate program graph models for measurement, documentation and testing activities. The representation refers to procedural languages, D‐structured programs and one‐in/one‐out modules but its definition can be extended to programs structured in terms of an arbitrary set of one‐in/one‐out legal control structures. Since it is possible to produceF(p)directly from the program code using reverse engineering techniques, the algorithms proposed are of considerable interest for the setting up of tools supporting the program comprehension phase, which is a fundamental first step in any maintenance operation.
Identifying syntactic differences between two programs
Authors: Yang Wuu
Published: November 2006

Programmers frequently face the need to identify the differences between two programs, usually two different versions of a program. Text‐based tools such as the UNIXr̀ utility diff often produce unsatisfactory comparisons because they cannot accurately pinpoint the differences and because they sometimes produce irrelevant differences. Since programs have a rigid syntactic structure as described by the grammar of the programming language in which they are written, we develop a comparison algorithm that exploits knowledge of the grammar. The algorithm, which is based on a dynamic programming scheme, can point out the differences between two programs more accurately than previous text comparison tools. Finally, the two programs are pretty‐printed ‘synchronously’ with the differences highlighted so that the differences are easily identified.
Transparent process migration: Design alternatives and the sprite implementation
Authors: Douglis Fred , Ousterhout John
Published: November 2006

The Sprite operating system allows executing processes to be moved between hosts at any time. We use this process migration mechanism to offload work onto idle machines, and also to evict migrated processes when idle workstations are reclaimed by their owners. Sprite's migration mechanism provides a high degree of transparency both for migrated processes and for users. Idle machines are identified, and eviction is invoked, automatically by daemon processes. On Sprite it takes up to a few hundred milliseconds on SPARCstation 1 workstations to perform a remote exec, whereas evictions typically occur in a few seconds. The pmake program uses remote invocation to invoke tasks concurrently. Compilations commonly obtain speed‐up factors in the range of three to six; they are limited primarily by contention for centralized resources such as file servers. CPU‐bound tasks such as simulations can make more effective use of idle hosts, obtaining as much as eight‐fold speed‐up over a period of hours. Process migration has been in regular service for over two years.
PROTOB: An object‐oriented case tool for modelling and prototyping distributed systems
Authors: Baldassari Marco , Bruno Giorgio , Castella Andrea
Published: November 2006

The PROTOB object‐oriented methodology for the executable specification of large‐scale event‐driven systems is introduced and described. Two supporting features of PROTOB are also presented: the graphic and textual language that formally describes the behaviour of objects, which is based on high‐level Petri nets called “PROT nets” and which is demonstrated to be more powerful than SA/RT dataflows; and a CASE environment with tools for specification, modelling, simulation and prototyping. Use of PROTOB is illustrated by discussion of the automated generation of distributed systems running on a network of VMS and UNIX computers.
Evaluation of fortran vector compilers and preprocessors
Authors: Luecke Glenn , Haque Waqar , Hoekstra James , Jespersen Howard , Coyle James
Published: November 2006

Many scientific codes can achieve significant performance improvement when executed on a computer equipped with a vector processor. Vector constructs in source code should be recognized by a vectorizing compiler or preprocessor. This paper discusses, from a general point of view, how a vectorizing compiler/preprocessor can be evaluated. The areas discussed include data dependence analysis, IF loop analysis, nested loops, loop interchanging, loop collapsing, indirect addressing, use of temporary storage, and order of arithmetic. The ideas presented are based on vectorization of over a million lines of production codes and an extensive test suite developed to evaluate preprocessors under varying degrees of code complexity. Areas for future research are also discussed.
DMT—a demonstration tool
Authors: Zheng Yi , Hague Jim
Published: November 2006

DMT is a software demonstration tool, running on workstations, that can be used to demonstrate other software tools. The paper describes the reasons for developing DMT and the implementation of DMT. DMT simulates a video recorder/player system and provides recording, winding (forward/backward) and replaying functions. During recording, DMT records the target tool window image changes and the interactions between the target tool and the controlling mouse. By deleting and inserting visual‐image scripts and by adding textual comments to explain the visual‐image changes, a user can obtain editing of what has been recorded. During replay, DMT shows how the target window changes as if the target tool is being demonstrated in real time. The textual comments are played synchronously with the visual images.
Experience compiling Fortran to program dependence graphs
Authors: Ottenstein Kar L. J. , Ellcey Steven J.
Published: November 2006

The program dependence graph (PDG) is being used in research projects for compilation to parallel architectures, program version integration and program semantics. This paper describes the methods used in a prototype Fortran‐to‐PDG translator called the PDG Testbed. Implementation decisions and details of the PDG Testbed project are described as a complement to the formal papers detailing the abstract PDG. In addition, experimental results are given that show the storage consumption for a PDG relative to a conventional internal representation as well as execution times for several analysis and optimization steps.
Optimizing stack frame accesses for processors with restricted addressing modes
Authors: Hartley David H.
Published: November 2006

Random access to local variables stored in a stack frame is more difficult for compiled functions when the target processor lacks register‐plus‐offset addressing. One alternative technique employs a roving pointer which the program increments or decrements as needed between stack accesses. Processors which support auto‐increment and auto‐decrement addressing modes are often capable of performing these increments for free when consecutive accesses are to adjacent stack locations. For these processors, the compiler's chosen ordering for the local variables in the stack frame can substantially affect the execution speed of the compiled program.

This paper is concerned with finding an ordering for the local variables in the frame that maximizes the likelihood that two consecutive references at run‐time will be to the same or to adjacent stack locations. We have formulated a solution to this problem in terms of finding a Hamiltonian path in a graph. Although this problem is NP‐complete in general, we have developed a heuristic algorithm that delivers good results with acceptable performance.
Experience with Fagan's inspection method
Authors: Doolan E. P.
Published: November 2006

Fagan's inspection method was used by a software development group to validate requirements specifications for software functions. The experiences of that group are described in this paper. In general, they have proved to be favourable. Because the costs of fixing errors in software were known, the payback for every hour invested in inspection was shown to be a factor 30. There are also other benefits that are much more difficult to quantify directly but whose effect is significant in terms of the overall quality of the software.

Some pointers are given at the end of this paper for those who want to introduce Fagan's inspection method into their own development environment.
The practical integration of manufacturing applications
Authors: Busby J. S. , Hutchison D.
Published: November 2006

The need to integrate the operation of computer applications is becoming an increasingly prominent issue in industrial firms. Mechanisms have to be developed to allow these systems to share the information they generate and use—to ensure that elements of data with a common meaning, in different systems, have consistent values. The applications are normally proprietary packages, of widely varying types, usually selected for their effectiveness as free‐standing systems; they cannot as a result be modified to any appreciable extent during integration. An approach to integration that is based on the distributed updates of complex objects just before use is described in this paper.

The implementation provides a transportation service that moves information from one location to another, and a transcription service that transforms objects from their native formats in one application to those comprehensible in another. Transcription is based on using an intermediate neutral data model—independent of data formats in particular applications. The transport facilities are modelled satisfactorily in a process‐oriented notation such as CSP, whereas the transcription operations are modelled better with a set‐based notation such as Z. These specifications have been implemented primarily using Unix communication mechanisms and a proprietary relational database management system.
The design and implementation of a grammar‐based data generator
Authors: Maurer Peter M.
Published: November 2006

DGL is a context‐free grammar‐based language for generating test data. Although many of the features of DGL are implemented in a straighforward way, the implementation of several of the most important features is neither trivial nor obvious. Before one can understand the implementation of these features, however, it is necessary to understand the overall structure of the compiler and its output, which was designed to be flexible enough to incorporate new features easily. Variables and chains are two of the most important features of DGL, and also two of the trickiest features to implement. The run‐time dictionaires, which are built into the C code generated by the compiler, are implemented as pure code rather than as table‐look‐up routines. The compiler itself is reasonably straightforward, except for the expansion of character sets and compile‐time macros. These two features can cause the ‘multi‐dimensional’ expansion of a string, the implementation of which must be carefully designed.
Profile‐guided automatic inline expansion for C programs
Authors: Chang Pohua P. , Mahlke Scott A. , Chen William Y. , Hwu Wen‐Mei W.
Published: November 2006

This paper describes critical implementation issues that must be addressed to develop a fully automatic inliner. These issues are: integration into a compiler, program representation, hazard prevention, expansion sequence control, and program modification. An automatic inter‐file inliner that uses profile information has been implemented and integrated into an optimizing C compiler. The experimental results show that this inliner achieves significant speedups for production C programs.
Tuning a parallel database algorithm on a shared‐memory multiprocessor
Authors: Graefe Goetz , Thakkar Shreekant S.
Published: November 2006

Database query processing can benefit significantly from parallelism. Parallel database algorithms combine substantial CPU and I/O activity, memory requirements, and massive data exchange between processes, all of which must be considered to obtain optimal performance. Since parallel external sorting is a very typical example, we have focused on sorting to tune Volcano, a new query processing system. The purpose of the Volcano project is to provide efficient, extensible tools for query and request processing in novel application domains, particularly in object‐oriented and scientific database systems, and for experimental database performance research. It includes all query processing algorithms conventionally used in relational database systems as well as several new ones, and can execute all of them in parallel. In this article, we present Volcano's parallel external sorting algorithm and a sequence of enhancements to improve its performance. We obtained very good absolute performance, 84 seconds for 100 MB of data, as well as near‐linear speedup with sixteen CPUs and disks. Furthermore, these results were achieved on a shared‐memory machine despite the common belief that parallel query processing is best implemented on distributed‐memory systems. We detail our tuning measures and report on their effectiveness.
Extension table built‐ins for prolog
Authors: Fan Changguan , Dietrich Suzanne Wagner
Published: November 2006

The ET* algorithm is a complete evaluation strategy for Datalog programs, which are logic programs without function symbols. The ET* algorithm uses extension tables and depth‐first iterative deepening to provide the evaluation of pure function‐free logic programs as declarative specifications. Extension tables are a memo facility that the algorithm uses both to cut infinite derivation paths for complete evaluation and to optimise the evaluation of logic programs.

The original implementation of the ET* algorithm incorporated extension tables as part of the Prolog database using the built‐in predicates assert and retract. The advantage of implementing the extension table using the Prolog database is the portability of the ET* algorithm. There are several disadvantages, however, with this approach. One disadvantage is the cost associated with the built‐in predicates assert and retract, which are known to be expensive operations in most current Prolog systems. Another disadvantage is the differences across implementations in the semantics that these built‐ins provide for dynamic predicates. This paper presents an efficient implementation of extension tables as a global data structure in Prolog, which includes a set of built‐in primitives for manipulating the extension table. The ET* algorithm is updated to reflect the utilisation of the global extension table data structure. The implementations of the ET* algorithm are compared using time and space performance on a variety of benchmark programs.
An efficient implementation of trie structures
Authors: Aoe Jun‐Ichi , Morimoto Katsushi , Sato Takashi
Published: November 2006

A new internal array structure, called a double‐array, implementing a trie structure is presented. The double‐array combines the fast access of a matrix form with the compactness of a list form. The algorithms for retrieval, insertion and deletion are introduced through examples. Although insertion is rather slow, it is still practical, and both the deletion and the retrieval time can be improved from the list form. From the comparison with the list for various large sets of keys, it is shown that the size of the double‐array can be about 17 per cent smaller than that of the list, and that the retrieval speed of the double‐array can be from 3–1 to 5–1 times faster than that of the list.
Incrementally maintained network→relational database mapping
Authors: Mark Leo , Roussopoulos Nick , Newsome Tina , Laohapipattana Piriya
Published: November 2006

An incrementally maintained mapping from a network to a relational database is presented. This mapping may be established either to support the efficient retrieval of data from a network database through a relational interface, or as the first step in a gradual conversion of data and applications from a network to a relational database system. After the mapping has been established, the only data mapped from the network to the relational database are the increments resulting from updates on the network database. The mapping is therefore an efficient alternative to mappings that repeatedly map the results of retrievals through the relational interface from the network database to the relational database. This is in particular the case when the two databases reside on different hosts. Applications on the network database may, under certain restrictions, gradually be moved to the relational database, while the mapping incrementally maintains the relational database for the applications that remain on the network database.

A detailed, but generic, account of how to build such a mapping from a network to a relational database is given, including all the algorithms needed and examples of their use.
Designing and implementing multi‐user applications: A case study
Authors: Dewan Prasun
Published: November 2006

We have developed a new multi‐user application that integrates and extends the concepts in a variety of current multi‐user applications. It allows multiple users to store, retrieve and browse through information, communicate information both synchronously and asynchronously, create ‘pipes’ of consistent, editable and persistent views, and interactively specify handlers for events. It has been implemented using the experimental technologies of distributed objects and multi‐user editor generation. Our work on this application suggests a new and practical model for designing and implementing multi‐user applications. In this paper, we describe the user interface and implementation of the application, give the rationale for our design choices, describe our experience with the tools and techniques used in the implementation, and present conclusions and directions for future work.
High‐level management of computation history for the design and implementation of a prolog system
Authors: Loia Vincenzo , Quaggetto Michel
Published: November 2006

We present the implementation of a Prolog system composed of interpreter and compiler. The originality of our work consists in the adoption of a new framework to realize the main components of the system. The framework relies on new mechanisms, called sleepers. With their help we have developed a complete Prolog interpreter in which all the control activities, from backtracking up to last‐call optimization, are performed by the sleeper mechanism. We have also produced a Prolog compiler by using a philosophy and tactics that are completely independent of hardware constraints; it exploits an incremental and abstract implementation technique, based on a delayed non‐local execution protocol. Our approach to Prolog system implementation has been extremely useful both in terms of software design and overall performance.
Iconic control graph representation
Authors: Robillard Pierre N. , Simoneau Mario
Published: November 2006

This paper presents a new representation of control flow graphs which is readable and concise, keeping all pertinent information as it appears in the source code. The iconic control graph provides an exact transformation of the source code. It is a basis for control flow visualization, unstructuredness identification, path crossing and path computation. The representation is programming‐language independent. The iconic control flow construction is automated.
Query by diagram: A visual environment for querying databases
Authors: Santucci Giuseppe , Sottile Pier Angelo
Published: November 2006

In recent years, several attempts have been made to define query languages characterized by both high expressive power and easy query formulation. Several issues concern graphical applications, based on the diagrammatic representation of a semantic model and visual interaction. This paper describes the architecture and the implementation of a graphical query system, based on the diagrammatic representation of entity relationship schemata. The query language underlying the system allows the formulation of recursive queries; moreover, user interaction in both managing diagrams and expressing queries is simplified by the presence of a fully visual environment and a rich set of interaction strategies.
An implementation of precompiled headers
Authors: Litman Andy
Published: November 2006

Compilation time can be improved by precompiling interfaces so that the compiler can avoid processing unreferenced declarations. However, in C‐based languages precompiling a header is difficult because a header can have several meanings depending on the context in which it is included. We present anad hocsolution to this problem, and give the results of our precompilation strategy, which improved compile times by 25 to 65 per cent over compilation without precompiled headers.
Construction of an interactive programming environment for control of theatrical‐set effects via object‐oriented methods
Authors: Thirion Bernard
Published: November 2006

This paper describes the object‐oriented design of a novel application, for control of complex theatricalset effects defined by an appropriate language. Besides giving a general description of the proposed system, the paper presents the language and its programming environment, which is intended for inexperienced users and integrates facilities to create, edit, check and run the effect scripts. The description of the implementation demonstrates the relevance of an object‐oriented approach when it is associated with compiler techniques. The object paradigm is used to build support classes such as character streams, run‐time values or symbols as well as syntactic objects. Each syntactic‐object class models a different LL(1) grammar non‐terminal and allows for an object‐oriented predictive parsing. Moreover, organizing the instances of these classes as an object‐based parse tree simplifies parsing, unparsing, syntax‐directed editing, syntax‐directed help, interpretation, etc. The description of these various operations shows the flexibility of our method, e.g. with respect to an iterative prototyping of the language and its environment.
The duality of fault‐tolerant system structures
Authors: Shrivastava Santosh K. , Mancini Luigi V. , Randell Brian
Published: November 2006

An examination of the structure of fault‐tolerant systems incorporating backward error recovery indicates a partitioning into two broad classes. Two canonical models, each representing a particular class of systems, have been constructed. The first model incorporates objects and actions as the entities for program construction whereas the second model employs communicating processes and conversations. Applications in areas such as office information and banking systems are typically described and built in terms of the first model whereas applications in the area of process control are usually described and built in terms of the second model. The paper claims that the two models are duals of each other and presents arguments and examples to substantiate this claim. It will be shown that the techniques that have been developed within the context of one model turn out to have interesting and hitherto unexplored duals in the other model.
A method for fast tape backups and restores
Authors: Drizis Leonidas
Published: November 2006

This paper describes a method for fast backups and restores on tape drives. By using a tight synchronization between disk and tape accesses, the total throughput can be accelerated by a factor ranging from 30 to 100 per cent. The method imposes no special requirements on an operating system; only a timer with a resolution better than one fiftieth of a second is needed. Further, it can be used with virtually all types of streaming tapes and backup data formats.
ISA [k] trees: A class of binary search trees with minimal or near minimal internal path length
Authors: Abuali Faris N. , Wainwright Roger L.
Published: November 2006

In recent years several authors have investigated binary search trees with minimal internal path length. In this paper we propose relaxing the requirement of inserting all nodes on one level before going to the next level. This leads to a new class of binary search trees called ISA [k] trees. We investigated the average locate cost per node, average shift cost per node, total insertion cost, and average successful search cost for ISA[k] trees. We also present an insertion algorithm with associated predecessor and successor functions for ISA[k] trees. For large binary search trees (over 160 nodes) our results suggest the use of ISA[2] or ISA[3] trees for best performance.
Utopia: A load sharing facility for large, heterogeneous distributed computer systems
Authors: Zhou Songnian , Zheng Xiaohu , Wang Jingwen , Delisle Pierre
Published: November 2006

Load sharing in large, heterogeneous distributed systems allows users to access vast amounts of computing resources scattered around the system and may provide substantial performance improvements to applications. We discuss the design and implementation issues in Utopia, a load sharing facility specifically built for large and heterogeneous systems. The system has no restriction on the types of tasks that can be remotely executed, involves few application changes and no operating system change, supports a high degree of transparency for remote task execution, and incurs low overhead. The algorithms for managing resource load information and task placement take advantage of the clustering nature of large‐scale distributed systems; centralized algorithms are used within host clusters, and directed graph algorithms are used among the clusters to make Utopia scalable to thousands of hosts. Task placements in Utopia exploit the heterogeneous hosts and consider varying resource demands of the tasks. A range of mechanisms for remote execution is available in Utopia that provides varying degrees of transparency and efficiency.

A number of applications have been developed for Utopia, ranging from a load sharing command interpreter, to parallel and distributed applications, to a distributed batch facility. For example, an enhanced Unix command interpreter allows arbitrary commands and user jobs to be executed remotely, and a parallel make facility achieves speed‐ups of 15 or more by processing a collection of tasks in parallel on a number of hosts.
A faster scrabble move generation algorithm
Authors: Gordon Steven A.
Published: November 2006

Appel and Jacobson1 presented a fast algorithm for generating every possible move in a given position in the game of Scrabble using a DAWG, a finite automaton derived from the trie of a large lexicon. This paper presents a faster algorithm that uses a GADDAG, a finite automaton that avoids the non‐deterministic prefix generation of the DAWG algorithm by encoding a bidirectional path starting from each letter of each word in the lexicon. For a typical lexicon, the GADDAG is nearly five times larger than the DAWG, but generates moves more than twice as fast. This time/space trade‐off is justified not only by the decreasing cost of computer memory, but also by the extensive use of move‐generation in the analysis of board positions used by Gordon2 in the probabilistic search for the most appropriate play in a given position within realistic time constraints.
Implementations and performances of two RPC‐based LAN gateway applications
Authors: Yasrebi Mehrad
Published: November 2006

A predominant (‘base’) scheme currently used in many circuit‐switched LAN‐WAN gateway applications is based on device‐driver LAN redirections. Various functional and performance deficiencies associated with the LAN redirection (base) scheme and an RPC programming interface are described. This RPC definition supports the base scheme, as well as another (‘enhanced’) scheme. The enhanced scheme overcomes the various outlined functional deficiencies associated with the cited implementations of the base scheme. Implementations of these two client‐server application schemes on top of the IEEE portable operating‐system interface and the Open Software Foundation RPC are described for both schemes. Performances of these two schemes are compared, both based on a simplified Markov chain model and on actual implementations and long‐duration experiments. Some of the similarities between the predictive simple‐model behaviors and the actual experienced results for the applications are encouraging. This experience shows that the described RPC programming interface is a reasonable candidate for immediate practical implementations on heterogeneous systems.