bluuebunny/crossref_metadata_2025_split huggingface dataset:
Simple and effective link-time optimization of Modula-3 programs
Authors: Fernández Mary F. 
Published: November 2005

Modula-3 supports development of modular programs by separating an object's interface from its implementation. This separation induces a runtime overhead in the implementation of objects, because it prevents the compiler from having complete information about a program's type hierarchy. This overhead can be reduced at link time, when the entire type hierarchy becomes available. We describe opportunities for link-time optimization of Modula-3, present two link-time optimizations that reduce the runtime costs of Modula-3's opaque types and methods, and show how link-time optimization could provide C++ which the benefits of opaques types at no additional runtime cost.
Our optimization techniques are implemented in mld, a retargetable linker for the MIPS, SPARC, and Intel 486, mld links a machine-independent intermediate code that is suitable for link-time optimization and code generation. Linking intermediate code simplifies implementation of the optimizations and makes it possible to evaluate them on a wide range of architectures. mld's optimizations are effective: they reduce the total number of instructions executed by up to 14% and convert as many as 79% of indirect calls to direct calls.
Escape analysis for object-oriented languages
Authors: Blanchet Bruno 
Published: November 2005

Escape analysis [27, 14, 5] is a static analysis that determines whether the lifetime of data exceeds its static scope.
The main originality of our escape analysis is that it determines precisely the effect of assignments, which is necessary to apply it to object oriented languages with promising results, whereas previous work [27, 14, 5] applied it to functional languages and were very imprecise on assignments. Our implementation analyses the full Java™ Language.
We have applied our analysis to stack allocation and synchronization elimination. We manage to stack allocate 13% to 95% of data, eliminate more than 20% of synchronizations on most programs (94% and 99% on two examples) and get up to 44% speedup (21% on average). Our detailed experimental study on large programs shows that the improvement comes from the decrease of the garbage collection and allocation times than from improvements on data locality [7], contrary to what happened for ML [5].
Role model designs and implementations with aspect-oriented programming
Authors: Kendall Elizabeth A. 
Published: November 2005

This paper describes research in applications of aspect-oriented programming (AOP) as captured in the AspectJ™ language. In particular, it compares object-oriented and aspect-oriented designs and implementations of role models.
Sections 1, 2, and 3 provide background information on role models, object-oriented role model implementations, and aspect-oriented programming, respectively. New aspect-oriented designs for role models are explored in sections 4, 5, and 6.
The base reference for this exploration is the Role Object pattern. Although useful for role models, this pattern introduces some problems at the implementation level, namely object schizophrenia, significant interface maintenance, and no support for role composition. Our research has resulted in alternative aspect-oriented designs that alleviate some of these problems.
Section 7 discusses how an agent framework that implements role models has been partially reengineered with aspects. The reengineering addressed concerns that are orthogonal or cross cut both the core and the role behavior. The aspect oriented redesign significantly reduced code tangling, overall method and module count, and total lines of code. These results and other conclusions are presented in section 8.
Static analysis of large programs (invited talk) (abstract only)
Authors: Das Manuvir 
Published: November 2005

Our research group at Microsoft has spent some effort over the last few years attempting to apply static analysis methods to large application programs (over a million lines of code). In the first part of the talk, I will share some of the insights we have gained along the way. The first insight is that the static analysis method of interest must scale to large programs. It must scale in terms of performance, both running time and memory requirements. The interesting complexity metric is average-case behaviour. The analysis must also scale in terms of the quality of information produced. This metric is hard to measure, and depends on the problem to be solved. The second insight is that large commercial applications differ from the benchmark programs typically used in the literature in many ways beyond sheer size: For instance, they routinely circumvent the type system, they make use of every conceivable language feature, they use large shared libraries, they contain some very large automatically generated functions, they define functions with large numbers of call sites, and they include many indirect call sites. All of these characteristics make analysis hard. In particular, they make the implementation of a scalable analysis an exercise in careful engineering.
In the second part of the talk, I will make the claim that it is possible to develop scalable static analysis methods for large programs, using the following approach: First, implement an efficient algorithm, and carefully engineer it to scale. Important requirements are modularity, a complete parser, and some form of garbage collection. Next, identify the conceptual limitations of the efficient algorithm, and examine the test programs to identify common cases or idioms in the code that expose these limitations. Finally, extend the original algorithm in a principled manner to account for these common cases, without compromising performance. I will use my work on pointer analysis of large programs as an example of this approach. The key insight is that it is possible to identify common idioms in the code that are the bottlenecks for efficient algorithms. A scalable static analysis method can be developed if these idioms can be identified and accommodated.
On the logical foundations of staged computation (invited talk)
Authors: Pfenning Frank 
Published: November 2005

Dividing a computation into stages and optimizing later phases using information from earlier phases is a familiar technique in algorithm design. In the realm of programming languages, staged computation has found two important realizations: partial evaluation and run-time code generation. A priori, these are fundamentally operational concepts, concerned with how a program executes, but not what it computes.
In this talk we provide a logical foundation for staged computation which is consistent with the operational intuition. We concentrate on run-time code generation which is related to modal logic via an interpretation of constructive proofs as programs. This correspondence yields new insights into issues of language design and leads to a static type system in which staging errors become type errors. We sketch the language PML (for Phased ML), whose design has been directly motivated by our foundational reconstruction, and discuss our ongoing compiler construction effort [1; 2; 3; 4].
Machine-adaptable dynamic binary translation
Authors: Ung David , Cifuentes Cristina 
Published: November 2005

Dynamic binary translation is the process of translating and optimizing executable code for one machine to another at runtime, while the program is “executing” on the target machine.
Dynamic translation techniques have normally been limited to two particular machines; a competitor's machine and the hardware manufacturer's machine. This research provides for a more general framework for dynamic translations, by providing a framework based on specifications of machines that can be reused or adapted to new hardware architectures. In this way, developers of such techniques can isolate design issues from machine descriptions and reuse many components and analyses.
We describe our dynamic translation framework and provide some initial results obtained by using this system.
Design and implementation of generics for the .NET Common language runtime
Authors: Kennedy Andrew , Syme Don 
Published: November 2005

The Microsoft.NET Common Language Runtime provides a shared type system, intermediate language and dynamic execution environment for the implementation and inter-operation of multiple source languages. In this paper we extend it with direct support for parametric polymorphism (also known as generics), describing the design through examples written in an extended version of the C# programming language, and explaining aspects of implementation by reference to a prototype extension to the runtime.
Our design is very expressive, supporting parameterized types, polymorphic static, instance and virtual methods, “F-bounded” type parameters, instantiation at pointer and value types, polymorphic recursion, and exact run-time types. The implementation takes advantage of the dynamic nature of the runtime, performing just-in-time type specialization, representation-based code sharing and novel techniques for efficient creation and use of run-time types.
Early performance results are encouraging and suggest that programmers will not need to pay an overhead for using generics, achieving performance almost matching hand-specialized code.
A parallel, real-time garbage collector
Authors: Cheng Perry , Blelloch Guy E. 
Published: November 2005

We describe a parallel, real-time garbage collector and present experimental results that demonstrate good scalability and good real-time bounds. The collector is designed for shared-memory multiprocessors and is based on an earlier collector algorithm [2], which provided fixed bounds on the time any thread must pause for collection. However, since our earlier algorithm was designed for simple analysis, it had some impractical features. This paper presents the extensions necessary for a practical implementation: reducing excessive interleaving, handling stacks and global variables, reducing double allocation, and special treatment of large and small objects. An implementation based on the modified algorithm is evaluated on a set of 15 SML benchmarks on a Sun Enterprise 10000, a 64-way UltraSparc-II multiprocessor. To the best of our knowledge, this is the first implementation of a parallel, real-time garbage collector.
The average collector speedup is 7.5 at 8 processors and 17.7 at 32 processors. Maximum pause times range from 3 ms to 5 ms. In contrast, a non-incremental collector (whether generational or not) has maximum pause times from 10 ms to 650 ms. Compared to a non-parallel, stop-copy collector, parallelism has a 39% overhead, while real-time behavior adds an additional 12% overhead. Since the collector takes about 15% of total execution time, these features have an overall time costs of 6% and 2%.
ESP
Authors: Kumar Sanjeev , Mandelbaum Yitzhak , Yu Xiang , Li Kai 
Published: November 2005

This paper presents the design and implementation of Event-driven State-machines Programming (ESP)—a language for programmable devices. In traditional languages, like C, using event-driven state-machine forces a tradeoff that requires giving up ease of development and reliability to achieve high performance. ESP is designed to provide all of these three properties simultaneously.
ESP provides a comprehensive set of features to support development of compact and modular programs. The ESP compiler compiles the programs into two targets—a C file that can be used to generate efficient firmware for the device; and a specification that can be used by a verifier like SPlN to extensively test the firmware.
As a case study, we reimplemented VMMC firmware that runs on Myrinet network interface cards using ESP. We found that ESP simplifies the task of programming with event-driven state machines. It required an order of magnitude fewer lines of code than the previous implementation. We also found that model-checking verifiers like SPIN can be used to effectively debug the firmware. Finally, our measurements indicate that the performance overhead of using ESP is relatively small.
Composite object support in an object-oriented database system
Authors: Kim Won , Banerjee Jay , Chou Hong-Tai , Garza Jorge F. , Woelk Darrel 
Published: November 2005

Many applications in such domains as computer-aided design require the capability to define, store and retrieve as a single unit a collection of related objects known as a composite object. A composite object explicitly captures and enforces the IS-PART-OF integrity constraint between child and parent pairs of objects in a hierarchical collection of objects. Further, it can be used as a unit of storage and retrieval to enhance the performance of a database system.
This paper provides a formal definition of the semantics of composite objects within an object-oriented data model, and describes their use as units of integrity control, storage and retrieval, and concurrency control in a prototype object-oriented database system we have implemented.
Dimensions of object-based language design
Authors: Wegner Peter 
Published: November 2005

The design space of object-based languages is characterized in terms of objects, classes, inheritance, data abstraction, strong typing, concurrency, and persistence. Language classes (paradigms) associated with interesting subsets of these features are identified and language design issues for selected paradigms are examined. Orthogonal dimensions that span the object-oriented design space are related to non-orthogonal features of real languages. The self-referential application of object-oriented methodology to the development of object-based language paradigms is demonstrated.
Delegation is defined as a generalization of inheritance and design alternatives such as non-strict, multiple, and abstract inheritance are considered. Actors and prototypes are presented as examples of classless (delegation based) languages. Processes are classified by their degree of internal concurrency. The potential inconsistency of object-oriented sharing and distributed autonomy is discussed, suggesting that compromises between sharing and autonomy will be necessary in designing strongly typed object-oriented distributed database languages.
Computer-Aided Software Engineering in a distributed workstation environment
Authors: Leblang David B. , Chase Robert P. 
Published: November 2005

Computer-Aided Software Engineering environments are becoming essential for complex software projects, just as CAD systems have become essential for complex hardware projects. DSEE, the DOMAIN Software Engineering Environment, is a distributed, production quality, software development environment that runs on Apollo workstations. DSEE provides source code control, configuration management, release control, advice management, task management, and user-defined dependency tracking with automatic notification.
DSEE incorporates some of the best ideas from existing systems. This paper describes DSEE, contrasts it other systems, and discusses some of the technical issues involved in the construction of a highly-reliable, safe, efficient, and distributed development environment.
Control flow analysis
Authors: Allen Frances E. 
Published: November 2005

Any static, global analysis of the expression and data relationships in a program requires a knowledge of the control flow of the program. Since one of the primary reasons for doing such a global analysis in a compiler is to produce optimized programs, control flow analysis has been embedded in many compilers and has been described in several papers. An early paper by Prosser [5] described the use of Boolean matrices (or, more particularly, connectivity matrices) in flow analysis. The use of “dominance” relationships in flow analysis was first introduced by Prosser and much expanded by Lowry and Medlock [6]. References [6,8,9] describe compilers which use various forms of control flow analysis for optimization. Some recent developments in the area are reported in [4] and in [7].
The underlying motivation in all the different types of control flow analysis is the need to codify the flow relationships in the program. The codification may be in connectivity matrices, in predecessor-successor tables, in dominance lists, etc. Whatever the form, the purpose is to facilitate determining what the flow relationships are; in other words to facilitate answering such questions as: is this an inner loop?, if an expression is removed from the loop where can it be correctly and profitably placed?, which variable definitions can affect this use?
In this paper the basic control flow relationships are expressed in a directed graph. Various graph constructs are then found and shown to codify interesting global relationships.
Report of evening session protection
Authors: Neumann Peter G. 
Published: November 2005

The session began late following an almost three hour dinner for some of us! (Southern hospitality?) Discussion centered on access control mechanisms in operating systems and/or in languages, weaknesses in the state of the art, and desirabilities for secure systems.
Should protection be specifiable within the base language of a system? Jack Dennis: a resounding “yes”. It is highly desirable to associate protection with accessing. (There was some disagreement here). Barbara Liskov: Some help obtainable from type checking during compilation where privileges can be specified at compile time. (Beware of subsequent modifications). Gio Wiederhold: Subsets of types can be useful here.
System correctness
Authors: Ballard Alan , Tsichritzis Dennis 
Published: November 2005

There is no question that reliability is an important factor in the production and life cycle of software. Logical correctness is the first step towards achieving reliability. While operating systems may be too large to prove correct, in view of the current state of the art, there are often key algorithms and critical properties which are good candidates.
A precise statement of the properties, assumptions, and theorems involved greatly influences the reliability of the program. As a side benefit we get a tremendous understanding of the operation of the programs while trying to prove their correctness. By the time we have stated formally all the properties, assertions and theorems involved, the program is sufficiently analyzed informally to ensure its correctness for all practical purposes.
SPIL
Authors: Liskov Barbara H. , Smith Leroy A. 
Published: November 2005

Structured programming is gaining wide acceptance as a technique for increasing the reliability and understandability of software. Nowhere is the need for better software felt more keenly than in the area of systems programming. In the near future it is likely that systems will be programmed in structured programming languages, just as systems have been programmed in higher level languages in the past.
This paper describes SPIL: a structured programming language intended to be used for system design and implementation. The paper discusses how the objectives of structured programming and system programming may be realized in a programming language, and delineates the influence of the objectives on the design of SPIL. The most important features of the language are briefly described. The paper concludes by evaluating SPIL as a language for system design and implementation.
A SIMPL distributed operating system and its formal definition
Authors: Noonan R. , Basili V. , Hamlet R. , Lay M. , Mills D. , Turner J. , Zelkowitz M. 
Published: November 2005

In recent years there has been a phenomenal growth of interest in networks of computers sharing both data and programs. For example, Cmdr. Grace Hopper has advocated a hierarchical network of minicomputers to perform the data processing function in which the tasks to be done would be distributed over the network, with only summary or extract information being passed from one level to another. While the hardware exists to build such a network, the software mechanisms to effectively (from both a time and cost viewpoint) control such a network have not yet been developed.
At the Computer Science Center of the University of Maryland a distributed operating system, which is independent of the specific number and hardware of the particular computers it is running on, is being developed and implemented. Supporting this project is the development of two linguistic tools: the design and implementation of a systems programming language called SIMPL and the use of formal semantics in the specification of both SIMPL and the distributed operating system. So far, each of these three elements has had a considerable effect on the others.
On programming parallel computers
Authors: Lamport Leslie 
Published: November 2005

In this paper, I will make some general observations about how computers should be programmed, and how programs should be compiled. I will restrict my attention to programming computers to solve numerical analysis problems, although most of my remarks can be applied to other problem areas as well. My primary concern is for large parallel computers. However, I will show that parallelism is not a major issue, and I will not restrict the discussion to any single type of computer architecture.
The paper is a very general one, and I will make few specific proposals for language or compiler design. Instead, I will examine the fundamental nature of the programming/compiling process, how this process is done now, and how it should be done in the future. Few of my observations will be new or original. However, a careful analysis will lead to a somewhat surprising conclusion: a higher level programming language is needed both to reduce programming costs and also to obtain more efficient programs. The analysis will also provide some useful ideas for designing a higher level language and compiling efficient code from it.
Problem formulation using array processing techniques
Authors: Evans D. J. 
Published: November 2005

This paper outlines the evolution of array processing computational techniques and systems and briefly discusses the important concepts of the software and programming strategies which enable these systems to be used effectively.
For very large problems, the advantages of parallel processing techniques are stressed and the use of a mathematical programming array language outlined for removing some of the arbitrariness from the problem formulation and programming stages of solving partial differential equations. The purpose of the proposed approach is to eliminate errors in the logical formulation early in the design of a large scientific program and hence prevent many of the logical errors that can creep into a program because of its sheer size and complexity. The discussion includes the solution of both boundary and initial value scientific problems using an approach in which APL augments FORTRAN in the problem formulation stage.