bluuebunny/crossref_metadata_2025 huggingface dataset:
Programming languages as operating systems (
or
revenge of the son of the lisp machine)
Authors: Flatt Matthew , Findler Robert Bruce , Krishnamurthi Shriram , Felleisen Matthias
Published: November 2005

The MrEd virtual machine serves both as the implementation platform for the DrScheme programming environment, and as the underlying Scheme engine for executing expressions and programs entered into DrScheme's read-eval-print loop. We describe the key elements of the MrEd virtual machine for building a programming environment, and we step through the implementation of a miniature version of DrScheme in MrEd. More generally, we show how MrEd defines a high-level operating system for graphical programs.
Haskell and XML
Authors: Wallace Malcolm , Runciman Colin
Published: November 2005

We present two complementary approaches to writing XML document-processing applications in a functional language.In the first approach, the generic tree structure of XML documents is used as the basis for the design of a library of combinators for generic processing: selection, generation, and transformation of XML trees.The second approach is to use a type-translation framework for treating XML document type definitions (DTDs) as declarations of algebraic data types, and a derivation of the corresponding functions for reading and writing documents as typed values in Haskell.
Type inference with rank 1 polymorphism for type-directed compilation of ML
Authors: Ohori Atsushi , Yoshida Nobuaki
Published: November 2005

This paper defines an extended polymorphic type system for an ML-style programming language, and develops a sound and complete type inference algorithm. Different frdm the conventional ML type discipline, the proposed type system allows full
rank 1 polymorphism
, where polymorphic types can appear in other types such as product types, disjoint union types and range types of function types. Because of this feature, the proposed type system significantly reduces the value-only restriction of polymorphism, which is currently adopted in most of ML-style impure languages. It also serves as a basis for efficient implementation of type-directed compilation of polymorphism. The extended type system achieves more efficient type inference algorithm, and it also contributes to develop more efficient type-passing implementation of polymorphism. We show that the conventional ML polymorphism sometimes introduces exponential overhead both at compile-time elaboration and run-time type-passing execution, and that these problems can be eliminated by our type inference system. Compared with a more powerful rank 2 type inference systems based on semi-unification, the proposed type inference algorithm infers a most general type for any typable expression by using the conventional first-order unification, and it is therefore easily adopted in existing implementation of ML family of languages.
Type dispatch for named hierarchical types
Authors: Glew Neal
Published: November 2005

Type dispatch constructs are an important feature of many programming languages. Scheme has predicates for testing the runtime type of a value. Java has a class cast expression and a try statement for switching on an exception's class. Crucial to these mechanisms, in typed languages, is type refinement: The static type system will use type dispatch to refine types in successful branches. Considerable previous work has addressed type case constructs for structural type systems without subtyping, but these do not extend to named type systems with subtyping, as is common in object oriented languages. Previous work on type dispatch in named type systems with subtyping has not addressed its implementation formally.This paper describes a number of type dispatch constructs that share a common theme: class cast and class case constructs in object oriented languages, ML style exceptions, hierarchical extensible sums, and multimethods. I describe a unifying mechanism,
tagging
, that abstracts the operation of these constructs, and I formalise a small tagging language. After discussing how to implement the tagging language, I present a typed language without type dispatch primitives, and a give a formal translation from the tagging language.
Principals in programming languages
Authors: Zdancewic Steve , Grossman Dan , Morrisett Greg
Published: November 2005

Programs are often structured around the idea that different pieces of code comprise distinct
principals
, each with a view of its environment. Typical examples include the modules of a large program, a host and its clients, or a collection of interactive agents.In this paper, we formalize this notion of principal in the programming language itself. The result is a language in which intuitive statements such as, "the client must call open to obtain a file handle," can be phrased and proven formally.We add principals to variants of the simply-typed λ-calculus and show how we can track the code corresponding to each principal throughout evaluation. This multiagent calculus yields syntactic proofs of some type abstraction properties that traditionally require semantic arguments.
Flexible type analysis
Authors: Crary Karl , Weirich Stephanie
Published: November 2005

Run-time type dispatch enables a variety of advanced optimization techniques for polymorphic languages, including tag-free garbage collection, unboxed function arguments, and flattened data structures. However, modern type-preserving compilers transform types between stages of compilation, making type dispatch prohibitively complex at low levels of typed compilation. It is crucial therefore for type analysis at these low levels to refer to the types of previous stages. Unfortunately, no current intermediate language supports this facility.To fill this gap, we present the language LX, which provides a rich language of type constructors supporting type analysis (possibly of previous-stage types) as a programming idiom. This language is quite flexible, supporting a variety of other applications such as analysis of quantified types, analysis with incomplete type information, and type classes. We also show that LX is compatible with a type-erasure semantics.
Typer inference builds a short cut to deforestation
Authors: Chitil Olaf
Published: November 2005

Deforestation optimises a functional program by transforming it into another one that does not create certain intermediate data structures. Short cut deforestation is a deforestation method which is based on a single, local transformation rule. In return, short cut deforestation expects both producer and consumer of the intermediate structure in a certain form. Warm fusion wan proposed to automatically transform functions into this form. Unfortunately, it is costly and hard to implement. Starting from the fact that short cut deforestation is based on a parametricity theorem of the second-order typed λ-calculus, we show how the required form of a list producer can be derived by the use of type inference. Typability for the second-order typed λ-calculus is undecidable. However, we present a linear-time algorithm that solves a partial type inference problem and that, together with controlled inlining and polymorphic type instantiation, suffices for deforestation. The resulting new short cut deforestation algorithm is efficient and removes more intermediate lists than the original.
Featherweight Java
Authors: Igarashi Atshushi , Pierce Benjamin , Wadler Philip
Published: November 2005

Several recent studies have introduced lightweight versions of Java: reduced languages in which complex features like threads and reflection are dropped to enable rigorous arguments about key properties such as type safety. We carry this process a step further, omitting almost all features of the full language (including interfaces and even assignment) to obtain a small calculus, Featherweight Java, for which rigorous proofs are not only possible but easy.

Featherweight Java bears a similar relation to full Java as the lambda-calculus does to languages such as ML and Haskell. It offers a similar computational “feel,” providing classes, methods, fields, inheritance, and dynamic typecasts, with a semantics closely following Java's. A proof of type safety for Featherweight Java thus illustrates many of the interesting features of a safety proof for the full language, while remaining pleasingly compact. The syntax, type rules, and operational semantics of Featherweight Java fit on one page, making it easier to understand the consequences of extensions and variations.

As an illustration of its utility in this regard, we extend Featherweight Java with
generic classes
in the style of GJ (Bracha, Odersky, Stoutamire, and Wadler) and sketch a proof of type safety. The extended system formalizes for the first time some of the key features of GJ.
Correspondence polymorphism for object-oriented languages
Authors: Rinat Ran , Magidor Menachem , Smith Scott F.
Published: November 2005

In this paper we propose a new form of polymorphism for object-oriented languages, called
correspondence polymorphism
. It lies in a different dimension than either parametric or subtype polymorphism. In correspondence polymorphism, some methods are declared to correspond to other methods, via a
correspondence relation
. With this relation, it is possible to reuse non-generic code in various type contexts—not necessarily subtyping or matching contexts—without having to plan ahead for this reuse. Correspondence polymorphism has advantages over other expressive object type systems in that programmer-declared types still may be simple, first-order types that are easily understood. We define a simple language LCP that reflects these new ideas, illustrating its behavior with multiple examples. We present formal type rules and an operational semantics for LCP, and establish soundness of the type system with respect to reduction.
An efficient meta-lock for implementing ubiquitous synchronization
Authors: Agesen Ole , Detlefs David , Garthwaite Alex , Knippel Ross , Ramakrishna Y. S. , White Derek
Published: November 2005

Programs written in concurrent object-oriented languages, especially ones that employ thread-safe reusable class libraries, can execute synchronization operations (lock, notify, etc.) at an amazing rate. Unless implemented with utmost care, synchronization can become a performance bottleneck. Furthermore, in languages where every object may have its own monitor, per-object space overhead must be minimized. To address these concerns, we have developed a meta-lock to mediate access to synchronization data. The meta-lock is fast (lock + unlock executes in 11 SPARC™ architecture instructions), compact (uses only two bits of space), robust under contention (no busy-waiting), and flexible (supports a variety of higher-level synchronization operations). We have validated the meta-lock with an implementation of the synchronization operations in a high-performance product-quality Java™ virtual machine and report performance data for several large programs.
A study of locking objects with bimodal fields
Authors: Onodera Tamiya , Kawachiya Kiyokuni
Published: November 2005

Object locking can be efficiently implemented by bimodal use of a field reserved in an object. The field is used as a lightweight lock in one mode, while it holds a reference to a heavyweight lock in the other mode. A bimodal locking algorithm recently proposed for Java achieves the highest performance in the absence of contention, and is still fast enough when contention occurs.

However, mode transitions inherent in bimodal locking have not yet been fully considered. The algorithm requires busy-wait in the transition from the light mode (inflation), and does not make the reverse transition (deflation) at all.

We propose a new algorithm that allows both inflation without busy-wait and deflation, but still maintains an almost maximum level of performance in the absence of contention. We also present statistics on the synchronization behavior of real multithreaded Java programs, which indicate that busy-wait in inflation and absence of deflation can be problematic in terms of robustness and performance. Actually, an implementation of our algorithm shows increased robustness, and achieves performance improvements of up to 13.1% in server-oriented benchmarks.
Reducing transfer delay using Java class file splitting and prefetching
Authors: Calder Brad , Krintz Chandra , Hölzle Urs
Published: November 2005

The proliferation of the Internet is fueling the development of mobile computing environments in which mobile code is executed on remote sites. In such environments, the end user must often wait while the mobile program is transferred from the server to the client where it executes. This downloading can create significant delays, hurting the interactive experience of users.

We propose Java class file splitting and class file prefetching optimizations in order to reduce transfer delay. Class file splitting moves the infrequently used part of a class file into a corresponding cold class file to reduce the number of bytes transferred. Java class file prefetching is used to overlap program transfer delays with program execution. Our splitting and prefetching compiler optimizations do not require any change to the Java Virtual Machine, and thus can be used with existing Java implementations. Class file splitting reduces the startup time for Java programs by 10% on average, and class file splitting used with prefetching reduces the overall transfer delay encountered during a mobile program's execution by 25% to 30% on average.
A performance evaluation of the mobile agent paradigm
Authors: Hagimont Daniel , Ismail L.
Published: November 2005

This paper presents a performance evaluation of the mobile agent paradigm in comparison to the client/server paradigm. This evaluation has been conducted on top of the Java environment, using respectively RMI, the Aglets mobile agents platform and a mobile agents prototype that we implemented. The measurements give the cost of the basic mechanisms involved in the implementation of a mobile agent platform, and a comparative evaluation of the two considered models (client/server and mobile agents) through two application scenarios. The results show that significant performance improvements can be obtained using mobile agents.
The generic graph component library
Authors: Lee Lie-Quan , Siek Jeremy G. , Lumsdaine Andrew
Published: November 2005

In this paper we present the Generic Graph Component Library (GGCL), a generic programming framework for graph data structures and graph algorithms. Following the theme of the Standard Template Library (STL), the graph algorithms in GGCL do not depend on the particular data structures upon which they operate, meaning a single algorithm can operate on arbitrary concrete representations of graphs. To attain this type of flexibility for graph data structures, which are more complicated than the containers in STL, we introduce several concepts to form the generic interface between the algorithms and the data structures, namely, Vertex, Edge, Visitor, and Decorator. We describe the principal abstractions comprising the GGCL, the algorithms and data structures that it provides, and provide examples that demonstrate the use of GGCL to implement some common graph algorithms. Performance results are presented which demonstrate that the use of novel lightweight implementation techniques and static polymorphism in GGCL results in code which is significantly more efficient than similar libraries written using the object-oriented paradigm.
A distributed object-oriented framework for dependable multiparty interactions
Authors: Zorzo A. F. , Stroud R. J.
Published: November 2005

In programming distributed object-oriented systems, there are several approaches for achieving binary interactions in a multiprocess environment. Usually these approaches take care only of synchronisation or communication. In this paper we describe a way of designing and implementing a more general concept:
multiparty interactions
. In a multiparty interaction, several parties (objects or processes) somehow “come together” to produce an intermediate and temporary combined state, use this state to execute some activity, and then leave this interaction and continue their normal execution. The concept of multiparty interactions has been investigated by several researchers, but to the best of our knowledge none have considered how failures in one or more participants of the multiparty interaction can be dealt with. In this paper, we propose a general scheme for constructing
dependable multiparty interactions
in a distributed object-oriented system, and describe its implementation in Java. In particular, we extend the notion of multiparty interaction to include facilities for handling exceptions. To show how our scheme can be used, we use our framework to build an abstraction mechanism that supports cooperative and competitive concurrency in distributed systems. This mechanism is then applied to program a system in which multiparty interactions are more than simple synchronisations or communications.
The second Futamura projection for type-directed partial evaluation
Authors: Grobauer Bernd , Yang Zhe
Published: November 2005

The second Futamura projection describes the automatic generation of non-trivial generating extensions by applying a partial evaluator to itself. We derive an ML implementation of the second Futamura projection for Type-Directed Partial Evaluation (TDPE). Due to the differences between `traditional', syntax-directed partial evaluation and TDPE, this derivation involves several conceptual and technical steps. These include a suitable formulation of the second Futamura projection and techniques for using TDPE to specialize type-indexed programs. In the context of the second Futamura projection, we also compare and relate TDPE with conventional offline partial evaluation.

We demonstrate our technique with several examples, including compiler generation for Tiny, a prototypical imperative language.
From recursion to iteration
Authors: Liu Yanhong A. , Stoller Scott D.
Published: November 2005

Transforming recursion into iteration eliminates the use of stack frames during program execution. It has been studied extensively. This paper describes a powerful and systematic method, based on incrementalization, for transforming general recursion into iteration: identify an input increment, derive an incremental version under the input increment, and form an iterative computation using the incremental version. Exploiting incrementalization yields iterative computation in a uniform way and also allows additional optimizations to be explored cleanly and applied systematically, in most cases yielding iterative programs that use constant additional space, reducing additional space usage asymptotically, and run much faster. We summarize major optimizations, complexity improvements, and performance measurements.
Code motion for explicitly parallel programs
Authors: Knoop Jens , Steffen Bernhard
Published: November 2005

In comparison to automatic parallelization, which is thoroughly studied in the literature [31, 33], classical analyses and optimizations of explicitly parallel programs were more or less neglected. This may be due to the fact that naive adaptations of the sequential techniques fail [24], and their straightforward correct ones have unacceptable costs caused by the interleavings, which manifest the possible executions of a parallel program. Recently, however, we showed that unidirectional
bitvector analyses
can be performed for parallel programs as easily and as efficiently as for sequential ones [17], a necessary condition for the successful transfer of the classical optimizations to the parallel setting.In this article we focus on possible subsequent code motion transformations, which turn out to require much more care than originally conjectured [17]. Essentially, this is due to the fact that interleaving semantics, although being adequate for correctness considerations, fails when it comes to reasoning about
efficiency
of parallel programs. This deficiency, however, can be overcome by strengthening the specific treatment of synchronization points.
Dynamic instrumentation of threaded applications
Authors: Xu Zhichen , Miller Barton P. , Naim Oscar
Published: November 2005

The use of threads is becoming commonplace in both sequential and parallel programs. This paper describes our design and initial experience with non-trace based performance instrumentation techniques for threaded programs. Our goal is to provide detailed performance data while maintaining control of instrumentation costs. We have extended Paradyn's dynamic instrumentation (which can instrument programs without recompiling or relinking) to handle threaded programs.Controlling instrumentation costs means efficient instrumentation code and avoiding locks in the instrumentation. Our design is based on low contention data structures. To associate performance data with individual threads, we have all threads share the same instrumentation code and assign each thread with its own private copy of performance counters or timers. The asynchrony in a threaded program poses a major challenge to dynamic instrumentation. To implement time-based metrics on a per-thread basis, we need to instrument thread context switches, which can cause instrumentation code to interleave. Interleaved instrumentation can not only corrupt performance data, but can also cause a scenario we call self-deadlock where an instrumentation code deadlocks a thread. We introduce thread-conscious locks to avoid self-deadlock, and per-thread virtual CPU timers to reduce the chance of interleaved instrumentation accessing the same performance counter or timer, and to reduce the number of expensive timer calls at thread context switches.Our initial implementation is on SPARC Solaris 2.5 and 2.6 including multiprocessor Sun UltraSPARC Enterprise machines. We tested our tool on large multithreaded applications, including the Java Virtual Machine (JVM). We show how our new techniques helped us to speed up a Java graphics native method by 42% and consequently increase by 24% the amount of work that can be done in unit time in a game applet.
Design challenges of virtual networks
Authors: Mainwaring Alan M. , Culler David E.
Published: November 2005

Virtual networks provide applications with the illusion of having their own dedicated, high-performance networks, although network interfaces posses limited, shared resources. We present the design of a large-scale virtual network system and examine the integration of communication programming interface, system resource management, and network interface operation. Our implementation on a cluster of 100 workstations quantifies the impact of virtualization on small message latencies and throughputs, shows full hardware performance is delivered to dedicated applications and time-shared workloads, and shows robust performance under demanding workloads that overcommit interface resources.
Performance prediction of large parallel applications using parallel simulations
Authors: Bagrodia Rajive , Deeljman Ewa , Docy Steven , Phan Thomas
Published: November 2005

Accurate simulation of large parallel applications can be facilitated with the use of direct execution and parallel discrete event simulation. This paper describes the use of COMPASS, a direct execution-driven, parallel simulator for performance prediction of programs that include both communication and I/O intensive applications. The simulator has been used to predict the performance of such applications on both distributed memory machines like the IBM SP and shared-memory machines like the SGI Origin 2000. The paper illustrates the usefulness of COMPASS as a versatile performance prediction tool. We use both real-world applications and synthetic benchmarks to study application scalability, sensitivity to communication latency, and the interplay between factors like communication pattern and parallel file system caching on application performance. We also show that the simulator is accurate in its predictions and that it is also efficient in its ability to use parallel simulation to reduce its own execution time which, in some cases, has yielded a nearlinear speedup.
Automatic node selection for high performance applications on networks
Authors: Subhlok Jaspal , Lieu Peter , Lowekamp Bruce
Published: November 2005

A central problem in executing performance critical parallel and distributed applications on shared networks is the selection of computation nodes and communication paths for execution. Automatic selection of nodes is complex as the best choice depends on the application structure as well as the expected availability of computation and communication resources. This paper presents a solution to this problem for realistic application and network scenarios. A new algorithm to jointly analyze computation and communication resources for different application demands is introduced and a framework for automatic node selection is developed on top of
Remos
, which is a query interface to network information. The paper reports results from a set of applications, including Airshed pollution modeling and magnetic resonance imaging, executing on a high speed network testbed. The results demonstrate that node selection is effective in enhancing application performance in the presence of computation load as well as network traffic. Under the network conditions used for experiments, the increase in execution time due to compute loads and network congestion was reduced by half with node selection. The node selection algorithms developed in this research are also applicable to dynamic migration of long running jobs.
An efficient implementation of Java's remote method invocation
Authors: Maassen Jason , van Nieuwpoort Rob , Veldema Ronald , Bal Henri E. , Plaat Aske
Published: November 2005

Java offers interesting opportunities for parallel computing. In particular, Java Remote Method Invocation provides an unusually flexible kind of Remote Procedure Call. Unlike RPC, RMI supports polymorphism, which requires the system to be able to download remote classes into a running application. Sun's RMI implementation achieves this kind of flexibility by passing around object type information and processing it at run time, which causes a major run time overhead. Using Sun's JDK 1.1.4 on a Pentium Pro/Myri.net cluster, for example, the latency for a null RMI (without parameters or a return value) is 1228 μsec, which is about a factor of 40 higher than that of a user-level RPC. In this paper, we study an alternative approach for implementing RMI, based on native compilation. This approach allows for better optimization, eliminates the need for processing of type information at run time, and makes a light weight communication protocol possible. We have built a Java system based on a native compiler, which supports both compile time and run time generation of marshallers. We find that almost all of the run time overhead of RMI can be pushed to compile time. With this approach, the latency of a null RMI is reduced to 34 μsec, while still supporting polymorphic RMIs (and allowing interoperability with other JVMs).
Using production grammars in software testing
Authors: Sirer Emin Gün , Bershad Brian N.
Published: November 2005

Extensible typesafe systems, such as Java, rely critically on a large and complex software base for their overall protection and integrity, and are therefore difficult to test and verify. Traditional testing techniques, such as manual test generation and formal verification, are too time consuming, expensive, and imprecise, or work only on abstract models of the implementation and are too simplistic. Consequently, commercial virtual machines deployed so far have exhibited numerous bugs and security holes.

In this paper, we discuss our experience with using production grammars in testing large, complex and safety-critical software systems. Specifically, we describe
lava,
a domain specific language we have developed for specifying production grammars, and relate our experience with using
lava
to generate effective test suites for the Java virtual machine. We demonstrate the effectiveness of production grammars in generating complex test cases that can, when combined with comparative and variant testing techniques, achieve high code and value coverage. We also describe an extension to production grammars that enables concurrent generation of certificates for test cases. A certificate is a behavioral description that specifies the intended outcome of the generated test case, and therefore acts as an oracle by which the correctness of the tested system can be evaluated in isolation. We report the results of applying these testing techniques to commercial Java implementations. We conclude that the use of production grammars in combination with other automated testing techniques is a powerful and effective method for testing software systems, and is enabled by a special purpose language for specifying extended production grammars.
Jargons for domain engineering
Authors: Nakatani Lloyd H. , Ardis Mark A. , Olsen Robert G. , Pontrelli Paul M.
Published: November 2005

In the Family-oriented Abstraction, Specification and Translation (FAST) domain engineering process for software production, a member of a software product family is automatically generated from a model expressed in a DSL. In practice, the time and skill needed to make the DSLs proved to be bottlenecks. FAST now relies on jargons, a kind of easy-to-make DSL that domain engineers who are not language experts can quickly make themselves. We report our experiences with jargons in the FAST process, and describe the benefits they provide above and beyond conventional DSLs for software production and other purposes.
A case for source-level transformations in MATLAB
Authors: Menon Vijay , Pingali Keshav
Published: November 2005

In this paper, we discuss various performance overheads in MATLAB codes and propose different program transformation strategies to overcome them. In particular, we demonstrate that high-level source-to-source transformations of MATLAB programs are effective in obtaining substantial performance gains regardless of whether programs are interpreted or later compiled into C or FORTRAN. We argue that automating such transformations provides a promising area of future research.
Hancock
Authors: Bonachea Dan , Fisher Kathleen , Rogers Anne , Smith Frederick
Published: November 2005

A signature is an evolving customer profile computed from call records. AT&T uses signatures to detect fraud and to target marketing. Code to compute signatures can be difficult to write and maintain because of the volume of data. We have designed and implemented Hancock, a C-based domain- specific programming language for describing signatures. Hancock provides data abstraction mechanisms to manage the volume of data and control abstractions to facilitate looping over records. This paper describes the design and implementation of Hancock, discusses early experiences with the language, and describes our design process.
Programming World Wide Web pages in scheme
Authors: Nørmark Kurt
Published: November 2005

In this paper we will argue that pages on the World Wide Web can be made directly as programs in a functional programming language instead of through HTML or an HTML-based authoring tool. We use the Scheme programming language from the Lisp family for WWW page production. It is concluded that a Lisp language is an attractive direct vehicle for authoring of Internet material in the sense that the source of a WWW document becomes a Lisp program. Abstraction from details in the underlying markup language constitutes the main advantage in our approach. This is consistent with the expected advantage of introducing XML as a successor of HTML. In addition we find it useful to have the power of a high quality programming language available for automation of routine tasks during the authoring process.
Java will be faster than C++
Authors: Reinholtz Kirk
Published: November 2005

This paper shows that it is possible for Java to have better general performance than C++, and that it is likely that this will actually occur. Java performance
can
exceed that of C++ because dynamic compilation gives the Java compiler access to runtime information not available to a C++ compiler. This
will
occur because the rapidly growing market for embedded systems will be driven to extend battery life. Since each CPU clock cycle consumes some energy, battery life is extended by improving performance, thus achieving more computation per clock cycle.
Efficient message dispatch in object-oriented systems
Authors: Naik Mayur , Kumar Rajeev
Published: November 2005

Single dispatch involves performing at run-time a multi-way switch over the possible classes of the receiver. Most object-oriented systems implement this switch as an array lookup using a table-based technique or as a binary search using a tree-based technique. However, each of these is the best choice only under a particular circumstance; neither outperforms the other under all circumstances. In this paper, we present a time and space efficient implementation of the switch that employs the table-based technique when an array lookup outperforms a binary search and the tree-based technique when a binary search outperforms an array lookup. Further, when neither an array lookup nor a binary search is superior, our scheme blends the two techniques in a manner that gains the benefits of both without suffering the disadvantages of either. We relate our scheme to recent work and discuss extending it to implement multiple dispatch.
Derive
Authors: Engler Dawson R. , Hsieh Wilson C.
Published: November 2005

Many binary tools, such as disassemblers, dynamic code generation systems, and executable code rewriters, need to understand how machine instructions are encoded. Unfortunately, specifying such encodings is tedious and error-prone. Users must typically specify thousands of details of instruction layout, such as opcode and field locations values, legal operands, and jump offset encodings. We have built a tool called DERIVE that extracts these details from existing software: the system assembler. Users need only provide the assembly syntax for the instructions for which they want encodings. DERIVE automatically reverse-engineers instruction encoding knowledge from the assembler by feeding it permutations of instructions and doing equation solving on the output.

DERIVE is robust and general. It derives instruction encodings for SPARC, MIPS, Alpha, PowerPC, ARM, and x86. In the last case, it handles variable-sized instructions, large instructions, instruction encodings determined by operand size, and other CISC features. DERIVE is also remarkably simple: it is a factor of 6 smaller than equivalent, more traditional systems. Finally, its declarative specifications eliminate the mis-specification errors that plague previous approaches, such as illegal registers used as operands or incorrect field offsets and sizes. This paper discusses our current DERIVE prototype, explains how it computes instruction encodings, and also discusses the more general implications of the ability to extract functionality from installed software.
Profile-guided optimization across process boundaries
Authors: Johansson Erik , Nyström Sven-Olof
Published: November 2005

We describe a profile-driven compiler optimization technique for
inter-process optimization
, which dynamically inlines the effects of sending messages. Profiling is used to find optimization opportunities, and to dynamically trigger recompilation and optimization at run-time. We apply the optimization technique on the concurrent programming language ERLANG, letting recompilation take place in a separate ERLANG process, and taking advantage of the facilities provided by ERLANG to dynamically replace code at run-time. We have implemented a prototype inter-process profiler and optimizer, that can handle small programs. Measurements on synthetic benchmarks show encouraging speedups of up to 1.8 times.
A framework for remote dynamic program optimization
Authors: Voss Michael J. , Eigenmann Rudolf
Published: November 2005

Dynamic program optimization allows programs to be generated that are highly tuned for a given environment and input data set. Optimization techniques can be applied and re-applied as program and machine characteristics are discovered and change. In most dynamic optimization and compilation frameworks, the time spent in code generation and optimization must be minimized since it is directly reflected in the total program execution time. We propose a generic framework for remote dynamic program optimization that mitigates this need. A local optimizer thread monitors the program as it executes and selects program sections that should be optimized. An optimizer, running on a remote machine or a free processor of a multiprocessor, is then called to actually perform the optimization and generate a new code variant for the section. A dynamic selector is used to select the most appropriate code variant for each code interval based upon the current runtime environment. We describe this framework in detail and present an example of its use on a simple application. We show that our framework, when used with changing input, can outperform the best statically optimized version of the application.
A comparative study of static and profile-based heuristics for inlining
Authors: Arnold Matthew , Fink Stephen , Sarkar Vivek , Sweeney Peter F.
Published: November 2005

In this paper, we present a comparative study of static and profile-based heuristics for inlining. Our motivation for this study is to use the results to design the best inlining algorithm that we can for the Jalapeño dynamic optimizing compiler for Java [6]. We use a well-known approximation algorithm for the KNAPSACK problem as a common “meta-algorithm” for the inlining heuristics studied in this paper. We present performance results for an implementation of these inlining heuristics in the Jalapeño dynamic optimizing compiler. Our performance results show that the inlining heuristics studied in this paper can lead to significant speedups in execution time (up to 1.68x) even with modest limits on code size expansion (at most 10%).
Probabilistic data flow system with two-edge profiling
Authors: Mehofer Eduard , Scholz Bernhard
Published: November 2005

Traditionally optimization is done statistically independent of actual execution environments. For generating highly optimized code, however, runtime information can be used to adapt a program to different environments. In probabilistic data flow systems runtime information on representative input data is exploited to compute the probability with what data flow facts may hold. Probabilistic data flow analysis can guide sophisticated optimizing transformations resulting in better performance. In comparison classical data flow analysis does not take runtime information into account. All paths are equally weighted irrespectively whether they are never, heavily, or rarely executed.

In this paper we present the best solution what we can theoretically obtain for probabilistic data flow problems and compare it with the state-of-the-art one-edge approach. We show that the differences can be considerable and improvements are crucial. However, the theoretically best solution is too expensive in general and feasible approaches are required. In the sequel we develop an efficient approach which employs two-edge profiling and classical data flow analysis. We show that the results of the two-edge approach are significantly better than the state-of-the-art one-edge approach.
Improving the Java memory model using CRF
Authors: Maessen Jan-Willem , Shen Xiaowei
Published: November 2005

This paper describes alternative memory semantics for Java programs using an enriched version of the Commit/Reconcile/Fence (CRF) memory model [16]. It outlines a set of reasonable practices for safe multithreaded programming in Java. Our semantics allow a number of optimizations such as load reordering that are currently prohibited. Simple thread-local algebraic rules express the effects of optimizations at the source or bytecode level. The rules focus on reordering source-level operations; they yield a simple dependency analysis algorithm for Java. An instruction-by-instruction translation of Java memory operations into CRF operations captures thread interactions precisely. The fine-grained synchronization of CRF means the algebraic rules are easily derived from the translation. CRF can be mapped directly to a modern architecture, and is thus a suitable target for optimizing memory coherence during code generation.
Exclusion for composite objects
Authors: Noble James , Holmes David , Potter John
Published: November 2005

Designing concurrent object-oriented programs is hard. Correct programs must coordinate multiple threads accessing composite objects, using low-level mechanisms such as locks and read-write sets. Efficient programs must balance the complexity and overhead of the coordination mechanisms against the increased performance possible through concurrency. A method-level algebra of exclusion provides a succinct description of the conditions under which a thread must be
excluded
from a component of a composite object. Using the algebra, programmers can check whether their programs meet their exclusion requirements, can eliminate redundant exclusion controls, and can remove synchronisation overhead by reducing concurrency.
A real world object modeling method for creating simulation environment of real-time systems
Authors: Lee Ji Y. , Kim Hye J. , Kang Kyo C.
Published: November 2005

Most real-time embedded control software feature complex interactions with asynchronous inputs and environment objects, and a meaningful simulation of a real-time control software specification requires realistic simulation of its environment. Two problems that need to be addressed in the simulation of a target software system and its environment: First, integration and simulation of the specifications of a target software system and its artificial environment are often performed too late in the lifecycle to provide any significant value. Second, real world objects in the environment usually have spatial characteristics (
form
) such as shape, motion, etc. that must be specified for simulation, and there is no method to express these spatial characteristics at various levels of abstraction that are adequate for the required simulation fidelity.To address these problems, we have developed a method that supports incremental specification and simulation of both the target software system and its environmental objects. The method includes: (1) a specification method for behavior, function, and form integrated objects; (2) form specification primitives that abstract common spatial characteristics of real world objects, their typical spatial relations, and spatial interactions; and (3) a methodology that refines, verifies, and validates behavior, function, and form specification of both the real-time embedded control software and its environment in a systematic and incremental manner. The proposed specification, verification, and validation method has been applied to a robot control system example to demonstrate its effectiveness and usefulness.
MultiJava
Authors: Clifton Curtis , Leavens Gary T. , Chambers Craig , Millstein Todd
Published: November 2005

We present MultiJava, a backward-compatible extension to Java supporting
open classes
and
symmetric multiple dispatch
. Open classes allow one to add to the set of methods that an existing class supports without creating distinct subclasses or editing existing code. Unlike the "Visitor" design pattern, open classes do not require advance planning, and open classes preserve the ability to add new subclasses modularly and safely. Multiple dispatch offers several well-known advantages over the single dispatching of conventional object-oriented languages, including a simple solution to some kinds of "binary method" problems. MultiJava's multiple dispatch retains Java's existing class-based encapsulation properties. We adapt previous theoretical work to allow compilation units to be statically typechecked modularly and safely, ruling out any link-time or run-time type errors. We also present a n compilation scheme that operates modularly and incurs performance overhead only where open classes or multiple dispatching are actually used.
Finding refactorings via change metrics
Authors: Demeyer Serge , Ducasse Stéphane , Nierstrasz Oscar
Published: November 2005

Reverse engineering is the process of uncovering the design and the design rationale from a functioning software system. Reverse engineering is an integral part of any successful software system, because changing requirements lead to implementations that drift from their original design. In contrast to traditional reverse engineering techniques ---which analyse a single snapshot of a system--- we focus the reverse engineering effort by determining where the implementation has changed. Since changes of object-oriented software are often phrased in terms of refactorings, we propose a set of heuristics for detecting refactorings by applying lightweight, object-oriented metrics to successive versions of a software system. We validate our approach with three separate case studies of mature object-oriented software systems for which multiple versions are available. The case studies suggest that the heuristics support the reverse engineering process by focusing attention on the relevant parts of a software system.
Mapping UML designs to Java
Authors: Harrison William , Barton Charles , Raghavachari Mukund
Published: November 2005

Tools for the generation of code from model descriptions are valuable in helping developers maintain consistency between a model and its implementation. In this paper, we describe a new method for generating Java implementation code from UML diagrams. Our method accepts UML diagrams specified at a higher-level than current tools, and places fewer constraints on the supported UML constructs, like multiple generalizations and association classes. Unlike current tools, it generates implementation code that shields system implementers from the low-level details of how associations and other UML constructs are mapped to Java. Furthermore, it supports the modular design of systems according to concerns[2, 10] by being able to generate code from a set of related UML diagrams. While our discussion is focused on the special problem of generating Java implementation code, the issues discussed in this paper are applicable more generally to object-oriented implementation languages.
Safely creating correct subclasses without seeing superclass code
Authors: Ruby Clyde , Leavens Gary T.
Published: November 2005

A major problem for object-oriented frameworks and class libraries is how to provide enough information about a superclass, so programmers can safely create new subclasses without giving away the superclass's code. Code inherited from the superclass can call down to methods of the subclass, which may cause nontermination or unexpected behavior. We describe a reasoning technique that allows programmers, who have no access to the code of the superclass, to determine both how to safely override the superclass's methods and when it is safe to call them. The technique consists of a set of rules and some new forms of specification. Part of the specification would be generated automatically by a tool, a prototype of which is planned for the formal specification language JML. We give an example to show the kinds of problems caused by method overrides and how our technique can be used to avoid them. We also argue why the technique is sound and give guidelines for library providers and programmers that greatly simplify reasoning about how to avoid problems caused by method overrides.