bluuebunny/crossref_metadata_2025_split huggingface dataset:
A technique for subclassing and its implementation exploiting polymorphic procedures
Authors: Mancini Luigi V. 
Published: November 2006

AbstractSince the introduction of Smalltalk, the object‐oriented approach towards the organization of data and programs has become popular. In this paper the possibilities of exploiting procedure‐oriented languages to allow an object‐oriented style of programming are analysed. Although the two approaches are apparently dissimilar, a family of procedure‐oriented languages is described which allows a high degree of freedom in programming and does not appear to restrain the programmer within the procedure‐oriented scheme. Popular languages of this family are ML and PS‐Algol. For such languages, a technique is developed which enables an efficient implementation of object‐oriented features, such as the subclassing form of inheritance provided by Smalltalk‐80 and Simula.
Edison‐N — an Edison implementation for a network of microcomputers
Authors: Dubnicki Cezary , Madey Jan , Wygla̧dała Wojciech 
Published: November 2006

AbstractThis paper describes an experimental implementation of the Edison programming language for a network of microcomputers based on the Z‐80 microprocessor. The resulting Edison‐N system allows parallel execution of concurrent processes. Its aim is to assist in teaching the principles of concurrent programming.
Structured FORTRAN preprocessors generating optimized output
Authors: Tsuji Tatsuo , Watanabe Katsumasa , Ikehata Atsushi 
Published: November 2006

AbstractUsually a structured FORTRAN program is transformed into a standard FORTRAN program by means of a one‐pass preprocessor. In this case, several problems are caused by the many redundant continue and goto statements that a preprocessor generates. These problems include: (i) the generated FORTRAN program is not easy to read; (ii) the size of files to store the related programs becomes large; (iii) the total time increases for executing both the FORTRAN compiler and the output program itself.This paper presents a new scheme for constructing a one‐pass preprocessor that generates the optimized FORTRAN code by suppressing the redundant statements. By employing this scheme we have constructed our own preprocessors for Westran (one of the Structured FORTRAN languages) and Ratfor and measured these against the traditional preprocessors for the Westran and Ratfor languages.One of the results is as follows. The total time for users, namely ‘preprocessing time + FORTRAN compiling time’ is rather less than the traditional ones. This is due to the fact that to suppress the input/output of the redundant statements from/to files contributes to the decreasing of both preprocessing and compiling times, and this compensates completely the time‐overhead of the optimization process.
Inaccuracies in program profilers
Authors: Ponder Carl , Fateman Richard J. 
Published: November 2006

AbstractRun‐time program profiling is a valuable tool in understanding software efficiency. Techniques for obtaining profiles make assumptions that may result in misleading data. In the paper we illustrate flaws in two profiling systems: the Unix ‘Gprof’ family (including the packages ‘monitor’, ‘prof’ and ‘profil’), and the TI Explorer metering package for Lisp.
A convenient way to incorporate semantic actions in two‐pass compiling schemes
Authors: Mössenböck H. 
Published: November 2006

AbstractWe present a simple method for connecting semantic actions to parsers. Although applicable to any kind of parser it is especially suited for LR parsers. The method is based on the idea of separating syntax analysis and semantic processing and executing semantic actions by procedures, similar to those of a recursive descent compiler. The procedures are driven by structural information about the source program, which is collected during parsing. The method is applicable to L‐attributed grammars. It can be incorporated easily into any existing parser.
Performance of multi‐tasking and synchronization mechanisms in the programming language SR
Authors: Atkins M. Stella , Olsson Ronald A. 
Published: November 2006

AbstractHigh‐level language primitives for concurrent programming exist in languages such as Ada and Modula‐2. However, each of these languages provides only a single means for specifying multitasking and synchronization, essential in the implementation of concurrent systems. The SR language provides several mechanisms for specifying multi‐tasking and synchronization, so it can be used to explore the performance of various communication techniques.This paper presents performance results for SR's multi‐tasking and synchronization mechanisms and discusses the effects of the generated code, the run‐time support and the hardware on these results. These results are compared with those for similar mechanisms in other languages, leading to some general conclusions about the performance of process communication primitives. These performance results can be used by programmers to make design choices that allow systems programs written in high‐level languages to meet real‐time performance specifications.
Independent testing of compiler phases using a test case generator
Authors: Homer William , Schooler Richard 
Published: November 2006

AbstractSince a compiler phase depends on previous phases for input, it can be difficult to do timely independent unit testing of some phases. This can make integration more difficult and reduce overall quality. A test case generator has been used to circumvent this problem by providing an independent source of phase test inputs. Using a context‐free grammar augmented with contextsensitive constructs, a test case generator can generate intermediate language graphs in textual form.
Circular programs and self‐referential structures
Authors: Allison Lloyd 
Published: November 2006

AbstractA circular program creates a data structure whose computation depends upon itself or refers to itself. The technique is used to implement the classic data structures circular and doubly‐linked lists, threaded trees and queues, in a functional programming language. These structures are normally thought to require updateable variables found in imperative languages. For example, a functional program to perform the breadth‐first traversal of a tree is given. Some of the examples result in circular data structures when evaluated. Some examples are particularly space‐efficient by avoiding the creation of intermediate temporary structures which would otherwise later become garbage. Lastly, the technique can be applied in an imperative language to give an elegant program.
Q'Nial: A portable interpreter for the nested interactive array language, Nial
Authors: Jenkins M. A. 
Published: November 2006

AbstractThe Q'Nial interpreter combines ideas from APL and Lisp implementations to provide a rich programming environment that supports several paradigms of programming. The interpreter is structured to reflect the division of Nial semantics into levels corresponding to zero‐, first‐and second‐order objects. The paper describes the design of the interpreter, discusses constraints imposed by the desire to achieve portability and comments on what has been learned in building an interpreter in this style.
The design and implementation of a version server for computer‐aided design data
Authors: Gedye David , Katz Randy H. 
Published: November 2006

AbstractThe Version Server is a system for managing the versions and configurations of design descriptions as they change over time. In this paper we focus on the design and implementation of such a system, which we have built at U.C. Berkeley. The data model supported and the browser application are introduced to illustrate the system's user and application interface. The design decisions and details of the internal architecture are described and the system's performance is evaluated. For structure‐oriented queries, such as ‘traverse an entire chip's design hierarchy’, the Version Server is about five times as fast as comparable design management systems that store their design objects as files in a hierarchical file system.
GMB: A tool for manipulating and animating graph data structures
Authors: Jablonowski David , Guarna Vincent A. 
Published: November 2006

AbstractThis paper describes a tool graph originally developed for the Faust environment. Faust is a scientific program development environment being implemented at the Center for Supercomputing Research and Development at the University of Illinois at Urbana‐Champaign. The graph tool comprises two major components: the Graph Manager that implements an abstract graph data type, and the Graph Browser that handles the details of displaying a subgraph of a graph created through the Graph Manager. The Graph Browser displays graph views, where a graph view is a subgraph of its parent graph. The concept of graph views is analogous to the concept of views in the traditional database sense. Several graph views may simultaneously exist for a single parent graph, where each view's subgraph depends on the context of the application requesting the view. Goals of the graph tool, GMB, included providing an abstract graph data type for general use and animating graphs efficiently.
A practical algorithm for evaluating database queries
Authors: De Vet John H. M. 
Published: November 2006

AbstractThis paper describes an algorithm for evaluating database queries represented as expressions in a logical language. Such a database query expression can be evaluated efficiently by focusing on the variable dependencies. The algorithm recursively computes the values of subexpressions to evaluate the input expression, but it avoids re‐evaluation of those subexpressions whose values are not affected by new variable assignments. The input expression is internally structured as a directed acyclic graph. Two additional techniques to improve efficiency of the evaluation are discussed: transformations of the input expression and special primitive database operations. Finally, its implementation in the natural language question‐answering system SPICOS is described.
Semantic extension possibilities in the proposed new fortran
Authors: Schonfelder J. L. 
Published: November 2006

AbstractThe next revision of the standard Fortran language, commonly referred to as Fortran 8x, has now been published, at least in draft form. It is therefore possible for some of its new features to be investigated and the type of programming that can be expected when implementations appear to be explored. This paper looks at the scope provided by the proposed new features for 'semantic extension' of the language. The capability is illustrated by way of example code which could provide an extended‐precision numeric facility if implemented. The new linguistic constructs that permit this type of approach to software provision are described as they are used.
Allocation without locking
Authors: Appel Andrew W. 
Published: November 2006

AbstractIn a programming environment with both concurrency and automatic garbage collection, the allocation and initialization of a new record is a sensitive matter: if it is interrupted half‐way through, the allocating process may be in a state that the garbage collector cannot understand. In particular, the collector will not know which words of the new record have been initialized and which are meaningless (and unsafe to traverse).For this reason, parallel implementations usually use a locking or semaphore mechanism to ensure that allocation is an atomic operation. The locking significantly adds to the cost of allocation. This paper shows how allocation can run extremely quickly even in a multi‐thread environment: open‐coded, without locking.
The parser generating system PGS
Authors: Klein E. , Martin M. 
Published: November 2006

AbstractPGS is a parser generating system accepting LALR(1) and related grammars in extended BNF notation and producing parsers based on table‐driven stack automata. To enable syntax‐directed translation, semantic actions can be attached to rules of the input grammar. An attribution mechanism allows the transfer of information between rules. The generated parsers have an automatic error recovery which can be tailored to satisfy specific needs of the language to be accepted. PGS generates parsers written in Pascal, Modula‐2, C or Ada. Compared with existing systems, e.g. YACC1, a parser generated by PGS is twice as fast and the parse tables require 25 per cent less storage. This paper gives a survey of algorithms involved in the generator and the generated parsers, and compares them with algorithms used in other systems. In detail, it compares several parse‐table representations and their implications for space and time efficiency of the generated parsers.
Efficient generation of lexical analysers
Authors: Grosch J. 
Published: November 2006

AbstractGeneral tools for the automatic generation of lexical analysers such as LEX1 convert a specification consisting of a set of regular expressions into a deterministic finite automaton. The main algorithms involved are subset construction, state minimization and table compression. Even if these algorithms do not show their worst‐case time behaviour they are still quite expensive. This paper shows how to solve the problem in linear time for practical cases, thus resulting in a significant speed‐up. The idea is to combine the automaton introduced by Aho and Corasick2 with the direct computation of an efficient table representation. Besides the algorithm we present experimental results of the scanner generator Rex3 which uses this technique.
Converting a portable Pascal p‐code interpreter to a code generator
Authors: Schneider Victor 
Published: November 2006

AbstractThis is a technical note that assumes reader familiarity with Pagan's paper on converting scaled down Pascal p‐code programming language interpreters into simple compilers.1 This note discusses the extension of Pagan's methods to a full‐scale Pascal‐to‐C translator. In order to make procedure calls and typed function calls work properly for such a translator, it was found necessary to add type information to one of the p‐code calling instructions (and alter the Pascal‐to‐p‐code translator accordingly). A table of execution times for Pagan's ‘50 primes’ bench‐mark program shows the improvements obtained as a result of successive refinements in the Pascal‐to‐C translator, until the present version that uses C ‘register variables’ for integer arithmetic.2 Programs compiled using this system can also be linked into C programs as functions or procedures and can be debugged using standard C debuggers.
Vertical migration of numerical routines in software and microcode
Authors: Charlton C. C. , Leng P. H. , Little J. 
Published: November 2006

AbstractVertical migration is a widely acknowledged technique for improving the performance of critical sections of code. Migration may be to the assembly‐language level or, for machines with writable control store, into microcode. The former is easier to implement and allows a degree of portability, albeit limited, of the target routines, although performance gains may not be as great as those resulting from migration into microcode. The latter however, requires considerable programming effort and the size of available control store may well place restrictions upon the amount of code which can be migrated to this level. Given the task of improving the performance of a large software base, full migration is rarely practical, so time must be spent determining the best migration strategy for a ‘target set’ of critical routines.In this paper, we report on work to improve, by vertical migration, the performance of the bask linear algebra subroutines of the FORTRAN NAG library. We identify a number of different migration strategies based upon the availability of two migration levels and report on the performance gains achieved by applying each of these strategies; various conditions under which each strategy may be most appropriate have thus been identified. In particular, this work shows how, by careful selection of just a small number of target routines, resulting performance gains can not only be significant for each individual routine, but also for the whole software system.
Building a real‐time kernel: First steps in validating a pure process/ADT model
Authors: Callison H. Rebecca , Shaw Alan C. 
Published: November 2006

AbstractA model based on simple, unadorned processes and abstract data types has been proposed for the design and implementation of real‐time systems. We describe our generally successful experiences in using this model for the construction of a real‐time operating system kernel containing services for process control, synchronization, time and input‐output. Our work and results focus on the usefulness of the scheme for designing modules at hardware/software interfaces, for predicting deterministic timing behaviour, and for software development.
The design and implementation of a high‐level language converter
Authors: Moynihan Vincent D. , Wallis Peter J. L. 
Published: November 2006

AbstractThere is now a good understanding of problems encountered in the design, implementation and use of a high‐level language converter. These general issues are illustrated in terms of an account of the design and implementation of one particular converter, which converts programs from Pascal‐SC (a Pascal dialect) to Ada. A specific aim of the presentation is to provide guidance for those contemplating future language conversion projects.
An implementation of distributed shared memory
Authors: Ramachandran Umakishore , Khalidi M. Yousef A. 
Published: November 2006

AbstractShared memory is a simple yet powerful paradigm for structuring systems. Recently, there has been an interest in extending this paradigm to non‐shared memory architectures as well. For example, the virtual address spaces for all objects in a distributed object‐based system could be viewed as constituting a globaldistributed shared memory. We propose a set of primitives for managing distributed shared memory. We present an implementation of these primitives in the context of an object‐based operating system as well as on top of Unix.
Reverse engineering: Algorithms for program graph production
Authors: Cimitile Aniello , de Carlini Ugo 
Published: November 2006

AbstractThe paper proposes an algebraic representation of program modules, calledF(p), and illustrates the algorithms that useF(p)to generate program graph models for measurement, documentation and testing activities. The representation refers to procedural languages, D‐structured programs and one‐in/one‐out modules but its definition can be extended to programs structured in terms of an arbitrary set of one‐in/one‐out legal control structures. Since it is possible to produceF(p)directly from the program code using reverse engineering techniques, the algorithms proposed are of considerable interest for the setting up of tools supporting the program comprehension phase, which is a fundamental first step in any maintenance operation.
Identifying syntactic differences between two programs
Authors: Yang Wuu 
Published: November 2006

AbstractProgrammers frequently face the need to identify the differences between two programs, usually two different versions of a program. Text‐based tools such as the UNIXr̀ utility diff often produce unsatisfactory comparisons because they cannot accurately pinpoint the differences and because they sometimes produce irrelevant differences. Since programs have a rigid syntactic structure as described by the grammar of the programming language in which they are written, we develop a comparison algorithm that exploits knowledge of the grammar. The algorithm, which is based on a dynamic programming scheme, can point out the differences between two programs more accurately than previous text comparison tools. Finally, the two programs are pretty‐printed ‘synchronously’ with the differences highlighted so that the differences are easily identified.
Transparent process migration: Design alternatives and the sprite implementation
Authors: Douglis Fred , Ousterhout John 
Published: November 2006

AbstractThe Sprite operating system allows executing processes to be moved between hosts at any time. We use this process migration mechanism to offload work onto idle machines, and also to evict migrated processes when idle workstations are reclaimed by their owners. Sprite's migration mechanism provides a high degree of transparency both for migrated processes and for users. Idle machines are identified, and eviction is invoked, automatically by daemon processes. On Sprite it takes up to a few hundred milliseconds on SPARCstation 1 workstations to perform a remote exec, whereas evictions typically occur in a few seconds. The pmake program uses remote invocation to invoke tasks concurrently. Compilations commonly obtain speed‐up factors in the range of three to six; they are limited primarily by contention for centralized resources such as file servers. CPU‐bound tasks such as simulations can make more effective use of idle hosts, obtaining as much as eight‐fold speed‐up over a period of hours. Process migration has been in regular service for over two years.
PROTOB: An object‐oriented case tool for modelling and prototyping distributed systems
Authors: Baldassari Marco , Bruno Giorgio , Castella Andrea 
Published: November 2006

AbstractThe PROTOB object‐oriented methodology for the executable specification of large‐scale event‐driven systems is introduced and described. Two supporting features of PROTOB are also presented: the graphic and textual language that formally describes the behaviour of objects, which is based on high‐level Petri nets called “PROT nets” and which is demonstrated to be more powerful than SA/RT dataflows; and a CASE environment with tools for specification, modelling, simulation and prototyping. Use of PROTOB is illustrated by discussion of the automated generation of distributed systems running on a network of VMS and UNIX computers.
Evaluation of fortran vector compilers and preprocessors
Authors: Luecke Glenn , Haque Waqar , Hoekstra James , Jespersen Howard , Coyle James 
Published: November 2006

AbstractMany scientific codes can achieve significant performance improvement when executed on a computer equipped with a vector processor. Vector constructs in source code should be recognized by a vectorizing compiler or preprocessor. This paper discusses, from a general point of view, how a vectorizing compiler/preprocessor can be evaluated. The areas discussed include data dependence analysis, IF loop analysis, nested loops, loop interchanging, loop collapsing, indirect addressing, use of temporary storage, and order of arithmetic. The ideas presented are based on vectorization of over a million lines of production codes and an extensive test suite developed to evaluate preprocessors under varying degrees of code complexity. Areas for future research are also discussed.
DMT—a demonstration tool
Authors: Zheng Yi , Hague Jim 
Published: November 2006

AbstractDMT is a software demonstration tool, running on workstations, that can be used to demonstrate other software tools. The paper describes the reasons for developing DMT and the implementation of DMT. DMT simulates a video recorder/player system and provides recording, winding (forward/backward) and replaying functions. During recording, DMT records the target tool window image changes and the interactions between the target tool and the controlling mouse. By deleting and inserting visual‐image scripts and by adding textual comments to explain the visual‐image changes, a user can obtain editing of what has been recorded. During replay, DMT shows how the target window changes as if the target tool is being demonstrated in real time. The textual comments are played synchronously with the visual images.