bluuebunny/crossref_metadata_2025 huggingface dataset:
Developing human‐computer interface models and representation techniques
Authors: Hartson H. Rex , Hix Deborah , Kraly Thomas M.
Published: November 2006

The Dialogue Management Project at Virginia Tech is studying the poorly understood problem of human‐computer dialogue development. This problem often leads to low usability in human‐computer dialogues. The Dialogue Management Project approaches solutions to low usability in interfaces by addressing human‐computer dialogue development as an integral and equal part of the total system development process. This project consists of two rather distinct, but dependent, parts. One is development of concepts for dialogue management, and the other is implementation of a dialogue management system (DMS) to evaluate these concepts. The goal of this paper is to describe our approach to the development of two of these conceptual aspects and how we oriented those toward the needs of practical implementation. The two conceptual aspects are

A structural, descriptive model of human‐computer interaction, and

Techniques for representing both the behavioural (end‐user's) view and the constructional (developer's) view of dialogue.

The approach to their development was a technology transfer process that was part of a two‐year university/industry research liaison between the Dialogue Management Project and IBM Federal Systems Division (FSD), now called Systems Integration Division. Part of this liaison was aimed at moving our research ideas and results into a real‐world dialogue development environment. Following presentation of the technical problems and solutions, the paper concludes with a discussion of results of our liaison and by raising and addressing some questions of mutual interest that arose during our co‐operative interaction.
LexAGen: An interactive incremental scanner generator
Authors: Szafron Duane , Ng Randy
Published: November 2006

This paper describes LexAGen, an interactive scanner generator which is the first component of an interactive compiler generation environment. LexAGen can generate fast scanners for languages whose tokens can be specified by regular grammars. However, LexAGen also supports several context‐sensitive programming language constructs such as nested comments and the interaction between floating‐point numbers and the range operator in Modula‐2. In addition, LexAGen includes a fast new algorithm for keyword identification. However, the most important and novel aspects of LexAGen are that it constructs scanners incrementally and that specifications can be executed anytime for validation testing.

LexAGen specifications are expressed and entered interactively in a restricted BNF format (no left recursion). All syntactic errors and token conflicts are detected and reported immediately as LexAGen incrementally constructs a deterministic finite automaton to represent the scanner. At any time, the user can test the scanner fragment which has been entered by supplying text to be scanned. Alternatively, the user can generate a C‐code scanner from the automaton. The generated automaton uses a direct execution approach and is quite fast.

LexAGen is implemented in Smalltalk‐80. Its extensive use of interactive graphics makes it very easy to use. In addition, the object‐oriented paradigm of Smalltalk‐80 is the basis for the incremental analysis, the error detection scheme and an intermediate representation which can be easily modified to generate scanners in other target languages such as Pascal, Modula‐2 and Ada.
Even faster lr parsing
Authors: Horspool R. Nigel , Whitney Michael
Published: November 2006

Conventional LR parser generators create tables which are used to drive a standard parser procedure. Much faster parsers can be obtained by compiling the table entries into code that is directly executed. A possible drawback with a directly executable parser is its large size. In this paper, we introduce optimization techniques that increase the parsing speed even further while simultaneously reducing the size of the parser.
TICL—A type inference system for Common Lisp
Authors: Ma Kwan‐Liu , Kessler Robert R.
Published: November 2006

Most current Common Lisp compilers generate more efficient code when supplied with data type information. However, in keeping with standard Lisp programming style, most programmers are reluctant to provide type information; they simply allow the run‐time type system to manage the data types accordingly. To fill this gap, we have designed and implemented a type inference system for Common Lisp (TICL). TICL takes a Lisp program that has been annotated with a few type declarations, adds as many declarations as possible, and produces a type declared program. The compiler can then use this information to generate more efficient code. Measurements indicate that a 20 per cent speed improvement can generally be achieved.
A tale of three spelling checkers
Authors: Mullin James K. , Margoliash Daniel J.
Published: November 2006

This paper describes three spelling checkers implemented at the University of Western Ontario. The first is interesting for its functionality and high compression of its dictionary; the second for its unexpected failure and the third for using the lesson of the previous to good advantage.

The principal contributions of this work are a compressed dictionary structure at 12 bits per dictionary token; and the ability to offer suggested corrections from a structure without the words explicitly stored.
The implementation of Newsqueak
Authors: Pike Rob
Published: November 2006

The implementation of the concurrent applicative language Newsqueak has several unusual features. The interpreter, squint, uses a copy‐on‐write scheme to manage storage honouring Newsqueak's strictly applicative (by‐value) semantics for data. There is no explicit scheduler. Instead, the execution of processes is interleaved very finely, but randomly, by an efficient scheme that integrates process switching into the interpreter's main loop. The implementation of select, the non‐deterministic, multi‐way communications operator, exploits details in the implementation of processes. This paper describes much of the interpreter but explains only small aspects of the language. Further detail about the language may be found in the References.
Experiences structuring software in a periodic real‐time environment
Authors: Jordan J. E.
Published: November 2006

This paper describes experiences in structuring software for an aircraft ‘flying laboratory’ used in a variety of scientific experiments in the areas of geophysics, oceanography and advanced navigation. The software is required to operate in a hard real‐time fashion, processing a number of streams of sampled sensor data within the time interval defined by corresponding periodic sampling clocks.

The operational software for this system is structured into a number of real‐time periodic processes which are executed under the control of a real‐time kernel developed for this environment. Both the scheduler used in the real‐time kernel and the structuring of the various processes in the system are described in detail. Various other aspects of the system along with experiences gained over a development life cycle are noted.
Pitfalls of conservative garbage collection
Authors: Wentworth E. P.
Published: November 2006

Researchers have recently proposed conservative garbage collection as a technique which allows smooth integration of automatic memory management into existing high‐level languages. Conservative techniques carry the cost of some leakage‐they fail to reclaim all the available garbage.

This paper reports on a conservative collector and measurements of its leakage. The results indicate that the loss depends critically on the application: a Lisp interpreter shows very small leakage (typically less than 5 per cent of the total heap space for classroom examples), whereas the garbage collector collapses completely when used with a KRC interpreter. Uncovering the reasons reveals that it is possible to write Lisp programs that also fail.

Previous work has used very sparsely populated address spaces where the probability for leakage was minimized. This work considers small, densely populated address spaces, and probably represents a worst‐case scenario.

Although the conservative technique appears to be a cost‐effective and clean way of integrating automatic memory management into an off‐the‐shelf host language, we are led to conclude that it is not reliable in all situations.
A microcode compiler for the watch‐oriented RISC processor
Authors: Iseli Christian
Published: November 2006

The WORP project embodies the design of a real‐time oriented RISC microprocessor and a complete application development environment for this processor. The three most original aspects of this project are: (a) the microprocessor has no assembly language, but is programmed in microcode; the compiler will translate the high‐level language directly into microcode; (b) there is a certain amount of parallelism available at the microcode level; the compiler will take advantage of this parallelism without putting extra burden on the programmer; (c) the compiler performs instruction rescheduling in order to take further advantage of the parallelism available at the microcode level. This paper describes the high‐level language and compiler aspects of the WORP project, and concentrates on the instruction rescheduling and other optimizations performed by the compiler. A modest comparative bench‐mark is provided.
Lazy recursive descent parsing for modular language implementation
Authors: Koskimies Kai
Published: November 2006

A variant of the well‐known recursive descent parsing technique is developed, based on the assumption that each non‐terminal of the language is implemented through a separate module. The modularization principle requires that the recursive descent parser of one non‐terminal must be written knowing only the production rules of that non‐terminal, and not the other parts of the language. This leads to a parsing technique which is ‘lazy’ in the sense that part of the parser is constructed during parsing, according to the needs of a particular input text. It turns out that this technique can be implemented as efficiently as conventional recursive descent parsing, which is one of the fastest known parsing methods. The main benefit of the technique is that it allows a language to be implemented in small pieces which are easy to modify, replace, and reuse.
Synchronization of nested atomic actions
Authors: Tripathi Anand , Hili Zine Attia El
Published: November 2006

The concept of atomic actions has been a useful and powerful abstraction in designing concurrent and fault‐tolerant systems. Nested atomic actions are used in hierarchically structured systems where an atomic action may itself be composed of other atomic actions. This paper presents a semaphore‐based protocol for synchronizing a set of concurrently executing nested atomic actions. The approach followed consists of first designing a protocol for synchronizing non‐nested actions, and then extending it to the nested case. The paper also details the difficulties involved in integrating deadlock resolution algorithms into the synchronization protocol. Both deadlock‐prevention and deadlock‐detection schemes for handling deadlocks are discussed.
Formal verification of safety‐critical systems
Authors: Moser Louise E. , Melliar‐Smith P. M.
Published: November 2006

We describe our practical experience in the use of formal verification to obtain increased confidence in the design of safety‐critical systems. The experiment involved demonstrating the consistency of the design specifications of SIFT, a software‐implemented fault‐tolerant operating system for aircraft flight control. Specifications were written at successive levels of abstraction from the most abstract requirements definition down to the detailed level of program code. Consistency of the successive levels of specification was demonstrated using the enhanced HDM verification system. Formal verification is currently feasible only for carefully simplified systems, but there appears to be no alternative method that can meet the extreme safety requirements for safety‐critical systems.
LR parsing of CFGs with restrictions
Authors: McKenzie B. J.
Published: November 2006

A method for extending the LR parsing method to enable it to deal with context‐free grammars containing embedded restrictions is presented. Such restrictions are usually dealt with in LR‐based parsers by executing semantic code outside the context of the LR method. By including such restrictions within the LR method itself, potential shift‐reduce and reduce‐reduce conflicts can be resolved and provide greater control over the language accepted. The proposed method can be incorporated easily into existing LR‐based parser‐generating systems.
Efficient automated protocol implementation using RTAG
Authors: Hernek Diane , Anderson David P.
Published: November 2006

RTAG is a system for automated implementation of communication protocols from formal specifications. The RTAG specification language is based on attribute grammars, and allows complex protocols to be specified concisely and with minimal need for additional program code. This paper describes a set of techniques for efficient automated implementation of protocols from RTAG specifications, and compares the performance to that of hand‐coded protocol implementations. We conclude that in many cases the performance of RTAG‐based protocol implementations is acceptable for experimental or production uses.
The μsystem: Providing light‐weight concurrency on shared‐memory multiprocessor computers running UNIX
Authors: Buhr Peter A. , Stroobosscher Richard A.
Published: November 2006

This paper presents a description of the μSystem, which is a library of C routines that provide light‐weight concurrency on uniprocessor and multiprocessor computers running the UNIX operating system. A discussion of the run‐time structure of a μSystem program is given, which includes the following concepts: coroutines, tasks, virtual processors and clusters. Next the routines that implement these concepts are discussed in detail. Finally, some performance figures from the μSystem are given and discussed, followed by a comparison of the μSystem with other similar systems.
On the distributed parallel simulation of Hopfield's neural networks
Authors: Barbosa Valmir C. , Lima Priscila M. V.
Published: November 2006

Neural networks, or connectionist systems, have recently emerged as a powerful model of collective, parallel computation of great interest in artificial intelligence and combinatorial optimization. The understanding of neural networks is still largely dependent upon simulations, which in turn can be of great interest to the designer of parallel software, owing to the inherently distributed character of those systems. This paper is concerned with the simulation of one specific class of neural networks, namely those introduced by J. J. Hopfield. We discuss the design and occam implementation of a distributed parallel simulator of such networks, allowing for both binary‐ and continuous‐response neurons. A design is provided which we judge to be generic to a large extent, and then problems related to an occam implementation are discussed. One problem of particular relevance is the potential occurrence of communication deadlocks as a result of the unbuffered communication among occam processes.
Implementation of a portable screen manager
Authors: Reyes Tom C. , Sills James L.
Published: November 2006

Application programs that involve full‐screen interaction are often difficult to transport from their source environments, partly because of their use of system‐specific screen managers. This paper examines the rationale, design, and implementation of a screen management package that is transportable to a broad class of computing systems.
Integrating prolog and CADAM to produce an intelligent CAD system
Authors: Bond Alan H. , Soetarman Basuki
Published: November 2006

A discussion is presented of system issues in integrating an artificial intelligence system with a conventional computer‐aided design system. Two different schemes for integration, and experience in implementing a combined VM/PROLOG and CADAM, are described.

Both Prolog and CADAM are separately interactively systems, and it was necessary to provide an interactive interface to each, and to be able to move between them. Since CADAM is not reentrant, a coroutining relationship was required. It was necessary to specify a Prolog form for drawings and to be able to transform drawings in the CADAM workspace in Fortran array form into Prolog clauses, representing the same information and residing in the Prolog workspace, and vice versa. The problems of linking to CADAM, and of storage management in a VM virtual machine had to be dealt with. Finally, error recovery had to be considered.

Examples of the use of the system are presented, including examples of CAD graphics, and the setting of goals, with the corresponding system responses.

The main practical application area was the design and manufacture of assemblies made of sheet metal and extrusions, such as components of aircraft. Several application programs, implemented using the intelligent CAD system, are described.
Using SR for discrete event simulation: A study in concurrent programming
Authors: Olsson Ronald A.
Published: November 2006

This paper demonstrates the use of the SR concurrent programming language for discrete event simulation. SR provides a rich collection of synchronization mechanisms, whose use can lead to programs that are simpler and more efficient than those constrained to employ only one synchronization mechanism. Several SR solutions to a simulation problem are presented and contrasted with an Ada solution to the same problem. The paper also introduces a technique that exploits asynchronous message passing to program concise solutions to several problems involving lists. In the context of the simulation problem, this technique is used to manage the event list and the list of blocked processes. The technique can also be applied to several other concurrent programming problems. The results of this paper should be of interest both to programmers using concurrent programming languages and to language designers.
High‐level goal‐directed concurrent processing in icon
Authors: Nilsen Kelvin
Published: November 2006

Concurrent language features have been added to an experimental dialect of Icon called Conicon. These new language features allow Icon to deal with new application domains such as intelligent robot control and real‐time natural language processing. Besides widening the scope of Icon's intended application domain, these experimental concurrent processing notations also encourage programmers to revise existing programs to take advantage of the new language capabilities. For example, concurrent evaluation of the alternative arms of compound goal‐directed expressions is now possible. This paper describes these concurrent processing notations and presents several examples of their expressive power.
Modules, objects and distributed programming: Issues in RPC and remote object invocation
Authors: Levy Henry M. , Tempero Ewan D.
Published: November 2006

Distributed programming can be greatly simplified by language support for distributed communication, such as that provided by remote procedure call (RPC) or remote object invocation. This paper examines design and implementation issues in these systems, and focuses on the influence of the communication system on a distributed program. To make the discussion concrete, we introduce a single application as implemented in two environments: Modula‐2+, an extension of Modula‐2 with RPC, and Emerald, an object‐based language that supports remote object invocation. We show that small differences in the implementation of the communication system can have a significant impact on how distributed applications are structured.
Modelling the software development process using an expert simulation system having fuzzy logic
Authors: Levary Reuven R. , Lin Chi Y.
Published: November 2006

This paper describes an intelligent computerized tool designed to aid managers of software development projects in planning, managing and controlling the development process of medium‐ to large‐scale software projects. Systems dynamics is used to model and simulate the dynamic process of software development. The software development process is affected by some imprecise and vague variables that are treated as fuzzy variables. The simulation model is integrated with two expert systems. The fuzzy input variables to the system dynamics simulation model are handled by an input expert system having fuzzy logic. This expert system is designed to check the consistency of input variables. The simulation results are analysed by an output expert system having fuzzy logic. This expert system is designed to make recommendations based on experimentation with the simulation model.
Methods for saving and restoring register values across function calls
Authors: Davidson Jack W. , Whalley David B.
Published: November 2006

The method used to save and restore the values of registers across function calls can affect performance and influence the design of specific instructions. This paper describes the results of an experiment that empirically evaluated six different schemes for saving and restoring registers on CISC machines. The methods do not require special hardware or interprocedural analysis to be performed. The six schemes were logically divided into two classes. Three of the techniques do not require the compiler to perform data‐flow analysis, whereas the other three schemes do. Within each class one scheme delegates the responsibility of preserving the state of the registers to the calling function. The second scheme of each class delegates the responsibility of saving the registers to the function being called. In the third scheme of the two classes, the registers are partitioned into two disjoint sets. The calling function is responsible for preserving register values in one of the sets whereas the called function is responsible for the other set. For each class the third scheme is shown to produce the most effective code.
Implementing a user interface management system for existing applications using an object‐oriented database tool
Authors: Hardwick Martin , Uejio Wayne , Spooner David , Czechowski Joe , Lohr Phil , Sarachan Brion
Published: November 2006

Numerous engineering application systems have been developed over the past twenty years, and many of these applications will continue to be used for many years to come. Examples of such applications include CAD Systems, finite‐element analysis packages and inspection systems. Because many of these applications were developed before graphical workstations became available, they often have simple command‐line user interfaces. Thus, there is a need for a graphical user interface management system (UIMS) that can be used to build point‐and‐click style interfaces for these existing engineering applications.

In this paper we describe such a UIMS, and discuss its implementation using an object‐oriented database tool. This UIMS allows users to create and modify user interfaces by editing graphical representations of the interfaces, thus eliminating the need to write code to build or modify an interface. The UIMS is implemented using an object‐oriented database tool to take advantage of the data manipulation and storage management capabilities it provides. This approach reduces both the quantity and complexity of the code needed to implement the UIMS. It also allowed the UIMS to be implemented in a minimal amount of time.
Correcting a widespread error in unification algorithms
Authors: Norvig Peter
Published: November 2006

The unification of two patterns both containing variables is a ubiquitous operation in logic programming and in many artificial intelligence applications. Thus, many texts present unification algorithms. Unfortunately, at least seven of these presentations are incorrect. The common error occurs when logic variables are represented as binding lists; implementations that destructively update variable cells do not manifest the error. This note gives the examples that uncover the error and presents a correction.
A hybrid implementation of a process‐oriented programming language for system simulation
Authors: Rozin Roman , Treu Siegfried
Published: November 2006

The implementation of a hierarchical, process‐oriented programming language for simulation (HSL) is described. It features a hybrid approach, involving the front end of a compiler and the back end of an interpreter. An HSL program is dichotomous in structure. Source statements from each part are translated into three‐address code for an abstract machine, and the resulting code is then interpreted. The algorithms and the supportive data structures that effect the translation and interpretation of HSL are detailed. The host language for HSL is C++. HSL is machine independent and can be ported to any machine on which the host language is available. Its initial implementation was carried out on an NCR Tower. More recently, it was transferred to an NCR PC916.
Style control in the quill document editing system
Authors: Wolfsthal Yaron
Published: November 2006

A critical problem in the design of editors for structured documents is that of style control, i.e. mapping the logical elements of the documents to their physical appearance on pages. This paper presents a novel approach to style control, used in the Quill document editing system that has been prototyped at the IBM Almaden Research Center. In our approach, the style control mechanism is an integral part of the editing system and consistent with the overall system architecture, in both its inner structure and its user interface. Properties that specify the formatting process, together with action routines for specifying complex semantics, are the basic style control primitives in the proposed approach.
Reducing and manipulating complex trace data
Authors: Touati Hervé , Smith Alan Jay
Published: November 2006

In performance analysis of computer systems, trace‐driven simulation techniques have the important advantage of credibility and accuracy. Unfortunately, traces are usually difficult to obtain, and little work has been done to provide efficient tools to help in the process of reducing and manipulating them. This paper presents TRAMP, a tool for the data reduction and data analysis phases of trace‐driven simulation studies. TRAMP has three main advantages: it accepts a variety of common trace formats; it provides a programmable user interface in which many actions can be directly specified; and it is easy to extend. TRAMP is particularly helpful for reducing and analysing complex trace data, such as traces of file system or database activity. This paper presents the design principles and implementation techniques of TRAMP and provides a few concrete examples of the use of this tool.
Floating‐point number LISP
Authors: Umemura Kyoji
Published: November 2006

A floating‐point‐number‐oriented LISP has been developed. Though it performs type checking on every numeric operation, it runs as fast as Fortran for simple differential‐equation problems. This paper describes the implementation, provides some measurements of its efficiency, and discusses the feasibility of this type of implementation.
Perly—Unix with buttons
Authors: Hesketh Richard
Published: November 2006

Modern UNIX‐based graphical workstations still lack really graphical interfaces. Yet recreating existing UNIX tools with graphical interfaces may prove to be a prohibitive task. This paper describes the design and implementation of a set of tools that make the task of providing a graphical UNIX user interface easier. The main tool, called Perly, provides on‐screen graphical buttons connected to UNIX command scripts. When a button is pressed, the associated command script is executed. The buttons are highly configurable, encouraging users to tailor and extend their workstation environment. The idea of onscreen buttons with underlying programmable scripts comes from the work done at Xerox EuroPARC into user‐tailorable systems. Descriptions of Perly buttons are held in plain text files, allowing them to be given to other users via electronic mail. Examples of the use of buttons and the ideas behind the implementation of Perly buttons under the X Window System are discussed.
EcliPse: A system for high performance concurrent simulation
Authors: Sunderam V. S. , Rego Vernon J.
Published: November 2006

A description of a system which provides for the concurrent execution of stochastic simulation applications is presented. The EcliPSe system provides high‐level simulation primitives that enable common sawlation tasks. An application programmer describes the simulation process in terms of these primitives using a sequential computation model. The system transparently replicates appropriate sections of the simulation when the program is executed on a concurrent system. By binding to machine‐dependent versions of the EcliPSe library, the simulation program can execute without modification on a variety of architectures including uniprocessors, hypercubes, shared‐memory machines and loosely coupled networks. In those experiments conducted, near‐linear speed‐ups were obtained. The main design aspects of the system, salient implementation features and performance figures for some simulation applications are presented. The usefulness of the system for more general applications is also discussed.
Fast string searching
Authors: Hume Andrew , Sunday Daniel
Published: November 2006

Since the Boyer‐Moore algorithm was described in 1977, it has been the standard benchmark for the practical string search literature. Yet this yardstick compares badly with current practice. We describe two algorithms that perform 47% fewer comparisons and are about 4.5 times faster across a wide range of architectures and compilers.

These new variants are members of a family of algorithms based on the skip loop structure of the preferred, but often neglected, fast form of Boyer‐Moore. We present a taxonomy for this family, and describe a toolkit of components that can be used to design an algorithm most appropriate for a given set of requirements.
The distributed ada run‐time system darts
Authors: Göthe M. Carlsson , Wengelin D. , Asplund L.
Published: November 2006

A distributed Ada run‐time system, DARTS, is presented. DARTS is used with a source code transformation method for pre‐partitioning, and it also allows a late configuration. A single program can be partitioned to run on a loosely coupled multiprocessor system. The distributed units are tasks, task objects, packages, variables, procedures and functions. Task objects can by dynamically distributed. High fault tolerance is assured by unit redistribution. Design decisions, implementation details and ideas are presented.
Case study: Using its style tools to implement IBM's CUA‐2 user interface style
Authors: Ukelson Jacob P. , Gould John D. , Boies Stephen J. , Wiecha Charles
Published: November 2006

In an empirical case study of software tools, two participants used the ITS style designer's language to implement a general purpose, executable, rule‐based user interface style. This language allows style designers to select, combine and modify rule prototypes in order to construct a rule‐based user interface style. The participants implemented the entire IBM CUA‐2 user interface style, plus nine additional human‐computer interaction techniques, in 5–7 person‐weeks. This is impressive productivity. Typically the time to complete a single CUA‐2 application is measured in person‐years, not person‐weeks. The style implemented here is reusable by any ITS‐implemented application. The achievement reported here shows that about half the work of all ITS‐implemented CUA‐2 applications has been completed in a few person‐weeks. This result demonstrates the power and productivity of the ITS approach and tools. The results of this case study showed that key ‘ready‐mades’ (e.g. named attribute groups) provided in the style designer's toolkit could be used intact, which is important for importing or exporting interaction techniques from one style to another style. The results generalize to other computer‐literate designers who may want to use these tools to create other user interface styles.
Using profile information to assist classic code optimizations
Authors: Chang Pohua P. , Mahlke Scott A. , Hwu Wen‐Mei W.
Published: November 2006

This paper describes the design and implementation of an optimizing compiler that automatically generates profile information to assist classic code optimizations. This compiler contains two new components, an execution profiler and a profile‐based code optimizer, which are not commonly found in traditional optimizing compilers. The execution profiler inserts probes into the input program, executes the input program for several inputs, accumulates profile information and supplies this information to the optimizer. The profile‐based code optimizer uses the profile information to expose new optimization opportunities that are not visible to traditional global optimization methods. Experimental results show that the profile‐based code optimizer significantly improves the performance of production C programs that have already been optimized by a high‐quality global code optimizer.
An investigation into concurrent semantic analysis
Authors: Seshadri V. , Wortman D. B.
Published: November 2006

Concurrency is an attractive method for reducing the execution time of compilers. By dividing source programs into segments which can be compiled concurrently, the task of compiling programs can be accelerated.

Many of the difficult problems which arise when constructing a concurrent compiler occur in the implementation of the semantic analyser. This paper investigates the problems involved in designing the semantic analyser for a concurrent compiler for a modern, block‐structured language. Several approaches to solving the problems which arise are presented. These solutions are then implemented as part of a concurrent Modula‐2 + compiler, running on a shared memory multiprocessor. A performance evaluation of these semantic analysers is presented.
Towards a toolkit for building language implementations
Authors: Fédèle Carine , Lecarme Olivier
Published: November 2006

The current work of the authors in the area of software tools for automatic construction of compilers is described. This focuses on attempts to provide for automatic production of the semantic‐analysis and intermediate‐code‐generation parts of the Cigale compiler‐writing system, developed at the University of Nice. This work relies on use of the Amsterdam Compiler Kit (ACK) to ensure a full set of optimizers and code generators based on a semi‐universal intermediate language, and, therefore, emphasizes the filling of the gap between parsing and the intermediate language. It is intended as a pragmatic contribution to the automation of the production of true compilers (rather than mere program evaluators) that generate efficient machine code.
Hypertext development using a model‐based approach
Authors: Schwabe Daniel , Caloini Andrea , Garzotto Franca , Paolini Paolo
Published: November 2006

Hypertext development is still, for the most part, at the ‘handcrafting’ level, where each hypertext document must be hand‐designed. We present a compiler which takes hyperdocuments designed using a model‐based approach and generates stacks executable in Hyper Card. This compiler is implemented in standard SQL over a relational database representation of a hyperdocument designed using the hypermedia design model (HDM). The compiling approach, even though illustrated with HDM, can be used with any ‘structured’ design methodology.
The design and implementation of dynamic hashing for sets and tables in icon
Authors: Griswold William G. , Townsend Gregg M.
Published: November 2006

Two key features in the Icon programming language are tables and sets. An Icon program may use one large set or table, or thousands of small ones. To improve space and time performance for these diverse uses, their hashed data structures were reimplemented to dynamically resize during execution, reducing the minimum space requirement and achieving constant‐time access to any element for virtually any size set or table. The implementation is adapted from Per‐Åke Larson's dynamic hashing technique by using well‐known base‐2 arithmetic techniques to decrease the space required for small tables without degrading the performance of large tables. Also presented are techniques to prevent dynamic hashing from interfering with other Icon language features. Performance measurements are included to support the results.
An evaluation of self‐adjusting binary search tree techniques
Authors: Bell Jim , Gupta Gopal
Published: November 2006

Much has been said in praise of self‐adjusting data structures, particularly self‐adjusting binary search trees. Self‐adjusting trees are most suited to skewed key‐access distributions as the techniques attempt to place the most commonly accessed keys near the root of the tree. Theoretical bounds on worst‐case and amortized performance (i.e. performance over a sequence of operations) have been derived which compare well with those for optimal binary search trees. In this paper, we compare the performance of three different techniques for self‐adjusting trees with that of AVL and random binary search trees. Comparisons are made for various tree sizes, levels of key‐access‐frequency skewness and ratios of insertions and deletions to searches. The results show that, because of the high cost of maintaining self‐adjusting trees, in almost all cases the AVL tree outperforms all the self‐adjusting trees and in many cases even a random binary search tree has better performance, in terms of CPU time, than any of the self‐adjusting trees. Self‐adjusting trees seem to perform best in a highly dynamic environment, contrary to intuition.
Calendrical calculations, II: Three historical calendars
Authors: Reingold Edward M. , Dershowitz Nachum , Clamen Stewart M.
Published: November 2006

Algorithmic presentations are given for three calendars of historical interest, the Mayan, French Revolutionary, and Old Hindu.
Object identification in the lego kernel
Authors: Hughes Larry
Published: November 2006

In a message‐based operating system, the kernel is responsible for forwarding messages to destination objects using a destination identifier. Part of the kernel overhead in processing the message involves mapping the identifier into a network address. This paper describes how the choice of identifier structure has simplified the techniques used by the Lego kernel when handling messages, notably: minimizing the overheads associated with address mapping, eliminating the reception of unwanted network packets, while permitting both individual (unicast) and group (multicast) communications.
Practical experience of the limitations of gprof
Authors: Varley Dominic A.
Published: November 2006

The Unix profiling tool Gprof produces an execution profile in which the time taken by each routine is added to that of its caller. This communication demonstrates that gprof generates a misleading profile when a routine is called from more than one module.
A performance comparison of event calendar algorithms: An empirical approach
Authors: Chung Kehsiung , Sang Janche , Rego Vernon
Published: November 2006

We propose a suite of tests based on two‐state Markov chains for experimentally assessing the dynamic performance of a variety of simulation event calendar implementations. In contrast to previous studies based on the standard hold model for evaluation of performance statically, the proposed Markov hold model is more general and can be used to examine how different implementations respond dynamically to dependent sequences of insertion and deletion requests. The Markov hold model is used to conduct tests based on random, stressed, and correlated input sequences of requests, with performance measures including completion times, sensitivity to correlations, sensitivity to duplication, and efficiency of data‐handling. We apply these tests to fourteen different event calendar implementations. To demonstrate the utility of the proposed model, we also include a comparison of the event calendar algorithms on a token ring protocol with bursty Markovian packet‐traffic.
Guarded attribute grammars
Authors: Frost R. A.
Published: November 2006

Contrary to a widely‐held belief, it is possible to construct executable specifications of language processors that use a top‐down parsing strategy and which have structures that directly reflect the structure of grammars containing left‐recursive productions. A novel technique has been discovered by which the non‐termination that would otherwise occur is avoided by ‘guarding’ top‐down left‐recursive language processors by non‐left‐recursive recognizers. The use of a top‐down parsing strategy increases modularity and the use of left‐recursive productions facilitates specification of semantic equations. A combination of the two is of significant practical value because it results in modular and expressively clear executable specifications of language processors. The new approach has been tested in an attribute grammar programming environment that has been used in a number of projects including the development of natural language interfaces, SQL processors and circuit design transformers within a VLSI design package.
Design of a safe string library for C
Authors: Narayanan Ajith K.
Published: November 2006

The C programming language provides no bounds‐checking for arrays. As a result, string operations provided in the standard C library are potentially unsafe. A solution, in the form of a safe string library, is presented. The design goals are safety, inter‐operability with existing safe and unsafe routines, debugging help and ease of use.
Multiple‐length division revisited: A tour of the minefield
Authors: Hansen Per Brinch
Published: November 2006

Long division of natural numbers plays a crucial role in Cobol arithmetic, cryptography, and primality testing. Only a handful of textbooks discuss the theory and practice of long division, and none of them do it satisfactorily. This tutorial attempts to fill this surprising gap in the literature on computer algorithms. We illustrate the subtleties of long division by examples, define the problem concisely, summarize the theory, and develop a complete Pascal algorithm using a consistent terminology.
Signature‐check based unification filter
Authors: Maeda Alfredo M. , Aoe Jun‐Ichi , Tomabechi Hideto
Published: November 2006

Among the different processes that entail unification‐based grammar parsing, the unification of feature structures is by far the most expensive one in terms of execution time. Unification of the feature structures of a given sentence typically takes between 85 and 98 per cent of the total elapsed time during parsing, thus the need to develop faster unification methods. The approach presented in this paper is based on the fact that, in general, between 60 and 85 per cent of unifications attempted in a typical parse result in failure. Our claim is that the efficient treatment of such unification failures reduces unification time significantly. In this paper we present what we call a unification filter or U‐filter, that preprocesses the feature structures to be unified. If the U‐filter succeeds, unification is then skipped because the attempt to unify the involved structures would result in failure. On the other hand, when the U‐filter does not succeed it is not possible to determine at that moment whether or not the structures unify, so unification is performed. The U‐filter stops around 87 per cent of unification failures, and speeds up unification time by an average of around 29 per cent over quasi‐destructive graph unification, the fastest unification method known so far.
Automatic synthesis of state machines from trace diagrams
Authors: Koskimies Kai , Mäkinen Erkki
Published: November 2006

The automatic synthesis of state machines describing the behaviour of a class of objects in object‐oriented software modelling is studied. It is shown that the synthesis can be carried out on the basis of trace diagrams giving possible sequences of events during the execution of the system. An algorithm originally developed for the automatic construction of programs on the basis of their execution traces is applied to the problem, and an experimental state machine synthesizer is implemented. It is demonstrated that such a synthesizer is a highly useful component in a practical object‐oriented CASE system.
The application of prolog to structured design
Authors: Tse T. H. , Chen T. Y. , Chan F. T. , Chen H. Y. , Xie H. L.
Published: November 2006

In this paper, we investigate the feasibility of applying logic programming to structured design. We propose to use Prolog as a common machinery for the representation of various structured tools. We illustrate through examples how to produce structure charts from data flow diagrams, and evaluate them according to commonly recommended design guidelines. If the structure charts produced are not satisfactory, the inherent backtracking mechanism in Prolog will help to produce other versions for further evaluation.
Complex performance measurements with NICE (Notation for interval combinations and events)
Authors: Woodside C. Murray , Schramm Cheryl
Published: November 2006

This paper presents a notation for extracting complex performance measurements of parallel software from an event log. NICE defines a ‘complex interval’ as a sequence of events in the event log that match a rather general template using an interval monitor process (IMP). The IMP process model combines an extended FSM with parametrized event descriptors to provide a generalized description of a sequence of subintervals each one of which may be measured for duration. An interval matching algorithm provides a strategy for distributing the events in the log to multiple concurrent IMPs, thereby handling interval occurrences that overlap and/or share the same event. Practical issues of implementing and using NICE are addressed in a discussion of our performance monitoring tool called Finale.
Object request broker: Foundation for distributed simulation
Authors: Kuhl Frederick , Neal William , Cohen Howard
Published: November 2006

Real‐time, human‐in‐the‐loop simulation of air traffic control is naturally distributed across computing platforms because of the need for many input and display devices, the need for computing power, and the need to integrate legacy simulations that run on a variety of platforms. Object orientation has a long history of fruitful application to simulation problems, including real‐time simulation. Thus there is great interest in commercial products for distributed object management. We have examined the suitability of object request broker (ORB) technology for simulation control, i.e. applications‐as‐objects, and for supporting truly object‐oriented, distributed, real‐time simulation. Our experience with DEC's ORB shows that at present the former is feasible but the latter is probably not; however the available implementations are changing rapidly. ORB technology can also bring the distributed interactive simulation (DIS) protocol of the DoD into an object‐oriented framework.