bluuebunny/crossref_metadata_2025 huggingface dataset:
Relocating machine instructions by currying
Authors: Ramsey Norman
Published: November 2005

Relocation adjusts machine instructions to account for changes in the locations of the instructions themselves or of external symbols to which they refer. Standard linkers implement a finite set of relocation transformations, suitable for a single architecture. These transformations are enumerated, named, and engraved in a machine-dependent object-file format, and linkers must recognize them by name. These names and their associated transformations are an unnecessary source of machine-dependence.The New Jersey Machine-Code Toolkit is an application generator. It helps programmers create applications that manipulate machine code, including linkers. Guided by a short instruction-set specification, the toolkit generates the bit-manipulating code. Instructions are described by
constructors
, which denote functions mapping lists of operands to instructions' binary representations. Any operand can be designated as "relocatable," meaning that the operand's value need not be known at the time the instruction is encoded. For instructions with relocatable operands, the toolkit computes relocating transformations. Tool writers can use the toolkit to create machine-independent software that relocates machine instructions. mld, a retargetable linker built with the toolkit, needs only 20 lines of C code for relocation, and that code is machine-independent.The toolkit discovers relocating transformations by currying encoding functions. An attempt to encode an instruction with a relocatable operand results in the creation of a closure. The closure can be applied when the values of the relocatable operands become known. Currying provides a general, machine-independent method of relocation.Currying rewrites a λ-term into two nested λ-terms. The standard implementation has the first λ allocate a closure and store therein its operands and a pointer to the second λ. Using this strategy in the toolkit means that, when it builds an application, the toolkit generates code for many different inner λ-terms---one for each instruction that uses a relocatable address. Hoisting some of the computation out of the second λ into the first makes many of the second λs identical---a handful are enough for a whole instruction set. This optimization reduces the size of machine-dependent assembly and linking code by 15--20% for the MIPS, SPARC, and PowerPC, and by about 30% for the Pentium. It also makes the second λs equivalent to relocating transformations named in standard object-file formats.
A note on covariance and contravariance unification
Authors: Barrett Myles F. , Giguere Marshall E.
Published: November 2005

Viewing functions with arguments as defining attribute spaces leads to a consistent extension of the conventional object-oriented type system as well as suggesting a more general dispatching strategy which unites the covariant and contravariant views of function subtyping. These views are properties of a function definition, rather than mutually exclusive constraints.
A model for implementing an object-oriented design without language extensions
Authors: Hamilton Jennifer
Published: November 2005

This paper proposes a means of implementing an object-oriented design in programming languages that do not directly support the object-oriented paradigm, without requiring language extensions. The model supports information hiding, dynamic binding, polymorphism and single inheritance through a typeless, dynamic approach similar to that of Smalltalk. Effecient dynamic method binding is achieved through direct lookup method tables constructed using an incremental graph-colouring algorithm. The methodology can be applied to any language that supports data and procedure pointers and dynamic memory allocation.
A translator from C to a λ-calculus representation
Authors: Karr Michael
Published: November 2005

We describe a translator from C to a representation based on the, λ-calculus; the representation can be annotated with execution statistics obtained by running the C program. This tool may be of use in projects investigating the analysis and transformation of programs, particularly those that involve optimization under explicit cost models. The translator may be obtained by contacting the author.
Annealing and data decomposition in VDM
Authors: Goldsack S. J. , Lano K.
Published: November 2005

VDM
++
is a formal specification language derived from VDMSL and incorporating object-oriented structuring based on language extensions which owe much to SmallTalk (though features have been added to cater for specifying reactive real-time systems). Research on the language has been in progress since about 1991[1][2], but it is only recently that papers have begun to be published on the subject[3][4][5].Several more-detailed papers are in preparation. In particular, a paper describing the concept of
annealing
in some detail will be ready shortly.Our attention has recently been drawn to the paper by Jian Lu [6] which describes a process of data decomposition in VDM bearing some relationship to our concept of annealing. The present paper is intended to give an introduction to the annealing concept, and to show how it relates to the work of Jian Lu.
Global computation
Authors: Cardelli Luca
Published: November 2005

Computation over planet-wide structures is hindered by administrative, architectural, and physical constraints. These problems are surmountable, but must be addressed by developing new models of programming and of computation.
ML and beyond
Authors: Harper Robert , Mitchell John C.
Published: November 2005

ML is a successful programming language that reconciles theoretical principles with pragmatic requirements. However, there are many shortcomings of the current language and implementations. This short note outlines some promising directions for future work.
Perspectives on program analysis
Authors: Nielson Flemming
Published: November 2005

To guide the research efforts in the area of program analysis it is necessary to provide a taxonomy of the various approaches (identifying strengths and weaknesses), and to explore the links to programming languages and theoretical computer science.
Programming language semantics
Authors: Riecke Jon G.
Published: November 2005

Programming language semantics focuses on the structure of computation rather than the computability of functions. We review some key ideas in semantics and describe future directions.
Program analysis
Authors: Wilhelm Reinhard
Published: November 2005

Program Analysis is largely based on generic theories that have the potential for toolmaking. Intensive research should go into the still open problems faced by the creators of program analysis generators. To date, the more generic method of abstract interpretation has advantages for toolmaking compared to type inference based and set based analysis methods.
Program adaptation based on program transformation
Authors: Consel Charles
Published: November 2005

Much research effort in program transformation has traditionally been devoted to better compile programs. Key examples include program optimization and program parallelization. Program transformation has sometimes been used in program development to derive implementations from high-level specifications.This position paper advocates another promising application of program transformation:
program adaptation
. That is, the ability for a program to adapt to the context in which it is used. We claim that program adaptation is a key technique in the program development process and is applicable to real size systems.In the following sections, we first explain why program adaptation is important and what this process involves. Then, we discuss how program adaptation can be achieved. Finally, we outline research directions which can contribute to this line of work.
An introduction to the Beetle Forth virtual processor
Authors: Thomas Reuben R.
Published: November 2005

Beetle is a virtual processor designed for the Forth language. It uses a modified, byte-stream code designed for efficient execution which is binary portable between implementations. It has been implemented in C and assembler. The C implementation is completely machine independent with the exception of interactive input and output; the assembler version runs the supplied Forth compiler at up to half the speed of the corresponding native code compiler and generates more compact code. Beetle is designed to be embedded in other programs; a simple debugger has been written to demonstrate this ability. Beetle can be configured to perform bounds checking on all memory references. A standard library is implemented; access to native code routines is also possible, allowing Forth and C programs to call each other.
Re-engineering needs generic programming language technology
Authors: van den Brand Mark , Klint Paul , Verhoef Chris
Published: November 2005

Generic language technology and compiler construction techniques are a prerequisite to build analysis and conversion tools that are needed for the re-engineering of large software systems. We argue that generic language technology is a crucial means to do fundamental re-engineering. Furthermore, we address the issue that the application of compiler construction techniques in re-engineering generates new research questions in the field of compiler construction.
An intelligent backtracking schema in a logic programming environment
Authors: Cicekli Ilyas
Published: November 2005

We present a new method to represent variable bindings in the Warren Abstract Machine (WAM), so that the ages of variable bindings can be easily found using this new representation in our intelligent backtracking schema. The age of a variable bound to a non-variable term is the youngest choice point such that backtracking to that choice point can make that variable an unbound variable again. The procedure backtracking point is the choice point of the procedure currently being executed or the choice point of its first ancestor having a choice point. Variable ages and procedure backtracking points are used in the process of figuring out backtracking points in our intelligent backtracking schema. Our intelligent backtracking schema performs much better than the results of other intelligent backtracking methods in the literature for deterministic programs, and its performance for non-deterministic programs are comparable with their results.
NDC++
Authors: Chen Jiajun , Zheng Guoliang
Published: November 2005

In this paper, we present an approach to extending C++ with the capability of describing concurrent computation. The concurrent object-oriented model we adopt consists of a group of concurrent objects which may have bodies. When a concurrent object is created, its body begins to run. Inter-object communication uses the synchronous message passing and the internal concurrency of object is permitted. Concurrency control is distributed among each method's activation condition in an object. We also provide a policy to transform the classes defined in the extended C++ into C++ classes. The implementation is based on the multithreading and synchronization facilities supported in some multitasking operating systems such as Windows 95.
On the need for predictable floating-point arithmetic in the programming languages Fortran 90 and C/C++
Authors: Verschaeren Dennis , Cuyt Annie , Verdonk Brigitte
Published: November 2005

During the past decade the IEEE 754 standard for binary floating-point arithmetic has been very successful. Many of today's hardware platforms conform to this standard and compilers should make floating-point functionality available to programmers through high-level programming languages. They should also implement certain features of the IEEE 754 standard in software, such as the input and output conversions to and from the internal binary representation of numbers. In this report, a number of Fortran 90 and C/C++ compilers for workstations as well as personal computers will be screened with respect to their IEEE conformance. It will be shown that most of these compilers do not conform to the IEEE standard and that shortcomings are essentially due to their respective programming language standards which lack attention for the need of predictable floating-point arithmetic.
Programming the Loral LDF 100 dataflow machine
Authors: Kaplan I
Published: November 2005

Multiprocess programs date back to the earliest multiuser operating systems. Recently this venerable programming methodology has been adapted to programming computer systems that consist of multiple processors. In this paper we discuss the large grain dataflow programming model and its strengths compared to the process model.Unlike the process model, the dataflow model was developed for parallel processors. Using dataflow it can be shown that a program (e.g., a graph) will be free from race conditions (deterministic). Large grain dataflow gives the programmer a framework that can be used in program design. Large grain dataflow programming is discussed in the context of the LDF 100, a distributed memory parallel processor.
Computer User Support degree program
Authors: Beisse Fred
Published: November 2005

In a previous 3C ONLINE article,
"Degree Program Planned in Computer User Support"
[1], a new two-year professional/technical degree program was described which would train students for the computer user support job market. The Computer User Support (CUS) degree was launched at Lane Community College during the 1995-96 year, and we will graduate our first class of approximately 26 students in June, 1997.
Automatic inline allocation of objects
Authors: Dolby Julian
Published: November 2005

Object-oriented languages like Java and Smalltalk provide a uniform object model that simplifies programming by providing a consistent, abstract model of object behavior. But direct implementations introduce overhead, removal of which requires aggressive implementation techniques (e.g. type inference, function specialization); in this paper, we introduce
object inlining
, an optimization that automatically inline allocates objects within containers (as is done by hand in C++) within a uniform model. We present our technique, which includes novel program analyses that track how inlinable objects are used throughout the program. We evaluated object inlining on several object-oriented benchmarks. It produces performance up to three times as fast as a dynamic model without inlining and roughly equal to that of manually-inlined codes.
Reverse interpretation + mutation analysis = automatic retargeting
Authors: Collberg Christian S.
Published: November 2005

There are three popular methods for constructing highly retargetable compilers: (1) the compiler emits abstract machine code which is interpreted at run-time, (2) the compiler emits C code which is subsequently compiled to machine code by the native C compiler, or (3) the compiler's code-generator is generated by a back-end generator from a formal machine description produced by the compiler writer.These methods incur high costs at run-time, compile-time, or compiler-construction time, respectively.In this paper we will describe a novel method which promises to significantly reduce the effort required to retarget a compiler to a new architecture, while at the same time producing fast and effective compilers. The basic idea is to use the native C compiler at
compiler construction time
to discover architectural features of the new architecture. From this information a formal machine description is produced. Given this machine description, a native code-generator can be generated by a back-end generator such as BEG or burg.A prototype
Automatic Architecture Discovery Unit
has been implemented. The current version is general enough to produce machine descriptions for the integer instruction sets of common RISC and CISC architectures such as the Sun SPARC, Digital Alpha, MIPS, DEC VAX, and Intel x86. The tool is completely automatic and requires minimal input from the user: principally, the user needs to provide the internet address of the target machine and the command-lines by which the C compiler, assembler, and linker are invoked.
Exploiting hardware performance counters with flow and context sensitive profiling
Authors: Ammons Glenn , Ball Thomas , Larus James R.
Published: November 2005

A program profile attributes run-time costs to portions of a program's execution. Most profiling systems suffer from two major deficiencies: first, they only apportion simple metrics, such as execution frequency or elapsed time to static, syntactic units, such as procedures or statements; second, they aggressively reduce the volume of information collected and reported, although aggregation can hide striking differences in program behavior.This paper addresses both concerns by exploiting the hardware counters available in most modern processors and by incorporating two concepts from data flow analysis--flow and context sensitivity--to report more context for measurements. This paper extends our previous work on efficient path profiling to flow sensitive profiling, which associates hardware performance metrics with a path through a procedure. In addition, it describes a data structure, the calling context tree, that efficiently captures calling contexts for procedure-level measurements.Our measurements show that the SPEC95 benchmarks execute a small number (3--28) of hot paths that account for 9--98% of their L1 data cache misses. Moreover, these hot paths are concentrated in a few routines, which have complex dynamic behavior.
Interprocedural dataflow analysis in an executable optimizer
Authors: Goodwin David W.
Published: November 2005

Interprocedural dataflow information enables link-time and post-link-time optimizers to perform analyses and code transformations that are not possible in a traditional compiler. This paper describes the interprocedural dataflow analysis techniques used by Spike, a post-linktime optimizer for Alpha/NT executables. Spike uses dataflow analysis to summarize the register definitions, uses, and kills that occur external to each routine, allowing Spike to perform a variety of optimizations that require interprocedural dataflow information. Because Spike is designed to optimize large PC applications, the time required to perform interprocedural dataflow analysis could potentially be unacceptably long, limiting Spike's effectiveness and applicability. To decrease dataflow analysis time, Spike uses a compact representation of a program's intraprocedural and interprocedural control flow that efficiently summarizes the register definitions and uses that occur in the program. Experimental results are presented for the SPEC95 integer benchmarks and eight large PC applications. The results show that the compact representation allows Spike to compute interprocedural dataflow information in less than 2 seconds for each of the SPEC95 integer benchmarks. Even for the largest PC application containing over 1.7 million instructions in 340 thousand basic blocks, interprocedural dataflow analysis requires just 12 seconds.
Aggressive inlining
Authors: Ayers Andrew , Schooler Richard , Gottlieb Robert
Published: November 2005

Existing research understates the benefits that can be obtained from inlining and cloning, especially when guided by profile information. Our implementation of inlining and cloning yields excellent results on average and very rarely lowers performance. We believe our good results can be explained by a number of factors: inlining at the intermediate-code level removes most technical restrictions on what can be inlined; the ability to inline across files and incorporate profile information enables us to choose better inline candidates; a high-quality back end can exploit the scheduling and register allocation opportunities presented by larger subroutines; an aggressive processor architecture benefits from more predictable branch behavior; and a large instruction cache mitigates the impact of code expansion. We describe the often dramatic impact of our inlining and cloning on performance: for example, the implementations of our inlining and cloning algorithms in the HP-UX 10.20 compilers boost SPECint95 performance on a PA8000-based workstation by a factor of 1.32.
Module-sensitive program specialisation
Authors: Dussart Dirk , Heldal Rogardt , Hughes John
Published: November 2005

We present an approach for specialising large programs, such as programs consisting of several modules, or libraries. This approach is based on the idea of using a compiler generator (cogen) for creating generating extensions. Generating extensions are specialisers specialised with respect to some input program. When run on some input data the generating extension produces a specialised version of the input program. Here we use the cogen to tailor modules for specialisation. This happens once and for all, independently of all other modules. The resulting module can then be used as a building block for generating extensions for complete programs, in much the same way as the original modules can be put together into complete programs. The result of running the final generating extension is a collection of residual modules, with a module structure derived from the original program.
Two for the price of one
Authors: Sperber Michael , Thiemann Peter
Published: November 2005

One of the flagship applications of partial evaluation is compilation and compiler generation. However, partial evaluation is usually expressed as a source-to-source transformation for high-level languages, whereas realistic compilers produce object code.We close this gap by composing a partial evaluator with a compiler by automatic means. Our work is a successful application of several meta-computation techniques to build the system, both in theory and in practice. The composition is an application of deforestation or fusion.The result is a run-time code generation system built from existing components. Its applications are numerous. For example, it allows the language designer to perform interpreter-based experiments with a source-to-source version of the partial evaluator before building a realistic compiler which generates object code automatically.
Automatic verification of pointer programs using monadic second-order logic
Authors: Jensen Jakob L. , Jørgensen Michael E. , Schwartzbach Michael I. , Klarlund Nils
Published: November 2005

We present a technique for automatic verification of pointer programs based on a decision procedure for the monadic second-order logic on finite strings.We are concerned with a while-fragment of Pascal, which includes recursively-defined pointer structures but excludes pointer arithmetic.We define a logic of stores with interesting basic predicates such as pointer equality, tests for nil pointers, and garbage cells, as well as reachability along pointers.We present a complete decision procedure for Hoare triples based on this logic over loop-free code. Combined with explicit loop invariants, the decision procedure allows us to answer surprisingly detailed questions about small but non-trivial programs. If a program fails to satisfy a certain property, then we can automatically supply an initial store that provides a counterexample.Our technique had been fully and efficiently implemented for linear linked lists, and it extends in principle to tree structures. The resulting system can be used to verify extensive properties of smaller pointer programs and could be particularly useful in a teaching environment.
Register promotion in C programs
Authors: Lu John , Cooper Keith D.
Published: November 2005

The combination of pointers and pointer arithmetic in C makes the task of improving C programs somewhat more difficult than improving programs written in simpler languages like Fortran. While much work has been published that focuses on the analysis of pointers, little has appeared that uses the results of such analysis to improve the code compiled for C. This paper examines the problem of register promotion in C and presents experimental results showing that it can have dramatic effects on memory traffic.
Functional programming with graphs
Authors: Erwig Martin
Published: November 2005

Graph algorithms expressed in functional languages often suffer from their inherited imperative, state-based style. In particular, this impedes formal program manipulation. We show how to model persistent graphs in functional languages by graph constructors. This provides a decompositional view of graphs which is very close to that of data types and leads to a "more fictional" formulation of graph algorithms. Graph constructors enable the definition of general fold operations for graphs. We present a promotion theorem for one of these folds that allows program fusion and the elimination of intermediate results. Fusion is not restricted to the elimination of tree-like structures, and we prove another theorem that facilitates the elimination of intermediate graphs. We describe an ML-implementation of persistent graphs which efficiently supports the presented fold operators. For example, depth-first-search expressed by a fold over a functional graph has the same complexity as the corresponding imperative algorithm.
Flexible representation analysis
Authors: Shao Zhong
Published: November 2005

Statically typed languages with Hindley-Milner polymorphism have long been compiled using inefficient and fully boxed data representations. Recently, several new compilation methods have been proposed to support more efficient and unboxed multi-word representations. Unfortunately, none of these techniques is fully satisfactory. For example, Leroy's coercion-based approach does not handle recursive data types and mutable types well. The type-passing approach (proposed by Harper and Morrisett) handles all data objects, but it involves extensive runtime type analysis and code manipulations.This paper presents a new
flexible representation analysis
technique that combines the best of both approaches. Our new scheme supports unboxed representations for recursive and mutable types, yet it only requires little runtime type analysis. In fact, we show that there is a continuum of possibilities between the coercion-based approach and the type-passing approach. By varying the amount of boxing and the type information passed at runtime, a compiler can freely explore any point in the continuum---choosing from a wide range of representation strategies based on practical concerns. Finally, our new scheme also easily extends to handle type abstractions across ML-like higher-order modules.
A bounds inference method for vector-based memoization
Authors: Chin Wei-Ngan , Hagiya Masami
Published: November 2005

The dynamic-sized tabulation method can be used to eliminate redundant calls for certain classes of recursive programs. An innovative aspect of the method is the use of
lambda abstractions
that may subsequently be converted to
bounded vectors
, in order to share redundant calls via vector lookup.To facilitate this conversion to vector form, we propose a new inference method to conservatively determine the bounds for arithmetic parameters of recursive functions. Suitable techniques for inferring the safe bounds of these parameters are introduced, together with supporting transformations. The resulting method can obtain efficient vector-based programs without the need for run-time bounds checking.
On global dynamics of optimal graph reduction
Authors: Lawall Julia L. , Mairson Harry G.
Published: November 2005

Optimal graph reduction technology for the λ-calculus, as developed by Lamping, with modifications by Asperti, Gonthier, Abadl, and Lévy, has a well-understood
local dynamics
based on a standard menagerie of reduction rules, as well as a
global context
semantics based on Girard's geometry of interaction. However, the
global dynamics
of graph reduction has not been subject to careful investigation. In particular, graphs lose their structural resemblance to λ-terms after only a few graph reduction steps, and little is known about
graph
reduction strategies that maintain efficiency or structure. While the context semantics provides global information about the computation, its use as part of a reduction strategy seems computationally infeasible. We propose a tractable graph reduction strategy that preserves computationally relevant global structure, and allows us to efficiently bound the computational resources needed to implement optimal reduction.A simple canonical representation for graphs is introduced that we call
fan-normal form
. This normal form allows us to reduce graphs based on efficient identification of β-redexes, rather than being guided by lower-level search for interacting nodes. In addition and perhaps more important, the fan-normal form facilitates a complexity analysis of graph reductions, showing that the number of fan interactions is essentially bounded by a polynomial in the number of unique Lévy labels generated during a labelled reduction. This global analysis of the finitary dynamics of optimal reduction is the first demonstration that a reasonable implementation-independent cost model for the λ-calculus is in fact realized by Lamping's abstract algorithm. It remains to be seen whether similar claims can be made about so-called
bookkeeping
for fan interactions.
Self-applicable partial evaluation for the pi-calculus
Authors: Gengler Marc , Martel Matthieu
Published: November 2005

In this paper, we are interested in self-applicable partial evaluation for the pi-calculus, a language which models the concurrent behavior of communicating processes. We use the classic three-steps methodology. First, we write a meta-interpreter for the language. Second, we introduce an abstract analysis that determines which operations (communications) can be executed at compile-time. The notion of well-annotatedness of terms is defined. Finally, we exhibit the self-applicable partial evaluator which is applied to well-annotated terms, and we prove its correctness with respect to the interpreter. This approach is compatible with Futamura's projections. Proofs of correctness are baaed on the notion of weak reduction equivalence.
A functional approach to type constraints of generic definitions
Authors: Kim Myung Ho
Published: November 2005

This paper addresses a frequently encountered problem related to type constraints in many contemporary strongly typed object-oriented languages. The problem is that type parameters are often more strongly constrained than is actually needed. As a consequence, reusability of the whole generic definition is limited even when those constraints are only for a portion of the operations it provides. A useful programming idiom to remedy this problem is proposed. It mitigates the problem by moving some of type constraints from the generic definitions to the clients. The only tool required to aid the idiom is the functional parameter.
The F programming language
Authors: Frisbie Ralph , Hendrickson Richard , Metcalf Michael
Published: November 2005

We introduce a new programming language, F, that is intended for the teaching of modern concepts. Strong typing and a strict syntax facilitate teaching and learning. The language is available in optimized form for all major platforms and some teaching experience has already been gained.
Maintaining the consistency of class libraries during their evolution
Authors: Mezini Mira
Published: November 2005

Two important problems of object-oriented reuse are the propagation of design and implementation specifics of the base software to the inheritors, and the protection of the inheritors against changes in the base software. In this paper, we argue that the simple inheritance rules of existing object-oriented languages are not sufficient for properly dealing with these problems. In the proposal presented in this paper, programmers are enabled to make metalevel declarations of the internal protocols and dependencies of their classes. Additionally, changes of the base module are automatically monitored to filter out information about the alterations that may invalidate already existing inheritors. Based on these informations, the subclassing semantics is adjusted such that the maintenance of the base module properties and the protection of the inheritor is ensured during their integration, In this way, language support is provided for keeping the behavior of reusable software consistent during its evolution.
Reuse of algorithms
Authors: Weihe Karsten
Published: November 2005

This paper is about reusable, efficient implementations of complex algorithms and their integration into software packages. It seems that this problem is not yetwell understood, and that it is not at all clear how object-oriented and other approaches may contribute to a solution. We analyze the problem and try to reduce it to a few key design goals. Moreover, we discuss various existing approaches in light of these goals, and we briefly report experiences with experimental case studies, in which these goals were rigorously addressed.
Adding type parameterization to the Java language
Authors: Agesen Ole , Freund Stephen N. , Mitchell John C.
Published: November 2005

Although the Java programming language has achieved widespread acceptance, one feature that seems sorely missed is the ability to use type parameters (as in Ada generics, C++ templates, and ML polymorphic functions or data types) to allow a general concept to be instantiated to one or more specific types. In this paper, we propose parameterized classes and interfaces in which the type parameter may be constrained to either implement a given interface or extend a given class. This design allows the body of a parameterized class to refer to methods on objects of the parameter type, without introducing any new type relations into the language. We show that these Java extensions may be implemented by expanding parameterized classes at class load time, without any extension or modification to existing Java bytecode, verifier or bytecode interpreter.
Parasitic methods
Authors: Boyland John , Castagna Giuseppe
Published: November 2005

In an object-oriented programming language, method selection is (usually) done at run-time using the class of the receiver. Some object-oriented languages (such as CLOS) have
multi-methods
which comprise several methods selected on the basis of the runtime classes of all the parameters, not just the receiver. Multi-methods permit intuitive and typesafe definition of binary methods such as structural equality, set inclusion and matrix multiplication, just to name a few. Java as currently defined does not support multimethods. This paper defines a simple extension to Java that enables the writing of "encapsulated" multi-methods through the use of
parasitic
methods, methods that "attach" themselves to other methods. Encapsulated multi-methods avoid some of the modularity problems that, arise with fully general multi-methods. Furthermore, this. extension yields for free both covariant and contravariant specialization of methods (besides Java's current invariant specialization).Programs using this extension. can be translated automatically at the source level into programs that do not; they are modular, type-safe, and allow separate compilation.
The design and performance of a real-time CORBA event service
Authors: Harrison Timothy H. , Levine David L. , Schmidt Douglas C.
Published: November 2005

The CORBA Event Service provides a flexible model for asynchronous communication among objects. However, the standard CORBA Event Service specification lacks important features required by real-time applications. For instance, operational flight programs for fighter aircraft have complex real-time processing requirements. This paper describes the design and performance of an object-oriented, real-time implementation of the GORBA Event Service that is designed to meet these requirements.This paper makes three contributions to the design and performance measurement of object-oriented real-time systems. First, it illustrates how to extend the CORBA Event Service so that it is suitable for real-time systems. These extensions support periodic rate-based event processing and efficient event filtering and correlation. Second, it describes how to develop object-oriented event dispatching and scheduling mechanisms that can provide real-time guarantees. Finally, the paper presents benchmarks that demonstrate the performance tradeoffs of alternative concurrent dispatching mechanisms for real-time Event Services.
Tiling design patterns—a case study using the interpreter pattern
Authors: Lorenz David H.
Published: November 2005

This paper explains how patterns can be used to describe the implementation of other patterns. It is demonstrated how certain design patterns can describe their own design. This is a fundamental reflexive relationship in pattern relationships. The process of assembling patterns by other patterns is named pattern tiling. Tiling enables us to interweave simple understood concepts of patterns into their complex real-life implementation. Several pattern tilings for the Interpreter design pattern are illustrated.
An open implementation analysis and design for lightweight threads
Authors: Haines Matthew
Published: November 2005

Open Implementation Analysis and Design (OIA/D) has been introduced as a design methodology for object-oriented software systems, and in particular for substrate software. In this paper we detail our experiences with using OIA/D to design and implement a common substrate component for parallel language runtime systems: a lightweight threads package. We show how existing thread packages employ a "black-box" design, hiding crucial design decisions that drastically reduce their ability to be re-used. We detail these design decisions (dilemmas) and show how an implementation based on OIA/D principles results in a thread package that is flexible, efficient, portable, and re-usable.
Migrating relational data to an ODBMS
Authors: Oler Jon , Lindstrom Gary , Critchlow Terence
Published: November 2005

The growing maturity of ODBMS technology is causing many enterprises to consider migrating relational databases to ODBMS's. While data remapping is relatively straightforward in most cases, greater challenges lie in economically and non-invasively adapting legacy application software. We report on a genetics laboratory database migration experiment, which was facilitated by both organization of the relational data in object-like form and a C++ framework designed to insulate application code from relational artifacts. Although this experiment was largely successful, we discovered to our surprise that the framework failed to encapsulate three subtle aspects of the relational implementation, thereby "contaminating" application code. We analyze the underlying issues, and offer cautionary guidance to future migrators.
Class hierarchy specialization
Authors: Tip Frank , Sweeney Peter F.
Published: November 2005

Class libraries are generally designed with an emphasis on versatility and extensibility. Applications that use a library typically exercise only part of the library's functionality. As a result, objects created by the application may contain unused members. We present an algorithm that
specializes
a class hierarchy with respect to its usage in a program
P
. That is, the algorithm analyzes the member access patterns for
P
's variables, and creates distinct classes for variables that access different members. Class hierarchy specialization reduces object size, and is hence primarily a space optimization. However, execution time may also be reduced through reduced object creation/destruction time, and caching/paging effects.
Declarative specialization of object-oriented programs
Authors: Volanschi Eugen N. , Consel Charles , Muller Gilles , Cowan Crispin
Published: November 2005

Designing and implementing generic software components is encouraged by languages such as object-oriented ones and commonly advocated in most application areas. Generic software components have many advantages among which the most important is reusability. However, it comes at a price: genericity often incurs a loss of efficiency.This paper presents an approach aimed at reconciling genericity and efficiency. To do so, we introduce declarations to the Java language to enable a programmer to specify how generic programs should be specialized for a particular usage pattern. Our approach has been implemented as a compiler from our extended language into standard Java.
The OT idea life-cycle (panel)
Authors: Hill Laura , Anderson Bruce , Goldberg Adele , Kiczales Gregor , Scott Colin , Tyson Kevin
Published: November 2005

Over the past years, the Object Technology community has seen the birth of a number of new technology ideas that have changed the way we do computing. These ideas have affected compiler design, analysis approaches, project management techniques, user interface design, deployment strategies and implementation tactics. But where do these ideas come from? And how do they evolve? Do they address the needs as specified by members of the Object Community? Is there a way we can nurture the introduction and assimilation of these ideas to and by the community at large? And what are the market forces that bend ideas to their will. This panel will look at new ideas in Object Technology from a variety of perspectives and will attempt to get to the heart of the way that we, as technologists, create, buy, sell and grow ideas.
Query-based debugging of object-oriented programs
Authors: Lencevicius Raimondas , Hölzle Urs , Singh Ambuj K.
Published: November 2005

Object relationships in modem software systems are becoming increasingly numerous and complex. Programmers who try to find violations of such relationships need new tools that allow them to explore objects in a large system more efficiently. Many existing debuggers present only a low-level, one-object-at-a-time view of objects and their relationships. We propose a new solution to overcome these problems: query-based debugging. The implementation of the query-based debugger described here offers programmers an effective query tool that allows efficient searching of large object spaces and quick verification of complex relationships. Even for programs that have large numbers of objects, the debugger achieves interactive response times for common queries by using a combination of fast searching primitives, query optimization, and incremental result delivery.
Back to the future
Authors: Ingalls Dan , Kaehler Ted , Maloney John , Wallace Scott , Kay Alan
Published: November 2005

Squeak is an open, highly-portable Smalltalk implementation whose virtual machine is written entirely in Smalltalk, making it easy to. debug, analyze, and change. To achieve practical performance, a translator produces an equivalent C program whose performance is comparable to commercial Smalltalks.Other noteworthy aspects of Squeak include: a compact object format that typically requires only a single word of overhead per object; a simple yet efficient incremental garbage collector for 32-bit direct pointers; efficient bulk-mutation of objects; extensions of BitBlt to handle color of any depth and anti-aliased image rotation and scaling; and real-time sound and music synthesis written entirely in Smalltalk.
Constraint diagrams
Authors: Kent Stuart
Published: November 2005

A new visual notation is proposed for precisely expressing constraints on object-oriented models, as an alternative to mathematical logic notation used in methods such as Syntropy and Catalysis. The notation is potentially intuitive, expressive, integrates well with existing visual notations, and has a clear and unambiguous semantics. It is reminiscent of informal diagrams used by mathematicians for illustrating relations, and borrows much from Venn diagrams. It may be viewed as a generalization of instance diagrams.
Beyond the hype (panel)
Authors: Fraser Steven , Beck Kent , Booch Grady , Coplien Jim , Johnson Ralph , Opdyke Bill
Published: November 2005

Patterns and frameworks are two approaches to the development of both new and evolving software systems. An implicit hypothesis is that "discovery costs" are reduced by leveraging knowledge previously collected, analyzed, organized, and packaged. "Discovery costs" (or "getting started" costs) include both the costs of understanding the problem to be solved and the cost of understanding the tools, methods, existing software, etc. For large, multi-year development projects in industries such as defense or telecommunications, discovery costs can dominate the overall cost (and risk) of software development.This panel will share its experience and perspectives with the audience with a discussion initiated by the following questions:• Have patterns and frameworks really delivered on their claims for reducing discovery costs? Can current best-practices be characterized as meaningful or marginal (what are the measures)?• What are the discovery cost factors where frameworks and patterns appear to deliver the biggest bang for the buck?• While mature pattern languages and frameworks may reduce the learning curve, they do not, eliminate it. How much of a learning curve is required to develop a sufficient shared context with the authors of a set of patterns or a framework?
Call graph construction in object-oriented languages
Authors: Grove David , DeFouw Greg , Dean Jeffrey , Chambers Craig
Published: November 2005

Interprocedural analyses enable optimizing compilers to more precisely model the effects of non-inlined procedure calls, potentially resulting in substantial increases in application performance. Applying interprocedural analysis to programs written in object-oriented or functional languages is complicated by the difficulty of constructing an accurate program call graph. This paper presents a parameterized algorithmic framework for call graph construction in the presence of message sends and/or first class functions. We use this framework to describe and to implement a number of well-known and new algorithms. We then empirically assess these algorithms by applying them to a suite of medium-sized programs written in Cecil and Java, reporting on the relative cost of the analyses, the relative precision of the constructed call graphs, and the impact of this precision on the effectiveness of a number of interprocedural optimizations.
Garbage collecting the world
Authors: Hudson Richard L. , Morrison Ron , Moss J. Eliot B. , Munro David S.
Published: November 2005

A new garbage collection algorithm for distributed object systems, called DMOS (Distributed. Mature Object Space), is presented. It is derived from two previous algorithms, MOS (Mature Object Space), sometimes called the train algorithm, and PMOS (Persistent Mature Object Space). The contribution of DMOS is that it provides the following unique combination of properties for a distributed collector: safety, completeness, non-disruptiveness, incrementality, and scalability. Furthermore, the DMOS collector is non-blocking and does not use global tracing.
Dynamic pointer alignment
Authors: Zhang Xingbin , Chien Andrew A.
Published: November 2005

Loop tiling and communication optimization, such as message pipelining and aggregation, can achieve optimized and robust memory performance by proactively managing storage and data movement. In this paper, we generalize these techniques to pointer-based data structures (PBDSs). Our approach,
dynamic pointer alignment
(DPA), has two components. The compiler decomposes a program into non-blocking threads that operate on specific pointers and labels thread creation sites with their corresponding pointers. At runtime, an explicit mapping from pointers to dependent threads is updated at thread creation and is used to dynamically schedule both threads and communication, such that threads using the same objects execute together, communication overlaps with local work, and messages are aggregated. We have implemented DPA to optimize remote reads to global PBDSs on parallel machines. Our empirical results on the force computation phases of two applications that use sophisticated PBDSs,
Barnes-Hut
and FMM, show that DPA achieves good absolute performance and speedups by enabling tiling and communication optimization on the CRAY T3D.