bluuebunny/crossref_metadata_2025 huggingface dataset:
A uniform object model for parallel programming
Authors: Crowl L. A.
Published: November 2005

This position statement presents a uniform object model of parallel programming that enables use of multiple programming styles, binding parallelism late, and porting programs among a wide variety of architectures. It then argues for concurrent operations on objects, as opposed to mutually exclusive operations on objects, based on orthogonality between encapsulation and concurrency. The final section argues for its relatively novel insistence on uniform control, based on the flexibility it provides the programmer.
Object-oriented concurrent programming in CST
Authors: Dally W. J. , Chien A. A.
Published: November 2005

CST is a programming language based on Smalltalk-80 that supports concurrency using locks, asynchronous messages, and distributed objects. Distributed objects have their state distributed across many nodes of a machine, but are referred to by a single name. Distributed objects are capable of processing many messages simultaneously and can be used to efficiently connect together large collections of objects. They can be used to construct a number of useful abstractions for concurrency. We describe describe the CST language and give examples of its use.
Object oriented languages and actors: which language for a distributed approach?
Authors: Carre F. , Clere P.
Published: November 2005

In the last years, hardware research has produced new parallel architectures. Now, it is time to define a language adapted to run applications in Artificial Intelligence area on these architectures.
Concurrent data structures and actor programming under the Matroshka model
Authors: Crowl L. A.
Published: November 2005

In the late panel session, Maurice Herlihy questioned whether the Actor model [1] could implement wait-free shared queue. Processes are guaranteed to complete queue operations in a finite amount of steps even if other processes may fail at arbitrary points. Consequently, the queue may not have an implementation based on mutual exclusion, but may be implemented with non-trivial atomic operations. Gul Agha did not provide a method for implementing such an abstraction, but argued that the techniques used to implement the wait-free queue would also apply to implementing the Actor model.The Matroshka model (described in the position statement "A Uniform Object Model for Parallel Programming" within these proceedings and [2]) can implement both wait-free queues and the Actor model of computation.
Parallel objects on distributed constraint logic programming machines
Authors: Koegel J. F.
Published: November 2005

The programming language POOL (Parallel Object Oriented Logic) allows computation to be represented as a collection of parallel objects which communicate via asynchronous message passing. Object procedures are Constraint Logic Programming (CLP) programs. POOL objects are mapped transparently to a network of CLP machines which execute concurrently. An implementation on a distributed network of workstations supports parallel object execution, automatic object placement, and a global object name space.
Evaluating correctness criteria for transactions
Authors: Langworthy D. E.
Published: November 2005

We propose a metric to evaluate correctness criteria for transactions which measures the number of conflicts between transactions and the amount of concurrency a criterion allows. This metric is then used to evaluate several correctness criteria.
Language issues in the specification and design of composite systems
Authors: Feather M. S.
Published: November 2005

Our focus is on the design of composite systems, that is, systems to be realized as the combination of interacting autonomous components. Typically there are some overall goals that the system is intended to achieve, and the components act
concurrently
, interleaving their actions, to achieve those goals. Since multiple components are involved, they must
communicate
in order to coordinate their individual activities. We will argue that the design of such a system should progress from a set of requirements for the entire system, and outline features of our specification language, Gist, that make it suited to expressing the stages in such a design process.
Garp: a graphical/textual language for concurrent programming
Authors: Kaplan S. M. , Goering S. K.
Published: November 2005

Concurrent systems in which the number of processes and their interconnections can change dynamically suffer from the problem of ensuring that process interconnections are correctly maintained at all times. We propose a hybrid solution to this problem in which processes are described textually, but interconnections are described graphically using a graph grammar to constrain the legal sets of processes and interconnections that the system may evolve. This paper discusses G
ARP
, a hybrid graphical/textual concurrent programming language that acts as a testbed for our ideas, and illustrates its use with an example.
Object-based real-time programming
Authors: Nigro Libero , Tisato F.
Published: November 2005

RTO (Real-Time Objects) is an object-based programming paradigm suited for Real-Time and, in particular, Hard-Real-Time applications. A Real-Time (RT) system must provide (with high probability) response times small in comparison with the time constants of the environment. A Hard-Real-Time (HRT) system is a RT system which must also fulfill deterministic constraints on response times. The aim of RTO is to provide a test bed for the experimentation of concepts which are relevant in the RT area. Then it is focused on those dimensions of Object-Based language design [Wegner 87b] which are tightly related to specific requirements of that area. This paper introduces the rationale for the basic choices of RTO.
SN-2: a data acquisition and processing system
Authors: Defu Z. , Peigen Y. , Zhongxiu S.
Published: November 2005

SN-2 is a distributed microcomputer system designed for the testing of agricultural machines. The system is not only lower in cost but also higher in performance. A set of distributed parallel algorithms for calculating FFT etc is presented. By the algorithms the processing speed can be increased.
A three-processor Lisp machine architecture based on statistical analysis of Common Lisp programs
Authors: Klaassen A. J. , van Wezenbeek A. M.
Published: November 2005

A package has been written for statically analyzing Common Lisp source code programs. The analysis was performed on source code of the implementation of the Common Lisp dialect Spice Lisp and indicated which parts of Lisp are used often and therefore are important to be implemented such that they run fast. Based upon the identification of those parts we sketch the outlines of a three-processor Lisp machine architecture.
Indirect naming in distributed programming languages
Authors: Jung D. D. , Sibert E.
Published: November 2005

Direct naming of processes in message communication is not desirable in distributed programming, because it requires a priori knowledge of sending and receiving process names. This not only complicates the construction of library or utility programs, but also is not suitable for a dynamic process creation environment. Indirect naming of processes in distributed message communication can be achieved either by introducing channels (ports) or by using process variables. This paper discusses how a new distributed programming language, COPL, achieves indirect naming effectively by using process variables without introducing shared objects, such as channels, in a distributed environment where dynamic process acitivation and selection of communicating partners are important.
Application programming as the construction of language interpreters
Authors: Frost R. A.
Published: November 2005

Application programming is often carried out in an ad hoc way compared to the construction of code for implementing operations in 'standard calculi' such as relational calculus, number theory, set theory, etc. The various programming techniques, such as 'abstraction' and 'transformation', which are often used in the latter are infrequently used in application programming. We believe that more structured approaches to application programming may facilitate the use of established programming techniques in application programming. In this paper, we explore one such approach that is based on the notion of 'application programming as the construction of language interpreters'. We have built a 'system' to support this approach. The system that we have built consists of a number of higher order functions that can be used to 'glue together' parts of a specification of an attribute grammar such that the result is an executable interpreter. These functions facilitate the 'language processing' part of application programming. Our implementation language is a higher order, lazy, pure functional programming language; this facilitates the 'standard calculi' part of application programming. We claim that for certain types of application programming, our system not only helps the programmer to separate these two aspects of the problem, but that it also provides a framework in which both aspects can be addressed methodically, taking advantage of various programming techniques such as 'abstraction' and 'transformation', and subsequently re-integrated to obtain the required program. We have extended the basic notion of attribute grammars so that our approach has wider application. The extension is based upon a new notion of 'multi-input parsing'.
The Alonzo functional programming language
Authors: Ramsdell J. D.
Published: November 2005

Alonzo is a programming language for specifying an output stream of characters as a function of a given input stream of characters. It is a non-strict language based on the untyped λ-calculus, and it has been enriched by adding syntax for local bindings and mutual recursion. Primitive data and their operators have been included along with strict vectors.
Debugging heterogeneous distributed systems using event-based models of behavior
Authors: Bates Peter
Published: November 2005

Event Based Behavioral Abstraction (EBBA)
is a high-level debugging approach which treats debugging as a process of creating
models
of actual behavior from the activity of the system and comparing these to models of expected system behavior. The differences between the actual and expected models are used to characterize erroneous system behavior and direct further investigation.

A set of
EBBA-based tools
has been implemented that users can employ to construct libraries of behavior models and investigate the behavior of an errorful system through these models. EBBA evolves naturally as a cooperative distributed program that can take better advantage of computational power available in a network computer system to enhance debugging tool transparency, reduce latency and uncertainty for fundamental debugging activities and accommodate diverse, heterogeneous architectures.
Debugging parallel programs in parallel
Authors: Rubin Robert , Rudolph Larry , Zernik Dror
Published: November 2005

There often exists a large gap between the user's conceptual picture of a parallel machine and the real machine, and between the user's expectations for program execution and the real process of execution. A monitoring and debugging machine can be used to bridge this gap. The Makbilan machine described here creates and maintains in real time a picture of the system that displays different layers of the machine. It can display hardware performance (such as bus accesses, memory references), operating-system abstractions (such as dynamic process tree or resource allocation), and special-purpose animations of the program (designed by the programmer in a constraint-based graphical environment).

This paper introduces the design of a non-intrusive monitor with a constraint-based graphic display machine, and is event-driven. The Makbilan machine on which the parallel programs run is under construction, and the monitor is thus designed and simulated in concordance with hardware specifications. The contributions of this paper are:

The use of interesting events to integrate a monitor, a debugger and an animation tool for parallel algorithms.

A non-intrusive architecture for monitoring executing programs.

A flexible animation tool and a set of animations that can be used to understand the parallel structures of parallel algorithms and their execution on a parallel machine.
Hypercube experiments with Joyce
Authors: Andersen B.
Published: November 2005

Joyce is a programming language for distributed systems. This paper describes an implementation of Joyce, which runs on an Intel iPSC hypercube, and discusses the performance of the implementation based on experiments. The first version of iPSC hypercube is finally concluded to be an inadequate distributed computer for execution of Joyce programs.
Aspects of OBERON suitable for graphics applications
Authors: Milanese V.
Published: November 2005

The requirement of complex data structures and efficient algorithms are strictly connected in graphics. The use of languages suitable for facing such need has led to sophistacated programming techniques (functional, logical, object programming). Also procedural programming, however, can provide idoneous tools to handle complex data models, which are realized according to modern criteria of software development.
A better way to combine efficient string length encoding and zero-termination
Authors: Bron C. , Dijkstra E. J.
Published: November 2005

In this note we describe conventions for string handling, and in particular for efficient string length encoding. These conventions are based on the (C-language) zero--terminator convention, and assume that the size of the area containing the string is known. They do not require any special provisions on the part of the language implementation. The mechanism to be described caters smoothly for strings of arbitrary length. The notes are based on several years of experience within the framework of Modular Pascal.
An improved mixture rule for pattern matching
Authors: Ophel J.
Published: November 2005

An improved mixture rule for compiling the pattern matching mechanism used in function definitions for ML, Miranda and Hope is presented. The new rule produces better code for patterns with mixed constructors and variables in multiple columns.
Shift-reduce conflicts in LR parsers
Authors: Pezaris S. D.
Published: November 2005

In this note, the shift-reduce conflicts of LR(1) and LR(0) are compared. It is concluded that, if LR(1) has no shift-reduce conflicts, or, if the LR(1) shift-reduce conflicts are resolved in favor of the shift, then all shift-reduce conflicts of the corresponding LR(0) can be correctly resolved by the simple rule: resolve in favor of the shift. With this resolution, LR(0) is adequate for parsing the C grammar.
Object Oriented Programming
Authors: Pokkunuri B. P.
Published: November 2005

Object Oriented Programming (OOP) is being used quite widely in the fields of both software engineering and artificial intelligence. The aim of this article is to give an idea of OOP and its features. It includes an indication of the available OOP environments and the Object-Oriented extensions made to the conventional languages such as C and Pascal. Some of the advantages in the use of OOP are also described briefly.
A note on the Power Operators “loops are harmful”
Authors: De Kerf J. L. F.
Published: November 2005

Power Operators have been proposed in several papers but have only been implemented in STSC's experimental "NARS". An overview is given of these proposals and implementations. Two forms of a restricted simulation by a defined operator are discussed, the first form incorporating an explicit loop, and the second form applying the execute function (♠). Efficiency in cpu time are compared and it is concluded -- once more -- that "Loops are Harmful".
A heretical view on type embedding
Authors: Boute R. T.
Published: November 2005

Based on a useful concept of type-ordering that implicity or explicitly underlies the type of certain programming languages, it is shown that the type "boolean" can be viewed as a subtype of the type "natural" and hence, by transitivity, of "integer", "rational", and so on. This implies defining 𝔹 = {0, 1 } rather than B = {false, true}, and results in many useful mathematical properties that are not available with the latter definition. It is shown how the danger of confusion (which is often considerably overrated anyway) can be eliminated, and how a slight modification in the formulation of predicate logic can accommodate this definition rather conveniently. The theoretical and practical advantages are illustrated by means of examples.
Survey and comparison of PARLOG and Concurrent Prolog
Authors: Talia D.
Published: November 2005

The integration of logic programming and concurrent programming has created a new class of languages, concurrent logic languages. These languages are born from a new interpretation of Horn clauses, called the process interpretation. The main goal of concurrent logic languages is the exploitation of parallelism which is inside logic programs. Furthermore, they extend the application areas of logic programming. This paper surveys and compares the two most significant concurrent programming languages, PARLOG and Concurrent Prolog. For both languages the main features are presented and discussed.
The semantics of program dependence
Authors: Cartwright Robert , Felleisen Mattias
Published: November 2005

Optimizing and parallelizing compilers for procedural languages rely on various forms of program dependence graphs (
pdgs
) to express the essential control and data dependencies among atomic program operations. In this paper, we provide a semantic justification for this practice by deriving two different forms of program dependence graph — the
output pdg
and the
def-order pdg
—and their semantic definitions from
non-strict
generalizations of the denotational semantics of the programming language. In the process, we demonstrate that both the
output pdg
and the
def-order pdg
(with minor technical modifications) are conventional data-flow programs. In addition, we show that the semantics of the
def-order pdg
dominates the semantics of the
output pdg
and that both of these semantics dominate—rather than preserve—the semantics of sequential execution.
Process decomposition through locality of reference
Authors: Rogers A. , Pingali K.
Published: November 2005

In the context of sequential computers, it is common practice to exploit temporal locality of reference through devices such as caches and virtual memory. In the context of multiprocessors, we believe that it is equally important to exploit spatial locality of reference. We are developing a system which, given a sequential program and its domain decomposition, performs process decomposition so as to enhance spatial locality of reference. We describe an application of this method - generating code from shared-memory programs for the (distributed memory) Intel iPSC/2.
An LR substring parser for noncorrecting syntax error recovery
Authors: Cormack G. V.
Published: November 2005

For a context-free grammar
G
, a construction is given to produce an LR parser that recognizes any substring of the language generated by
G
. The construction yields a conflict-free (deterministic) parser for the
bounded context
class of grammars (Floyd, 1964). The same construction yields either a left-to-right or right-to-left substring parser, as required to implement
Non-correcting Syntax Error Recovery
as proposed by Richter (1985). Experience in constructing a substring parser for Pascal is described.
Scannerless NSLR(1) parsing of programming languages
Authors: Salomon D. J. , Cormack G. V.
Published: November 2005

The disadvantages of traditional two-phase parsing (a scanner phase preprocessing input for a parser phase) are discussed. We present metalanguage enhancements for context-free grammars that allow the syntax of programming languages to be completely described in a single grammar. The enhancements consist of two new grammar rules, the exclusion rule, and the adjacency-restriction rule. We also present parser construction techniques for building parsers from these enhanced grammars, that eliminate the need for a scanner phase.
Incremental generation of parsers
Authors: Heering J. , Klint P. , Rekers J.
Published: November 2005

An LR-based parser generator for arbitrary context-free grammars is described, which generates parsers by need and processes grammar modifications by updating already existing parsers. We motivate the need for these techniques in the context of interactive language definition environments, present all required algorithms, and give measurements comparing their performance with that of conventional techniques.
Spill code minimization techniques for optimizing compliers
Authors: Bernstein D. , Golumbic M. , Mansour y. , Pinter R. , Goldin D. , Krawczyk H. , Nahshon I.
Published: November 2005

Global register allocation and spilling is commonly performed by solving a graph coloring problem. In this paper we present a new coherent set of heuristic methods for reducing the amount of spill code generated. This results in more efficient (and shorter) compiled code. Our approach has been compared to both standard and priority-based coloring algorithms, universally outperforming them.

In our approach, we extend the capability of the existing algorithms in several ways. First, we use
multiple
heuristic functions to increase the likelihood that less spill code will be inserted. We have found three complementary heuristic functions which together appear to span a large proportion of good spill decisions. Second, we use a specially tuned greedy heuristic for determining the order of deleting (and hence coloring) the unconstrained vertices. Third, we have developed a “cleaning” technique which avoids some of the insertion of spill code in non-busy regions.
Coloring heuristics for register allocation
Authors: Briggs P. , Cooper K. D. , Kennedy K. , Torczon L.
Published: November 2005

We describe an improvement to a heuristic introduced by Chaitin for use in graph coloring register allocation. Our modified heuristic produces better colorings, with less spill code. It has similar compile-time and implementation requirements. We present experimental data to compare the two methods.
On-the-fly detection of access anomalies
Authors: Schonberg D.
Published: November 2005

Access anomalies are a common class of bugs in shared-memory parallel programs. An access anomaly occurs when two concurrent execution threads both write (or one thread reads and the other writes) the same shared memory location without coordination. Approaches to the detection of access anomalies include static analysis, post-mortem trace analysis, and on-the-fly monitoring.

A general on-the-fly algorithm for access anomaly detection is presented, which can be applied to programs with both nested fork-join and synchronization operations. The advantage of on-the-fly detection over post-mortem analysis is that the amount of storage used can be greatly reduced by data compression techniques and by discarding information as soon as it becomes obsolete. In the algorithm presented, the amount of storage required at any time depends only on the number V of shared variables being monitored and the number N of threads, not on the number of synchronizations. Data compression is achieved by the use of two techniques called
merging
and
subtraction
. Upper bounds on storage are shown to be V × N
2
for merging and V × N for subtraction.
Demonic memory for process histories
Authors: Wilson P. R. , Moher T. G.
Published: November 2005

Demonic memory is a form of reconstructive memory for process histories. As a process executes, its states are regularly checkpointed, generating a history of the process at low time resolution. Following the initial generation, any prior state of the process can be reconstructed by starting from a checkpointed state and re-executing the process up through the desired state, thereby exploiting the redundancy between the states of a process and the description of that process (i.e., a computer program).

The reconstruction of states is automatic and transparent. The history of a process may be examined as though it were a large two-dimensional array, or
address space-time
, with a normal address space as one axis and steps of process time as the other. An attempt to examine a state that is not physically stored triggers a “demon” which reconstructs that memory state before access is allowed.

Regeneration requires an exact description of the original execution of the process. If the original process execution depends on non-deterministic events (e.g., user input), these events are recorded in an
exception list
, and are replayed at the proper points during re-execution.

While more efficient than explicitly storing all state changes, such a checkpointing system is still prohibitively expensive for many applications; each copy (or
snapshot
) of the system's state may be very large, and many snapshots may be required. Demonic memory saves both space and time by using a
virtual copy
mechanism. (Virtual copies share unchanging data with the objects that they are copies of, only storing differences from a prototype or original [MiBK86].) In demonic memory, the snapshot at each checkpoint is a virtual copy of the preceding checkpoint's snapshot. Hence it is called a
virtual snapshot
. In order to make the virtual snapshot mechanism efficient, state information is initially saved in relatively large units of space and time, on the order of pages and seconds, with single-word/single-step regeneration undertaken only as needed. This permits the costs of indexing and lookup operations to be amortized over many locations.
Unified management of registers and cache using liveness and cache bypass
Authors: Chi C.-H. , Dietz H.
Published: November 2005

In current computer memory system hierarchy, registers and cache are both used to bridge the reference delay gap between the fast processor(s) and the slow main memory. While registers are managed by the compiler using program flow analysis, cache is mainly controlled by hardware without any program understanding. Due to the lack of coordination in managing these two memory structures, significant loss of system performance results because:

Cache space is wasted to hold inaccessible copies of values in registers.

Inaccessible copies of values replace those accessible ones from cache.

Despite the fact that register allocation has long recognized the benefits of live range analysis, current cache management has completely ignored live range information.

In this paper, we propose an unified management of registers and cache using liveness and cache bypass. By using a single model to manage these two memory structures, most redundant copies of values in cache can be eliminated. Consequently, bus traffic and memory traffic in data cache are greatly reduced and cache effectiveness is improved.
Extending the operating system to support an object-oriented environment
Authors: Marques J. A. , Guedes P.
Published: November 2005

Comandos is a project within the European Strategic Programme for Research on Information Technology -
ESPRIT
and it stems from the identified need of providing simpler and more integrated environments for application development in large distributed systems.

The fundamental goal of the project is the definition of an integrated platform providing support for distributed and concurrent processing in a LAN environment, extensible and distributed data management and tools for monitoring and administrating the distributed environment.

An object oriented approach was used as the ground level for the integration of the multidisciplinary concepts addressed in the project.

This paper starts by describing the basic model and architecture of Comandos, which results from a common effort by all the partners in the project. We focus then on the description of a first prototype of the system, which implements a subset of the architecture and is currently running on a set of personal computers and workstations at INESC. The prototype is a testbed for the architecture, providing dynamic linking, access to persistent objects and transparent distribution. Special attention is given to the performance aspects of object invocation in virtual memory.
Neural agents - a frame of mind
Authors: Adams S. S. , Nabi A. K.
Published: November 2005

Several recent theories have been advanced to model complex heuristic behavior. From Minsky's
Society of Mind
to neural networks, these theories all share a common architecture consisting of many highly connected elements that together exhibit sophisticated macro behavior. This paper describes NeuralAgents, a framework developed in Smalltalk-80 that combines the high level interaction and collaboration of rule-based agents with the topological connectivity of neural nets. The Client-Facilitator-Consultant model for agencies will be presented, along with the object oriented design and implementation of the NeuralAgents system. PetWorld, an animated environment for the simulation of animal behavior is presented as an example application.
An extended frame language
Authors: Block F. P. , Chan N. C.
Published: November 2005

This paper describes several extensions to the traditional frame based programming semantics. We generalize the treatment of slots to include frame-like semantics; in addition we allow slots to be referenced by complex terms, whereas previously described frame based systems typically allow only scalar slot references. The resulting frame system naturally accommodates complex data structures and provides an extremely powerful mechanism for specifying complex relationships between objects represented by frames.
Strategies for scientific prototyping in Smalltalk
Authors: Walther S. S. , Peskin R. L.
Published: November 2005

This paper describes the design of a scientific prototyping environment in Smalltalk and discusses implementation strategies to achieve high performance interactive modeling of computationally intensive physical problems. Classes for scientific visualization, including contour plotting and 3D surface representations which incorporate the model-view-controller paradigm are presented. Techniques for inclusion of user primitives written in C to support computationally intense methods are described in detail in their current implementation on advanced Smalltalk workstations (SUN4, Ardent Titan, Tektronix 4317).
Function minimization and automatic differentiation using C++
Authors: Jerrell M. E.
Published: November 2005

Function minimization techniques often require values for the first partial derivatives of the function at a point. Certain techniques, such as Newton's method, require the values of the second partial derivatives as well. The methods commonly used to obtain these values have certain drawbacks which can be eliminated using a technique known as automatic differentiation. When this technique is implemented in an object oriented language with operator overloading capabilities, the problem of differentiation and minimization can be mapped into a code which fits well with the problem space.
Object-oriented programming for linear algebra
Authors: McDonald J. A.
Published: November 2005

Many numerical analysts and Lisp/Smalltalk programmers share the assumption that languages like Fortran are more appropriate for traditional, quantitative scientific programming than object-oriented languages. To show how straightforward application of object-oriented design to standard algorithms in numerical linear algebra improves clarity and expressiveness, without sacrificing speed or accuracy, I describe parts of Cactus, a system for numerical linear algebra and constrained optimization, implemented in Common Lisp and CLOS.
A fast method dispatcher for compiled languages with multiple inheritance
Authors: Dixon R. , McKee T. , Vaughan M. , Schweizer P.
Published: November 2005

This paper addresses the problem of an efficient dispatch mechanism in an object-oriented system with multiple inheritance. The solution suggested is a direct table indexed branch such as is used in C++. The table slot assignments are made using a coloring algorithm. The method is applicable to strongly typed languages such as C++ (with multiple inheritance added) and Eiffel, and in a slightly slower form to less strongly typed languages like Objective C.
PCLOS: a critical review
Authors: Paepcke A.
Published: November 2005

This paper uses the persistent object system PCLOS to survey some problems and benefits of object persistence. The system is analyzed along several relevant dimensions. PCLOS provides object persistence for an object-oriented language. The insights gained on desirable and detrimental components of the system are presented. The intent is to outline some of the expected and unexpected problems encountered in the construction of support for object persistence.
An object addressing mechanism for statically typed languages with multiple inheritance
Authors: Conner R. C. H. , Dearle A. , Morrison R. , Brown A. L.
Published: November 2005

In this paper we are concerned with addressing techniques for statically typed languages with multiple inheritance. The addressing techniques are responsible for the efficient implementation of record field selection. In object-oriented languages, this record selection is equivalent to the access of methods. Thus, the efficiency of these techniques greatly affects the overall performance of an object-oriented language. We will demonstrate that addresses, in such systems, cannot always be calculated statically and show how symbol tables have been used as address maps at run time. The essence of the paper is a new addressing technique that can statically calculate either the address of a field or the address of the address of the field. This technique is powerful enough to support an efficient implementation of multiple inheritance with implicit subtyping as described by Cardelli.
An object-oriented modelling enviornment
Authors: Page T. W. , Berson S. , Cheng W. , Muntz R. R.
Published: November 2005

Many tools and techniques exist for the modeling and analysis of computer and communication systems. These tools are often complex and tailored to a narrow range of problems. The system analysis task often requires coordinated use of multiple tools and techniques which is not supported by currently available systems. The Tangram project goal is to develop an environment which makes a large set of tools and techniques readily accessible and is easily tailored to specialized applications.

This system has been prototyped in an object-oriented extension to Prolog. The impact that these two paradigms, logic and objects, have had on the design is discussed. Several example applications are presented to illustrate the extensibility of the system.
An environment for literate Smalltalk programming
Authors: Reenskaug T. , Skaar A. L.
Published: November 2005

The programming environment described in this paper is an adaptation of Donald Knuth's concept of literate programming, applied to Smalltalk programs. The environment provides a multi-media document production system including media for Smalltalk class and method definitions.

There are two outputs from the system. The first output is a document which contains general descriptions and discussions intermixed with precise definitions of program fragments, test inputs and test results. The second output consists of compiled Smalltalk programs installed and ready for execution.

The main idea was to produce program documentation that was just as interesting and fascinating to read as ordinary literature. Our experience showed an added benefit, namely that the literate programming environment was an active aid in the problem solving process. The simultaneous programming and documentation lead to significantly improved quality of both programs and documentation.
An event-driven model-view-controller framework for Smalltalk
Authors: Shan Y.-P.
Published: November 2005

The Smalltalk Model-View-Controller (MVC) user interface paradigm uses polling for its input control. The polling loops consume CPU cycles even when the user is not interacting with the interface. Applications using Smalltalk as their front-end often suffer unnecessary performance loss. This paper presents a prototype event-driven MVC framework to solve these problems. A solution to the compatibility problem is also provided to allow interface objects built under both polling and event-driven mechanisms to be used by each other with no modification and no performance penalty.
Constraint technology for user-interface construction in ThingLab II
Authors: Moloney J. , Borning A. , Freeman-Benson B.
Published: November 2005

ThingLab II is an object-oriented constraint programming system designed specifically for interactive user interface construction and implemented in Smalltalk-80 For constraints to be effective in building user interfaces, they must not impede the responsiveness of the user interface either at run time or during construction. The necessary speed is attained in ThingLab II by making judicious tradeoffs between compilation and interpretation, and by using a fast, incremental algorithm for constraint satisfaction. The resulting system allows user interface components to be assembled, tested, and modified expediently while maintaining interactive responsiveness.
Extending ordinary inheritance schemes to include generalization
Authors: Pedersen C. H.
Published: November 2005

The arrangement of classes in a specialization hierarchy has proved to be a useful abstraction mechanism in class-based object oriented programming languages. The success of the mechanism is based on the high degree of code reuse that is offered, along with simple type conformance rules.

The opposite of specialization is generalization. We will argue that support of generalization in addition to specialization will improve class reusability. A language that only supports specialization requires the class hierarchy to be constructed in a top down fashion. Support for generalization will make it possible to create super-classes for already existing classes, hereby enabling exclusion of methods and creation of classes that describe commonalties among already existing ones.

We will show how generalization can coexist with specialization in class-based object oriented programming languages. Furthermore, we will verify that this can be achieved without changing the simple conformance rules or introducing new problems with name conflicts.
Programming with explicit metaclasses in Smalltalk-80
Authors: Briot J.-P. , Cointe P.
Published: November 2005

This paper discusses the introduction of explicit metaclasses á la ObjVlisp into the Smalltalk-80 language. The rigidity of Smalltalk metaclass architecture motivated this work. We decided to implement the ObjVlisp model into the standard Smalltalk-80 system. The resulting combination defines the Classtalk platform. This platform provides a full-size environment to experiment with class-oriented programming by combining implicit metaclasses á la Smalltalk and explicit metaclasses á la ObjVlisp. Obviously, these experiments are not limited to the Smalltalk world and will be useful to understand and practice the metaclass concept advocated by modern object-oriented languages such as ObjVlisp and CLOS.
Interactive mathematics textbooks
Authors: Sinclair Robert
Published: November 2005

An interactive mathematics textbook presupposes the existence of a language in which it may be written. We approach the specification of such a language from the point of view of what functions it must perform. Special attention needs to be paid to a clear separation of the roles of the author and the reader. We present examples created with the help of a prototype interactive viewer.
Applying priorities to memory allocation
Authors: Robertz Sven G.
Published: November 2005

A novel approach of applying priorities to memory allocation is presented and it is shown how this can be used to enhance the robustness of real-time applications. The proposed mechanisms can also be used to increase performance of systems with automatic memory management by limiting the amount of garbage collection work.A way of introducing priorities for memory allocation in a Java system without making any changes to the syntax of the language is proposed and this has been implemented in an experimental Java virtual machine and verified in an automatic control application.
Reducing pause time of conservative collectors
Authors: Endo Toshio , Taura Kenjiro
Published: November 2005

This paper describes an incremental conservative garbage collector that significantly reduces pause time of an existing collector by Boehm et al. Like their collector, it is a true conservative collector that does not require compiler cooperation but uses virtual memory primitives (page protection) of operating systems for write barriers. While much successful work has been done on incremental collectors in general, achieving small pause time of the order of a few milliseconds in such uncooperative settings has been challenging. Our collector combines several ideas that bound pause times without introducing significant overheads. They include: (1) bounding the number of dirty (writable) pages during concurrent marking, (2) adaptive repetition of concurrent marking phases, and (3) allocating objects in black (marked) in later stages of a collection. With these techniques, we have achieved the maximum pause time of 2.6--4.5ms for five application benchmarks on 400MHz UltraSPARC processors. They are up to forty times shorter than the basic incremental collector similar to Boehm et al.'s. The overhead (total work time) of our collector is 1.2--53% to the stop-the-world collector and 9% or less to the basic incremental collector.
Heap architectures for concurrent languages using message passing
Authors: Johansson Erik , Sagonas Konstantinos , Wilhelmsson Jesper
Published: November 2005

We discuss alternative heap architectures for languages that rely on automatic memory management and implement concurrency through asynchronous message passing. We describe how interprocess communication and garbage collection happens in each architecture, and extensively discuss the tradeoffs that are involved. In an implementation setting (the Erlang/OTP system) where the rest of the runtime system is unchanged, we present a detailed experimental comparison between these architectures using both synthetic programs and large commercial products as benchmarks.
Using passive object garbage collection algorithms for garbage collection of active objects
Authors: Vardhan Abhay , Agha Gul
Published: November 2005

With the increasing use of active object systems, agents and concurrent object oriented languages like Java, the problem of garbage collection (GC) of unused resources has become more complex. Since active objects are autonomous computational agents, unlike passive object systems the criterion for identifying garbage in active objects cannot be based solely on reachability from a root set. This has led to development of specialized algorithms for GC of active objects. We reduce the problem of GC of active objects to that of passive objects by providing a transformation of the active object reference graph to a passive object reference graph so that if a garbage collector for a passive object system is applied to the transformed graph, precisely those objects are collected which correspond to garbage objects in the original active object reference graph. The transformation technique enables us to reuse the algorithms already developed for passive objects systems. We provide a proof of correctness of the transformation and discuss its cost. An advantage of the transformation is that it can prove valuable for mixed systems of active and passive objects by providing a common approach to GC.
Adaptive caching for demand prepaging
Authors: Kaplan Scott F. , McGeoch Lyle A. , Cole Megan F.
Published: November 2005

Demand prepaging was long ago proposed as a method for taking advantage of high disk bandwidths and avoiding long disk latencies by fetching, at each page fault, not only the demanded page but also other pages predicted to be used soon. Studies performed more than twenty years ago found that demand prepaging would not be generally beneficial. Those studies failed to examine thoroughly the interaction between prepaging and main memory caching. It is unclear how many main memory page frames should be allocated to cache pages that were prepaged but have not yet been referenced. This issue is critical to the efficacy of any demand prepaging policy.In this paper, we examine prepaged allocation and its interaction with two other important demand prepaging parameters: the degree, which is the number of extra pages that may be fetched at each page fault, and the predictor that selects which pages to prepage. The choices for these two parameters, the reference behavior of the workload, and the main memory size all substantially affect the appropriate choice of prepaged allocation. In some situations, demand prepaging cannot provide benefit, as any allocation to prepaged pages will increase page faults, while in other situations, a good choice of allocation will yield a substantial reduction in page faults. We will present a mechanism that dynamically adapts the prepaged allocation on-line, as well as experimental results that show that this mechanism typically reduces page faults by 10 to 40% and sometimes by more than 50%. In those cases where demand prepaging should not be used, the mechanism correctly allocates no space for prepaged pages and thus does not increase the number of page faults. Finally, we will show that prepaging offers substantial benefits over the simpler solution of sing larger pages, which can substantially increase page faults.
Dynamic memory management for programmable devices
Authors: Kumar Sanjeev , Li Kai
Published: November 2005

The paper presents the design and implementation of a novel dynamic memory-management scheme for ESP---a language for programmable devices. The firmware for programmable devices has to be fast and reliable. To support high performance, ESP provides an explicit memory-management interface that can be implemented efficiently. To ensure reliability, ESP uses a model checker to verify memory safety.The VMMC firmware is used as a case study to evaluate the effectiveness of this memory-management scheme. We find that the Spin model checker is able to exhaustively verify memory safety of the firmware; the largest process took 67.6 seconds and used 34.45 Mbytes of memory to verify. We also find that the runtime overhead to maintain the reference counts is small; the additional overhead accounts for 7.35% of the total message processing cost (in the worst case) over a malloc/free interface.
The cache behaviour of large lazy functional programs on stock hardware
Authors: Nethercote Nicholas , Mycroft Alan
Published: November 2005

Lazy functional programs behave differently from imperative programs and these differences extend to cache behaviour. We use hardware counters and a simple yet accurate execution cost model to analyse some large Haskell programs on the x86 architecture. The programs do not interact well with modern processors---L2 cache data miss stalls and branch misprediction stalls account for up to 60% and 32% of execution time respectively. Moreover, the program code exhibits little exploitable instruction-level parallelism.We then use simulation to pinpoint cache misses at the instruction level. With this information we apply prefetching to minimise the cost of write misses, speeding up Haskell programs by up to 22%. We conclude with more ideas for changing the Glasgow Haskell Compiler and its garbage collector to improve the cache performance of large programs.