bluuebunny/crossref_metadata_2025_split huggingface dataset:
Signalling regions: Multiprocessing in a shared memory reconsidered
Authors: Reynolds Charles W. 
Published: November 2006

AbstractThe goal of this paper is to return attention to two problems that arise in the context of supporting the monitor as a mechanism for concurrent programming. This paper will re‐examine the monitor concept in its original context—a multiprocessing environment implemented on a single processor sharing memory with and being interrupted by asynchronous peripheral devices—and will address the two previously unresolved problems. The first is the conflict between the immediate resumption requirement in explicit signalling and the policies and priorities of the process scheduler. The second is the possibility of deadlock inherent in nested monitors and in its most important instance, the dynamic resource allocation problem. After briefly describing the historical context of these two problems, the paper proposes a language structure called a signalling region that together with the notion of encapsulation by modules solves the immediate resumption problem and avoids the nested monitor problem. The former is done by a combination of the signal‐and‐return semantics of Concurrent Pascal and the signal‐and‐continue semantics of Mesa and StarMod. The latter is done by suggesting that mutual exclusion and data encapsulation are distinct concepts that, if separated, make nested encapsulation possible while avoiding the problems of nested mutual exclusion. Classical examples of the use of signalling regions in an extended Modula‐2 are given as well as an implementation by translation to unextended Modula‐2 together with a Kernel module.
Run‐time detection of undefined variables considered essential
Authors: Kempton Willett , Wichmann Brian A. 
Published: November 2006

AbstractAccess to an undefined variable—one which has never been assigned a value—can be detected by automatic means. However, today's compilers do not detect undefined variables comprehensively, and the environment dependence of these errors often allows them to evade normal testing procedures. Language standards for Pascal, Modula‐2 and Ada specify the circumstances in which the undefined variable access should cause an error trap. The logic of undefined in these standards is compared, revealing problems in security, implementation effort and consistency with accepted programming practice. An alternative logic, ‘undefined if totally‐undefined’ is proposed.
Univers: An attribute‐based name server
Authors: Bowman Mic , Peterson Larry L. , Yeatts Andrey 
Published: November 2006

AbstractUnivers is a generic attribute‐based name server upon which a variety of high‐level naming services can be built. This paper defines Univers' underlying attribute‐based naming model. It also describes several aspects of its implementation and demonstrates how various naming services—including a global white‐pages service, a local yellow‐pages service and a conventional name‐to‐address mapper—can be built on top of Univers.
Developing human‐computer interface models and representation techniques
Authors: Hartson H. Rex , Hix Deborah , Kraly Thomas M. 
Published: November 2006

AbstractThe 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

AbstractThis 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

AbstractConventional 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

AbstractMost 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

AbstractThis 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

AbstractThe 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

AbstractThis 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

AbstractResearchers 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

AbstractThe 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

AbstractA 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

AbstractThe 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

AbstractWe 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

AbstractA 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

AbstractRTAG 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

AbstractThis 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

AbstractNeural 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.
Integrating prolog and CADAM to produce an intelligent CAD system
Authors: Bond Alan H. , Soetarman Basuki 
Published: November 2006

AbstractA 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

AbstractThis 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

AbstractConcurrent 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

AbstractDistributed 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

AbstractThis 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.