bluuebunny/crossref_metadata_2025 huggingface dataset:
A distributed load‐balancing policy for a multicomputer
Authors: Barak Amnon , Shiloh Amnon
Published: November 2006

This paper deals with the organization of a distributed load‐balancing policy for a multicomputer system which consists of a cluster of independent computers that are interconnected by a local area communication network. We introduce three algorithms necessary to maintain load balancing in this system: the local load algorithm, used by each processor to monitor its own load; the exchange algorithm, for exchanging load information between the processors, and the process migration algorithm that uses this information to dynamically migrate processes from overloaded to underloaded processors.

The policy that we present is distributed, i.e. each processor uses the same policy. It is both dynamic, responding to load changes without using an a priori knowledge of the resources that each process requires; and stable, unnecessary overloading of a processor is minimized. We give the essential details of the implementation of the policy and initial results on its performance.

Our results confirm the feasibility of building distributed systems that are based on network communication for uniform access, resource sharing and improved reliability, as well as the use of workstations without a secondary storage device.
A reliable stable storage system for unix
Authors: Anyanwu J. A.
Published: November 2006

This paper describes the implementation of a stable storage system which converts several fallible disk stores into reliable devices for storing data. It provides reliable reading and writing of data in a distributed UNIX

UNIX is a Trademark of AT&T Bell Laboratories

environment in spite of transient I/O faults, decay of physical storage devices and processor crashes. The implementation makes available to UNIX users a convenient way of using the facilities of a stable storage system by providing the abstraction of stable files and by maintaining the standard UNIX system call interface. It systematically handles abnormal situations by separating normal and exceptional processing in both the system description and implementation. This is achieved through the use of a fault tolerance design notation for the description of the system and the implementation of that notation using an exception handling package.
Compilers — some good, some bad!
Authors: Vella A. D.
Published: November 2006

The paper examines the code produced by three compilers on a DEC‐20 together with the effects of some compiler switches on this code. Some very surprising results are found.
Integration of diskless workstations in unix united
Authors: Lobelle Marc C.
Published: November 2006

This document evaluates the feasibility of diskless UNIX systems connected to a disk‐providing machine via a local area network. The diskless UNIX systems are to be used as workstations in a UNIX United

UNIX is a trademark of A. T. & T. Bell Laboratories.

environment.

Several solutions are presented and estimated to enable booting, file system access and swapping. Implementation techniques, compatible with the UNIX United philosophy, are proposed. Specific topics covered are file servers, swap servers, disk servers, indirect drivers, system call service access from kernel coroutines of UNIX processes, and communication subsystems.

It is shown that the modifications to the UNIX system can be limited to one new device driver in the diskless workstation and one in the system providing the secondary storage facility.
DDA — a data definition facility for unix using awk
Authors: Bailes Paul A.
Published: November 2006

We discuss how the Awk language is an effective tool for interrogating sequential data files whose records consist of characters grouped into fields. This facility is used to implement a system to manage an ‘address book’ database. We then generalize the design, describing a system which allows one to interactively specify a DBMS according to one's own requirements within our general framework. We choose a wine‐tasting DBMS as an example specification for further consideration and evaluation.
Producing good code for the case statement
Authors: Bernstein Robert L.
Published: November 2006

After summarizing different ways of generating selection code for the case statement, the execution speed of each type of selection code is described using the RISC machine model. A method for combining the selection code schemes is proposed. The method, part of the PL.8 compiler, is flexible enough to handle case‐selector data‐types that have a large range of values, such as the character‐string or floating‐point datatypes, and can be fine‐tuned when the probabilities of the case selector taking on particular values are known.
A file comparison program
Authors: Miller Webb , Myers Eugene W.
Published: November 2006

This paper presents a simple method for computing a shortest sequence of insertion and deletion commands that converts one given file to another. The method is particularly efficient when the difference between the two files is small compared to the files' lengths. In experiments performed on typical files, the program often ran four times faster than the UNIX diff command.
A software tool for the construction and maintenance of structured analysis notation
Authors: Woodman M. , Ince D. C.
Published: November 2006

This paper describes a portable software tool used for the processing and maintenance of data flow diagrams which form the basis of structured analysis techniques. The tool itself is based on the idea that data flow diagrams can be modelled by means of semantic nets and can be manipulated by a semantic net processor. A major feature of the tool is the facilities it provides for the maintenance programmer.
The pulse distributed file system
Authors: Tomlinson G. M. , Keeffe D. , Wand I. C. , Wellings A. J.
Published: November 2006

A network of powerful personal computers, linked by a high‐speed local area network, is being seen increasingly as an alternative to a traditional centralized time‐sharing operating system. The PULSE project is investigating how such a system may be constructed to give the benefits of a self‐sufficient personal computer to each user without losing the facilities for communication and sharing of data inherent in centralized systems. In particular, a distributed file system has been built which provides a single global UNIX

UNIX is a trademark of Bell Laboratories.

‐like hierarchy, with a consistent appearance when accessed from any machine. Replicated copies of files are maintained to improve reliability, increase performance, and enable each machine to run stand‐alone, albeit with reduced facilities.
Treatment of tab characters by a compiler
Authors: Waite W. M.
Published: November 2006

How expensive is it for a compiler to process horizontal tab characters introduced arbitrarily into program text? The measurements discussed in this note show that if tabs are uniformly expanded by the source text input module of the compiler, the process of reading and tokenizing the source program is slowed by about 20 per cent. This overhead can be completely eliminated by using an ‘extra space count’ in the lexical analyser instead of a uniform expansion.
A critique of unix
Authors: Blair Gordon S. , Malone Jon R. , Mariani John A.
Published: November 2006

The UNIX operating system enjoys an ever increasing popularity throughout the computing community; there will be 1.4 million UNIX licences distributed by 1985, rising at a rate of about 400,000 per annum.

With universal acceptance of a system comes a dangerously high degree of inertia. Consider the analogous area of programming languages, where there has been great resistance to change, despite major advancements.

This paper presents a critique of UNIX, based on three areas which we consider to be of vital importance to future operating systems. These areas are operating system structures and design, programming support environments and distributed computing.

The criticisms presented are in no way intended to discredit UNIX. UNIX compares favourably with most of the present generation of operating systems. The intention is to highlight deficiencies in the state of the art in operating system design.
Specifications and an implementation of the type‐ambiguity problem in pascal
Authors: Partridge Derek
Published: November 2006

Certain ambiguities in the definition of Pascal imperil the portability of Pascal programs. Specifications and an implementation of alternative interpretations are presented. Context‐free grammars augmented with guarded commands are demonstrated as a notation for specifying the static context‐sensitive constraints of programming languages.

Most of the advantages of context‐free grammars are preserved and yet the potential range of the syntactic definition component has been extended to encompass all static constraints. Context‐sensitive syntax typically tends to either clutter the semantic definition component or (as with type equivalence in Pascal) result in undesirable implementor‐dependent decisions.

An implementation of a CFG‐based parser that automatically checks for the defined context‐sensitive constraints is also described. In addition stepwise abstraction is introduced as a practical technique for communicating formal programming language definitions.
The function of T and NIL in LISP
Authors: Lichtman Zavdi L.
Published: November 2006

The conventional pure LISP interpreter written in pure LISP is commonly believed to be executable. As it turns out, this interpreter does not recognize the atoms t and nil — commonly regarded as part of pure LISP. The problem is explained, and the interpreter is fixed.
Using coroutines in pascal
Authors: Horton I. A. , Turner S. J.
Published: November 2006

Coroutines are routines which communicate with each other in a more general way than that provided by the normal subroutine mechanism. Although they have many potential applications, their use has been restricted by their lack of availability in common high‐level languages. This paper discusses some of the issues involved in implementing coroutines, and proposes an implementation written in Pascal which may be incorporated into a Pascal program to give coroutine facilities. Use of the system is illustrated by two solutions to the N‐Queens problem by different coroutine strategies. The basic system is then extended to allow more advanced use of coroutines.
Communicating parallel processes
Authors: Kerridge Jon , Simpson Dan
Published: November 2006

By considering the problem of an event timer it is shown that the commonly available synchronizing facilities (monitors, CSP, distributed processes) are not able to always satisfactorily model the requirements of several processes which must run in parallel and which have to communicate with each other. The problem is discussed in general terms which show that what is required are new concepts for communicating processes. The synchronization facilities proposed are augmented to incorporate the concept of process scheduling directly from a process. This ensures that proper scheduling of process components can take place. The new mechanism is then applied to a number of the standard problems. It is also shown that the use of nondeterminacy in current facilities is probably not required and is, in fact, for many applications, a positive disadvantage.
Implementing ALGOL 68 predicates
Authors: Patel R. R. , Hunter R. B.
Published: November 2006

Predicates are used in the Revised ALGOL 68 Report to indicate blind alleys and to reduce the number of rules in the Report. They may also be used by the compiler writer to implement some of the non‐context‐free aspects of the language. This paper shows how the predicates can be transformed in a relatively straightforward way into ALGOL 68 procedures to form part of an analyser for the revised language.
Separate compilation in a modula‐2 compiler
Authors: Foster David G.
Published: November 2006

A new approach to the compilation of Modula‐2

Modula‐2 was designed at the Institut für Informatik, ETH, Zurich.

is described. The compiler uses a simple database which provides the basis for a portable programming support environment. The environment consists of a number of tools which operate on the database and provide the programmer with facilities to create, and easily maintain, a multi‐module system.
A crash resistant UNIX file system
Authors: Anyanwu J. A. , Marshall L. F.
Published: November 2006

The UNIX

UNIX is a trademark of AT&T Bell Laboratories.

operating system has been extended to support a crash resistant file system. This paper describes the modifications which were made to the UNIX kernel to support such a file system and the associated recovery facilities for maintaining the internal consistency of files despite the failure of the host processor, transient hardware failures and decay of the storage medium.
Routines: An argument against the conventional approach to functions and procedures
Authors: Middleton A. G.
Published: November 2006

This paper discusses the concept of a ‘routine’, which embraces both the concepts of ‘function’ and ‘procedure’. Several related functions and procedures can be mechanically derived from the same routine. These functions and procedures are ‘variants’ of the routine.

Variants of a routine are identified by specifying some subset of the capabilities of the routine. A routine can be regarded as a means of specifying several related functions and procedures ‘at one go’. Alternatively, a routine can be thought of as a collection of functions consorting together for the purposes of optimization.
SOFTLIB — a documentation management system
Authors: Sommerville I. , Welland R. , Bennett I. , Thomson R.
Published: November 2006

This paper describes a software sysem (SOFTLIB) that has been developed to assist in the management of software documentation generated during systems development projects. It provides facilities to manage large numbers of documents, to file documents when they are complete and to issue them to system developers and maintainers. It also includes an information retrieval facility that allows programming staff to find documents, to examine their contents before issue and to assess the state of the software project documentation. SOFTLIB is explicitly intended to help manage the documentation generated during software development — it is not designed for use by end‐users of that software or for managing end‐user documentation.

The novel characteristic of this system is the approach that is taken to the consistency and completeness of documentation. The documentation associated with a software system is organized in such a way that it may be detected if document sets are complete (that is, if all documentation which should be provided for a software component is available) and if document sets are likely to be inconsistent. This means that if a document has been changed without a comparable change being made to other associated documents, this is detectable by the librarian system.

In addition, a subsidiary aim of our work was to investigate the utility of menu systems to complex software tools by building a user interface to SOFTLIB. We conclude that menu systems are far from ideal in such situations because of the range of possible options which must be handled by the system.
A new list compaction method
Authors: Li Kai , Hudak Paul
Published: November 2006

List compaction, or so‐called ‘cdr‐coding’, can greatly reduce the storage needs of list processing languages. However, existing methods do not perform well when several lists are being constructed simultaneously from the same heap, since the non‐contiguous nature of the cells being allocated eliminates the opportunity for compaction. This situation arises not only in true parallel systems sharing a common memory, and sequential systems supporting multiple processes, but also quite often in purely sequential systems, where it is not uncommon to build several different lists simultaneously within a single loop. In this paper, a new list compaction method is presented that performs well during both sequential and ‘parallel’ list generation. The method is essentially a generalization of cdr‐coding, in which lists are represented explicitly as linked vectors rather than implicitly as compacted memory. In addition, an encoding scheme is used that is as simple or simpler than all known encodings, and destructive operations are supported with no greater overhead than existing schemes. Performance figures in a simulated environment suggest that the strategy consistently performs better than conventional cdr‐coding, with essentially the same complexity.
Template design for file processing applications
Authors: Ramanathan Jay , Shubra Charley
Published: November 2006

Even though the data processing domain is relatively well‐defined, application‐specific details vary too widely to conceive of totally automating programming and specification support. Conventional tools lack the semantic knowledge to constructively support software development. On the other hand, it is possible to design a prompting and guiding system that can elicit the application details. The limits of automated programming support possible for file and data processing applications were identified by means of a case study of COBOL and PL/I programs. The data gathered from this study facilitated the definition of seventeen widely applicable templates. The resulting template set has immediate value as a manual specification and documentation tool. The templates encourage programmers to make well‐considered design decisions and enforce standardized documentation.
A distributed programs monitor for berkeley UNIX
Authors: Miller Barton P. , Macrander Cathryn , Sechrest Stuart
Published: November 2006

Writing and debugging distributed programs can be difficult. When a program is working, it can be difficult to achieve reasonable execution performance. A major cause of these difficulties is a lack of tools for the programmer. We use a model of distributed computation and measurement to implement a program monitoring system for programs running on the Berkeley UNIX 4.2BSD operating system. The model of distributed computation describes the activities of the processes within a distributed program in terms of computation (internal events) and communication (external events). The measurement model focuses on external events and separates the detection of external events, event record selection and data analysis. The implementation of the measurement tools involved changes to the Berkeley UNIX kernel, and the addition of daemon processes to allow the monitoring activity to take place across machine boundaries. A user interface has also been implemented.
Context: An on‐line documentation system
Authors: Ragan Richard R.
Published: November 2006

This paper presents CONTEXT, an on‐line documentation system that is simple in concept and implementation. In spite of the simplicity, CONTEXT still provides substantial power and ease‐of‐use in accessing material in structured on‐line manuals. This paper provides an overview of the system from both the writer's and the user's perspective.
An almost path‐free very high‐level interactive data manipulation language for a microcomputer‐based database system
Authors: Schach Stephen R. , Wood Peter T.
Published: November 2006

VIADUCT is a very high‐level non‐procedural language designed to simplify usage of MDBS, a microcomputer database management system. Users need not have any knowledge of the structure of the database, because no path through the database is specified in a VIADUCT command. Instead, VIADUCT automatically determines which of a number of paths should be traversed in order to process the command. As this choice of path can critically affect the processing time required, VIADUCT chooses that path which is most likely to minimize the number of record occurrences retrieved from the database. But when a command can have more than one valid semantic interpretation, VIADUCT computes and then displays the alternative paths from which the user is required to make a choice.

Following a brief description of relevant aspects of MDBS, an overview of VIADUCT is given. The body of the paper describes the algorithms that are used to find paths through the database, as well as the path‐traversal algorithms. An evaluation of VIADUCT is presented and some restrictions noted.
A communication system supporting large datagrams on a local area network
Authors: Linton A. , Panzieri F.
Published: November 2006

This paper describes an implementation of a software interface designed for use from within UNIX

UNIX is a trademark of A T & T Bell Laboratories.

application programs for network communications. This interface provides the abstraction of possibly very large datagrams, supports ‘scatter‐gather’ facilities, and maintains standard network addresses consisting of (host number; port number) pairs. This interface has been provided on different data communication facilities, allowing uniform program access to those facilities. The particular implementation developed for a local area network is described, and performance results obtained are examined and compared with those obtained from a conventional datagram interface to that network. The results obtained confirm that the abstraction of very large datagrams enables the construction of an efficient mechanism for process‐to‐process communications over the network that is not only more convenient, but also has significant performance advantages over the use of conventional (small) datagrams.
Process administration in a high level language
Authors: Pedersen T.
Published: November 2006

The traditional approach to the implementation of process administration in multiprogrammed systems is to make it part of the run‐time system or ‘kernel’. This implies first, that the implementation is written in assembler language, and secondly that the process administration will be very inflexible. This article outlines a high level language PoMP, a Pascal extension. Following the trend set by Concurrent Pascal and Modula towards integrating ever increasing parts of the ‘kernel’ in the individual application program, PoMP provides language constructs for implementing process administration. It is shown that the multiprogramming language constructs of a number of languages may be ‘imitated’ in PoMP.
The construction of information management system prototypes in Ada
Authors: Burns A. , Kirkham J. A.
Published: November 2006

The use of a data‐flow diagram and data dictionary for the requirements specification of an information management system is described together with the benefits to be gained from using prototypes. Construction of such prototypes in Ada is discussed in detail with a simple example being given. The use of a flexible user interface, generic data‐flows, exception handlers for error conditions and a top‐down design method that makes use of separate compilation indicates that Ada is an appropriate language for the development of such systems. Consideration is also given to the use of Ada in the construction of actual as well as prototype information systems.
A persistent graphics facility for the ICL PERQ
Authors: Morrison R. , Brown A. L. , Bailey P. J. , Davie A. J. T. , Dearle A.
Published: November 2006

The facilities of the PS‐algol programming language are described in this paper to show how they may be used to provide an integrated programming support environment. The persistent store mechanism and the secure transaction facilities provide the basic environment in which an integrated system may be implemented. In particular the paper makes use of the data type picture of PS‐algol to show how such an environment may be built for a graphics system ideal for use with a medium range computer workstation. An implementation of a picture editor on the ICL PERQ workstation is described to show the utility of the system.
AWK as glue for programs
Authors: Van Wyk Christopher J.
Published: November 2006

Although AWK is usually presented as a language for simple data retrieval and formatting, it is also well suited to writing program generators. This use gives AWK much more power as a means of communicating among programs than its usual role as reformatter suggests. This paper discusses features of AWK that are especially useful for program generation. As an extended example, it presents a complete AWK program for typesetting charts in TROFF documents.
Yet another storage technique for lr parsing tables
Authors: Al‐Hussaini A. M. M. , Stone R. G.
Published: November 2006

A submatrix storage scheme for sparse matrices is presented which has been found useful for storing LR parsing tables. It is not the most compact representation but it is easy to use and of order (1) in speed of access. The method is compared with the two most popular methods of storing LR parsing tables which use ‘linear lists’ and ‘row displacement’. Results of using the submatrix method to store the parsing tables for the Pascal language are included.
Processing variable length abbreviations: Some observations
Authors: Newman I. A.
Published: November 2006

A recently published technique for processing variable length abbreviations is examined, some improvements are suggested and some experiences with the technique are reported.
A Distributed Real‐Time Operating System
Authors: Tuÿnman F. , Hertzberger L. O.
Published: November 2006

A distributed real‐time operating system, Fados, has been developed for an embedded multiprocessor system. The operating system is based on a host‐target approach and provides for communication between arbitrary processes on host and target machines. The facilities offered are, apart from process communication, access to the file system on the host by programs on the target machine and monitoring and debugging of programs on the target machine from the host. The process communication has been designed in such a way that the possibilities are the same as those offered by the Ada programming language. The operating system is implemented on an MC 68000 based multiprocessor system in combination with a Unix

Unix is a trademark of A. T. & T. Bell laboratories.

host.
Experimenting with data structures
Authors: Taylor David J. , Black James P.
Published: November 2006

Research in robust data structures can be done both by theoretical analysis of properties of abstract implementations and by empirical study of real implementations. Empirical study requires a support environment for the actual implementation. In particular, if the response of the implementation to errors is being studied, a mechanism must exist for artificially injecting appropriate kinds of errors. This paper discusses techniques used in empirical investigations of data structure robustness, with particular reference to tools developed for this purpose at the University of Waterloo.
A modula‐2 kernel for supporting monitors
Authors: Terry P. D.
Published: November 2006

The concept of the monitor as a device for handling the problems of mutual exclusion and synchronization in a set of concurrent processes is now well understood. In addition to being of considerable theoretical interest, the monitor concept has been found suitable for the design of several practical operating systems. This paper discusses an implementation of monitors using a kernel written in Modula‐2.
The cost of lexical analysis
Authors: Waite W. M.
Published: November 2006

This paper examines a common design for a lexical analyser and its supporting modules. An implementation of the design was tuned to produce the best possible performance. In effect, many of the optimizations that one would expect of a production‐quality compiler were carried out by hand. After measuring the cost of tokenizing two large programs with this version, the code was ‘detuned’ to remove specific optimizations and the measurements were repeated. In all cases, the basic algorithm was unchanged, so that the difference in cost is an indication of the effectiveness of the optimization. Comparisons were also made with a tool‐generated lexical analyser for the same task. On the basis of the measurements, several specific design and optimization strategies are recommended. These recommendations are also valid for software other than lexical analysers.
A string pattern matching extension to pascal and some comparisons with snobol4
Authors: Liu Ken‐Chih
Published: November 2006

This paper presents an extension of Pascal with string pattern matching. Pattern definitions are built using six basic operations: alternation, concatenation, immediate value assignment, intersection, difference and complement. The last three have not been previously implemented and they increase the expressive power beyond context‐free languages. The pattern matching actions are augmented with three options: trace, prefix and suffix. Comparisons with a SNOBOL4 implementation are also presented. This experiment demonstrates that Pascal with pattern matching is a useful tool for string processing applications.
A management system for dirty data
Authors: Coombs R. F.
Published: November 2006

A computer system for managing error prone and complex time‐series data is described. The system processes statistics on the catches and fishing operations of fishermen operating in New Zealand waters. These statistics are used primarily for fisheries management and, for this purpose, many years of data may be required. Errors in the data can seriously compromise management and must be weeded out as far as possible.

The system is organized around four groups of files: an input file in which data are held temporarily for error checking and correction; a master file which provides medium‐term storage for the basic data; derived from this, several summary files tailored to the needs of different user groups; and, lastly, archival files in which the basic data are stored in the long term.

The most significant feature of the system is providing effective and comprehensive error detection and correction, and in this is has proved most successful.
Automatic generation of useful syntax error messages
Authors: Kantorowitz E. , Laor H.
Published: November 2006

Many current compilers produce in some situations wrong error messages that mislead the user and harm his confidence in the system. It is demonstrated that a reliable and efficient syntax error handling system may be produced automatically by a compiler generator from the BNF specification of the language, and without any effort by the language implementor. This result is achieved in three ways:

Some errors may not be diagnosed without knowledge of the intentions of the programmer. Some compilers employ a sophisticated analysis that attempts to capture these intentions, but which is not always successful. Such an elaborate analysis is not employed here, and instead a list of all the legal corrections is displayed, so that the programmer may readily select the right one.

The recovery symbols are selected by a ‘careful’ algorithm resulting in a high probability for correct error recovery.

The ‘honest’ error messages show also the parts of the code which could not be analysed correctly because of errors, and where more errors may exist.

Efficiency is achieved by computing the recovery sets once and for all at compiler generation time, so that a fast error recovery at program compilation time is achieved. Experiments with erroneous programs suggest that the method compares well with the best compilers that we have seen, and is specially good at the avoidance of wrong error messages.
Multiplication by integer constants
Authors: Bernstein Robert
Published: November 2006

Methods are given for finding a sequence of ‘add’, ‘subtract’ and ‘shift’ instructions to multiply the contents of a register by an integer constant. Each method generalizes the previous one and requires only a few intermediate or scratch registers. A variation of the last method is used in the PL.8 compiler and uses an unnoticeable amount of the overall compile time. Some statistics roughly indicating the effectiveness of the methods are presented.
A practical approach to data modelling in spatial applications
Authors: Norris‐Sherborn A. , Milne W. J.
Published: November 2006

The storage and manipulation of spatial data requires a different style of support from that normally found in commercial database systems. This paper explores the use of the functional data model and the high level language Daplex to provide an integrated tool for the conceptual modelling of spatial data and the manipulation of data values. Importance is attached to allowing dynamic schema definition and to the provision of abstract data types to support spatial objects. The implementation comprises three separate modules and uses an underlying relational DBMS to store all metadata and data values. This modular design has enabled the user interface, Daplex language and storage aspects of the software to be developed independently, creating a system which has already proved to be easily portable. Consideration has also been given to ways of improving system performance.
Foreet: A tool for design and documentation of fortran programs
Authors: Ben‐Ari Mordechai
Published: November 2006

Foreet is a software tool for the design and documentation of Fortran programs. It is based on the premise that documents accompanying a program should be computerized and integrated: computerized–to ensure fast, easy and inexpensive updating; integrated–to ensure that the documents reflect what is actually contained in the program and not some idealized notion. Foreet takes a syntactically correct Fortran program (or skeleton of a program) and comments in a specified format and writes a report. It can be used to document existing programs, though the best results will be obtained if the documentation is developed concurrently with the program. Foreet is concerned with data description and subprogram interfaces. By encouraging precise specification of these critical facets of a program, Foreet can improve the quality of programs.
Logicon: An integration of prolog into icon
Authors: Lapalme Guy , Chapleau Suzanne
Published: November 2006

This paper describes the coupling of logic programming with Icon, which is a programming language aimed at string processing. Icon and Prolog have many similarities and their integration is feasible and desirable because the weaknesses of one can be compensated for by the strengths of the other. In our case, a Prolog interpreter was written as an Icon procedure that can be linked and called by an Icon program. This interpreter deals with all Icon data types and can be called in the context of the goal‐directed evaluation of Icon. We give an example showing the power of this symbiosis between these two languages where a Prolog call in Icon is a generator and an Icon call in a Prolog clause is a built‐in predicate.
Segments on bit‐mapped graphics displays
Authors: Slater Mel
Published: November 2006

The problems associated with using picture segments in interactive applications on workstations with bit‐mapped displays are discussed. A method for displaying and updating segments is introduced.
An algorithm for the selection problem
Authors: Dromey R. Geoff
Published: November 2006

A refinement to a well‐known selection algorithm is described. The refinement results in a useful improvement in the performance of the original algorithm, particularly when the selection index is small relative to the median.
A functional processor for the relational algebra on a microcomputer
Authors: Merrett T. H. , Van Rossum Ted
Published: November 2006

We have built on the U.C.S.D. P‐system (running on an IBM Personal Computer) a relational algebra processor, MRDS/FS, which is extremely powerful and which supports a functional syntax for the programmer‐user. The relational algebra is provided in the extended operators μ‐join, σ‐join, project and select. The domain algebra is fully implemented for the first time, giving operations on attributes: arithmetic, logic, comparison and four different categories of aggregation of these. A strictly functional syntax is provided, permitting user‐defined functions using the relational and domain algebras as primitive operations. An interactive editor permits the creation, copying and changing of both relations and user‐defined functions.
Specification methodology: An integrated relational approach
Authors: Mili Ali , Xiao‐Yang Wang , Qing Yu
Published: November 2006

The effectiveness of set theoretic concepts for the purpose of software specification is becoming more and more widely recognized. This paper presents an integrated relational methodology for software specification, and shows its effectivness when applied to a practical example.
Computing advice at a distance: The ‘remote advisory’ concept
Authors: Anstey P.
Published: November 2006

The means whereby computing advice can be given to a scattered community of networked computer users are reviewed and evaluated, particularly with respect to the convenience and effectiveness of the user/adviser contact. Current methods are found lacking and an integrated software ‘advisory environment’ is consequently proposed.
Three way branching self consistency checking of hardware and software
Authors: Cantoni A. , Kleeman L.
Published: November 2006

A simple technique that improves a system's capability of error detection and correction, and enhances software debugging is described in this note. The technique relies on consistency checking of branching variables during branching decisions and the appropriate selection of codes for the permissible values of variables.
Algorithms for BD trees
Authors: Dandamudi Sivarama P. , Sorenson Paul G.
Published: November 2006

Database applications often require a sophisticated class of storage structures in order to answer different types of queries efficiently. This often dictates that the file should be organized on multiple keys. Several storage structures have been proposed to satisfy these needs. Most are generalizations of the storage structures used for managing one‐dimensional data. Recently, a new storage structure, called the BD tree, was proposed to manage multidimensional data. This structure has good dynamic characteristics. This paper presents algorithms for the BD tree to perform insertion, deletion, and to answer exact match, partial match and range queries. In addition, some experimental evidence is presented that suggests that BD trees have good dynamic characteristics.
Another approach to the implementation of synchronization primitives
Authors: Hoppe Jiri
Published: November 2006

A new method for the implementation of synchronization primitives is described. The method combines the flexibility of user defined primitives with the possibility of compiler checks. The method allows the tailoring of the size and of the performance of the synchronization primitives to the needs of the user.
Writing concurrent assemblers–a case study in path pascal
Authors: Dowsing R. D. , Sanderson M. T.
Published: November 2006

This paper describes an investigation into the use of Path Pascal for implementing a number of different concurrent algorithms for an assembler for a subset of the PAL‐11A assembly language for the PDP‐11 range of computers. The various programs which resulted were run using simulated concurrency under the VMS operating system on a VAX 11‐780 computer, and measurements were obtained relating to the performances of the programs on different architectures. The suitability of path expressions for specifying object concurrency in such problems is discussed.
Lazy garbage collection
Authors: Glaser H. W. , Thompson P.
Published: November 2006

This paper describes a variation on the reference count method of garbage collection which can be particularly effective for the implemention of modern, truly functional languages. This method gives a high degree of control over the collection process and an increase in efficiency for many systems, particularly those with small, fast memories local to the central processor, such as a stack or an addressable cache.
Formatting texts accessed randomly
Authors: Smith John B. , Weiss Stephen F.
Published: November 2006

Full‐text systems that access text randomly cannot normally determine the format operations in effect for a given target location. The problem can be solved by viewing the format marks as the non‐terminals in a format grammar. A formatted text can then be parsed using the grammar to build a data structure that serves both as a parse tree and as a search tree. While processing a retrieved segment, a full‐text system can follow the search tree from root to leaf, collecting the format marks encountered at each node to derive the sequence of commands active for that segment. The approach also supports the notion of a ‘well formatted’ document and provides a means for verifying the well‐formedness of a given text. To illustrate the approach, a sample set of format marks and a sample grammar are given suitable for formatting and parsing the article as a sample text.
Transporting TEX into the HITAC VOS3 environment
Authors: Hayashi Tsunetoshi
Published: November 2006

An attempt to transport TEX82 and to implement a typesetting program which realizes the output of the former at Hokkaido University Computing Center is described. The target operating environment and the environment required for running the TEX82 program are compared. The transporting procedure and the requirements for compiling and running the TEX82 program are described, along with the problems that they caused. The measures taken to adapt TEX82 to the target operating environment are explained, where considerations of how the system‐dependent parts are designed in accordance with the conventions of the target environment are illustrated in detail.

The working principles and some implementation details of the output typesetting program are described, where rather esoteric techniques are employed. Finally, some measurements of performance are given.
A browser for directed graphs
Authors: Rowe Lawrence A. , Davis Michael , Messinger Eli , Meyer Carl , Spirakis Charles , Tuan Allen
Published: November 2006

A general‐purpose browser for directed graphs is described. The browser provides operations to examine and edit graphs and to generate a layout for a graph automatically that minimizes edge crossings. Two layout algorithms were implemented. A hierarchical graph layout algorithm was found to be best for directed graphs. The graph browser also has facilities that allow it to be integrated with other applications (e.g. a program browser). These facilities and our experiences building a program call‐graph browser are described.
Debugging programs that use macro‐oriented data abstractions
Authors: Katzenelson Jacob , Strominger Avy
Published: November 2006

Enhanced C (EC) is a set‐oriented, extensible, C‐like language. EC uses data abstractions to define new types. These data abstractions, called clusters, are macro‐like devices that perform substitution on the typed syntax tree. Debugging programs that use clusters raise problems that are not encountered in ordinary programming languages. At compile time there is a need to determine and report whether the macro expansion will result in a legal program before this expansion actually takes place. At run‐time the problems are how to account for replaced statements and how to handle variables whose types have been established by the clusters, variables that disappear, or variables whose names have been changed.

This article presents these problems and their solutions as implemented by the EC compiler and the EC symbolic debugger.

Similar debugging problems appear in other languages: The need to handle variables at run time is common to all languages that support data abstraction even if the abstractions are procedure oriented; also, a mild form of the problem of the replaced statement appears in inline procedure substitution of Ada. The solutions developed for the EC debugger apply to these cases as well.
Tree matching and simplification
Authors: Purdom Paul Walton , Brown Cynthia A.
Published: November 2006

A fast algorithm for performing simplification and matching is described. The algorithm gives an improvement of up to an order of magnitude on suitable problems. It makes use of a dag data structure and tag fields to avoid redundant matches. Performance studies were done to determine the relative importance of various features in improving the running time.
The suitability for master/slave concurrency of concurrent euclid, ada and modula
Authors: Butler Gregory , Kendall Mathhew J.
Published: November 2006

The suitability of Concurrent Euclid, Ada and Modula for a special form of asynchronous concurrency, called master/slave concurrency, is investigated. No language is ideal, with Concurrent Euclid and Modula having major drawbacks. The conclusion lists the features desirable in a language for master/slave concurrency.
A structural testing method for JSP designed programs
Authors: Roper M. , Smith P.
Published: November 2006

A new structural testing method (STM) is presented for use with JSP (Jackson structured programming) designed programs. The method involves the creation of a path expression from the program structure and subsequent expansion of the expression into a set of paths using an algebra described in the paper. The treatment of each JSP construct is dealt with in detail. A worked example demonstrates the use of the method to generate test cases. The method is compared in terms of coverage to other well‐known structural testing methods. The advantages and disadvantages of the method are discussed and further work currently being undertaken by the authors is outlined.
A depth‐first and tool‐supportable programming strategy
Authors: Huang J. C.
Published: November 2006

This paper describes a software im plementation strategy that allows the programmer to construct a running version of a program early in its development. In general, the first version of the program only works for a subset of the intended input domain. The subset is defined by a number of constraints placed on the program by the programmer. The program can be completed by removing the constraints one at a time. In the process, each new part added to the program can be validated independently. Software tools can be built to facilitate the validation process.
Implementing an extended functional data model using PS‐algol
Authors: Kulkarni K. G. , Atkinson M. P.
Published: November 2006

A number of data models have been proposed in the literature to improve the usability of database systems. Most of these proposals have not been implemented. It is felt that a working implementation is a necessary prerequisite for a serious study of these proposals. So far, implementing data models has been a daunting task, requiring a large team. We report here on a simple implementation technique using the persistent algorithmic language. PS‐algol, which promises to make the task of implementing data models a manageable one. The feasibility of the approach is demonstrated by implementing an entity‐based functional data model (extended function data model) using PS‐algol.
DEMOS/MP: The development of a distributed operating system
Authors: Miller Barton P. , Powell Michael L. , Presotto David L.
Published: November 2006

The DEMOS/MP operating system has moved from a supercomputer with a simple addressing structure to a network of microcomputers. This transformation was done without significant changes to the semantics of the original DEMOS, i.e. existing DEMOS programs should run on DEMOS/MP. The changes to DEMOS were simplified by the structure of its primitive objects and the functions over those objects. The structure of DEMOS links and processes were the major contributors to the simplicity. The changes made to produce DEMOS/MP involved the internal structure of link, modification to parts of the kernel, and limited changes to the various system processes.