bluuebunny/crossref_metadata_2025 huggingface dataset:
An integrated data dictionary to facilitate automatic report generation in a network database
Authors: Lirov Yuval , Daunov Nissim
Published: November 2006

An integrated data dictionary (IDD) is defined to contain data definitions and their applications descriptions. An IDD which includes report descriptions may be used as an input data structure for the automatic constructor of report generators (ACORG) in any data manipulation language. ACORG may be programmed in an elegant way using recursive techniques.
Real‐time interrupt handling in Ada
Authors: Rasmussen Jørgen Born , Appelbe Bill
Published: November 2006

The Ada† programming language defines the semantics of interrupt handling as part of the tasking mechanism, making it possible to construct implementation‐independent interrupt handlers. However, for the Ada mechanism to be effective, an implementation must provide support not specified by the Ada standard, such as for initializing hardware interrupting devices, handling unexpected interrupts and optimizing for real‐time performance constraints. This paper analyses some of the constraints that efficient interrupt support places on an implementation. It develops a model for the interaction between interrupt hardware and Ada tasks and describes optimizations for Ada interrupt handlers. Implementation issues, including task priorities and task termination for interrupt handlers, are discussed in detail.
Microprocessor debugging techniques and their application in debugger design
Authors: Gondzio Marek
Published: November 2006

Every microprocessor‐based system needs powerful debugging tools. Debugging power strongly depends on a mechanism of control exchange between the debugger and an application program. Several implementation methods of such a mechanism are briefly described and compared in this paper. It is shown that conditional breakpoints facilitate a semantics‐oriented approach to program debugging. Some debugging techniques derived from elementary control‐exchange mechanisms are proposed. Most of the techniques discussed are implemented in the MD‐86 debugger designed for the Intel 8086 microprocessor. The debugger itself is also briefly described.
AIDA–A dynamic data flow anomaly detection system for pascal programs
Authors: Chan Fun Ting , Chen Tsong Yueh
Published: November 2006

This paper presents a description of, and experience in using, AIDA, an automated instrumentation system to perform data flow analysis for Pascal programs. AIDA is capable of detecting not only data flow anomalies, but also certain kinds of errors. It is a useful software testing and development tool for Pascal programs. The associated implementation problems and their solutions are presented.
Strongly typed user interfaces in an abstract data store
Authors: Powell M. S.
Published: November 2006

The UMIST Abstract Data Store is a software tool which supports abstract data types together with flexible mechanisms for specifying, for each abstract data type, alternative user interface and memory representations appropriate to different physical media. These mechanisms facilitate the definition of types, the specification of their alternative representations and the creation and manipulation of their values in a persistent fashion. The media supported may include such things as disks and visual displays and collections of these connected together via a network. This paper focuses on the mechanisms which have evolved in this environment for specifying safe user interfaces to complex data structures.
A joyce implementation
Authors: Hansen Per Brinch
Published: November 2006

Joyce is a programming language for distributed systems based on CSP and Pascal. A Joyce program defines concurrent agents which communicate through unbuffered channels. This paper describes a surprisingly simple single‐processor implementation of Joyce which runs on an IBM‐PC.
Experience acquiring and retargeting a portable Ada compiler
Authors: Ardö Anders
Published: November 2006

A technique for implementing Ada with reasonable effort on a piece of non‐standard hardware is described. The target machine is a single processing element in an experimental multiprocessor based on NS32000. A portable Ada front‐end compiler was used for retargeting, and the process of acquiring and evaluating the front end is described. Based on this experience, comments on the validation, quality and efficiency of Ada compilers are given, along with a detailed overview of the resultant system. The Ada system was built from scratch on the bare hardware. It has three main components: a code generator, a run‐time system and an Ada kernel. The code generator is table driven and generates symbolic NS32000 assembler. This code is then assembled and linked by commercially available components. The run‐time system and the kernel are implemented in assembly language and Concurrent Euclid and handle tasking, exceptions and scheduling. The result is a complete Ada implementation.
A prolog implementation of an instruction‐level processor simulator
Authors: Pashtan Ariel
Published: November 2006

This paper describes the implementation of a Prolog‐based, instruction‐level simulator used in the design of a new processor. The adaptability of Prolog as a hardware description language is reported. Prolog was a good choice for purposes of rapid prototyping and as a means to derive high‐level executable specifications for the instruction set. The rapid software development strategy entailed a price to be paid in the form of a relatively slow performance. Methods to improve the speed of Prolog‐based simulators are suggested.
Mkscan—An interactive scanner generator
Authors: Horspool R. Nigel , Levy Michael R.
Published: November 2006

Mkscan is a tool for generating and editing scanners. It has been designed with ease of use in mind. The tol is interactive and uses a full screen interface. No attempt is made to provide an all‐purpose tool that can generate a recognizer for any regular language. Instead, mkscan has been tailored to suit the lexical structure of common programming languages and command languages. Using mkscan, a scanner for Pascal can be created in under ten minutes–including the time taken to type the list of keywords.
A method for interconnecting heterogeneous computer networks
Authors: Cole Robert
Published: November 2006

The real problems of network interconnection lie in the management of heterogeneity. The heterogeneity is not confined to the mechanical protocols but to much wider issues such as service philosophy (connection‐orientated vs connectionless), addressing, routing, applications models, management facilities and the foresight of the network designers in allowing for interconnection with alien networking systems.

This paper describes a system which interconnects two heterogeneous networking environments through a third (local) system. Application layer relaying was chosen to provide the services of computer mail and remote terminal access. The interconnection architecture uses special network front‐ends and a local area network to provide a flexible and manageable system. A transport service interface is used to provide functional separation between the front‐ends and general purpose computers, including the relays.
Hashing as a compaction technique for parser tables
Authors: Horspool R. N. , Cormack G. V.
Published: November 2006

Authors of papers on LR parser table compaction and authors of books on compiler construction appear to have either overlooked or discounted the possibility of using hashing. In fact, hashing is easy to implement as a compaction technique and gives reasonable performance. It produces tables that are as compact as some of the other techniques reported in the literature while permitting efficient table lookups.
The design and use of a prolog trace generator for CSP
Authors: Kourie D. G.
Published: November 2006

The role of traces in the context of formal description techniques is discussed, as well as issues arising in the generation of these traces by means of software. A trace generator (written in Prolog) for systems described in terms of CSP is outlined, with emphasis on the translation from CSP to Prolog, the central implementation issues in a Prolog context, and techniques for generating all traces up to termination or recursion. Some experiences with the use of the generator are mentioned, and potential extensions for generating traces of LOTOS descriptions are mentioned.
Dynamic compilation in the unix environment
Authors: Crowe M. K.
Published: November 2006

A system for dynamic compilation under the Unix operating system is described. The basis of the system is an incremental assembler that can be used statically or during program execution to insert or replace a module in an executable image. All cross‐module references are via offets into a run‐time symbol table. All generated code is independent of its location or the location of the symbol table. The symbol table and all modules reside in memory segments compatible with the memory allocator malloc(). The symbol table origin is maintained in a processor register. Library procedures allow the assembler (or C compiler) to be called to alter the currently executing program, or to place a stub function which acts as a trap, so that when the stub is invoked it caues a file to be dynamically compiled into the executing program to replace the stub with a bona fide procedure. This facilitates the construction of advanced interactive environments using native code. Some example applications, to Prolog and to incremental compilation, are considered.
Music—A language for typesetting music scores
Authors: Foxley Eric
Published: November 2006

This paper describes a language which has been devised to facilitate the inclusion of printed music in the output of a typesetting system. The music program acts as a preprocessor to troff, which is the typesetting program associated with the UNIX system. The design of the music input language has concentrated on the simplicity of the process of transcribing and typing in data from a standard music score, yet still allowing some of the complex requirements of serious music scores to be handled.
A portable implementation of a modular multiprocessing database programming language
Authors: Hughes J. G. , Connolly Michelle
Published: November 2006

This paper introduces the database programming language RAPP, which is an integration of the data type relation and relational algebraic operations with the modular multiprocessing language Pascal Plus. A portable version of the RAPP compiler has been implemented and is described.
The implementation and use of toolpack/1 on a graphics workstation
Authors: Broom M. A. , Hopkins T. R.
Published: November 2006

We report on the implementation and some of the extensions to the Toolpack/1 suite of Fortran software tools and the porting of a number of numerical software libraries to the ICL PERQ workstation.
Formal specification of an access control system
Authors: Stepney Susan , Lord Stephen P.
Published: November 2006

Computing facilities networked together but controlled by different administrations pose a problem of access control. Who decides who can use what?

We specify a formal model for an access control system which allows users and services from different administrations to communicate with each other, while still allowing the administrators to retain control of their own parts of the network. The model, written in the Z specification language, has been developed as the access control system for ADMIRAL, though it is not specific to ADMIRAL. It provides a framework for administrators to build access control systems to meet their differing requirements.

A system based on the model would allow users to log in to a distributed computing system and to make requests for services in any part of the system, without having to provide any more information about themselves. After this initial log in all subsequent access control decisions are handled automatically, and remain invisible to the user unless access is refused.ö

We also discuss the experience we have had animating this model in Prolog.
Fixing some space leaks with a garbage collector
Authors: Wadler Philip
Published: November 2006

Some functional programs may use more space than would be expected. A modification to the garbage collector is suggested which solves this problem in some cases. Related work is discussed.
An object‐oriented approach to application generation
Authors: Van Hoeve Frans , Engmann Rolf
Published: November 2006

The TUBA system consists of a set of integrated tools for the generation of business‐oriented applications. Tools and applications have a modular structure, represented by class objects. The article describes the architecture of the environments for file processing, screen handling and report writing.
A processing algorithm for master—detail records in a relational database
Authors: Bullers William I.
Published: November 2006

Large numbers of data processing applications require processing of master records and their associated detail records. These relationships between master and detail files may be classified as one‐to‐many, zero‐or‐one‐to‐many and many‐to‐many. All are important to information systems, but database management system implementations differ widely in their ability to represent and process such relationships. Processing of zero‐or‐one‐to‐many relationships, in particular, is difficult in most relational databases. An obscure relational algebra operator, left outer join, that provides such a capability is described and its importance to master‐detail processing is illustrated. An implementation of left outer join is presented for dBase III, a database management system providing some relational‐like capability.
Profiling under UNIX by patching
Authors: Bishop Matt
Published: November 2006

Profiling under UNIX is done by inserting counters into programs either before compiling, during compiling or during assembly. A fourth type of profiling involves monitoring the execution of a program, and gathering relevant statistics during the run. This paper looks at this method and an implementation of it, and discusses its advantages and disadvantages.
GCI—A tool for developing interactive cad user interfaces
Authors: Gudes Ehud , Bracha Gilad
Published: November 2006

GCI is a Unix‐based tool for developing interactive CAD programs. By separating command/ menu definitions from the progam, GCI makes it easier to change and extend the user interface. The language provided by GCI is used to define the syntax of commands, menus, messages, and help text. Generally, GCI supports a static hierarchical structure of commands and menus. However, through a program interface, an application program has the freedom to change environments, commands and menus. This flexibility of run‐time control of the user interface is essential for developing highly responsive interfaces in a CAD environment.

This paper presents the main concepts and definition language of GCI. It then discusses architectural and implementation issues, and finally presents a typical application's view of using the tool.
Automatic inference and fast interpretation of peephole optimization rules†
Authors: Davidson Jack W. , Fraser Christopher W.
Published: November 2006

Peephole optimizers that are driven by machine descriptions are generally more thorough but less efficient than their classical rule‐directed counterparts. This paper describes a system that addresses this shortcoming. It automatically infers rules by tracking the behaviour of a description‐directed optimizer on a testbed, and it adapts a classical optimizer to interpret these rules efficiently. Experiments show that an easily constructed testbed can generate rules similar to those in a large hand‐written rulebase. This software forms part of a compiler that simplifies retargeting by substituting peephole optimization for case analysis.
The text editor sam
Authors: Pike Rob
Published: November 2006

Sam is an interactive multi‐file text editor intended for bitmap displays. A textual command language supplements the mouse‐driven, cut‐and‐paste interface to make complex or repetitive editing tasks easy to specify. The language is characterized by the composition of regular expressions to describe the structure of the text being modified. The treatment of files as a database, with changes logged as atomic transactions, guides the implementation and makes a general ‘undo’ mechanism straightforward.

Sam is implemented as two processes connected by a low‐bandwidth stream, one process handling the display and the other the editing algorithms. Therefore it can run with the display process in a bitmap terminal and the editor on a local host, with both processes on a bitmap‐equipped host, or with the display process in the terminal and the editor in a remote host. By suppressing the display process, it can even run without a bitmap terminal.
A real‐time messaging system for token ring networks
Authors: Weaver Alfred C. , Colvin M. Alex
Published: November 2006

The Computer Networks Laboratory at the University of Virginia has developed a real‐time messaging service that runs on IBM PCs and PC/ATs when interconnected with a Proteon ProNET‐10 token ring local area network. The system is a prototype for a real‐time communications network to be used aboard ships. The system conforms to the IEEE 802.2 logical link control standard for type I (connectionless, or datagram) service, with an option for acknowledged datagrams.

The application environment required substantial network throughput and bounded message delay. Thus, the development philosophy was to emphasize performance initially and to offer only primitive user services. After providing and measuring the performance of a basic datagram service, the intent is to add additional user services one at a time and to retain only those which the user can ‘afford’ in terms of their impact on throughput, delay, and CPU utilization.

The current system is programmed in C. The user interface is a set of C procedure calls that initialize tables, reserve buffer space, send and receive messages, and report network status. The system is now operational, and initial performance measurements are complete. Using this system, an individual PC can transmit or receive approximately 200 short (about 100 bytes) messages per second, and the PC/AT operates at nearly 500 short messages per second.
An object‐oriented class library for C++ programs
Authors: Gorlen Keith E.
Published: November 2006

The Object‐Oriented Program Support (OOPS) class library is a portable collection of classes similar to those of Smalltalk‐80 that has been developed using the C++ programming language under the UNIX operating system. The OOPS library includes generally useful data types, such as String, Date and Time, and most of the Smalltalk‐80 collection classes such as OrderedCtn (indexed arrays), LinkedList (singly linked lists), Set (hash tables), and Dictionary (associative arrays). Arbitrarily complex data structures comprised of OOPS and user‐defined objects can be stored on disk files or moved between UNIX processes by means of an object I/O facility. The classes Process, Scheduler, Semaphore and SharedQueue provide multiprogramming with coroutines. This paper gives a brief introduction to object‐oriented programming and how it is supported by the C+ + programming language. An overview of the OOPS library is also presented, followed by a programming example. The implementation details of two of the class library's more interesting features, object I/O and processes, are described. The paper concludes with a discussion of the differences between the OOPS library and Smalltalk‐80 and some observations based on our programming experience with C++ and OOPS.
A file replication facility for berkeley unix
Authors: Purdin Titus D. M. , Schlichting Richard D. , Andrews Gregory R.
Published: November 2006

This paper describes two mechanisms – reproduction sets and metafiles – that provide low‐cost, semi‐automatic file replication and location transparency facilities for an interconnected collection of machines running Berkeley Unix. A reproduction set is a collection of files that the system attempts to keep identical; this is done on a ‘best effort’ basis, with the system relying on the user to handle unusual situations. A metafile is a special file that contains symbolic pathnames of other files, each of which may be on any machine in the network; opening a metafile results in opening an available constituent file. Examples are given to illustrate the use of these mechanisms. Their implementation and performance are also described.
A programmer‐friendly LL(1) parser generator
Authors: Grune Dick , Jacobs Ceriel J. H.
Published: November 2006

LL(1) grammars have the conceptual and practical advantage that they allow the compiler writer to view the grammar as a program; this allows a more natural positioning of semantic actions and a simple attribute mechanism. Resulting parsers can be constructed that achieve fully automatic error‐recovery, which allows the compiler writer to ignore totally the issue of syntax errors. Measurement shows that such parsers can be reasonably efficient.
An architectural approach to improved program maintainability
Authors: Einbu John M.
Published: November 2006

A programming standard is described, with the emphasis on the visual aspects of the final product rather than on how the programs are engineered.
A microprogrammed occam interpreter for the HLH orion
Authors: Cooper R. E. M. , Jones G.
Published: November 2006

A micro‐coded interpreter has been written for the occam programming language that runs on the fully microprogrammable HLH Orion mini‐computers. The resulting software gives performance which is comparable with native‐code operation on similar hardware, and is able to be extended easily to support new instructions as the language is developed further.
The design of a language processor generator
Authors: Koskimies Kai , Nurmi Otto , Paakki Jukka , Sippu Seppo
Published: November 2006

Language processor generators are systems that produce various language processors (including compilers) on the basis of a high‐level specification. The design of language processor generators is discussed on the basis of experiments with a traditional compiler writing system (HLP78) employing pore LALR parsing and general attribute grammars. It is argued that these methods are too primitive from the practical point of view. The design of a new language processor generator, HLP84, is based on this view. This system is an attempt to provide high‐level tools for a restricted class of applications (one‐pass analysis). The syntactic facilities include regular expressions on the right‐hand sides of productions, a disambiguating mechanism that is integrated with regular expressions, and a mechanism for using semantic information to aid parsing. The semantic facilities include automatic support for semantic error handling and for symbol tables. Early experiences with the new system show that in spite of the general overhead caused by the higher automation level, the system allows the generation of reasonably efficient processors.
Converting help systems to hypertext
Authors: Brown P. J. , Russell M. T.
Published: November 2006

Hypertext systems have great potential for displaying help information. There is, however, a problem in moving over smoothly to a hypertext system without having a throw away existing help‐scripts. This note describes an exercise in achieving this smooth transfer.
PICASSO: A graphical query language
Authors: Kim Hyoung‐Joo , Korth Henry F. , Silberschatz Avi
Published: November 2006

PICASSO (PICture Aided Sophisticated Sketch Of database queries) is a graphics‐based database query language designed for use with a universal relation database system. The primary objective of PICASSO is ease of use. Graphics are used to provide a simple method of expressing queries and to provide visual feedback to the user about the system's interpretation of the query. Inexperienced users can use the graphical feedback to aid them in formulating queries whereas experienced users can ignore the feedback. Inexperienced users can pose queries without knowing the details of underlying database schema and without learning the formal syntax of SQL‐like query language. This paper presents the syntax of PICASSO queries and compares PICASSO queries with similar queries in standard relational query languages. Comparisons are also made with System/U, a non‐graphical universal relation system on which PICASSO is based. The hypergraph semantics of the universal relation are used as the foundation for PICASSO and their integration with a graphical workstation enhances the usability of database systems.
Low‐level programming in modula‐2: An experience with local area network access
Authors: Tagg A. G.
Published: November 2006

Access to a computer network, which is currently a topic of some importance to the high‐level language programmer, can be provided in a number of ways. This paper describes one such example, where users of the language Modula‐2 were given access to a local area network. The author discusses the type of problem that needs to be overcome, when a language such as Modula‐2, which was designed as part of an integrated systems architecture, is used for low‐level programming in a different architectural environment.
CSP‐i: An implementation of communicating sequential processes
Authors: Wrench K. L.
Published: November 2006

Hoare's proposal for a notation for communicating sequential processes has led to the development of a number of concurrent languages based on the concept of message passing. CSP‐i is a new language which reflects the design objectives of the original CSP notation more faithfully than most of these other languages. This paper describes the development of the language, as well as an implementation for a single processor, with simulated time‐slicing providing pseudo‐concurrency.
A LISP implementation of the model for ‘communicating sequential processes’
Authors: Fidge C. J.
Published: November 2006

To explain his abstract model of Communicating Sequential Processes, Hoare includes an implementation of the concepts being expounded as a set of LISP functions. However, the final sections are only described sketchily. This paper completes the missing details, and briefly discusses experience with the system. The usefulness of the implementation is enhanced by the addition of features to ensure that incomplete program fragments can be executed, and that no restrictions are placed on the way operators may be combined.
RTS: A system to simulate the real time cost behaviour of parallel computations
Authors: Qin Bin , Sholl Howard A. , Ammar Reda A.
Published: November 2006

In this paper, we present a software tool, RTS (real time simulator), that analyses the time cost behaviour of parallel computations through simulation. It is assumed in RTS that the computer system which supports the executions of parallel computations has a limited number of processors all processors have the same speed and they communicate with each other through a shared memory. In RTS, the time cost of a parallel computation is defined as a function of the input, the algorithm, the data structure, the processor speed, the number of processors, the processor power allocation, the communication and the execution environment. How RTS models the time cost is first discussed in the paper. In the model, a locking technique is used to manipulate the access to the shared memory, processing power is equally allocated among all the operations that are currently being performed in parallel in the computer system, and the number of operations in the execution environment of a parallel computation changes from time to time. How RTS works and how the simulation is used to do time cost analysis are also discussed.
NSEDIT: A syntax‐directed editor and testing tool based on Nassi—Shneiderman charts
Authors: Halewood K. , Woodward M. R.
Published: November 2006

This paper describes a programming environment for Pascal, called NSEDIT, which runs under VAX/VMS

VAX/VMS is a trademark of the Digital Equipment Corporation.

. NSEDIT is based upon the notion of Nassi‐Shneiderman charts (abbreviated to N‐S charts in this paper) and is designed for ease of use by novice programmers in a teaching situation. A key component of the system is the editor, which enables structural features of Pascal to be manipulated in terms of their N‐S chart box representations. Simultaneous editing of more than one program or module is permitted. Another key feature of the system is a semiautomatic interface to the VAX/VMS Pascal compiler, with subsequent display of execution counts as part of the N‐S charts. In this way users can obtain immediate feedback on the coverage of program elements by test runs, while still inside an editing session.
GNU Emacs as a dynamically extensible programming environment
Authors: Halme Heikki , Heinänen Juha
Published: November 2006

GNU Emacs is usually used only as an extensible editor. However, the ability to integrate inferior processes into GNU Emacs makes it an attractive programming environment. Like Interlisp and Smalltalk‐80, GNU Emacs can be extended dynamically by its user. Unlike these programming environments, it can be used easily as a programming environment for an arbitrary programming language, and not just for its extension language. This paper discusses the methods of extending GNU Emacs and how we have applied them in creating a programming environment for a high‐level specification language called AGENT.
Support for graphs of processes in a command interpreter
Authors: McDonald Chris , Dix Trevor I.
Published: November 2006

Since the inception of pipes in the UNIX operating system, the standard UNIX command interpreters, or shells, have supported processes connected only in linear arrangements. This paper explains why linear pipe structures are too restrictive and how the standard UNIX shells have dictated the interface strategy of new commands. A new command interpreter is presented that supports general directed process graphs. Processes and files are considered simply as nodes and pipes as arcs in a process graph.
DAG—a program that draws directed graphs
Authors: Gansner E. R. , North S. C. , Vo K. P.
Published: November 2006

DAG is a program that draws directed graphs by reading a list of noeds and edges, computing a layout and then writing a PIC or PostScript description of a picture. Optional drawing instructions specify the way nodes are drawn, attach labels and control spacing. DAG works best on directed acyclic graphs, which are often used to represent hierarchical relationships. For example, here is a drawing of a graph from J. W. Forrester's book, World Dynamics (Wright‐Allen, Cambridge, MA, 1971), which took 1.63 CPU seconds to draw using a VAX‐8650.
Load balancing in a session‐based distributed file‐store architecture
Authors: Santana M. J. , Zaluska E. J.
Published: November 2006

This paper discusses novel dynamic‐load‐balancing and user‐allocation mechanisms for an advanced session‐based file‐store architecture to improve overall system performance. Such an architecture comprises several LAN‐based file servers working together, implementing a global and distributed file‐store for a loosely coupled distributed computing system. The load‐balancing and user‐allocation algorithms are responsibilities of a high‐level co‐ordinator server, which may be either centralized or distributed. The mechanism discussed considers three basic parameters in order to optimize the global performance: the individual file‐server performance, the cost of connection between user workstations and file servers and the cost of accessing different file servers. The paper presents the algorithms developed, together with a brief description of the file‐store architecture and associated environment. Results obtained from a simulation study and practical aspects are also presented and discussed.
Attribute grammars in constraint‐based graphics systems
Authors: Barford Lee Alton , Vander Zanden Bradley T.
Published: November 2006

A constraint‐based graphics system provides a flexible, intuitive framework for describing relationships among graphical objects in applications such as document preparation, fount design and solid modelling. This paper describes two constraint‐based graphics systems, micro‐COSM and the IDEAL Synthesizer, and their implementation in terms of attribute grammars. Our experiences with attribute grammars suggest that they provide a powerful framework for representing constraints and extracting important semantic information such as the equations to be solved by the constraint solver. We discuss the advantages of using attribute grammars in constraint‐based graphics and from our experiences make several observations about the way attribute grammars should be used.
A session editor with incremental execution functions
Authors: Holsti Niklas
Published: November 2006

Editing the script of an interactive session on‐line can replace or enhance common interaction techniques and help to separate the user interface from the computation. We describe a text editor that executes scripts incrementally, co‐operating with application programs to undo and redo script parts. The user edits the input part of a transcript, and the editor updates the output part. The transcript becomes a clear and reusable document. The applications choose the backtracking steps, and can thus evolve gradually. Extensions to non‐linear dialogues are in progress.
Implementation of a declarative state‐transition system
Authors: Foster Ian
Published: November 2006

A declarative programming style is claimed to have significant advantages from a software engineering point of view. However, these benefits cannot generally be realized when writing programs that are concerned with changing state, such as environments and programming tools. Declarative state‐transition (DST) systems have been proposed as a solution to this problem. In DST systems, computation and update are separated. Programs are interpreted as defining functions or relations over states, and update follows successful computation of new states. Support for persistent state and atomic, serializable transactions facilitates the implementation of programming environments and tools. This paper describes an implementation scheme for DST systems. The scheme is illustrated by a presentation of the implementation of PPS, a DST system for parallel logic programming.
Object management in a persistent smalltalk system
Authors: Straw Andrew , Mellender Fred , Riegel Steve
Published: November 2006

The main goal of the Alltalk project is to provide transparent database support to the Smalltalk programmer. As a first step towards this goal, the current version of Alltalk extends Smalltalk‐80 by providing persistence to Smalltalk objects without adding a database sublanguage, new language syntax, classes or methods. This paper describes the implementation of object management in Alltalk, including database layout, database access methods, in‐memory object management and high‐level interface from the interpreter. It also discusses how the object manager is integrated in a unique way with the operations of the Alltalk garbage collector and interpreter.
Mapping massive SIMD parallelism onto vector architectures for simulation
Authors: Rosenberg Jonathan B. , Becker Jonathan D.
Published: November 2006

A software behavioural simulator for a new massively parallel single‐instruction/multiple data (SIMD) architecture has been developed that can accurately simulate the entire 16, 384 bit‐serial processor array. The key to this high performance modelling is the exploitation of an inherent mapping that exists between massively parallel SIMD architectures and the vector architectures used in many high performance scientific super‐computers. The new SIMD architecture, called BLITZEN, is based on the Massively Parallel Processor (MPP) built for NASA by Goodyear in the late 1970s. By simulating the full‐scale machine with very high performance, the simulator allows development of algorithms and high‐level software to proceed before realization of the hardware. This paper describes the SIMD ‐ vector architecture mapping, the highly vectorized simulator in which it is used, and how the result was a simulator that achieved a level of performance three orders of magnitude faster than the conventional uniprocessor approach.
A simple technique for automatic recompilation in modular programming languages
Authors: Olsson Ronald A. , Whitehead Gregory R.
Published: November 2006

This paper presents simple techniques that can be used to automate recompilation and avoid unnecessary recompilation in modular programming languages. The basic technique generates a Makefile that reflects the dependencies among modules. This technique is demonstrated for programs written in SR, although it can easily be adapted to other modular languages. The recompilation problem for SR programs is complicated by the flexible way components can be placed in source files and by how an SR module's specification and implementation can be combined. A small modification to the basic technique reduces the amount of unnecessary compilation. This ‘semi‐smart’ approach is worth the small extra effort. The techniques described in this paper should be considered as an inexpensive, yet reasonably effective, alternative to smart recompilation. These techniques are especially applicable when the language's compiler cannot easily be modified.
A parallel Ada system on an experimental multiprocessor
Authors: Lundberg Lars
Published: November 2006

This paper describes the development of a parallel Ada system on an experimental MIMD multiprocessor. The system enables a single unmodified Ada program, with a number of tasks, to execute in parallel on different processors. Allocation and migration strategies are controlled by mechanisms in the run‐time system, and are thus transparent to the Ada programmer. The parallel Ada system is based on a validated portable front‐end compiler. Implementation issues related to the multiprocessor environment are pointed out, and solutions to these issues are suggested. The experimental multiprocessor environment, consisting of both hardware and software, is described. Applicable resource allocation strategies in, and feasible experiments with, the Ada system are discussed. The complete experimental system provides unique possibilities to experiment with, and monitor the effects of, design decisions at different levels in a multiprocessor environment.
A language‐independent prettyprinter
Authors: Jokinen Matti O.
Published: November 2006

A general‐purpose prettyprinting program is presented. The input to the prettyprinter is a linear stream composed of visible symbols and elementary formatting instructions. The user can specify a set of alternative formats and the precedence of the alternatives. The prettyprinter attempts to select automatically the ‘best’ layout that fits on the bounded horizontal space available on the output medium. The prettyprinter is implemented as a library module, which makes it more flexible than many traditional prettyprinters that are written as main programs. For instance, formatted expressions can be mixed with plain text or displayed interactively on the user's terminal, and the application program can use several prettyprinters simultaneously.
A parallel version of cook and Kim's algorithm for presorted lists
Authors: McGlinn Robert J.
Published: November 2006

The Cook and Kim algorithm is a well known method for sorting presorted lists. This paper presents observations based on an implementation of the algorithm on a single processor. An extension of the algorithm to a tightly coupled multiprocessor will also be presented. The performance of the parallel version of the algorithm on presorted lists will be compared to that of a heavily used parallel sort algorithm for tightly coupled multiprocessors, Parallel Quicksort.
Near‐perfect hashing of large word sets
Authors: Brain Marshall D. , Tharp Alan L.
Published: November 2006

This article presents a procedure for constructing a near‐perfect hashing function. The procedure, which is a modification of Cichelli's algorithm, builds the near‐perfect hashing function sufficiently fast to allow larger word sets to be used than were previously possible. The improved procedure is the result of examining the original algorithm for the causes of its sluggish performance and then modifying them. In doing so an attempt was made to preserve the basic simplicity of th original algorithm. The improved performance comes at the expense of more storage. The six modifications used to improve performance are explained in detail and experimental results are given for word sets of varying sizes.
Fast allocation and deallocation of memory based on object lifetimes
Authors: Hanson David R.
Published: November 2006

Dynamic storage‐management algorithms are based either on object sizes or object lifetimes. Stack allocation, which is based on object lifetimes, is the most efficient algorithm, but severely restricts object lifetimes and creation times. Other algorithms based on object sizes, such as first fit and related algorithms, permit arbitrary lifetimes but cost more. More efficient variations capitalize on application‐specific characteristics. Quick fit, for example, is more efficient when there are only a few object sizes. This paper describes a simple algorithm that is very efficient when there are few object lifetimes. In terms of instructions executed per byte allocated, the algorithm is almost half the cost of quick fit and less than twice the cost of stack allocation. Space for all objects with the same lifetime is allocated from a list of large arenas, and the entire list is deallocated at once. An implementation in ANSI C is included.
Ceres‐net: A low‐cost computer network
Authors: Wirth N.
Published: November 2006

This paper describes a local‐area network, its hardware and software structure, and its protocol. The principal objective was to minimize the complexity of hardware and software, yet to offer an adequate functionality and performance for a system of up to 30 workstations with local file stores. The primary benefit of the achieved simple structure and low‐overhead protocol is the system's reliability.
Tools to aid in discovering parallelism and localizing arithmetic in Fortran programs
Authors: Cowell Wayne R. , Thompson Christopher P.
Published: November 2006

We describe a collection of software tools that analyse and transform Fortran programs. The analysis tools detect parallelism in blocks of code and are primarily intended to aid in adapting existing programs to execute on multiprocessors. The transformation tools are aimed at eliminating data dependencies, thereby introducing parallelism, and at localizing arithmetic in registers, of primary interest in adapting programs to execute on machines that can be memory bound (common for machines with vector architecture). The tools are unified conceptually by their use of a set of conditions for data independence; these conditions have been implemented so as to combine tool analysis with user/tool interaction. We include timing results from applying the tools to programs intended for execution on two machines with different architectures — a Sequent Balance and a CRAY‐2. The tools are written in Fortran in the tool‐writing environment provided by Toolpack and are easily incorporated into a Toolpack installation.
Code generation using an orthogonal model
Authors: Cordy James R. , Holt Richard C.
Published: November 2006

This paper describes a new systematic approach to code generation. The approach is based on an orthogonal model, in which implementation of language‐level operators (‘operators’) and addressing operators (‘operands’) is achieved by two independent subtasks. Each of these phases is specified using a set of decision trees that encode the set of possible implementation templates for each language feature and the set of constraints under which each can be applied. Code selection in each phase is achieved by interpreting these trees using a single comprehensive selection algorithm.

The method easily extends to machine independence across a large class of target computers by abstracting the implementation templates into machine‐independent implementation strategies. The selection algorithm is then modified to select between implementation strategies based on a machine capability ‘menu’ that describes each target machine in terms of the subset of implementation strategies for which it has corresponding instruction sequences.

The method has been used to implement a prototype machine‐independent code generator for the Concurrent Euclid programming language whose generated code density is consistently within four per cent of production machine‐dependent code generators across its entire target class of five modern computers.
Signalling regions: Multiprocessing in a shared memory reconsidered
Authors: Reynolds Charles W.
Published: November 2006

The 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.
Restructuring for style
Authors: Zimmer J. A.
Published: November 2006

An older FORTRAN program is restructured to a style that is related to data abstraction and object‐oriented programming. The restructuring process, which can be applied to many older procedural languages, is driven by goals that are related to clarity of function. Possible benefits include maintainability and a better understanding of the original program.
Run‐time detection of undefined variables considered essential
Authors: Kempton Willett , Wichmann Brian A.
Published: November 2006

Access 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

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