bluuebunny/crossref_metadata_2025 huggingface dataset:
An exception handling method for constructive algebraic specifications
Authors: van Horebeek Ivo , Lewi Johan , Bevers Eddy , Duponcheel Luc , van Puymbroeck Willy
Published: November 2006

This paper describes an exception detection and exception handling method for constructive algebraic specifications. A notation that supports exception handling is introduced. First, a safety function is provided for every sort. This function characterizes each object as being safe or unsafe. Secondly, axioms may contain markers that indicate when they are applicable.

The proposed notation is a trade‐off between readability and capability to handle a large class of exceptional situations. The description of exception handling promotes a two‐step design method for constructive algebraic specifications. In a first step the specification is given with exception detection only; in a second step exception handling is superimposed.
A micro‐kernel for concurrency in C
Authors: Cormack Gordon V.
Published: November 2006

A micro‐kernel that supports concurrent execution of C procedures within a single user process is described. A micro‐kernel provides only four primitives, which have been used to build a number of higher‐level abstractions, including support for distributed processing. The micro‐kernel differs from other efforts in that it is small and efficient, it is written entirely as a non‐privileged user program, and it provides fine‐grained unpredictable interleaving of execution.
Garbage collection of strings and linked data structures in real time
Authors: Nilsen K.
Published: November 2006

Modern high‐level languages frequently need to collect garbage not only from regions of linked structures similar to LISP's dotted pairs, but also from string regions where data is organized as an array of characters. Some characteristics of string regions that make garbage collection particularly difficult are as follows: multiple pointers to the same characters within the array are allowed and encouraged; all possible character values are legitimate as data, so it is not possible to ‘mark’ a string by overwriting with a reserved character; and a character is generally much smaller than a pointer, so it is not possible to overwrite a single character value with a forwarding pointer to a new location for a particular string. This paper describes the addition of certain information to a string descriptor and enhancements to existing copying garbage collection algorithms that permit linked data structures and strings to be allocated and garbage collected from a shared region of memory in real time. This algorithm is real‐time in the sense that the time required for allocation of each basic unit of memory is bounded by a constant. An analysis of performance is reported, and comparisons are made with traditional garbage collection.
A simple system for constructing distributed, mixed‐language programs
Authors: Hayes Roger , Manweiler Steve W. , Schlichting Richard D.
Published: November 2006

The Mixed‐Language Programming (MLP) System is a simple system that facilitates construction of sequential programs in which procedures can be written in different programming languages to exploit heterogeneity in language functionality. In addition, MLP provides a simple remote procedure call (RPC) facility that allows heterogeneity in machine functionality to be exploited. To minimize implementation cost, the system does not solve all of the problems related to mixed‐language programming; rather, MLP is designed to handle common situations well. Among the unique aspects of MLP are its advanced facilities, which allow complex situations to be handled with user intervention; for example, these facilities allow arguments of a type not defined by a language to be used by procedures written in that language. This paper overviews the use of MLP and describes its implementation. In addition, two programs that have been written using the MLP system—a small database system and a collection of plot routines—are discussed. The system executes on a collection of Vaxes and Suns running Berkeley UNIX. Currently supported languages are C, Pascal and Icon.
From modula to oberon
Authors: Wirth N.
Published: November 2006

The programming language Oberon is the result of a concentrated effort to increase the power of Modula‐2 and simultaneously to reduce its complexity. Several features were eliminated, and a few were added in order to increase the expressive power and flexibility of the language. This paper describes and motivates the changes. The language is defined in a concise report1.
A retrospective on DOSE: An interpretive approach to structure editor generation
Authors: Kaiser Gail E. , Feiler Peter H. , Jalili Fahimeh , Schlichter Johann H.
Published: November 2006

DOSE is unique among structure editor generatiors in its interpretive approach. This approach leads to very fast turn‐around time for changes and provides multi‐language facilities for no aditional effort or cost. This article compares the interpretive approach to the compilation approach of other structure editor generators. It describes some of the design and implementation decisions made and remade durign this project and the lessons learned. It emphasizes the advantages and disadvantages of DOSE with respect to other structure editing systems.
Animation of requirements specifications
Authors: Kramer Jeff , Ng Keng
Published: November 2006

Requirements analysis has been recognized as one of the most critical and difficult tasks in software engineering. The need for tool support is essential. This paper reports some work done to provide such support for interpretation and validation of requirements specifications by animation.

The Animator provides facilities for the selection and execution of a transaction to reflect the specified behaviour of a particular scenario specified in the requirements specification. Actions are described in terms of input‐output mappings and or functions with pattern matching. Simple rules can be specified to control the triggering of actions. In addition, facilities are provided to replay and interact with transactions. User interaction during animation includes the ability to change data values or role play selected actions as desired. A full graphical interface is supported.

The approach has been tested by the provision of an Animator for the requirements analysis method CORE and an associated ‘Analyst Workstation’. Animation has been tested on a number of small examples and a major case study. This paper describes the Animator, justifies the approach taken and discusses experience and future work.
A study of a C function inliner
Authors: Davidson Jack W. , Holler Anne M.
Published: November 2006

Although the inline expansion of subprograms has often been cited as a method for improving a program's execution time, few available compilers perform the operation, and fewer still perform it without requiring explicit direction from the programmer. The authors have written a tool called INLINER, which is a source‐to‐source filter that automatically performs inline expansion of C functions in a module. With this tool, the effect of inlining was investigated using a set of programs on several machines. The authors' findings are presented, including an instance (unrelated to the size of the inlined executable) in which inlining can diminish a program's performance, and evidence that the size of the inlined executable does not, in practice, prove to cause problems.
GPROC—an integrated system for the processing of numerical scientific data
Authors: O'Neill M. A.
Published: November 2006

Work done on an interactive graphical processing system is described. An overview is given of the uses to which a system could be put, with especial reference to aspects of solid state physics. Algorithms which may be usefully included in such a system, when used in a technical scientific environment, are described. The problems of implementing such a system on small microcomputer systems are outlined, and some possible areas of future development are discussed.
The distributed operating system of the SMD project
Authors: Marques J. Alves , Cunha J. P. , Guedes P. , Guimarães N. , Cunha A.
Published: November 2006

This article analyses the structure of the distributed operating system of the SMD project— DIOS.

The description of the basic structure is followed by a global view of the services and the supporting kernel of the system. Each service is analysed according to its functionality and implementation.

DIOS was implemented on bare machines and on top of commercial operating systems. The port of the system to hetereogeneous environments is discussed and some implementation details are described.

In parallel with the research on DIOS a multiprocessor station has been developed. These two projects had clear influences on each other; to illustrate some of the major interdependencies, the performance of DIOS in their particular architecture is analysed.

The paper ends with information on the current status of the project and on some planned directions of work.
Compiler performance analysis tools
Authors: Heines T. S. , Jalics P. J.
Published: November 2006

Most of the performance bench‐marks for compilers do not give detailed performance characteristics that might be useful to a programmer. The goal of most bench‐marks seems to be to produce a single number. A set of bench‐mark tools that measure individual language features of C and generate a large number of measurements has been designed to create a detailed performance profile of any C compiler. There is an emphasis on the detailed statement‐level measurements of both CPU and I/O aspects of C, but there is also a range of routine and program‐level bench‐marks that seek to measure the interaction of CPU and I/O in actual application programs. The programs are portable, parametrized, and openended so that additional measurements can be added with little effort. With some additional effort, the tools could be adapted to other languages.
The design of an object‐oriented command interpreter
Authors: Budd Timothy A.
Published: November 2006

Object‐oriented programming languages are noted for their ability to allow users quickly to construct large software systems. They achieve this ability by allowing the programmer to concentrate on what it is they want to do, ignoring details of how that functionality is achieved. Such characteristics should make the object‐oriented style of programming attractive to casual or novice computer users, indeed one of the best known object‐oriented programming languages, Smalltalk, was initially designed with just such novice users in mind.

The Unix operating system is widely regarded as a good environment for doing software development. Nevertheless, its large number of often terse and cryptic commands make it difficult for novice or casual users to use. In this paper we argue that one solution is to create an object‐oriented command interpreter, or shell, between the user and the underlying system. This paper reports on the construction of one such prototype shell, and the lessons we have learned from the use of this system.
Quick compilers using peephole optimization
Authors: Davidson Jack W. , Whalley David B.
Published: November 2006

Abstract machine modelling is a popular technique for developing portable compilers. A compiler can be quickly realized by translating the abstract machine operations to target machine operations. The problem with these compilers is that they trade execution efficiency for portability. Typically, the code emitted by these compilers runs two to three times slower than the code generated by compilers that employ sophisticated code generators. This paper describes a C compiler that uses abstract machine modelling to achieve portability. The emitted target machine code is improved by a simple, classical rule‐directed peephole optimizer. Our experiments with this compiler on four machines show that a small number of very general handwritten patterns (under 40) yields code that is comparable to the code from compilers that use more sophisticated code generators. As an added bonus, compilation time on some machines is reduced by 10 to 20 per cent.
Practical interface specification
Authors: Hoffman Daniel
Published: November 2006

Although software development based on modules is now widely practiced and taught, specification of module interfaces has received far less acceptance. Languages such as Ada and Modula‐2 require an interface specification, but it is syntactic, merely listing the exported procedures and functions and their signatures. No semantic information is given, leaving the effect of each call on the return value of other calls unspecified. Module users must either guess the interface semantics or infer them from the module implementation, seriously compromising the value of the modular approach. Formal methods, such as the algebraic and trace approaches, do specify interface semantics, but have proved difficult to teach and to apply in practice.

In this paper we present the software cost reduction (SCR) method for specifying the syntax and semantics of the module interface. We describe the basic approach and illustrate it on simple, but complete examples. We describe and demonstrate the additional features and techniques we have introduced to handle more complex problems. We also show the precise relationship between the SCR and trace techniques by presenting a method for converting any SCR specification to an equivalent trace specification.
Interprocedural optimization: Experimental results
Authors: Richardson Stephen , Ganapathi Mahadevan
Published: November 2006

The problem of tracking data flow across procedure boundaries has a long history of theoretical study by people who believed that such information would be useful for code optimization. Building upon previous work, an algorithm for interprocedural data flow analysis has been implemented. The algorithm produces three flow‐insensitive summary sets: MOD, USE and ALIASES. The utility of the resulting information was investigated using an optimizing Pascal compiler. Over a sampling of 27 bench‐marks, new optimizations performed as a result of interprocedural summary information contributed almost nothing to program execution speed. Finally, related optimization techniques of possibly greater potential are discussed.
Simple generational garbage collection and fast allocation
Authors: Appel Andrew W.
Published: November 2006

Generational garbage collection algorithms achieve efficiency because newer records point to older records; the only way an older record can point to a newer record is by a store operation to a previously created record, and such operations are rare in many languages. A garbage collector that concentrates just on recently allocated records can take advantage of this fact. Such a garbage collector can be so efficient that the allocation of records costs more than their disposal. A scheme for quick record allocation attacks this bottleneck. Many garbage‐collected environments do not know when to ask the operating system for more memory. A robust heuristic solves this problem.

This paper presents a simple, efficient, low‐overhead version of generational garbage collection with fast allocation, suitable for implementation in a Unix environment.
Word‐based text compression
Authors: Moffat Alistair
Published: November 2006

The development of efficient algorithms to support arithmetic coding has meant that powerful models of text can now be used for data compression. Here the implementation of models based on recognizing and recording words is considered. Move‐to‐the‐front and several variable‐order Markov models have been tested with a number of different data structures, and first the decisions that went into the implementations are discussed and then experimental results are given that show English text being represented in under 2‐2 bits per character. Moreover the programs run at speeds comparable to other compression techniques, and are suited for practical use.
An implementation of the object‐oriented concurrent programming language SINA
Authors: Tripathi Anand , Berge Eric , Aksit Mehmet
Published: November 2006

SINA is an object‐oriented language for distributed and concurrent programming. The primary focus of this paper is on the object‐oriented concurrent programming mechanisms of SINA and their implementation. This paper presents the SINA constructs for concurrent programming and inter‐object communication, some illustrative examples and a message‐based implementation model for SINA that we have used in our current implementation.
Comparative timings of three different set implementations in occam
Authors: Wilson G. A. , Wilson G. A.
Published: November 2006

Three different occam implementations of a Set datatype have been investigated, using arrays of bits, booleans (bytes) and full integers, and the performance of each compared. Execution times and code/data requirements are recorded, and surprisingly the best implementation is not as originally expected.
SAHAYOG: A test bed for evaluating dynamic load‐sharing policies
Authors: Dikshit Piyush , Tripathi Satish K. , Jalote Pankaj
Published: November 2006

This paper describes the implementation of a test bed called SAHAYOG, for evaluating dynamic load‐sharing policies in which job‐transfer decisions are based on the state of the system. The test bed is implemented on a network of AT&T 3B2 minicomputers. It provides an interactive user interface for conducting load‐sharing experiments. Based on user‐specified parameters it creates independent job streams at different nodes in the network. Jobs are transferred among the nodes by the load‐sharing algorithm being evaluated. Each node collects data about the jobs, which are used to generate statistics about the experiment. Five load‐sharing algorithms are implemented and evaluated using the test bed under different load conditions and for various parameter values. These experiments confirm some earlier results about load sharing and also provide some new insights. SAHAYOG also contains an optional fault‐tolerance feature to handle single‐node failures, and evaluates the effect of fault tolerance on the performance of different policies.
A user interface specification for a program debugging and measuring environment
Authors: Lopriore Lanfranco
Published: November 2006

A high level of complexity is involved in program dynamics. A number of tools have been developed to assist the programmer in mastering this complexity in the various phases of software development. However, these tools are specifically oriented towards the monitoring of particular aspects of program behaviour. This paper presents the results of a systematic attempt at defining the user interface to an environment for program debugging, program performance evaluation and program structure analysis. This environment can be used to implement many common debugging techniques, and to evaluate important program performance indexes and program structure statistics. It supports both sequential and concurrent block‐oriented high‐level languages.
A performance study of deadlock prevention algorithms in a distributed file system
Authors: Ha&Ca Anna , Jin Xiaowei , Soo Jo‐Han
Published: November 2006

This paper describes an implementation and performance evaluation of different deadlock prevention algorithms. A deadlock prevention algorithm ensures that deadlock will never happen. The algorithms for deadlock prevention are proposed and implemented in a locally distributed system. A number of experiments were executed in a distributed system for various lengths of file operation and different numbers of files. The performance of the system and of each algorithm is evaluated and discussed. Some general results are derived for a single‐host and a distributed system.
A visual shell interface to a database
Authors: Rowe Lawrence A. , Danzig Peter , Choi Wilson
Published: November 2006

This paper describes a visual command language for a workstation with a bit‐mapped display and a mouse that can be used to create different user interfaces. Primitive interface components can be combined into more complex user interfaces. The user specifies interconnections between these components over which data and commands can be sent by pointing with a mouse.

Primitive interface components are described for creating several different database user interfaces. The design and implementation of the software architecture is described, including the primitives for database interfaces and the communication protocols used by the system.
A multiprocessor implementation of joyce
Authors: Hansen Per Brinch
Published: November 2006

Joyce is a programming language for parallel computers based on CSP and Pascal. A Joyce program defines concurrent agents which communicate through unbuffered channels. This paper describes a multiprocessor implementation of Joyce.
Set notation as a language to specify data transformation programs
Authors: Abbott Russell J.
Published: November 2006

To allow tools in a computer‐based working environment to share data, it is sometimes necessary to transform the data from the form used by one tool to the form expected by another. An application generator has been developed that generates data transformation programs from high‐level descriptions of the required transformations. The transformation specifications are expressed in traditional set notation, which combines features of functional and logic programming. The system thus offers a powerful declarative language for expressing data transformations.
The errors of tex
Authors: Knuth Donald E.
Published: November 2006

This paper is a case study of program evolution. The author kept track of all changes made to TEX during a period of ten years, including the changes made when the original program was first debugged in 1978. The log book of these errors, numbering more than 850 items, appears as an appendix to this paper. The errors have been classified into fifteen categories for purposes of analysis, and some of the noteworthy bugs are discussed in detail. The history of the TEX project can teach valuable lessons about the preparation of highly portable software and the maintenance of programs that aspire to high standards of reliability.
The performance of message‐passing using restricted virtual memory remapping
Authors: Tzou Shin‐Yuan , Anderson David P.
Published: November 2006

DASH is a distributed operating system kernel. Message‐passing (MP) is used for local communication, and the MP system uses virtual memory ( VM) remapping instead of software memory copying for moving large amounts of data between virtual address spaces. Remapping eliminates a potential communication bottleneck and may increase the feasibility of moving services such as file services to the user level. Previous systems that have used VM remapping for message transfer, however, have suffered from high per‐operation delay, limiting the use of the technique. The DASH design reduces this delay by restricting the generality of remapping: a fixed part of every space is reserved for remapping, and a page's virtual address does not change when it is moved between spaces.

We measured the performance of the DASH kernel for Sun 3/50 workstations, on which memory can be copied at 3·9 MB/s. Using remapping, DASH can move large messages between user spaces at a rate of 39 MB/s if they are not referenced and 24·8 MB/s if each page is referenced. Furthermore, the per‐operation delay is low, so VM remapping is beneficial even for messages containing only one page. To further understand the performance of the DASH MP system, we broke an MP operation into short code segments and timed them with microsecond precision. The results show the relative costs of data movement and the other components of MP operations, and allow us to evaluate several specific design decisions.
TPDL: Extended temporal profile description language
Authors: Cabodi G. , Camurati P. , Prinetto P. , Reorda M. Sonza
Published: November 2006

This paper presents TPDL (extended temporal profile description language), a general‐purpose language to observe and condition dynamic systems by means of temporal and logical expressions. It describes how time is modelled in TPDL, gives an overview of the language through its basic types, primitives and conditional constructs, and its use in computer‐aided design of digital systems. The paper discusses TPDL's facilities to support the description of hardware behaviour, to define the environment in which devices operate, and to observe and control both circuits and environments. The characteristics of the language are demonstrated through some representative examples.
NovAtel's novel approach to CPU usage measurement
Authors: Crowe David R.
Published: November 2006

This paper describes a set of CPU usage analysis tools, named CPU Probes, with the benefits of both hardware and software tools, and few of their disadvantages. CPU probes use a serial line unit or programmable interval timer as a clock to sample the CPU usage of a system, resulting in fast and accurate CPU usage estimates. CPU usage can be monitored for all processes simultaneously or as little as a single machine instruction. CPU probes are well suited for monitoring real‐time system performance. These tools have been implemented on PDP‐11/RSX and UNIX System V/386 systems.
Profiling software through the use of metrics
Authors: Robillard Pierre N. , Coupal Daniel , Coallier François
Published: November 2006

This paper presents an approach to software assessment using a new software tool that integrates most of the known static metrics. A six‐step method shows how to use metrics to obtain a picture of the software project. The method is visual and each step provides graphical representations of the data. Successive integration of data results in normality profiles. Examples illustrate each step. The method is adaptable to various environments and specific applications.
Design and implementation of a distributed file system
Authors: Cheng Hsiao‐Chung , Sheu Jang‐Ping
Published: November 2006

We introduce a new model for replication in distributed systems. The primary motivation for replication lies in fault tolerance. Although there are different kinds of replication approaches, our model combines the advantages ofmodular redundancyandprimary‐stand‐byapproaches to give more flexibility with respect to system configuration.

To implement such a model, we select the IBM PC‐net with MS‐DOS environment as our base.Transparencyas well asfault‐tolerance file accessare the highlights of our system design. To fulfil these requirements, we incorporate the idea ofdirectory‐oriented replicationandextended prefix tablesin the system design. The implementation consists of a command shell, a DOS manager, and a recovery manager. Through this design, we can simulate a UNIX‐like distributed file system whose function is compatible with MS‐DOS.
Literate programming on a team project
Authors: Ramsey Norman , Marceau Carla
Published: November 2006

We used literate programming on a team project to write a 33,000 line program for the Synthesizer Generator. The program, Penelope, was written using WEB, a tool designed for writing literate programs. Unlike other WEB programs, many of which have been written by WEB's developer or by individuals, Penelope was not intended to be published. We used WEB in the hope that both our team and its final product would benefit from the advantages often attributed to literate programming. The WEB source served as good internal documentation throughout development and maintenance, and it continues to document Penelope's design and implementation. Our experience also uncovered a number of problems with WEB.
An inheritance model for supporting flexible displays of data structures
Authors: Dewan Prasun
Published: November 2006

We have designed an inheritance model that reduces the effort required to define presentations of data structures of programs written in conventional languages. It assumes that the presentation of a data structure is determined by one or more attributes of the data structure; classifies data structures into several groups based on their types, contexts, siblings, ancestors and other properties; and allows an attribute to be defined once for all members of a group. These groups are arranged in multiple intersecting hierarchies, and a subgroup is allowed to inherit attributes from its supergroups(s). This paper motivates, describes, and illustrates our method of grouping values and arranging the value groups in inheritance hierarchies.
Extending regular expressions with context operators and parse extraction
Authors: Kearns Steven M.
Published: November 2006

Regular expressions are used in many applications to specify patterns because any regular expression can be compiled into a very efficient one‐pass pattern matcher called a finite automaton. Finding matches is useful, but even more useful is parse extraction, which describes in detail how a pattern matches some input. After matching an address, for example, parse extraction makes it easy to find out the Zip code part of the address. We present an elegant, efficient algorithm for extracting a parse after matching with a finite automaton. In addition, we extend the regular expression language to include new operators for matching arbitrary left context and single character right context. The extended language can be matched as efficiently as the usual regular expression language, but is more expressive. Finally, we suggest how to apply the matching algorithms to match regular expressions containing arbitrary right context and single character left context. In effect, this allows one to specify patterns that seem to require an unlimited amount of look‐ahead to match.
Compiled instruction set simulation
Authors: Mills Christopher , Ahalt Stanley C. , Fowler Jim
Published: November 2006

An efficient method for simulating instruction sets is described. The method allows for compiled instruction set simulation using the macro expansion capabilities found in many languages. Additionally, we show how the semantics of the C case statement allows instruction branching to be incorporated in an efficient manner. The method is compared with conventional interpreted techniques and is shown to offer considerable performance benefits.
A multi‐protocol campus time server
Authors: Snow C. R.
Published: November 2006

A time server system has been constructed at the University of Newcastle upon Tyne which may be accessed by users of the campus Ethernet. It uses a commercially available radio clock to receive an accurate time signal from the MSF transmitter at Rugby, and can respond to requests from users of the network using a number of different protocols. This paper describes the server system, both hardware and software, and discusses some network management issues raised as a result of the associated experimentation and testing of the system.
A design rationale for a language‐based editor
Authors: Welsh Jim , Broom Brad , Kiong Derek
Published: November 2006

This paper reviews the design issues that arise in the construction of effective language‐based editors for the preparation of syntactically and static semantically correct language sentences, typically computer programs. The need for such editors to support a pluralistic view of program structure is identified, together with the need to observe the constraints on performance and storage consumption if such editors are to be accepted by professional programmers. From these basic needs, more specific requirements for the display, parsing and semantic checking components of such an editor are derived.
Simple register spilling in a retargetable compiler
Authors: Fraser Christopher W. , Hanson David R.
Published: November 2006

This paper describes the management of register spills in a retargetable C compiler. Spills are rare, which means that testing is a bigger problem than performance. The trade‐offs have been arranged so that the common case (no spills) generates respectable code quickly and the uncommon case (spills) is less efficient but as simple as possible. The technique has proven practical and is in production use on VAX, Motorola 68020, SPARC and MIPS machines.
Incremental semantic evaluation in language‐based editors
Authors: Kiong Derek , Welsh Jim
Published: November 2006

We present an incremental semantic analysis strategy for use in language‐based editors. Its advantage is the low storage cost involved in achieving incremental semantic operation with a relatively small loss in response. The scheme, which involves limiting identifier attribute flow, is first described for a simple block‐structured language like Pascal, and then extended to more modern modular languages.
Efficient prolog programming
Authors: Knuutila Timo
Published: November 2006

This paper presents some basic programming strategies for Prolog programmers. The strategies are based on knowledge about the operational behaviour of the Warren Abstract Machine (WAM). The aim is to provide simple principles for making programs both faster and less space‐consuming. The programming hints given are mostly local, i.e. only a single clause or procedure need be considered at a time.
A parallel database‐driven protocol verification system prototype
Authors: Frieder O.
Published: November 2006

Protocol verification systems test the specification of communication protocols. A prototype of a protocol verification system based on parallel database primitives for a hypercube multicomputer is described. Using the described prototype, two conventional protocols are verified. To evaluate the performance of verification systems, a synthetic protocol that is to be used as a benchmark is proposed. Extensions to and properties of the synthetic protocol are described. Using this protocol, the performance of the developed verification system is evaluated.
Implementing concurrent C
Authors: Gehani N. H. , Roome W. D.
Published: November 2006

Concurrent C (C++) is a parallel superset of C (C++). Versions of Concurrent C have now been implemented for a variety of uniprocessors and multiprocessors. We first implemented a uniprocessor version of Concurrent C correctly anticipating that it would be relatively easy to extend the uniprocessor implementation to run on multiprocessors. Concurrent C is translated to C. The generated C code contains calls to the C library implementing the Concurrent C run‐time system.

This paper describes the ‘hard core’ details of the Concurrent C implementation: the specifics of process states, the data structures used, the library functions, and the C code generated for various Concurrent C constructs. We also give an overview of the Concurrent C facilities and of the uniprocessor, distributed and shared‐memory multiprocessor implementations.
Object‐oriented implementation issues in an experimental CAD system
Authors: Wolf Wayne
Published: November 2006

This case study of object‐oriented program design illustrates two limitations of object‐oriented programming languages. Existing object‐oriented languages do not have good facilities to support two key program design problems: the definition of composite objects, or data structures that include sets of related subobjects; and the specification and run‐time management of temporary data structures required to implement efficient algorithms. Both composite objects and temporary data structures are important to the construction of a wide variety of programs. We use the design and implementation of an interactive computer‐aided design system to describe how the limitations of present object‐oriented languages complicate the design of composite objects and temporary data structures.
ARTK‐M2: A kernel for Ada tasking requirements: An implementation and an automatic generator
Authors: Díaz‐Herrera Jorge L. , Graft Ronald D. , Rupp Douglas B.
Published: November 2006

A run‐time kernel, ARTK‐M2, supporting Ada tasking semantics is discussed; full support for task creation, synchronization, communication, scheduling, and termination is provided, together with all options of the Ada rendezvous. An implementation in Modula‐2 is presented and a method for automatically translating Ada programs into semantically equivalent Modula‐2 programs with corresponding kernel calls is introduced. A parser generator and an attribute grammar were used for the automatic translation. A subset of the Ada Compiler Validation Capability was processed to test the implementation and to illustrate the translation mechanism. The kernel is applicable to the study of real‐time control systems; it can also serve as a baseline for studying implementation alternatives of Ada concepts, such as new scheduling algorithms, and for analysing new language constructs. Work is under way to implement some of the changes to the Ada tasking model being proposed as a result of the language revision (Ada9X). Finally, through proper extensions, ARTK‐M2 can form an integral part of programming tools such as an Ada compilation system and a distributed kernel for multi‐processing environments.
A vector C and Fortran compiler for the FPS T‐series: Experiences with compiling to occam I
Authors: Stevenson D. E. , Ammons L. K. , Crosmun W. G. , Jackson A. , Raj G. L.
Published: November 2006

We describe our implementation of C and Fortran preprocessors for the FPS T‐series hypercube. The target of these preprocessors is the occam I language.

We provide a brief overview of the INMOS transputer and the Weitek vector processing unit (VPU). These two units comprise one node of the T‐series. Some depth of understanding of the VPU is required to fully appreciate the problems encountered in generating vector code. These complexities were not fully appreciated at the outset.

The occam I language is briefly described. We focus on only those aspects of occam I which differ radically from C. The transformations used to preprocess C into occam I are discussed in detail. The special problems with the VPU both in terms of its (non)interface with occam I and in dealing with numerical programs is discussed separately.

A lengthy discussion on the special techniques required for compilation is provided. C and Fortran are simply incompatible with the occam I model. We provide a catalogue of problems encountered. We emphasize that these problems are not so much with occam I but with preprocessing to occam I. We feel the CSP and occam I models are quite good for distributed processing.

The ultimate message from this work should be seen in a larger context.

Several languages—such as Ada and Modula‐2—are being touted as the standards for the 1990s. These languages severely restrict parallel programming style; this may make saving dusty decks by preprocessing an impossibility.
A new parsing method for non‐LR(1) grammars
Authors: Harford A. Gayler , Heurinc Vincent P. , Main Michael G.
Published: November 2006

One of the difficult problems that faces a compiler writer is to devise a grammar that is suitable for both efficient parsing and semantic attribution. This paper describes a system that resolves conflicts in LR(1) parsing by taking advantage of information in the parse tree. The system, which functions as part of a compiler generator, rewrites the user's grammar to remove parsing conflicts. It then places code into the generated compiler that rewrites the parse tree during parsing so as to produce the tree of the original grammar. The compiler writer can then write the semantic attribution to fit his or her original grammar without any knowledge of the changes made. The method is expected to be efficient in most cases, even in parsing systems that do not explicitly build the entire parse tree. The method complements previous work in its capabilities and advantages. The system has been implemented and integrated into a compiler generator system.
Selecting the median and two quartiles in a set of numbers
Authors: Cunto Walter , Munro J. Ian , Rey Manuel
Published: November 2006

The median, the 0.25‐percentile and the 0.75‐percentile are three of the most relevant ranks in data analysis. MED2Q is a new in situ algorithm to solve this problem. It asymptotically performs an average of 2 5/8 n + o(n) comparisons when n numbers are given as input thus becoming the asymptotically fastest algorithm for this problem reported to date. The performance of MED2Q is compared with those of FIND1 and ALGORITHM 4892, two well‐known selection algorithms adapted to this specific problem. From this performance comparison, MED2Q is best when input sets consist of more than 50,000 numbers.
Ingest—A simple program for performing distributed relational database operations
Authors: Silberberg David
Published: November 2006

The Hubble Space Telescope (HST) and ground system produce approximately 600 gigabytes of data per year in the form of many types of datasets. Because of the formidable size of the total data stream, the datasets are impractical to manage with a conventional database system. Therefore, they are archived onto an optical disk juke‐box system. A smaller HST Catalog exists to describe the archived data and manage access to the HST archived data. When the Catalog keywords are queried, the resulting records point to file names stored in the archive. This allows users to request datasets by their descriptive keywords instead of file names.

The Catalog is populated by data from several external databases via the Ingest program. Ingest normalizes and/or joins rows of multiple external database tables and writes the new rows to the HST Catalog. Secondarily, Ingest parses data values, translates data values, and creates row identifiers for each row to be written to the HST Catalog. The Ingest process is driven by translation tables residing in the object database which can be altered on‐the‐fly. This paper describes the design of the HST Catalog Data Ingest program in more detail.

Ingest has proven to be a powerful tool in the HST environment where functional requirements are many, database structures are enormous and both evolve rapidly.
Arithmetic equality constraints as C++ statements
Authors: Van Wyk Christopher J.
Published: November 2006

Simultaneous equations arise naturally in problems from a variety of application areas. This paper describes how to use two object‐oriented features of C++—operator overloading and virtual functions—to allow a programmer to express and to solve a system of simultaneous equations directly in a C++ program.
Problems with determining package cohesion and coupling
Authors: Rising Linda , Calliss Frank W.
Published: November 2006

The cohesion and coupling guidelines described by Yourdon, Constantine and Myers have proved useful aids for the design of modular programs. They have also provided direction for the evaluation of existing modules, pointing to those candidates for restructuring during perfective maintenance. For languages like Ada, where support for a higher‐level of abstraction is provided in the form of a package, subprogram heuristics are inadequate. This paper examines existing guidelines and taxonomies for the Ada package and proposes extensions to these schemes. These package‐level schemes are applied in a case study of an existing Ada program.
An optimizing compiler for the icon programming language
Authors: Walker Kenneth , Griswold Ralph E.
Published: November 2006

Compiling code for the Icon programming language presents several challenges, particularly in dealing with types and goal‐directed expression evaluation. In order to produce optimized code, it is necessary for the compiler to know much more about operations than is necessary for the compilation of most programming languages. This paper describes the organization of the Icon compiler and the way it acquires and maintains information about operations. The Icon compiler generates C code, which makes it portable to a wide variety of platforms and also allows the use of existing C compilers for performing routine optimizations on the final code. A specially designed implementation language, which is a superset of C, is used for writing Icon's run‐time system. This language allows the inclusion of information about the abstract semantics of Icon operations and their type‐checking and conversion requirements. A translator converts code written in the run‐time language to C code to provide an object library for linking with the code produced by the Icon compiler. The translation process also automatically produces a database that contains the information the Icon compiler needs to generate and optimize code. This approach allows easy extension of Icon's computational repertoire, alternate computational extensions, and cross compilation.
Multilevel security in the UNIX tradition
Authors: McIlroy M. D. , Reeds J. A.
Published: November 2006

The original UNIX system was designed to be small and intelligible, achieving power by generality rather than by a profusion of features. In this spirit we have designed and implemented IX, a multilevel‐secure variant of the Bell Labs research system. IX aims at sound, practical security, suitable for private‐and public‐sector uses other than critical national‐security applications. The major security features are: private paths for safe cooperation among privileged processes, structured management of privilege, and security labels to classify information for purposes of privacy and integrity. The labels of flies and processes are checked at every system call that involves data flow and are adjusted dynamically to assure that labels on outputs reflect labels on inputs.
Assignment of independent tasks to minimize completion time
Authors: Blake Ben A.
Published: November 2006

The task of scheduling dynamic applications that consist of single process tasks on a non‐shared memory multicomputer is examined in this paper. Each task of the application is assumed to (1) require execution on a single processor, (2) have an estimate of its maximum execution time, and (3) not wait on communications with other tasks. The objective of the studied schedulers is to map an application's tasks onto the underlying hardware in such a way that the application's completion time is minimized. Experimental evaluation of the schedulers indicate that in many situations, a more sophisticated scheduler fails to outperform simpler schedulers.
Synchronous and asynchronous handling of abnormal events in the μsystem
Authors: Buhr Peter A. , Macdonald Hamish I. , Zarnke C. Robert
Published: November 2006

This paper presents a general model for dealing with abnormal events during program execution and describes how this model is implemented in the μSystem. (The μSystem is a library of C definitions that provide light‐weight concurrency on uniprocessor and multiprocessor computers running the UNIX operating system.) Two different techniques can be used to deal with an abnormal event: an exception, which results in an exceptional change in control flow from the point of the abnormal event; and an intervention, which is a routine call from the point of the abnormal event that performs some corrective action. Users can define named exceptions and interventions in conjunction with ones defined by the μSystem. Exception handlers and intervention routines for dealing with abnormal events can be defined/installed at any point in a program. An exception or intervention can then be raised or called, passing data about the abnormal event and returning results for interventions. Interventions can also be activated in other tasks, like a UNIX signal. Such asynchronous interventions may interrupt a task's execution and invoke the specified intervention routine. Asynchronous interventions are found to be useful to get another task's attention when it is not listening through the synchronous communication mechanism.