bluuebunny/crossref_metadata_2025 huggingface dataset:
“Who cares about elegance?” The role of aesthetics in programming language design
Authors: MacLennan Bruce J.
Published: November 2005

The crucial role played by aesthetics in programming language design and the importance of elegance in programming languages are defended on the basis of analogies with structural engineering, as presented in Billington's
The Tower and the Bridge
.
A note on before and after metamethods
Authors: Zimmermann Chris
Published: November 2005

With the advent of object-oriented metalevel architectures, a new programming paradigm in the shape of before and after metamethods has arrived. This paradigm allows the hidden execution of additional functionality that previously had to be inserted explicitly into the source code of a program. Typically, this was implemented as a pair of invocations to some initialisation and finalisation routines. This paper provides the formal proof that before and after metamethods have the same expressive power as the explicit invocation of functionality, resulting in the equivalence of both paradigms.
Block structured object programming
Authors: Rapin Charles
Published: November 2005

Most popular object oriented languages have a flat class declaration structure. Providing the possibility of nesting classes gives several interesting properties. Objects may hide their internal representation. Objects may be born within other objects whose structure they know. Meta classes may be implemented as singular, one of its kind, objects in which are nested the classes they control. Languages of the scandinavian school of object oriented programming do offer these possibilities. The author has implemented them and experimented their effects in the Newton language developped at the Compiler Design Laboratory of the Swiss Federal Institute of Technology.
tcc
Authors: Poletto Massimiliano , Engler Dawson R. , Kaashoek M. Frans
Published: November 2005

tcc is a compiler that provides efficient and high-level access to dynamic code generation. It implements the 'C ("Tick-C") programming language, an extension of ANSI C that supports dynamic code generation [15]. 'C gives power and flexibility in specifying dynamically generated code: whereas most other systems use annotations to denote run-time invariants. 'C allows the programmer to specify and compose arbitrary expressions and statements at run time. This degree of control is needed to efficiently implement some of the most important applications of dynamic code generation, such as "just in time" compilers [17] and efficient simulators [10, 48, 46].The paper focuses on the techniques that allow tcc to provide 'C's flexibility and expressiveness without sacrificing run-time code generation efficiency. These techniques include fast register allocation, efficient creation and composition of dynamic code specifications, and link-time analysis to reduce the size of dynamic code generators. tcc also implements two different dynamic code generation strategies, designed to address the tradeoff of dynamic compilation speed versus generated code quality. To characterize the effects of dynamic compilation, we present performance measurements for eleven programs compiled using tcc. On these applications, we measured performance improvements of up to one order of magnitude.To encourage further experimentation and use of dynamic code generation, we are making the tcc compiler available in the public domain. This is, to our knowledge, the first high-level dynamic compilation system to be made available.
Interprocedural conditional branch elimination
Authors: Bodík Rastislav , Gupta Rajiv , Soffa Mary Lou
Published: November 2005

The existence of statically detectable correlation among conditional branches enables their elimination, an optimization that has a number of benefits. This paper presents techniques to determine whether an interprocedural execution path leading to a conditional branch exists along which the branch outcome is known at compile time, and then to eliminate the branch along this path through code restructuring. The technique consists of a demand driven interprocedural analysis that determines whether a specific branch outcome is correlated with prior statements or branch outcomes. The optimization is performed using a code restructuring algorithm that replicates code to separate out the paths with correlation. When the correlated path is affected by a procedure call, the restructuring is based on procedure
entry splitting and exit splitting
. The
entry splitting
transformation creates multiple entries to a procedure, and the
exit splitting
transformation allows a procedure to return control to one of several return points in the caller. Our technique is efficient in that the correlation detection is demand driven, thus avoiding exhaustive analysis of the entire program, and the restructuring never increases the number of operations along a path through an interprocedural control flow graph. We describe the benefits of our interprocedural branch elimination optimization (ICBE). Our experimental results show that, for the same amount of code growth, the estimated reduction in executed conditional branches is about 2.5 times higher with the ICBE optimization than when only intraprocedural conditional branch elimination is applied.
Efficient procedure mapping using cache line coloring
Authors: Hashemi Amir H. , Kaeli David R. , Calder Brad
Published: November 2005

As the gap between memory and processor performance continues to widen, it becomes increasingly important to exploit cache memory eflectively. Both hardware and aoftware approaches can be explored to optimize cache performance. Hardware designers focus on cache organization issues, including replacement policy, associativity, line size and the resulting cache access time. Software writers use various optimization techniques, including software prefetching, data scheduling and code reordering. Our focus is on improving memory usage through code reordering compiler techniques.In this paper we present a link-time procedure mapping algorithm which can significantly improve the eflectiveness of the instruction cache. Our algorithm produces an improved program layout by performing a color mapping of procedures to cache lines, taking into consideration the procedure size, cache size, cache line size, and call graph. We use cache line coloring to guide the procedure mapping, indicating which cache lines to avoid when placing a procedure in the program layout. Our algorithm reduces on average the instruction cache miss rate by 40% over the original mapping and by 17% over the mapping algorithm of Pettis and Hansen [12].
Near-optimal intraprocedural branch alignment
Authors: Young Cliff , Johnson David S. , Smith Michael D. , Karger David R.
Published: November 2005

Branch alignment reorders the basic blocks of a program to minimize pipeline penalties due to control-transfer instructions. Prior work in branch alignment has produced useful heuristic methods. We present a branch alignment algorithm that usually achieves the minimum possible pipeline penalty and on our benchmarks averages within 0.3% of a provable optimum. We compare the control penalties and running times of our algorithm to an older, greedy approach and observe that both the greedy method and our method are close to the lower bound on control penalties, suggesting that greedy is good enough. Surprisingly, in actual execution our method produces programs that run noticeably faster than the greedy method. We also report results from training and testing on different data sets, validating that our results can be achieved in real-world usage. Training and testing on different data sets slightly reduced the benefits from both branch alignment algorithms, but the ranking of the algorithms does not change, and the bulk of the benefits remain.
Program analysis using binary relations
Authors: Webber Adam Brooks
Published: November 2005

This paper presents a method called
relational constraint
for finding binary relations among the variables and constants of a program. The method constructs a table of binary relations and treats the program as a collection of constraints on tuples of relations in the table. An experimental optimizer called Thinner uses this method to analyze programs of size
n
in
O
(
n
2
) time.
Linear-time subtransitive control flow analysis
Authors: Heintze Nevin , McAllester David
Published: November 2005

We present a linear-time algorithm for bounded-type programs that builds a directed graph whose transitive closure gives exactly the results of the standard (cubic-time) Control-Flow Analysis (CFA) algorithm. Our algorithm can be used to list all functions calls from all call sites in (optimal) quadratic time. More importantly, it can be used to give linear-time algorithms for CFA-consuming applications such as:• effects analysis: find the side-effecting expressions in a program.•
k
-limited CFA: for each call-site, list the functions if there are only a few of them (≤ k) and otherwise output "many".• called-once analysis: identify all functions called from only one call-site.
A new algorithm for partial redundancy elimination based on SSA form
Authors: Chow Fred , Chan Sun , Kennedy Robert , Liu Shin-Ming , Lo Raymond , Tu Peng
Published: November 2005

A new algorithm, SSAPRE, for performing partial redundancy elimination based entirely on SSA form is presented. It achieves optimal code motion similar to lazy code motion [KRS94a, DS93], but is formulated independently and does not involve iterative data flow analysis and bit vectors in its solution. It not only exhibits the characteristics common to other sparse approaches, but also inherits the advantages shared by other SSA-based optimization techniques. SSAPRE also maintains its output in the same SSA form as its input. In describing the algorithm, we state theorems with proofs giving our claims about SSAPRE. We also give additional description about our practical implementation of SSAPRE, and analyze and compare its performance with a bit-vector-based implementation of PRE. We conclude with some discussion of the implications of this work.
Call-cost directed register allocation
Authors: Lueh Guei-Yuan , Gross Thomas
Published: November 2005

Choosing the right kind of register for a live range plays a major role in eliminating the register-allocation overhead when the compiled function is frequently executed or function tails are on the most frequently executed paths. Picking the wrong kind of register for a live range incurs a high penalty that may dominate the total overhead of register allocation. In this paper, we present three improvements, storage-class analysis, benefit-driven simplification, and preference decision that are effective in selecting the right kind of register for a live range. Then we compare an enhanced Chaitin-style register allocator (with these three improvements) with priority-based and optimistic coloring.
Data distribution support on distributed shared memory multiprocessors
Authors: Chandra Rohit , Chen Ding-Kai , Cox Robert , Maydan Dror E. , Nedeljkovic Nenad , Anderson Jennifer M.
Published: November 2005

Cache-coherent multiprocessors with distributed shared memory are becoming increasingly popular for parallel computing. However, obtaining high performance on these machines mquires that an application execute with good data locality. In addition to making efiective use of caches, it is often necessary to distribute data structures across the local memories of the processing nodes, thereby reducing the latency of cache misses.We have designed a set of abstractions for performing data distribution in the context of explicitly parallel programs and implemented them within the SGI MIPSpro compiler system. Our system incorporates many unique features to enhance both programmability and performance. We address the former by providing a very simple programmming model with extensive support for error detection. Regarding performance, we carefully design the user abstractions with the underlying compiler optimizations in mind, we incorporate several optimization techniques to generate efficient code for accessing distributed data, and we provide a tight integration of these techniques with other optimizations within the compiler Our initial experience suggests that the directives are easy to use and can yield substantial performance gains, in some cases by as much as a factor of 3 over the same codes without distribution.
Code compression
Authors: Ernst Jens , Evans William , Fraser Christopher W. , Proebsting Todd A. , Lucco Steven
Published: November 2005

Current research in compiler optimization counts mainly CPU time and perhaps the first cache level or two. This view has been important but is becoming myopic, at least from a system-wide viewpoint, as the ratio of network and disk speeds to CPU speeds grows exponentially.For example, we have seen the CPU idle for most of the time during paging, so compressing pages can increase total performance even though the CPU must decompress or interpret the page contents. Another profile shows that many functions are called just once, so reduced paging could pay for their interpretation overhead.This paper describes:• Measurements that show how code compression can save space
and
total time in some important real-world scenarios.• A compressed executable representation that is roughly the same size as gzipped x86 programs and can be interpreted without decompression. It can also be compiled to high-quality machine code at 2.5 megabytes per second on a 120MHz Pentium processor• A compressed "wire" representation that must be decompressed before execution but is, for example, roughly 21% the size of SPARC code when compressing gcc.
Strongly typed flow-directed representation transformations (extended abstract)
Authors: Dimock Allyn , Muller Robert , Turbak Franklyn , Wells J. B.
Published: November 2005

We present a new framework for transforming data representations in a strongly typed intermediate language. Our method allows both value producers (sources) and value consumers (sinks) to support multiple representations, automatically inserting any required code. Specialized representations can be easily chosen for particular source/sink pairs.The framework is based on these techniques:1.
Flow annotated types
encode the "flows-from" (source) and "flows-to" (sink) information of a flow graph.2.
Intersection and union types
support (a) encoding precise flow information, (b) separating flow information so that transformations can be well typed, (c) automatically reorganizing flow paths to enable multiple representations.As an instance of our framework, we provide a function representation transformation that encompasses both closure conversion and inlining. Our framework is adaptable to data other than functions.
Catenable double-ended queues
Authors: Okasaki Chris
Published: November 2005

Catenable double-ended queues are double-ended queues (deques) that support catenation (i.e., append) efficiently without sacrificing the efficiency of other operations. We present a purely functional implementation of catenable deques for which every operation, including catenation, takes
O
(1) amortized time. Kaplan and Tarjan have independently developed a much more complicated implemen-tation of catenable deques that achieves similar worst-case bounds. The two designs are superficially similar, but differ in the underlying mechanism used to achieve efficiency in a persistent setting (i.e., when used in a non-single-threaded fashion). Their implementation uses a technique called recursive slowdown, while ours relies on the simpler mechanism of lazy evaluation.Besides lazy evaluation, our implementation also exemplifies the use of two additional language features: polymorphic recursion and views. Neither is indispensable, but both significantly simplify the presentation.
Statically checkable pattern abstractions
Authors: Fähndrich Manuel , Boyland John
Published: November 2005

Pattern abstractions increase the expressiveness of pattern matthing, enabling the programmer to describe a broader class of regular forests with patterns. Furthermore, pattern abstractions support code reuse and code factoring, features that facilitate maintenance and evolution of code. Past research on pattern abstractions has generally ignored the aspect of compile-time checks for exhaustiveness and redundancy. In this paper we propose a class of expressive patterns that admits these compile-time checks.
Foundations for the implementation of higher-order subtyping
Authors: Crary Karl
Published: November 2005

We show how to implement a calculus with higher-order subtyping and subkinding by replacing uses of implicit subsumption with explicit coercions. To ensure this can be done, a polymorphic function is adjusted to take, as an additional argument, a proof that its type constructor argument has the desired kind. Such a proof is extracted from the derivation of a kinding judgement and may in turn require proof coercions, which are extracted from subkinding judgements. This technique is formalized as a type-directed translation from a calculus of higher-order subtyping to a subtyping-free calculus. This translation generalizes an existing result for second-order subtyping calculi (such as
F
≤).We also discuss two interpretations of subtyping, one that views it as type inclusion and another that views it is the existence of a well-behaved coercion, and we show, by a type-theoretic construction, that our translation is the minimum consequence of shifting from the inclusion interpretation to the coercion-existence interpretation. This construction shows that the translation is the natural one, and it also provides a framework for extending the translation to richer type systems. Finally, we show how the two interpretations can be reconciled in a common semantics. It is then easy to show the coherence of the translation relative to that semantics.
On the complexity of set-based analysis
Authors: Heintze Nevin , McAllester David
Published: November 2005

We define a general notion of set-based analysis --- any language whose operational semantics is defined by environment evaluation has a well defined set-based abstraction. This general definition covers both Aiken and Wimmers' type system and Heintze' set-based analysis. Aiken and Wimmers give a nondeterministic exponential time algorithm for their analysis. Heintze gives an
O
(
n
3
) procedure. We show that this discrepancy is due to the complexity of the case statements analyzed. For polymorphic programs with deep patterns in case statements (as in the Aiken-Wimmers language) we show that the problem of determining type-safety under set-based abstraction is complete for deterministic exponential time. The problem remains complete for deterministic exponential time for programs without let (monovariant programs). However, for monovariant programs in which all patterns in case statements are shallow, as in the Heintze language, type-safety under set-based abstraction is decidable in cubic time. We give five additional theorems which (nearly exhaustively) characterize the time complexity of set-based analysis as a function of the complexity of case statements.
Tupling calculation eliminates multiple data traversals
Authors: Hu Zhenjiang , Iwasaki Hideya , Takeichi Masato , Takano Akihiko
Published: November 2005

Tupling is a well-known transformation tactic to obtain new efficient recursive functions by grouping some recursive functions into a tuple. It may be applied to eliminate multiple traversals over the common data structure. The major difficulty in tupling transformation is to find what functions are to be tupled and how to transform the tupled function into an efficient one. Previous approaches to tupling transformation are essentially based on fold/unfold transformation. Though general, they suffer from the high cost of keeping track of function calls to avoid infinite unfolding, which prevents them from being used in a compiler.To remedy this situation, we propose a new method to expose recursive structures in recursive definitions and show how this structural information can be explored for calculating out efficient programs by means of tupling. Our new tupling calculation algorithm can eliminate most of multiple data traversals and is easy to be implemented.
The development of Erlang
Authors: Armstrong Joe
Published: November 2005

This paper describes the development of the programming language Erlang during the period 1985--1997.Erlang is a concurrent programming language designed for programming large-scale distributed soft real-time control applications.The design of Erlang was heavily influenced by ideas from the logic and functional programming communities. Other sources of inspiration came from languages such as Chill and Ada which are used in industry for programming control systems.
Type specialisation for imperative languages
Authors: Dussart Dirk , Hughes John , Thiemann Peter
Published: November 2005

We extend type specialisation to a computational lambda calculus with first-class references. The resulting specialiser has been used to specialise a self-interpreter for this typed computational lambda calculus optimally. Furthermore, this specialiser can perform operations on references at specialisation time, when possible.
Compositional references for stateful functional programming
Authors: Kagawa Koji
Published: November 2005

We introduce the notion of
compositional references
into the framework of monadic functional programming and propose a set of new primitives based on this notion. They enable us to use a wide range of mutable data structures. There, references may be passed around explicitly, or mutable data structures such as arrays and tuples may be passed implicitly as hidden state. The former style is called
the explicit style
and is usually more expressive, while the latter is called
the implicit style
and has simpler semantics. We investigate the relation between the two styles and discus implementation issues.
Formal models of distributed memory management
Authors: Ungureanu Christian , Goldberg Benjamin
Published: November 2005

We develop am abstract model of memory management in distributed systems. The model is low-level enough so that we can express communication, allocation and garbage collection, but otherwise hides many of the lower-level details of an actual implementation.Recently, such formal models have been developed for memory management in a functional, sequential setting [10]. The models are rewriting systems whose terms are programs. Programs have both the "code" (control string) and the "store" syntactically apparent. Evaluation is expressed as conditional rewriting and includes store operations. Garbage collection becomes a rewriting relation that removes part of the store without affecting the behavior of the program.Distribution adds another dimension to an already complex problem. By using techniques developed for communicating and concurrent systems [9], we extend their work to a distributed environment. Sending and receiving messages is also made apparent at the syntactic level. A very general garbage collection rule based on reachability is introduced and proved correct. Now proving correct a specific collection strategy is reduced to showing that the relation between programs defined by the strategy is a sub-relation of the general relation. Any actual implementation which is capable of providing the transitions (including their atomicity constraints) specified by the strategy is therefore correct.This model allows us to specify and prove correct in a compact manner two garbage collectors; the first one does a simple garbage collection local to a node. The second garbage collector uses migration of data in order to be able to reclaim inter-node cyclic garbage.
Partial-evaluation techniques for concurrent programs
Authors: Marinescu Mihnea , Goldberg Benjamin
Published: November 2005

This paper presents an application of
partial evaluation
(program specialization) techniques to
concurrent programs
. The language chosen for this investigation is a very simple CSP-like language. A standard binding-time analysis for imperative languages is extended in order to deal with the basic concurrent constructs (synchronous communication and nondeterministic choice). Based on the binding-time annotations, a specialization transformation is defined and proved correct. In order to maintain a simple and clear presentation, the specialization algorithm addresses only the data transfer component of the communication; partial evaluation, the way it is defined here, always generates residual synchronizations. However, a simple approximate analysis for detecting and removing redundant synchronizations from the residual program (i.e. synchronizations whose removal does not increase the nondeterminism of a program) can be performed. The paper also addresses pragmatic concerns such as improving the binding-time analysis, controlling loop unrolling and the consequences of lifting nondeterminism from run-time to specialization-time. Finally, the power of the newly developed technique is shown in several examples.
Accurate binding-time analysis for imperative languages
Authors: Hornof Luke , Noyé Jacques
Published: November 2005

Since a binding-time analysis determines how an off-line partial evaluator will specialize a program, the accuracy of the binding-time information directly determines the degree of specialization. We have designed and implemented a binding-time analysis for an imperative language, and integrated it into our partial evaluator for C, called Tempo [9]. This binding-time analysis includes a number of new features, not available in any existing partial evaluator for an imperative language, which are critical when specializing existing programs such as operating system components [24, 25].•
Flow sensitivity
. A different binding-time description is computed for each program point, allowing the same variable to be considered static at one program point and dynamic at another.•
Context sensitivity
. Each function call is analyzed with the context of the call site, generating multiple binding-time annotated instances of the same function definition.•
Return sensitivity
. A different binding-time description is computed for the side-effects and the return value of a function.
Lambda-dropping
Authors: Danvy Olivier , Schultz Ulrik P.
Published: November 2005

Lambda-lifting a functional program transforms it into a set of recursive equations. We present the symmetric transformation: lambda-dropping. Lambda-dropping a set of recursive equations restores block structure and lexical scope.For lack of scope, recursive equations must carry around all the parameters that any of their callees might possibly need. Both lambda-lifting and lambda-dropping thus require one to compute a transitive closure over the call graph:• for lambda-lifting: to establish the Def/Use path of each free variable (these free variables are then added as parameters to each of the functions in the call path);• for lambda-dropping: to establish the Def/Use path of each parameter (parameters whose use occurs in the same scope as their definition do not need to be passed along in the call path).Without free variables, a program is scope-insensitive. Its blocks are then free to float (for lambda-lifting) or to sink (for lambda-dropping) along the vertices of the scope tree.We believe lambda-lifting and lambda-dropping are interesting per se, both in principle and in practice, but our prime application is partial evaluation: except for Malmkjær and Ørbæk's case study presented at PEPM '95, most polyvariant specializers for procedural programs operate on recursive equations. To this end, in a pre-processing phase, they lambda-lift source programs into recursive equations, As a result, residual programs are also expressed as recursive equations, often with dozens of parameters, which most compilers do not handle efficiently. Lambda-dropping in a post-processing phase restores their block structure and lexical scope thereby significantly reducing both the compile time and the run time of residual programs.
Scaling up partial evaluation for optimizing the Sun commercial RPC protocol
Authors: Muller Gilles , Volanschi Eugen-Nicolae , Marlet Renaud
Published: November 2005

We report here a successful experiment in using partial evaluation on a realistic program, namely the Sun commercial RPC (Remote Procedure Call) protocol. The Sun RPC is implemented in a highly generic way that offers multiple opportunities of specialization.Our study also shows the incapacity of traditional binding-time analyses to treat real system programs. Our experiment has been made with Tempo, a partial evaluator for C programs targeted towards system software. Tempo's binding-time analysis had to be improved to integrate partially static data structures (interprocedurally), context sensitivity, use sensitivity and return sensitivity.The Sun RPC experiment files, including the specialized implementation, are publicly available upon request to the authors.
Partial evaluation in aircraft crew planning
Authors: Augustsson Lennart
Published: November 2005

In this paper we investigate how partial evaluation and program transformations can be used on a real problem, namely that of speeding up airline crew scheduling.Scheduling of crews is subject to many rules and restrictions. These restrictions are expressed in a rule language. However, in a given planning situation much is known to be fixed, so the rule set can be partially evaluated with respect to this known input.The approach is somewhat novel in that it uses truly static input data as well as static input data where the values are known only to belong to a set of values.The results of the partial evaluation is quite satisfactory: both compilation and running times have decreased by using it. The partial evaluator is now part of the crew scheduling system that Carmen Systems AB markets and which is in use at most of the major European airlines and in daily production.
Specialization of lazy functional logic programs
Authors: Alpuente M. , Falaschi M. , Julián P. , Vidal G.
Published: November 2005

Partial evaluation is a method for program specialization based on fold/unfold transformations [8, 25]. Partial evaluation of pure functional programs uses mainly static values of given data to specialize the program [15, 44]. In logic programming, the so-called static/dynamic distinction is hardly present, whereas considerations of determinacy and choice points are far more important for control [12]. We discuss these issues in the context of a (lazy) functional logic language. We formalize a two-phase specialization method for a non-strict, first order, integrated language which makes use of lazy narrowing to specialize the program w.r. t. a goal. The basic algorithm (first phase) is formalized as an instance of the framework for the partial evaluation of functional logic programs of [2, 3], using lazy narrowing. However, the results inherited by [2, 3] mainly regard the termination of the PE method, while the (strong) soundness and completeness results must be restated for the lazy strategy. A post-processing renaming scheme (second phase) is necessary which we describe and illustrate on the well-known matching example. This phase is essential also for other non-lazy narrowing strategies, like innermost narrowing, and our method can be easily extended to these strategies. We show that our method preserves the lazy narrowing semantics and that the inclusion of simplification steps in narrowing derivations can improve control during specialization.
Prescriptive Frameworks for Multi-Level Lambda-Calculi
Authors: Nielson Flemming , Riis Nielson Hanne
Published: November 2005

Two-level A-calculi have been heavily utilised for applications such as partial evaluation, abstract interpretation and code generation. Each of these applications pose different demands on the exact details of the twolevel structure and the corresponding inference rules. In a previous paper we have developed a descriptive framework for characterizing the key ingredients used in the various applications. Based on the insights offered by this characterisation we now develop a prescriptive framework that offers firm guidelines on what we regard as "good" definitions of multi-level lambda-calculi.
Forth as a robotics language
Authors: Frenger Paul
Published: November 2005

This is the second part of a two-part paper describing the author's recent experiences with robot control systems. In part one, the three principal robotics language philosophies were illustrated. This was followed by a discussion of unconventional languages for robot control, namely PostScript and Java. In this installment, the author describes how he used Forth as an object oriented programming language to develop a multiprocessor android control network. Some interesting Forth derivatives will be presented at the end.
How to achieve modularity in distributed object allocation
Authors: Zambonelli Franco
Published: November 2005

The paper focuses on language constructs for driving the allocation of parallel object-oriented applications onto a target architecture. The paper analyses the issues that arise in the definition of these constructs and presents the solutions adopted in several systems and programming environments, by discussing their capability of enforcing the principle of modularity. Open issues and future directions of research are outlined.
Analyzing and measuring reusability in object-oriented design
Authors: Price Margaretha W. , Demurjian Steven A.
Published: November 2005

In this paper, we present a technique to analyze and measure the reusability of object-oriented (OO) designs. The metrics can be incorporated into a design/development environment, so that reusability measurements, analysis, and improvements can be part of "business as usual" for an organization. Design reusability measurements also enable early identification of poor reuse potential, when it is still possible to modify/refine the design. The essential components of our approach are two reuse-specific characterizations of classes and hierarchies, and a set of metrics which objectively measures the dependencies among design components based on those reuse-specific characterizations.
Modeling dynamic collections of interdependent objects using path-based rules
Authors: Litman Diane , Patel-Schneider Peter F. , Mishra Anil
Published: November 2005

Standard object-oriented languages do not provide language support for modeling changing collections of interdependent objects. We propose that R++, an integration of the rule and object-oriented paradigms, provides a mechanism for easily implementing such models. R++ extends C++ by adding a new programming construct called the
path-based
rule. Such data-driven rules are restricted to follow pointers between objects, and are like "automatic methods" that are triggered by changes to monitored objects. Path-based rules encourage a more abstract level of programming, and unlike previous rule integrations, are not at odds with the object-oriented paradigm and offer performance advantages for natural applications.
Looking for the objects in object-relational DBMSs (panel)
Authors: Anderson Lougie , Carey Mike , Jacobs Ken , Kinikin Erin , Maier David
Published: November 2005

The Relational Model first came into vogue in the early 1980's. It was based on the simplifying idea that all data could be modeled as mathematical relations (tables in "normal form"). Permissible operations on this table data structure were specified by the relation algebra and calculus. The Relational Model led to years of research in areas such as query languages, query optimization, transaction models, and database design methodologies. This research has dominated DBMS conferences for the last fifteen years and has also lead to major products offerings in wide-spread use in the computer industry today.While the Relational revolution was happening in the DBMS community there was a minority opinion emerging from the object community. This minority opinion surfaced in heated debates and panels at DBMS conferences where it was often pitted against "relational purists." The object proponents wanted to discuss storing and retrieving complex objects and relationships in databases while the relational purists insisted on maintaining "mathematical purity and simplicity". These panels were often some of the most acrimonious (and entertaining) at these conferences and many thought there was no way to bridge the chasm between the two schools of thought.However times changes and so do the realities of the commercial world. Object languages such as C++, Smalltalk, and Java have become
de facto
standards. The Internet and the PC have increased the demand for complex data types. And the relational model is evolving to accommodate these realities.All of the major RDBMS vendors have announced plans for, or are already shipping, Object-Relational DBMS (ORDBMS) products. A natural question for the object community is how well these new products will address the well-known "impedance mismatch" between a pure object model and the relational model. For example, how does one make Java, Smalltalk, or C++ objects persist using an ORDBMS? Can one search for these objects in the database using their methods?The vendors for ORDBMS are claiming well-known OO features in their implementations, such as extensible data types, inheritance, object identity, and object language bindings. This panel will allow the major vendors to explain how those features match up with the kinds of object models that OO developers are accustomed to. The panel will consist of representatives from three of the major ORDBMS vendors as well as a representative of "pure object think". The vendor representatives will each present a brief overview of the object-related features of their products and will explain why OO programmers are going to have an easier time with these ORDBMSs. This will be followed by counterpoint discussion from the pure object thinker.
A framework for scalable dissemination-based systems
Authors: Franklin Michael , Zdonik Stanley
Published: November 2005

The dramatic improvements in global interconnectivity due to intranets, extranets, and the Internet has led to an explosion in the number and variety of new data-intensive applications. Along with the proliferation of these new applications have come increased problems of scale. This is demonstrated by frequent delays and service, disruptions when accessing networked data sources. Recently, push-based techniques have been proposed as a solution to scalability problems for distributed applications. This paper argues that push indeed has its place, but that it is just one aspect of a much larger design space for distributed information systems. We propose the notion of a Dissemination-Based Information System (DBIS) which integrates a variety of data delivery mechanisms and information broker hierarchies. We discuss the properties of such systems and provide some insight into the architectural imperatives that will influence their design. The DBIS framework can serve as the basis for development of a toolkit for constructing distributed information systems that better match the technology they employ to the characteristics of the applications they are intended to support.
Efficient dynamic dispatch without virtual function tables
Authors: Zendra Olivier , Colnet Dominique , Collin Suzanne
Published: November 2005

SmallEiffel is an Eiffel compiler which uses a fast simple type inference mechanism to remove most late binding calls, replacing them by static bindings. Starting from the system's entry point, it compiles only statically living code, which saves compiling and then removing dead code. As the whole system is analyzed at compile time, multiple inheritance and genericity do not cause any overhead.SmallEiffel features a coding scheme which eliminates the need for virtual function tables. Dynamic dispatch is implemented without any array access but uses a simple static binary branch code. We show that this implementation makes it possible to use modern hardware very efficiently. It also allows us to inline more calls even when dynamic dispatch is required. Some more dispatch sites are removed after the type inference algorithm has been performed, if the different branches of a dispatch site lead to the same code.The advantage of this approach is that it greatly speeds up execution time and considerably decreases the amount of generated code.
Efficient type inclusion tests
Authors: Vitek Jan , Horspool R. Nigel , Krall Andreas
Published: November 2005

A type inclusion test determines whether one type is a subtype of another. Efficient type testing techniques exist for single subtyping, but not for languages with multiple subtyping. To date, the fast constant-time technique relies on a binary matrix encoding of the subtype relation with quadratic space requirements. In this paper, we present three new encodings of the subtype relation, the
packed encoding
, the
bit-packed encoding
and the
compact encoding
. These encodings have different characteristics. The bit-packed encoding delivers the best compression rates: on average 85% for real life programs. The packed encoding performs type inclusion tests in only 4 machine instructions. We present a fast algorithm for computing these encoding which runs in less than 13 milliseconds for PE and BPE, and 23 milliseconds for CE on an Alpha processor. Finally, we compare our results with other constant-time type inclusion tests on a suite of 11 large -benchmark hierarchies.
Changing the engine of the car? (panel)
Authors: Coplien Jim , Hohmann Luke , Kerth Norm , Rae-Grant John , Strider Eileen
Published: November 2005

Most software development projects don't practice what is usually considered "proper" software engineering practices: well-documented, traceable requirements do not exist, formal inspections are non-existent, analysis and design inodels are incomplete or not even done at all, and so forth. We know that many of these projects fail, and it is easy to blame the failure of the project on the lack of good software engineering practices ("If we only had well-documented requirements, a complete and thorough test plan, and formal schedules then we would have been successful!")But many projects that do not practice what many consider to be good software engineering practices succeed, and succeed famously. Examples include the startup introducing a revolutionary new product, the skunkworks project of an established firm that succeeds in changing the status quo, and selecting a mission critical application as the first OO application of a group just beginning to make the transition to the new technology.Gaining a deeper understanding of success and failure on software projects is absolutely essential for the continued maturation of our industry, and object technology in particular.
Ephemerons
Authors: Hayes Barry
Published: November 2005

Finalization
occurs when a garbage collector informs an application that an object is "almost collectable." It is used to help an application maintain its invariants. To make finalization more useful, this paper defines "almost collectable" in terms of a new class of objects, called ephemerons. Ephemerons are similar to weak pairs, but an object in an ephemeron's key field may be classed as "almost collectable" even if it is reachable from the epehemeron's value fields.
UML (panel)
Authors: Coleman Derek , Ohnjec Viktor , Artim John , Rivas Erick , Rumbaugh Jim , Wirfs-Brock Rebecca
Published: November 2005

The Unified Method was launched by Grady Booch and Jim Rumbaugh at an OOPSLA'95 Conference Fringe meeting organised by Rational Software Corporation. In 1996 the Unified Method was re-scoped to a notation, and renamed the Unified Modeling Language (UML).Earlier this year, UML was submitted to the Object Management Group for standardisation and has been endorsed by Microsoft, IBM, HP, Platinum Technologies, ObjectTime and many other corporations. No wonder UML is the leading contender as the
de facto
standard notation for object-oriented analysis and design.The panel will take a sanity check, and will go beyond the hype and newsgroup flames and attempt to form an objective view of UML and its prospects.The members of the panel have been working closely with UhL in many different roles, including that of UML language designer, end-user, consultant, CASE tool expert, and object-oriented methodologist. The discussion will focus on how LJML matches up in practice against one of its original. raisons d'etre as "the language of blueprints for software".Specific issues to be addressed include:• What is the advantage of UML over existing OOA/D notations?• Can UML be used on real projects today?• Is the language sufficiently simple, and well-enough defined, to become the
de facto
standard?• Will UML lead to improved OOA/D methods and CASE tools?• What is the importance of the meta-model in UML?
Composite design patterns
Authors: Riehle Dirk
Published: November 2005

Software design patterns are the core abstractions from successful recurring problem solutions in software design. Composite
design patterns
are the core abstractions from successful recurring frameworks. A composite design pattern is a pattern that is best described as the composition of further patterns the integration of which shows a synergy that makes the composition more than just the sum of its parts. This paper presents examples of composite patterns, discusses a role-based analysis and composition technique, and demonstrates that composite patterns extend the pattern idea from single problem solutions to object-oriented frameworks.
Space-efficient implementation of nested parallelism
Authors: Narlikar Girija J. , Blelloch Guy E.
Published: November 2005

Many of today's high level parallel languages support dynamic, fine-grained parallelism. These languages allow the user to expose all the parallelism in the program, which is typically of a much higher degree than the number of processors. Hence an efficient scheduling algorithm is required to assign computations to processors at runtime. Besides having low overheads and good load balancing, it is important for the scheduling algorithm to minimize the space usage of the parallel program. This paper presents a scheduling algorithm that is provably space-efficient and time-efficient for nested parallel languages. In addition to proving the space and time bounds of the parallel schedule generated by the algorithm, we demonstrate that it is efficient in practice. We have implemented a runtime system that uses our algorithm to schedule parallel threads. The results of executing parallel programs on this system show that our scheduling algorithm significantly reduces memory usage compared to previous techniques, without compromising performance.