bluuebunny/crossref_metadata_2025_split huggingface dataset:
Practical predicate dispatch
Authors: Millstein Todd 
Published: November 2005

<i>Predicate dispatch</i> is an object-oriented (OO) language mechanism for determining the method implementation to be invoked upon a message send. With predicate dispatch, each method implementation includes a predicate guard specifying the conditions under which the method should be invoked, and logical implication of predicates determines the method overriding relation. Predicate dispatch naturally unifies and generalizes several common forms of dynamic dispatch, including traditional OO dispatch, multimethod dispatch, and functional-style pattern matching. Unfortunately, prior languages supporting predicate dispatch have had several deficiencies that limit its utility in practice.
We introduce JPred, a backward-compatible extension to Java supporting predicate dispatch. While prior languages with predicate dispatch have been extensions to toy or non-mainstream languages, we show how predicate dispatch can be naturally added to a traditional OO language. While prior languages with predicate dispatch have required the whole program to be available for type-checking and compilation, JPred retains Java's modular typechecking and compilation strategies. While prior languages with predicate dispatch have included special-purpose algorithms for reasoning about predicates, JPred employs general-purpose, off-the-shelf decision procedures. As a result, JPred's type system is more flexible, allowing several useful programming idioms that are spuriously rejected by those other languages. After describing the JPred language and type system, we present a case study illustrating the utility of JPred in a real-world application, including its use in the detection of several errors.
Discovering machine-specific code improvements
Authors: Kessler Peter B. 
Published: November 2005

I have designed and built a compiler construction tool that automates much of the case analysis necessary to exploit special purpose instructions on a target machine. Given a suitable description of the target machine, my analysis identifies instruction sequences that are equivalent to single instructions. During code generation, these equivalences can be used to avoid inefficient instruction sequences in favor of more efficient instructions.
I present a working prototype of the instruction set analyzer needed in the framework outlined by [Giegerich 83]. In contrast to the work presented in [Davidson and Fraser 80, 84], I analyze machine descriptions during compiler construction, rather than analyzing instruction sequences that occur during code generation. [R Kessler 84] describes a system which analyzes machine descriptions during compiler construction, but which which is limited to discovering instructions that are equivalent to instruction sequences of length 2. The techniques presented here can identify instruction sequences of arbitrary length that are equivalent to single instructions.
I have applied this analysis to the descriptions of two machines, and used the results to replace hand-written case analysis routines in an otherwise table-driven code generator [Henry 84].
A customizable substrate for concurrent languages
Authors: Jagannathan Suresh , Philbin Jim 
Published: November 2005

We describe an approach to implementing a wide-range of concurrency paradigms in high-level (symbolic) programming languages. The focus of our discussion is STING, a dialect of Scheme, that supports lightweight threads of control and virtual processors as first-class objects. Given the significant degree to which the behavior of these objects may be customized, we can easily express a variety of concurrency paradigms and linguistic structures within a common framework without loss of efficiency.
Unlike parallel systems that rely on operating system services for managing concurrency, STING implements concurrency management entirely in terms of Scheme objects and procedures. It, therefore, permits users to optimize the runtime behavior of their applications without requiring knowledge of the underlying runtime system.
This paper concentrates on (a) the implications of the design for building asynchronous concurrency structures, (b) organizing large-scale concurrent computations, and (c) implementing robust programming environments for symbolic computing.
Prototyping Fortran-90 compilers for massively parallel machines
Authors: Chen Marina , Cowie James 
Published: November 2005

Massively parallel architectures, and the languages used to program them, are among both the most difficult and the most rapidly-changing subjects for compilation. This has created a demand for new compiler prototyping technologies that allow novel style of compilation and optimization to be tested in a reasonable amount of time.
Using formal specification techniques, we have produced a data-parallel Fortran-90 subset compiler for Thinking Machines' Connection Machine/2 and Connection Machine/5. The prototype produces code from initial Fortran-90 benchmarks demonstrating sustained performance superior to hand-coded Lisp and competitive with Thinking Machines' CM Fortran compiler. This paper presents some new specification techniques necessary to construct competitive, easily retargetable prototype compilers.
The evolution of Lisp
Authors: Steele Guy L. , Gabriel Richard P. 
Published: November 2005

Lisp is the world's greatest programming language—or so its proponents think. The structure of Lisp makes it easy to extend the language or even to implement entirely new dialects without starting from scratch. Overall, the evolution of Lisp has been guided more by institutional rivalry, one-upsmanship, and the glee born of technical cleverness that is characteristic of the “hacker culture” than by sober assessments of technical requirements. Nevertheless this process has eventually produced both an industrial-strength programming language, messy but powerful, and a technically pure dialect, small but powerful, that is suitable for use by programming-language theoreticians.We pick up where McCarthy's paper in the first HOPL conference left off. We trace the development chronologically from the era of the PDP-6, through the heyday of Interlisp and MacLisp, past the ascension and decline of special purpose Lisp machines, to the present era of standardization activities. We then examine the technical evolution of a few representative language features, including both some notable successes and some notable failures, that illuminate design issues that distinguish Lisp from other programming languages. We also discuss the use of Lisp as a laboratory for designing other programming languages. We conclude with some reflections on the forces that have driven the evolution of Lisp.
Improving the performance of runtime parallelization
Authors: Leung Shun-Tak , Zahorjan John 
Published: November 2005

When the inter-iteration dependency pattern of the iterations of a loop cannot be determined statically, compile time parallelization of the loop is not possible. In these cases, runtime parallelization [8] is the only alternative. The idea is to transform the loop into two code fragements: the
inspector
and the
executor
. When the program is run, the inspector examines the iteration dependencies and constructs a parallel schedule. The executor subsequently uses that schedule to carry out the actual computation in parallel.

In this paper, we show how to reduce the overhead of running the inspector through its parallel execution. We describe two related approaches. The first, which emphasizes inspector efficiency, achieves nearly linear speedup relative to a sequential execution of the inspector, but produces a schedule that may be less efficient for the executor. The second technique, which emphasizes executor efficiency, does not in general achieve linear speedup of the inspector, but is guaranteed to produce the best achievable schedule. We present these techniques, show that they are correct, and compare their performance to existing techniques using a set of experiments.
Because in this paper we are optimizing inspector time, but leaving the executor unchanged, the techniques we present have most dramatic effect when the inspector must be run for each invocation of the source loop. In a companion paper [3], we explore techniques that build upon those developed here to also improve executor performance.
Attribute propagation by message passing
Authors: Demers Alan , Rogers Anne , Zadeck Frank Kenneth 
Published: November 2005

The goal of our work is to use the paradigms of syntax-directed editing to perform very sophisticated semantic checking, for example, to check flow-sensitive properties such as whether a variable is necessarily defined before it is used. Semantic checking of this power is much more important than syntax checking because it relieves the programmer of the need to keep track of numerous details as the program grows in complexity.
There has been a great deal of recent work on syntax-directed editing. This work primarily serves the needs of novice programmers: making the task of entering and editing programs easier and less error prone. Most syntax-directed editors guarantee that the program fragment under construction is syntactically correct at all times. Many of them also detect simple semantic errors such as undeclared variables or type errors. Few, however, attempt to perform more semantic analysis than a typical (non-optimizing) compiler.
Relations and attributes
Authors: Horwitz Susan , Teitelbaum Tim 
Published: November 2005

The ability to generate language-based editors depends on the existence of a powerful, language-independent model of editing. A model is proposed in which programs are represented as attributed abstract-syntax trees with an associated relational database. Relations can depend on the state of the attributed tree, and attributes can depend on the values in relations, provided there are no circular dependencies.
The power and the limitations of relational operations are demonstrated with respect to the support of static-semantic checking, anomaly detection, an interrogation facility, and the ability to define alternate views of a program. The advantages of the hybrid system over both the purely relational and purely attribute-based systems are presented, and a prototype implementation of an editor generator is discussed. New algorithms are given for query evaluation and incremental view updating motivated by the efficiency requirements of interactive editing under the defined model.
Cilk
Authors: Blumofe Robert D. , Joerg Christopher F. , Kuszmaul Bradley C. , Leiserson Charles E. , Randall Keith H. , Zhou Yuli 
Published: November 2005

Cilk (pronounced “silk”) is a C-based runtime system for multi-threaded parallel programming. In this paper, we document the efficiency of the Cilk work-stealing scheduler, both empirically and analytically. We show that on real and synthetic applications, the “work” and “critical path” of a Cilk computation can be used to accurately model performance. Consequently, a Cilk programmer can focus on reducing the work and critical path of his computation, insulated from load balancing and other runtime scheduling issues. We also prove that for the class of “fully strict” (well-structured) programs, the Cilk scheduler achieves space, time and communication bounds all within a constant factor of optimal.
The Cilk runtime system currently runs on the Connection Machine CM5 MPP, the Intel Paragon MPP, the Silicon Graphics Power Challenge SMP, and the MIT Phish network of workstations. Applications written in Cilk include protein folding, graphic rendering, backtrack search, and the *Socrates chess program, which won third prize in the 1994 ACM International Computer Chess Championship.
Storage assignment to decrease code size
Authors: Liao Stan , Devadas Srinivas , Keutzer Kurt , Tjiang Steve , Wang Albert 
Published: November 2005

DSP architectures typically provide indirect addressing modes with auto-increment and decrement. In addition, indexing mode is not available, and there are usually few, if any, general-purpose registers. Hence, it is necessary to use address registers and perform address arithmetic to access automatic variables. Subsuming the address arithmetic into auto-increment and auto-decrement modes improves the size of the generated code.
In this paper we present a formulation of the problem of optimal storage assignment such that explicit instructions for address arithmetic are minimized. We prove that for the case of a single address register the decision problem is NP-complete. We then generalize the problem to multiple address registers. For both cases heuristic algorithms are given. Our experimental results indicate an improvement of 3.
Detecting defects in object-oriented designs
Authors: Travassos Guilherme , Shull Forrest , Fredericks Michael , Basili Victor R. 
Published: November 2005

Inspections can be used to identify defects in software artifacts. In this way, inspection methods help to improve software quality, especially when used early in software development. Inspections of software design may be especially crucial since design defects (problems of correctness and completeness with respect to the requirements, internal consistency, or other quality attributes) can directly affect the quality of, and effort required for, the implementation.
We have created a set of “reading techniques” (so called because they help a reviewer to “read” a design artifact for the purpose of finding relevant information) that gives specific and practical guidance for identifying defects in Object-Oriented designs. Each reading technique in the family focuses the reviewer on some aspect of the design, with the goal that an inspection team applying the entire family should achieve a high degree of coverage of the design defects.
In this paper, we present an overview of this new set of reading techniques. We discuss how some elements of these techniques are based on empirical results concerning an analogous set of reading techniques that supports defect detection in requirements documents. We present an initial empirical study that was run to assess the feasibility of these new techniques, and discuss the changes made to the latest version of the techniques based on the results of this study.
Symbolic pointer analysis for detecting memory leaks
Authors: Scholz Berhard , Blieberger Johann , Fahringer Thomas 
Published: November 2005

It is well accepted that pointers are a common source of memory anomalies such as loosing references to dynamic records without deallocating them (also known as memory leaks). This paper presents a novel pointer analysis framework that detects memory leaks by statically analyzing the behavior of programs.
Our approach is based on symbolic evaluation of programs. Symbolic evaluation is an advanced static symbolic analysis that is centered around symbolic variable values, assumptions about and constraints between variable values, and control flow information (path conditions). As part of symbolic evaluation we introduce a new symbolic heap algebra for modeling heap operations. Predicates — defined over the program's input — are derived which allow to detect memory leaks. Our approach goes beyond previous work in the field of statically detecting memory leaks by considering also path conditions which increases the accuracy of our results, symbolically modeling heap data structures and heap operations. Examples are used to illustrate the effectiveness of our approach.
An annotation language for optimizing software libraries
Authors: Guyer Samuel Z. , Lin Calvin 
Published: November 2005

This paper introduces an annotation language and a compiler that together can customize a library implementation for specific application needs. Our approach is distinguished by its ability to exploit high level, domain-specific information in the customization process. In particular, the annotations provide semantic information that enables our compiler to analyze and optimize library operations as if they were primitives of a domain-specific language. Thus, our approach yields many of the performance benefits of domain-specific languages, without the effort of developing a new compiler for each domain.
This paper presents the annotation language, describes its role in optimization, and illustrates the benefits of the overall approach. Using a partially implemented compiler, we show how our system can significantly improve the performance of two applications written using the PLAPACK parallel linear algebra library.
Principled scavenging
Authors: Monnier Stefan , Saha Bratin , Shao Zhong 
Published: November 2005

Proof-carrying code and typed assembly languages aim to minimize the trusted computing base by directly certifying the actual machine code. Unfortunately, these systems cannot get rid of the dependency on a trusted garbage collector. Indeed, constructing a provably type-safe garbage collector is one of the major open problems in the area of certifying compilation.
Building on an idea by Wang and Appel, we present a series of new techniques for writing type-safe stop-and-copy garbage collectors. We show how to use intensional type analysis to capture the contract between the mutator and the collector, and how the same method can be applied to support forwarding pointers and generations. Unlike Wang and Appel (which requires whole-program analysis), our new framework directly supports higher-order funtions and is compatible with separate compilation; our collectors are written in provably type-safe languages with rigorous semantics and fully formalized soundness proofs.
The pointer assertion logic engine
Authors: Møller Anders , Schwartzbach Michael I. 
Published: November 2005

We present a new framework for verifying partial specifications of programs in order to catch type and memory errors and check data structure invariants. Our technique can verify a large class of data structures, namely all those that can be expressed as
graph types
. Earlier versions were restricted to simple special cases such as lists or trees. Even so, our current implementation is as fast as the previous specialized tools.

Programs are annotated with partial specifications expressed in Pointer Assertion Logic, a new notation for expressing properties of the program store. We work in the logical tradition by encoding the programs and partial specifications as formulas in monadic second-order logic. Validity of these formulas is checked by the MONA tool, which also can provide explicit counterexamples to invalid formulas.
To make verification decidable, the technique requires explicit loop and function call invariants. In return, the technique is highly modular: every statement of a given program is analyzed only once.
The main target applications are safety-critical data-type algorithms, where the cost of annotating a program with invariants is justified by the value of being able to automatically verify complex properties of the program.
Metaclasses are first class: The ObjVlisp Model
Authors: Cointe Pierre 
Published: November 2005

This paper shows how an attempt at a uniform and reflective definition resulted in an open-ended system supporting ObjVlisp, which we use to simulate object-oriented language extensions.
We propose to unify Smalltalk classes and their terminal instances. This unification allows us to treat a class as a “first class citizen”, to give a circular definition of the first metaclass, to access to the metaclass level and finally to control the instantiation link. Because each object is an instance of another one and because a metaclass is a real class inheriting from another one, the metaclass links can be created indefinitely.
This uniformity allows us to define the class variables at the metalevel thus suppressing the Smalltalk-80 ambiguity between class variables and instance variables: in our model the instance variables of a class are the class variables of its instances.
Preliminary experience from the dice system a distributed incremantal compiling environment
Authors: Fritzson Peter 
Published: November 2005

Abstracts The DICE system Is a highly Integrated programming environment which provides programmer support in the case where the programming environment resides in a host computer and the program Is running on a target computer that Is connected to the host. Such a system configuration is also suitable for remote debugging and maintenance of production versions of programs that has been installed in a user environment.
The system contains tools such as an screen-oriented structure editor, a statement-level incremental compiler, a screen-oriented debugger and a program database. The debugger uses the same facility for pointing and display as does the editor, and it uses the incremental compiler for insertion of breakpoints and statement evaluation. Most of these tools are automatically generated from compact descriptions.
This paper describes some aspects of a prototype version of the system and gives some preliminary data on the performance. Also, strategies for implementing portable programming environments are discussed and are exemplified by the DiCE system.
An incremental algorithm for software analysis
Authors: Carroll Martin , Ryder Barbara G 
Published: November 2005

In programming environments aimed at “industrial strength” software development, there is a need for software tools which facilitate both design and maintenance. These tools should encourage experimentation with different system configurations which enable designers toa prioriestimate the associated system complexity and judge the ease of accommodating enhancements. Maintainers should be able to check straightforwardly the ramifications of system changes due to enhancements or “bug fixes”. With interprocedural data flow information about the definition and use of global variables and parameters in a software system, tools can be built to perform these tasks.For large, complex systems, efficient methods for interprocedural analysis are necessarily incremental, as a software system is a dynamically evolving entity.Incremental algorithmsupdate current information about a system in response to a change rather than re-calculating the information by re-analyzing the entire system. This paper reports our development of a general purpose incremental data flow analysis algorithm, which is applicable to both intraprocedural and interprocedural domains. It is based on interval analysis, a technique whose observed performance is linear for most programs; under reasonable assumptions about program flow graphs this linearity can be verified [20].
Design characteristics of the WATFOR compiler
Authors: Cowan D. D. , Graham J. W. 
Published: November 2005

About 1960, it became fashionable to introduce computer techniques into many of the courses being taught at the university level. These courses tended to be technically oriented (Engineering, Science, Mathematics), and the language most often used was one of the versions of FORTRAN. Students were introduced to computing by a brief course in FORTRAN, and then were expected to apply their newly-discovered knowledge to the solution of numerous problems related to some discipline. Introducing large numbers of students to computing in this manner created an entirely new type of demand for computer services. These new demands for computer services had to satisfy the following needs.
(i) The programmers were not professionals; thus, the proportion of errors in a given number of written statements was higher than usual.
(ii) The programs themselves were often quite short, usually 30 to 50 statements in length.
(iii) The volume of submitted programs was very high, in the order of hundreds of thousands per day.
(iv) The debugged program tended to be run in production only once, and was set aside as a completed assignment.