bluuebunny/crossref_metadata_2025 huggingface dataset:
Change cases
Authors: Ecklund Earl F. , Delcambre Lois M. L. , Freiling Michael J.
Published: November 2005

Evolution of software systems is prompted by all sorts of changes. This paper demonstrates how the
use case
, a well known construct in object-oriented analysis, is adapted to form the
change case
, to identify and articulate anticipated system changes. A change case provides the ability to identify and incorporate expected future change into a design to enhance the long-term robustness of that design. In this paper, we define change cases and demonstrate how change cases are captured by the analyst. We present examples to illustrate how change cases can influence present system design and point the way toward designs that more easily accommodate expected future changes. Change cases can be effectively employed in the context of any methodology that supports use cases and traceability links.
Using role components in implement collaboration-based designs
Authors: VanHilst Michael , Notkin David
Published: November 2005

In this paper we present a method of code implementation that works in conjunction with collaboration and responsibility based analysis modeling techniques to achieve better code reuse and resilience to change. Our approach maintains a closer mapping from responsibilities in the analysis model to entities in the implementation. In so doing, it leverages the features of flexible design and design reuse found in collaboration-based design models to provide similar adaptability and reuse in the implementation. Our approach requires no special development tools and uses only standard features available in the C++ language. In an earlier paper we described the basic mechanisms used by our approach and discussed its advantages in comparison to the framework approach. In this paper we show how our approach combines code and design reuse, describing specific techniques that can be used in the development of larger applications.
Semantic-based visualization for parallel object-oriented programming
Authors: Attali Isabelle , Caromel Denis , Ehmety Sidi O. , Lippi Sylvain
Published: November 2005

We present a graphical environment for parallel object-oriented programming. It provides visual tools to develop and debug object-oriented programs as well as parallel or concurrent systems. This environment was derived from a structural operational semantics of an extension of the Eiffel language, Eiffel//. Object-related features of the language (inheritance, polymorphism) are formalized using a big-step semantics, while the interleaving model of concurrency is expressed with small-step semantics.Without user instrumentation, the interactive environment proposes features such as step-by-step animated executions, graphical visualization of object and process topology, futures and pending requests, control of interleaving, deadlock detection.
Translation
Authors: Booch Grady , Fraser Steven , Martin Robert C. , Mellor Steven J. , Lee Michael , Garone Steven , Fowler Martin , Schmidt Douglas C. , Lenzi Marie
Published: November 2005

In the realm of OO methodologies there are two major schools of thought. Both schools claim to define mechanisms whereby software applications can be created that are reusable, maintainable, and robust. Moreover, both schools claim to use abstraction as a key mechanism for achieving these benefits. At issue is whether or not these two schools are fundamentally different, or just variations on an object-oriented theme.Shlaer and Mellor have dubbed one of these schools "Translational". In the translational approach, two models are created. One is an abstract model of the application domain which is devoid of any design dependencies. The other model is an abstract model of the design which is devoid of any application dependencies. These two models are composed automatically to yield the code for the system.The other school - supported by Booch, Rumbaugh, Jacobson, and Martin - views the architecture of a system from several different perspectives of abstraction, e.g. logical, physical. These abstractions typically form a layer; abstractions in the logical sense manifest themselves as individual classes as well as collaborations of classes. There may be one layered model, at different layers of abstraction, or, especially given the Objectory view point, there may be multiple models, with an analysis model that's nearly independent from the design model.The panel will explore:• Is there a seamless transition between analysis and design?• Should there be a single model or should there be two - one for the analysis and one for the design?• If there are two models, how are they "bridged"?• What, if any, are the differences in process between the two schools?• How does architecture manifest itself!• Is there, in fact, a real difference between the two schools of thought?As a result of this exploration, we hope to answer the question: Is translation a myth or is it a reality?
Coping with deeply nested control structures
Authors: Perkins G R , Norman R W , Danicic S
Published: November 2005

Over the past three or four years SIGPLAN Notices has published a number of papers on the problem of deeply nested IF-THEN-ELSE structures. We maintain that the current editorial ban on proposals for new control structures is correct, not only for reasons of space in SIGPLAN Notices, but on the grounds that programmers (like any other workers) should resist the temptation to blame their tools when they come up with poor products.Here, we briefly indicate a few techniques for dealing with deeply nested structures, and suggest that working programmers develop other such techniques and publish papers about them, rather than merely ask the language designers for yet more constructs.
OBJEKT—a persistent object store with an integrated garbage collector
Authors: Harland D M , Beloff B
Published: November 2005

This paper describes OBJEKT, a single-level persistent storage system designed for the REKURSIV architecture.It will be shown that OBJEKT can be microcoded to implement "objects" efficiently, and that data integrity can be guaranteed by provision of an object oriented instruction set. Particular attention will be paid to its facilities for type and range checking, to its object by- object paging strategy and to ways of enhancing parallelism during garbage collection.
Synchronization and communication in the T3E multiprocessor
Authors: Scott Steven L.
Published: November 2005

This paper describes the synchronization and communication primitives of the Cray T3E multiprocessor, a shared memory system scalable to 2048 processors. We discuss what we have learned from the T3D project (the predecessor to the T3E) and the rationale behind changes made for the T3E. We include performance measurements for various aspects of communication and synchronization.The T3E augments the memory interface of the DEC 21164 microprocessor with a large set of explicitly-managed, external registers (E-registers). E-registers are used as the source or target for all remote communication. They provide a highly pipelined interface to global memory that allows dozens of requests per processor to be outstanding. Through E-registers, the T3E provides a rich set of atomic memory operations and a flexible, user-level messaging facility. The T3E also provides a set of virtual hardware barrier/eureka networks that can be arbitrarily embedded into the 3D torus interconnect.
Compiler-based prefetching for recursive data structures
Authors: Luk Chi-Keung , Mowry Todd C.
Published: November 2005

Software-controlled data prefetching offers the potential for bridging the ever-increasing speed gap between the memory subsystem and today's high-performance processors. While prefetching has enjoyed considerable success in array-based numeric codes, its potential in pointer-based applications has remained largely unexplored. This paper investigates compiler-based prefetching for pointer-based applications---in particular, those containing recursive data structures. We identify the fundamental problem in prefetching pointer-based data structures and propose a guideline for devising successful prefetching schemes. Based on this guideline, we design three prefetching schemes, we automate the most widely applicable scheme (
greedy prefetching
) in an optimizing research compiler, and we evaluate the performance of all three schemes on a modern superscalar processor similar to the MIPS R10000. Our results demonstrate that compiler-inserted prefetching can significantly improve the execution speed of pointer-based codes---as much as 45% for the applications we study. In addition, the more sophisticated algorithms (which we currently perform by hand, but which might be implemented in future compilers) can improve performance by as much as twofold. Compared with the only other compiler-based pointer prefetching scheme in the literature, our algorithms offer substantially better performance by avoiding unnecessary overhead and hiding more latency.
Improving cache performance with balanced tag and data paths
Authors: Peir Jih-Kwon , Hsu Windsor W. , Young Honesty , Ong Shauchi
Published: November 2005

There are two concurrent paths in a typical cache access --- one through the data array and the other through the tag array. The path through the data array drives the selected set out of the array. The path through the tag array determines cache hit/miss and, for set-associative caches, selects the appropriate line from within the selected set. In both direct-mapped and set-associative caches, the path through the tag array is significantly longer than that through the data array. In this paper, we propose a path balancing technique help match the delays of the tag and data paths. The basic idea behind this technique is to employ a separate subset of the tag array to decouple the one-to-one relationship between address tags and cache lines so as to achieve a design that provides higher performance. Performance evaluation using both TPC-C and SPEC92 benchmarks shows that this path balancing technique offers impressive improvements in overall system performance over conventional cache designs. For TPC-C, improvements in the range of 6% to 28% are possible.
Design and implementation of a C-based language for distributed real-time systems
Authors: Rizk A , Halsall F
Published: November 2005

This paper describes the design and implementation of a concurrent programming language suitable for use with real-time distributed systems. The language, MC, is an extension of the language C with some of the concrrency features of ADA. The implementation provides portability and simplicity by assuming a basic C compiler for its compilation and a minimal semaphore-based run-time support kernel.
Software pipelining showdown
Authors: Ruttenberg John , Gao G. R. , Stoutchinin A. , Lichtenstein W.
Published: November 2005

This paper is a scientific comparison of two code generation techniques with identical goals --- generation of the best possible software pipelined code for computers with instruction level parallelism. Both are variants of
modulo scheduling
, a framework for generation of software pipelines pioneered by Rau and Glaser [RaG181], but are otherwise quite dissimilar.One technique was developed at Silicon Graphics and is used in the MIPSpro compiler. This is the production compiler for SGI's systems which are based on the MIPS R8000 processor [Hsu94]. It is essentially a branch--and--bound enumeration of possible schedules with extensive pruning. This method is heuristic because of the way it prunes and also because of the interaction between register allocation and scheduling.The second technique aims to produce optimal results by formulating the scheduling and register allocation problem as an integrated integer linear programming (
ILP
1
) problem. This idea has received much recent exposure in the literature [AlGoGa95, Feautrier94, GoAlGa94a, GoAlGa94b, Eichenberger95], but to our knowledge all previous implementations have been too preliminary for detailed measurement and evaluation. In particular, we believe this to be the first published measurement of runtime performance for ILP based generation of software pipelines.A particularly valuable result of this study was evaluation of the heuristic pipelining technology in the SGI compiler. One of the motivations behind the McGill research was the hope that optimal software pipelining, while not in itself practical for use in production compilers, would be useful for their evaluation and validation. Our comparison has indeed provided a quantitative validation of the SGI compiler's pipeliner, leading us to increased confidence in both techniques.
Catching bugs in the web of program invariants
Authors: Flanagan Cormac , Flatt Matthew , Krishnamurthi Shriram , Weirich Stephanie , Felleisen Matthias
Published: November 2005

MrSpidey is a user-friendly, interactive static debugger for Scheme. A static debugger supplements the standard debugger by analyzing the program and pinpointing those program operations that may cause run-time errors such as dereferencing the null pointer or applying non-functions. The program analysis of MrSpidey computes value set descriptions for each term in the program and constructs a value flow graph connecting the set descriptions. Using the set descriptions, MrSpidey can identify and highlight potentially erroneous program operations, whose cause the programmer can then explore by selectively exposing portions of the value flow graph.
Static detection of dynamic memory errors
Authors: Evans David
Published: November 2005

Many important classes of bugs result from invalid assumptions about the results of functions and the values of parameters and global variables. Using traditional methods, these bugs cannot be detected efficiently at compile-time, since detailed cross-procedural analyses would be required to determine the relevant assumptions. In this work, we introduce annotations to make certain assumptions explicit at interface points. An efficient static checking tool that exploits these annotations can detect a broad class of errors including misuses of null pointers, uses of dead storage, memory leaks, and dangerous aliasing. This technique has been used successfully to fix memory management problems in a large program.
Simple garbage-collector-safety
Authors: Boehm Hans-J.
Published: November 2005

A conservative garbage collector can typically be used with conventionally compiled programs written in C or C++. But two safety issues must be considered. First, the source code must not hide pointers from the garbage collector. This primarily requires stricter adherence to existing restrictions in the language definition. Second, we must ensure that the compiler will not perform transformations that invalidate this requirement.We argue that the same technique can be used to address both issues. We present an algorithm for annotating source or intermediate code to either check the validity of pointer arithmetic in the source, or to guarantee that under minimal, clearly defined assumptions about the compiler, the optimizer cannot "disguise" pointers. We discuss an implementation based on a preprocessor for the GNU C compiler (gcc), and give some measurements of program slow down.
Optimizing ML with run-time code generation
Authors: Lee Peter , Leone Mark
Published: November 2005

We describe the design and implementation of a compiler that automatically translates ordinary programs written in a subset of ML into code that generates native code at run time. Run-time code generation can make use of values and invariants that cannot be exploited at compile time, yielding code that is often superior to statically optimal code. But the cost of optimizing and generating code at run time can be prohibitive. We demonstrate how compile-time specialization can reduce the cost of run-time code generation by an order of magnitude without greatly affecting code quality. Several benchmark programs are examined, which exhibit an average cost of only six cycles per instruction generated at run time.
Realistic compilation by partial evaluation
Authors: Sperber Michael , Thiemann Peter
Published: November 2005

Two key steps in the compilation of strict functional languages are the conversion of higher-order functions to data structures (
closures
) and the transformation to tail-recursive style. We show how to perform both steps at once by applying first-order offline partial evaluation to a suitable interpreter. The resulting code is easy to transliterate to low-level C or native code. We have implemented the compilation to C; it yields a performance comparable to that of other modern Scheme-to-C compilers. In addition, we have integrated various optimizations such as constant propagation, higher-order removal, and arity raising simply by modifying the underlying interpreter. Purely first-order methods suffice to achieve the transformations. Our approach is an instance of semantics-directed compiler generation.
Replay for concurrent non-deterministic shared-memory applications
Authors: Russinovich Mark , Cogswell Bryce
Published: November 2005

Replay of shared-memory program execution is desirable in many domains including cyclic debugging, fault tolerance and performance monitoring. Past approaches to repeatable execution have focused on the problem of re-executing the shared-memory access patterns in parallel programs. With the proliferation of operating system supported threads and shared memory for uniprocessor programs, there is a clear need for efficient replay of concurrent applications. The solutions for parallel systems can be performance prohibitive when applied to the uniprocessor case. We present an algorithm, called the repeatable scheduling algorithm, combining scheduling and instruction counts to provide an invariant for efficient, language independent replay of concurrent shared-memory applications. The approach is shown to have trace overheads that are independent of the amount of sharing that takes place. An implementation for cyclic debugging on Mach 3.0 is evaluated and benchmarks show typical performance overheads of around 10%. The algorithm implemented is compared with optimal event-based tracing and shown to do better with respect to the number of events monitored or number of events logged, in most cases by several orders of magnitude.
A new framework for exhaustive and incremental data flow analysis using DJ graphs
Authors: Sreedhar Vugranam C. , Gao Guang R. , Lee Yong-Fong
Published: November 2005

We present a new elimination-based framework for exhaustive and incremental data flow analysis using the DJ graph representation of a program. Unlike the previous approaches to elimination-based incremental data flow analysis, our approach can handle arbitrary non-structural and structural changes to program flowgraphs, including those causing irreducibility. We show how our approach is related to (iterated) dominance frontiers, and exploit this relationship to establish the complexity of our exhaustive analysis and to aid the design of our incremental analysis.
A framework for generalized control dependence
Authors: Bilardi Gianfranco , Pingali Keshav
Published: November 2005

We generalize the notion of
dominance
by defining a generalized dominance relation with respect to a set of paths in the control flow graph
G
= (
V, E
). This new definition leads to a generalized notion of
control dependence
, which includes
standard control dependence
and
weak control dependence
as special cases.If the set of paths underlying a generalized dominance relation satisfies some natural closure conditions, that dominance relation is tree-structured. Given this tree, the corresponding control dependence relation can be computed optimally by reduction to the
Roman Chariots Problem
, which we have developed previously for computing standard control dependence. More precisely, given linear preprocessing time and space, we can answer the (generalized version of the) so called cd, conds, and cdequiv queries in time proportional to the output of the query.To illustrate the utility of the framework, we show how weak control dependence can be computed optimally in
O
(|
E
|) preprocessing space and time. This improves the
O
(|
V
|
3
) time required by the best previous algorithm for this problem.
DDD—a free graphical front-end for UNIX debuggers
Authors: Zeller Andreas , Lütkehaus Dorothea
Published: November 2005

The Data Display Debugger (DDD) is a novel graphical user interface to GDB and DBX, the popular UNIX debuggers. Besides "usual" features such as viewing source texts and breakpoints, DDD provides a
graphical data display
, where data structures are displayed as graphs. A simple mouse click dereferences pointers or reveals structure contents. Complex data structures can be explored incrementally and interactively, using automatic layout if preferred. Each time the program stops, the data display reflects the current variable values. DDD has been designed to compete with well-known commercial debuggers; however, it is free software, protected by the GNU general public license. In this paper, we give a quick presentation of DDD and describe its architecture and basic functionality from a technical point of view.
Position statements on strategic directions for research on programming languages
Authors: Hankin Chris , Nielson Hanne Riis , Palsberg Jens
Published: November 2005

One of the working groups at the workshop on
Strategic Directions in Computing Research
was concerned with
Programming Languages
. We summarise the strategic directions identified by the group and we introduce 16 of the position statements that formed the basis for the report. These statements can then be found at the following pages.
Program analysis
Authors: Cousot Patrick
Published: November 2005

Program analysis should evolve from a disparate collection of methods and algorithms to a mature discipline founded on a well-established methodology. Abstract interpretation can be used as a basis for such a methodology.
Program analysis for software engineering
Authors: Le Métayer Daniel
Published: November 2005

In order to play a bigger role in software engineering tools, static analysis techniques must take into account the specific needs of this application area, in particular in terms of interaction with the user and scalability. This new perspective requires a reexamination of the field of static program analysis both internally and in connection with related areas like theorem proving and debugging.
Challenges in type systems research
Authors: Odersky Martin
Published: November 2005

Type systems are one backbones of programming language design and implementation. Current research addresses questions in fields as diverse as mathematical logic, program analysis, and human factors engineering. Some of the future challenges for the field are: increasing the expressiveness of typed programming languages, broadening the information carried by types, and making type systems amenable to user definition and customization.
A position paper on compile-time program analysis
Authors: Ryder Barbara G.
Published: November 2005

Current challenges to the compile-time analysis research community include unifying the nomenclature in program analysis, embedding analyses in practical software tools, influencing programming language design to allow analysis, and adapting analyses to the blend of architectures, languages and operating systems common in modern software. These challenges must be met to ensure that compile-time analyses will continue to be of practical benefit.
The design and implementation of a program development system based on rewriting method
Authors: Yongquiang Sun , Kai Lin , Li Shen
Published: November 2005

In this paper, we present a program development system based on rewriting method with the goal of providing an powerful tool for automatic software development and rapid prototyping. New mechanisms for defining constrained types and optimal rules are introduced to functional programming languages to achieve strong expressiveness. The enhanced functional programming language is combined with an algebraic specification language. Thus, the design from specification to program can be supported, and the efficiency and flexibility of programming can also be improved. In this system, both static and dynamic techniques are used to deal with constrained type check. All function definitions, computation constraints and optimal rules are regarded as rewriting rules. In order to provide a strong support for a large group of TRSs which may be neither terminating nor orthogonal, we propose a method using structure measure to decide TRSs' confluences. Based on this method, we present a partial completion algorithm to generate a rewriting model from a specification. Depending on term rewriting system, the mixed language system computes with parallel outermost and needed reduction. We explain the principles and implementation techniques in detail, some examples are provided.
Conservative pretty printing
Authors: Ruckert Martin
Published: November 2005

The main purpose of the pretty printing tool, presented here, is not so much the complete reformating of a program but is described better as finding and correcting formating errors.A set of relations is given describing the proper alignment of a piece of code in accordance with its syntactic structure. It is complemented by a simple algorithm to change any given source code to satisfy these relations.The relations are flexible enough to allow a variety of different formating styles while rejecting formating errors, i.e. code that is not formated according to its syntactic structure.Various examples illustrate the ideas, the problems, the goals, and the achievements.
Simple translation of goal-directed evaluation
Authors: Proebsting Todd A.
Published: November 2005

This paper presents a simple, powerful and flexible technique for reasoning about and translating the goal-directed evaluation of programming language constructs that either succeed (and generate sequences of values) or fail. The technique generalizes the
Byrd Box
, a well-known device for describing Prolog backtracking.
Incremental analysis of real programming languages
Authors: Wagner Tim A. , Graham Susan L.
Published: November 2005

A major research goal for compilers and environments is the automatic derivation of tools from formal specifications. However, the formal model of the language is often inadequate; in particular, LR(
k
) grammars are unable to describe the natural syntax of many languages, such as C
++
and Fortran, which are inherently non-deterministic. Designers of batch compilers work around such limitations by combining generated components with ad hoc techniques (for instance, performing partial type and scope analysis in tandem with parsing). Unfortunately, the complexity of
incremental
systems precludes the use of batch solutions. The inability to generate incremental tools for important languages inhibits the widespread use of language-rich interactive environments.We address this problem by extending the language model itself, introducing a program representation based on
parse dags
that is suitable for both batch and incremental analysis. Ambiguities unresolved by one stage are retained in this representation until further stages can complete the analysis, even if the reaolution depends on further actions by the user. Representing ambiguity explicitly increases the number and variety of languages that can be analyzed incrementally using existing methods.To create this representation, we have developed an efficient incremental parser for general context-free grammars. Our algorithm combines Tomita's generalized LR parser with reuse of entire subtrees via state-matching. Disambiguation can occur statically, during or after parsing, or during semantic analysis (using existing incremental techniques); program errors that preclude disambiguation retsin multiple interpretations indefinitely. Our representation and analyses gain efficiency by exploiting the local nature of ambiguities: for the S
PEC
95 C programs, the explicit representation of ambiguity requires only 0.5% additional space and less than 1% additional time during reconstruction.
Dynamic feedback
Authors: Diniz Pedro C. , Rinard Martin C.
Published: November 2005

This paper presents dynamic feedback, a technique that enables computations to adapt dynamically to different execution environments. A compiler that uses dynamic feedback produces several different versions of the same source code; each version uses a different optimization policy. The generated code alternately performs sampling phases and production phases. Each sampling phase measures the overhead of each version in the current environment. Each production phase uses the version with the least overhead in the previous sampling phase. The computation periodically resamples to adjust dynamically to changes in the environment.We have implemented dynamic feedback in the context of a parallelizing compiler for object-based programs. The generated code uses dynamic feedback to automatically choose the best synchronization optimization policy. Our experimental results show that the synchronization optimization policy has a significant impact on the overall performance of the computation, that the best policy varies from program to program, that the compiler is unable to statically choose the best policy, and that dynamic feedback enables the generated code to exhibit performance that is comparable to that of code that has been manually tuned to use the best policy. We have also performed a theoretical analysis which provides, under certain assumptions, a guaranteed optimality bound for dynamic feedback relative to a hypothetical (and unrealizable) optimal algorithm that uses the best policy at every point during the execution.
Spill code minimization via interference region spilling
Authors: Bergner Peter , Dahl Peter , Engebretsen David , O'Keefe Matthew
Published: November 2005

Many optimizing compilers perform global register allocation using a Chaitin-style graph coloring algorithm. Live ranges that cannot be allocated to registers are spilled to memory. The amount of code required to spill the live range depends on the spilling heuristic used. Chaitin's spilling heuristic offers some guidance in reducing the amount of spill code produced. However, this heuristic does not allow the partial spilling of live ranges and the reduction in spill code is limited to a local level. In this paper, we present a global technique called
interference region
spilling that improves the spilling granularity of any local spilling heuristic. Our technique works above the local spilling heuristic, limiting the normal insertion of spill code to a portion of each spilled live range. By partially spilling live ranges, we can achieve large reductions in dynamically executed spill code; up to 75% in some cases and an average of 33.6% across the benchmarks tested.
Fine-grain multithreading with minimal compiler support—a cost effective approach to implementing efficient multithreading languages
Authors: Taura Kenjiro , Yonezawa Akinori
Published: November 2005

It is difficult to map the execution model of multithreading languages (languages which support fine-grain dynamic thread creation) onto the single stack execution model of C. Consequently, previous work on efficient multithreading uses elaborate frame formats and allocation strategy, with compilers customized for them. This paper presents an alternative cost-effective implementation strategy for multithreading languages which can maximally exploit current sequential C compilers. We identify a set of primitives whereby efficient dynamic thread creation and switch can be achieved and clarify implementation issues and solutions which work under the stack frame layout and calling conventions of current C compilers. The primitives are implemented as a C library and named StackThreads. In StackThreads, a thread creation is done just by a C procedure call, maximizing thread creation performance. When a procedure suspends an execution, the context of the procedure, which is roughly a stack frame of the procedure, is saved into heap and resumed later. With StackThreads, the compiler writer can straightforwardly translate sequential constructs of the source language into corresponding C statements or expressions, while using StackThreads primitives as a blackbox mechanism which switches execution between C procedures.
Systematic realisation of control flow analyses for CML
Authors: Gasser Kirsten L. Solberg , Nielson Flemming , Nielson Hanne Riis
Published: November 2005

We present a methodology for the systematic realisation of control flow analyses and illustrate it for Concurrent ML. We start with an abstract
specification
of the analysis that is next proved semantically sound with respect to a traditional small-step operational semantics; this result holds for terminating w well as non-terminating programs. The analysis is defined coinductively and it is shown that all programs have a least analysis result (that is indeed the best one). To realise the analysis we massage the specification in three stages: (i) to explicitly record reachability of subexpressions, (ii) to be defined in a syntax-directed manner, and (iii) to generate a set of constraints that subsequently can be solved by standard techniques. We prove equivalence results between the different versions of the analysis; in particular it follows that the least solution to the constraints generated will be the least analysis result also to the initial specification.
Lambda-splitting
Authors: Blume Matthias , Appel Andrew W.
Published: November 2005

We describe an algorithm for automatic inline expansion across module boundaries that works in the presence of higher-order functions and free variables; it rearranges bindings and scopes as necessary to move nonexpansive code from one module to another. We describe---and implement---the algorithm as transformations on λ-calculus. Our inliner interacts well with separate compilation and is efficient, robust, and practical enough for everyday use in the SML/NJ compiler. Inlining improves performance by 4--8% on existing code, and makes it possible to use much more data abstraction by consistently eliminating penalties for modularity.
A practical subtyping system for Erlang
Authors: Marlow Simon , Wadler Philip
Published: November 2005

We present a type system for the programming language Erlang. The type system supports subtyping and declaration-free recursive types, using subtyping constraints. Our system is similar to one explored by Aiken and Wimmers, though it sacrifices expressive power in favour of simplicity. We cover our techniques for type inference, type simplification, and checking when an inferred type conforms to a user-supplied type signature, and report on early experience with our prototype.
Structuring graphical paradigms in TkGofer
Authors: Claessen Koen , Vullinghs Ton , Meijer Erik
Published: November 2005

In this paper we describe the implementation of several graphical programming paradigms (Model View Controller, Fudgets, and Functional Animations) using the GUI library TkGofer. This library relies on a combination of monads and multiple-parameter type classes to provide an abstract, type safe interface to Tcl/Tk. We show how choosing the right abstractions makes the given implementations surprisingly concise and easy to understand.
Functional reactive animation
Authors: Elliott Conal , Hudak Paul
Published: November 2005

Fran
(Functional Reactive Animation) is a collection of data types and functions for composing richly interactive, multimedia animations. The key ideas in Fran are its notions of
behaviors
and
events
. Behaviors are time-varying, reactive values, while events are sets of arbitrarily complex conditions, carrying possibly rich information. Most traditional values can be treated as behaviors, and when images are thus treated, they become animations. Although these notions are captured as data types rather than a programming language, we provide them with a denotational semantics, including a proper treatment of real time, to guide reasoning and implementation. A method to effectively and efficiently perform
event detection
using
interval analysis
is also described, which relies on the partial information structure on the domain of event times. Fran has been implemented in Hugs, yielding surprisingly good performance for an interpreter-based system. Several examples are given, including the ability to describe physical phenomena involving gravity, springs, velocity, acceleration, etc. using ordinary differential equations.
Automatic management of operating-system resources
Authors: Shivers Olin
Published: November 2005

One of the attractive features of functional programming languages is that they provide automatic management of the store, in the form of garbage collection. However, the benefits of automatic resource management can be applied to other resources as well. Scsh, a systems-programming dialect of Scheme, provides automatic resource management for operating-systems structures, notably processes, I/O channels, and signal events. This kind of automatic management extends the benefits of garbage collection---modularity, robustness, simplicity, and clarity---to new sets of objects in programming, and also gives us hints as to how operating systems should be structured from the perspective of functional programming languages.
The measured cost of copying garbage collection mechanisms
Authors: Hicks Michael W. , Moore Jonathan T. , Nettles Scott M.
Published: November 2005

We examine the costs and benefits of a variety of copying garbage collection (GC) mechanisms across multiple architectures and programming languages. Our study covers both low-level object representation and copying issues as well as the mechanisms needed to support more advanced techniques such as generational collection, large object spaces, and type segregated areas.Our experiments are made possible by a novel performance analysis tool,
Oscar
. Oscar allows us to capture snapshots of programming language heaps that may then be used to replay garbage collections. The replay program is self-contained and written in C, which makes it easy to port to other architectures and to analyze with standard performance analysis tools. Furthermore, it is possible to study additional programming languages simply by instrumenting existing implementations to capture heap snapshots.In general, we found that careful implementation of GC mechanisms can have a significant benefit. For a simple collector, we measured improvements of as much as 95%. We then found that while the addition of advanced features can have a sizeable overhead (up to 15%), the net benefit is quite positive, resulting in additional gains of up to 42%. We also found that results varied depending upon the platform and language. Machine characteristics such as cache arrangements, instruction set (RISC/CISC), and register pool were important. For different languages, average object size seemed to be most important.The results of our experiments demonstrate the usefulness of a tool like Oscar for studying GC performance. Without much overhead, we can easily identify areas where programming language implementors could collaborate with GC implementors to improve GC performance.
Partial evaluation and separate compilation
Authors: Heldal Rogardt , Hughes John
Published: November 2005

Hitherto all partial evaluators have processed a complete program to produce a complete residual program. We are interested in treating programs as collections of modules which can be processed independently: 'separate partial evaluation', so to speak. In this paper we still assume that the
original program
is processed in its entirety, but we show how to specialise it to the static data bit-by-bit, generating a different module for each bit. When the program to be specialised is an interpreter, this corresponds to specialising it to one module of its object language at a time: each module of the object language gives rise to one module of the residual program.
Partial evaluation of call-by-value λ-calculus with side-effects
Authors: Asai Kenichi , Masuhara Hidehiko , Yonezawa Akinori
Published: November 2005

We present a framework of an online partial evaluator for a call-by-value λ-calculus with destructive updates of data structures. It properly and correctly specializes expressions that contain side-effects, while preserving pointer equality, which is an important property for programs using updates. Our partial evaluator uses a side-effect analysis to extract immutable data structures and then performs an online specialization using preactions. Once mutable and immutable data structures are separated, partial evaluation is done in such a way that accesses to immutable ones are performed at specialization time, while accesses to mutable ones are residualized. For the correct residualization of side-effecting operations, preactions are used to solve various issues, including code elimination, code duplication, and execution order preservation. The preaction mechanism also enables us to reduce expressions that were residualized when the conventional let-expression approach of Similix was used. The resulting partial evaluator is simple enough to prove its correctness. Based on the framework, we have constructed a partial evaluator for Scheme, which is powerful enough to specialize fairly complicated programs with side-effects, such as an interpreter.
A type-directed, on-line, partial evaluator for a polymorphic language
Authors: Sheard Tim
Published: November 2005

Recently, Olivier Danvy introduced a new, simple method for implementing powerful partial evaluators, namely type-directed partial evaluation[9]. He introduced a partial evaluator for the simply-typed lambda calculus (§2). This paper explores the possibility of using the same techniques over a lambda calculus with a richer type system. We generalize and extend Danvy's work in four ways:1. Our system handles a much richer language than that presented by Danvy, including all of the features functional programmers have come to expect, such as polymorphism (§5), inductive datatypes (§10), and recursion (§9).2. Our system includes a new systematic treatment of primitive operators (§7) and the propagation of residualized code (§7.1). This question has either been ignored or treated in an ad-hoc manner in previous work.3. Our system handles non-closed terms (§6). This makes type-directed partial evaluation much more practically useful, and can easily be extended to work in languages with parameterized module systems.4. Our system makes the whole process more efficient, by using a lazy, on-demand implementation (§8). The laziness of our implementation also causes the code produced to be more abstract and compact. Using this lazy implementation we have observed speedup ratios in the range 2--10, and code compactness improvements of more than 10 in some cases.All these extensions are made possible by a key technical innovation, namely,
embedding types in values
.
Generating efficient virtual worlds for visualization using partial evaluation and dynamic compilation
Authors: Beshers Clifford , Feiner Steven
Published: November 2005

We argue that runtime program transformation, partial evaluation, and dynamic compilation are essential tools for automated generation of flexible, highly interactive graphical interfaces. In particular, these techniques help bridge the gap between a high-level, functional description and an efficient implementation. To support our claim, we describe our application of these techniques to a functional implementation of
n
-Vision, a real-time visualization system that represents multivariate relations as nested 3D interactors, and to
Auto Visual
, a rule-based system that designs
n
-Vision visualizations from high-level task specifications.
n
-Vision visualizations are specified using a simple functional language. These programs are transformed into a cached dataflow graph. A partial evaluator is used on particular computation-intensive function applications, and the results are compiled to native code. The functional representation simplifies generation of correct code, and the program transformations ensure good performance. We demonstrate why these transformations improve performance and why they cannot be done at compile time.
A transformation system for CLP with dynamic scheduling and CCP
Authors: Etalle Sandro , Gabbrielli Maurizio , Marchiori Elena
Published: November 2005

In this paper we study unfold/fold transformations for constraint logic programs (CLP) with dynamic scheduling and for concurrent constraint programming (CCP). We define suitable applicability conditions for these transformations which guarantee that the original and the transformed program have the same results of successful derivations and the same deadlock free queries.The possible applications of these results are twofold. On one hand we can use the unfold/fold system to optimize CLP and CCP programs while preserving their intended meaning and in particular without the risk of introducing deadlocks. On the other hand, unfold/fold transformations can be used for proving deadlock freeness of a class of queries in a given program: to this aim it is sufficient to apply our transformations and to specialize the resulting program with respect to the given queries in such a way that the obtained program is trivially deadlock free. As shown by several interesting examples, this yields a methodology for proving deadlock freeness which is simple and powerful at the same time.
Resource-bounded partial evaluation
Authors: Debray Saumya
Published: November 2005

Most partial evaluators do not take the availability of machine-level resources, such as registers or cache, into consideration when making their specialization decisions. The resulting resource contention can lead to severe performance degradation---causing, in extreme cases, the specialized code to run slower than the unspecialized code. In this paper we consider how resource considerations can be incorporated within a partial evaluator. We develop an abstract formulation of the problem, show that optimal resource-bounded partial evaluation is NP-complete, and discuss simple heuristics that can be used to address the problem in practice.
Implementation of a database factory
Authors: Selvaraj Asokan R. , Ghosh Debasish
Published: November 2005

Object oriented software systems that utilize relational databases for data-store have to deal with the problem of interfacing to the relational data. This aspect of the software is more relevant to the solution domain rather than the problem domain i.e., the business requirements of an application do not dictate that there be a mechanism that allows the application to store and retrieve relational data. Hence, de-coupling the application from the database and its interface is relevant from the perspective of portability that of the application to other kinds of databases. For example, it is conceivable the application may be required to work with relational databases from different vendors. This article shows an adaptation of the Factory Method Pattern and the Abstract Factory Pattern [1] as a generic solution to the problem of de-coupling application code from the underlying database and its associated interface mechanisms.