bluuebunny/crossref_metadata_2025 huggingface dataset:
Report of session on concurrency
Authors: Schroeder Michael D. , Dennis Jack
Published: November 2005

This session was devoted to discussion of primitives for synchronizing the execution of concurrent processes. Jack Dennis introduced the session by noting that concurrent activity in a computer systems leads to the possibility of nondeterminacy. While most users with applications programs do not want nondeterminate results, some applications are inherently nondeterminate in part, e.g., an airline seat reservation system. At a lower level, the programmers of the operating system itself need to write both determinate and nondeterminate programs. The challenge is in providing primitives at each level in a system which guarantee determinacy when that is required, yet allow the construction of nondeterminate programs when that is required. As a basis for discussion, Dennis invited Rick Holt to make a short presentation on the levels in a computer system and their relationship to synchronizing primitives.

Holt indicated that the principle reason we have concurrency in computer systems is the economic necessity to run I/O devices in parallel with the much faster central processors. There are also fancier reasons, like constructing nondeterminate computations. Concurrency is usually handled by embedding various synchronizing primitives in the system or in high-level programming languages. In order to decide what primitives are appropriate you need to know what problems are to be solved. The problems being solved depend in turn upon the level of the computer system being considered. A computer system can be divided into five levels: hardware, kernel, nucleus, subsystems, and applications. The kernel multiplexes the central processors, implementing processes. At this level very simple synchronization primitives may be sufficient, like turning off interrupts. A critical problem at this level is the processor allocation strategy and maintaining queues of waiting processes. The nucleus is responsible for sharing devices. We want to be able to write device managers that multiplex data paths and schedule the use of these paths. These managers can be built in two ways: distributed managers that execute as part of user processes or centralized managers that execute in their own processes. Dijkstra has told us how to handle the concurrency generated by decentralized managers using primitives like P and V. Message passing works for centralized managers. (Note that message buffers are an important system resource to be managed. They cannot be managed using message switching, so this management must occur in the kernel.) At the levels of subsystems and applications something more complex and specifically suited to certain applications may be required to control concurrency. At all levels concurrency is interrelated with problems of protection, reliability, and pre-emption. If we ignore these problems we will miss entirely the problems of implementing primitives to control concurrency. Holt also discussed the primitives used at the various levels in the SUE system, as described in his working paper.
Specification languages for control programs
Authors: Austin Joseph H.
Published: November 2005

This study (1) describes an approach to the formal specification of control programs based on the generalized concept of binding. From this viewpoint, the individual operations of a control program may be described by a graphic specification language [related to mem-theory (2)], whose statements are pairs of graphs depicting the original and final binding states of system elements. A global view of interrelationships and dynamic behavior of the system may be described by an extension of Petri-nets (3, 4) depicting the flow of system elements from one state of local binding to another.

A rational approach to the design of a new programming language must begin with an analysis of the “meanings” that are to be expressed; an appropriate, compilable syntax can then be developed around this skeleton. Consequently, we seek to identify, the characteristic features of operating system programming, and in particular those that differentiate these programs from conventional ones.
Towards ISMs for OPSs
Authors: Berry Daniel M.
Published: November 2005

Information structure models (ISMs) [Weg70] have been applied successfully to the study of programming languages both in their definitions [LW69, Wlk68,70,Wgb70] and in proofs of correctness and equivalence of various implementation strategies [Luc69,JH70,JL71,McG71,Bry72].

This paper examines briefly the possibility using ISMs to define operating systems (OPSs). We give a definition of the notion of ISM and indicate how to use them. Then we describe methods by which the process notion has been defined in the past in the hope that this will give some idea of the applicability of the ISM approach to the definition of OPSs.
An experience in structured programming and transferability
Authors: Lecarme Olivier
Published: November 2005

This paper is not concerned with a true operating system, but with a long and complex program, that is a translator writing system (TWS)
1
which has many of the characteristics of operating systems. The experience reported here is on transferring such a system from a PDP-10 computer to a CDC Cyber 74, and translating it from Fortran into Pascal
2
. We do not examine the points which are related to the host operating systems. Our principal purpose is to report on the different aspects of the work involved in translating such a program from Fortran to Pascal, and on the transferability of the resulting program.
The ILLIAC IV FORTRAN compiler
Authors: Millstein Robert E. , Muntz Charles A.
Published: November 2005

This paper provides a basic description of a FORTRAN system for the ILLIAC IV. In this context “FORTRAN system” means exactly what one would expect — a user familiar with a different system will find no major surprises when he uses ILLIAC FORTRAN. The language is the same — a dialect of ANSI standard FORTRAN. The processors are the same — a compiler which generates relocatable binary files from FORTRAN source text, a link editor which collects and joins separately compiled program pieces into a single module, a loader which loads and relocates a single module into ILLIAC memory, a library of functions, and an I/O subsystem which supports formatted and unformatted FORTRAN I/O.
A modest proposal for vector extensions to ALGOL
Authors: Zosel Mary E.
Published: November 2005

Machines that possess instructions that are actually “higher level” than high-level language statements require extensions to traditional programming language. This paper explores the kinds of extensions necessary for adequate access to the CDC STAR instruction set. Specific problem areas considered are: access to the vector instructions, definition of descriptors, support of the variety of hardware data-types, and facilities for memory and register management.

It is fairly straightforward to define language facilities to cover most of these problems with minimum disruption of existing language features. Informal descriptions are given for syntactic and semantic extensions to ALA, an ALGOL based language. Features include declaration and usage of vector and descriptor variables, generation of vector values, subscripting slicing, and procedure linkage. The language constructs described are not limited in application to either the STAR or ALA. They should be easily adaptable to other languages and machines where vector constructs would enhance programming power.
An approach to compiler correctness
Authors: Chirica Laurian M. , Martin David F.
Published: November 2005

This paper is a preliminary report on an experiment in applying Floyd's method of inductive assertions to the compiler correctness problem. Practical postfix translators are considered, and the semantics of source and object languages are characterized by Floyd verification conditions. Compiler correctness proofs are partitioned into two parts. The first part deals with proofs of the syntactic and translational phase of compilation, and generates semantic equivalence theorems which are proved in the second part. These techniques are illustrated by a small example.
SELECT—a formal system for testing and debugging programs by symbolic execution
Authors: Boyer Robert S. , Elspas Bernard , Levitt Karl N.
Published: November 2005

SELECT is an experimental system for assisting in the formal systematic debugging of programs. It is intended to be a compromise between an automated program proving system and the current ad hoc debugging practice, and is similar to a system being developed by King et al. of IBM. SELECT systematically handles the paths of programs written in a LISP subset that includes arrays. For each execution path SELECT returns simplified conditions on input variables that cause the path to be executed, and simplified symbolic values for program variables at the path output. For conditions which form a system of linear equalities and inequalities SELECT will return input variable values that can serve as sample test data. The user can insert constraint conditions, at any point in the program including the output, in the form of symbolically executable assertions. These conditions can induce the system to select test data in user-specified regions. SELECT can also determine if the path is correct with respect to an output assertion. We present four examples demonstrating the various modes of system operation and their effectiveness in finding bugs. In some examples, SELECT was successful in automatically finding useful test data. In others, user interaction was required in the form of output assertions. SELECT appears to be a useful tool for rapidly revealing program errors, but for the future there is a need to expand its expressive and deductive power.
Types, distribution, and test and correction times for programming errors
Authors: Shooman M. L. , Bolsky M. I.
Published: November 2005

In order to develop some basic information on software errors, an experiment in collecting data on types and frequencies of such errors was conducted at Bell Laboratories.

The paper reports the results of this experiment, whose objectives were to: (1) Develop and utilize a set of terms for describing possible types of errors, their nature, and their frequency; (2) Perform a pilot study to determine if data of the type reported in this paper could be collected; (3) Investigate the error density and its correspondence to predictions from previous data reported; (4) Develop data on how resources are expended in debugging.

A program of approximately 4K machine instructions (final size) was chosen. Programmers were asked to fill out for each error, in addition to the regular Trouble Report/Correction Report (TR/CR) form, a special Supplementary TR/CR form for the purposes of this experiment. Sixty-three TR/CR and Supplementary forms were completed during the Test and Integration phase of the program.

In general, the data collected were felt to be accurate enough for the purposes of the analyses presented. The 63 forms represented a little over 1-1/2% of the total number of machine instructions of the program. (In good agreement with the 1% to 2% range noted in previous studies.)

It was discovered that a large percentage of the errors was found by hand processing (without the aid of a computer). This method was found to be much cheaper than techniques involving machine testing.
Verifying programs by algebraic and logical reduction
Authors: Suzuki Norihisa
Published: November 2005

Methods for verifying programs written in a higher level programming language are devised and implemented. The system can verify programs written in a subset of PASCAL, which may have data structures such as ARRAY, POINTER, and RECORD and control structures such as WHILE, REPEAT, FOR, PROCEDURE, FUNCTION and COROUTINE. The process of creation of verification conditions is an extension of the work done by lgarashi, London and Luckham (1972) which is based on the deductive theory by Hoare (1969). Verification conditions are proved using specialized simplification and proof techniques, which consist of an arithmetic simplifier, equality replacement rules, fast algorithm for simplifying formulas using propositional truth value evaluation, and a depth first proof search process. The basis of deduction mechanism used in this prover is Gentzen-type formal system. Several sorting programs including Floyd's TREESORT3 and Hoare's FIND are verified. It is shown that the resulting array is not only ordered but also a permutation of the input array

This research was supported in part by the Advanced Research Projects Agency of the Office of the Secretary of Defence under contract DAHC 15-73-C-0435.
Towards the ideal programming language
Authors: Herriot Robert G.
Published: November 2005

A programming language with good features and notation can help the programmer represent his abstractions in the programming language, and can also help someone else understand the original abstraction. There have been numerous proposals for better features. In this paper we propose several new ideas to improve the notation. First we suggest that class instances be named with a sequence of identifiers consisting of the class name preceded by modifiers. Then we propose that prepositions be placed before procedure parameters to suggest their role. Finally, we suggest that applicative and imperative operations can be separated semantically, and then recombined syntactically through the use of the “which” and passive operators.
Some extensions to algebraic specifications
Authors: Guttag Jhon V. , Horowitz Ellis , Musser David R.
Published: November 2005

Algebraic specifications of abstract data types are beginning to gain wide currency. In this paper we discuss an extension to this specification technique which allows the specification of procedures which alter their parameters, and various ways of handling the specification of error conditions.
Early experience with Mesa
Authors: Geschke Charles M. , Morris James H. , Satterthwaite Edwin H.
Published: November 2005

The experiences of Mesa's first users—primarily its implementers—are discussed, and some implications for Mesa and similar programming languages are suggested. The specific topics addressed are:

module structure and its use in defining abstractions,

data-structuring facilities in Mesa,

equivalence algorithm for types and type coercions,

benefits of the type system and why it is breached occasionally,

difficulty of making the treatment of variant records safe.
Extending IDL to support concurrent views
Authors: Garlan D.
Published: November 2005

Derivation and refinement in IDL currently provide kinds of
views
in the sense that two IDL structures can describe the same data in different ways. But derivation and refinement are limited in that (a) they do not support concurrent access to shared information and (b) the range of differences between derived views is quite restricted. In this paper we outline an architecture in which IDL is extended to correct these problems. This design allows a collection of IDL-based tools to access a common object base concurrently through views defined as (extended) IDL structures. Mappings between views are provided automatically by the IDL translator and database support mechanisms.
Problems with automatic restructurers
Authors: Calliss Frank W.
Published: November 2005

The value of automatic restructurers in the maintenance phase of the software life cycle will be discussed. Our discussions will centre on programs written in COBOL but the arguments are applicable to programs written in other languages. Some of the dangers of automatically restructuring a program are highlighted and the use of interactive restructurers to overcome these dangers are considered.
A precompiler for modular, transportable Pascal
Authors: Egenhofer Max J. , Frank Andrew U.
Published: November 2005

Highly modular, object-oriented software systems require support from programming languages to produce reusable code. Pascal lacks such features that easily propagate type definitions and routines from one module to another, such as MODULA-2 or ADA. This paper describes a Pascal extension which includes directives to mark data definitions and operations as externally visible. A precompiler which handles import directives translates the source into the compiler-specific Pascal syntax. This precompiler has been successfully used for five years in education and research.
Automatic construction of incremental LR(1)—parsers
Authors: Yeh Dashing , Kastens Uwe
Published: November 2005

An effective method is presented for automatic construction of incremental LR(1) parsers. The resulting parsers allow multiple modifications of the original input as well as epsilon productions in the underlying LR(1) grammar. For parsing a modified input, their space require ment depends linear on the length of the input and their runtime is proportional to the total size of the modifications. The method has been implemented for experimental purposes.
Towards functional programming in Prolog
Authors: Furtado Antonio L.
Published: November 2005

The integration of functional and logic programming is attempted, using the strategy to add a functional component to Prolog. The component takes the form of extended computable expressions, allowing user-defined functions and operators as well as a number of functional forms. The problem of evaluating expressions combining functions and predicates is investigated. Examples are provided to illustrate the discussion. The paper includes a prototype implementation.
Data flow analysis of recursive procedures
Authors: Fairfield P. , Hennell M. A.
Published: November 2005

Data flow analysis is a technique used to detect suspicious variable usage within a program. Its evaluation requires analysis of the flow graphs of the program. This causes difficulties when the program contains recursive procedures because in order to fully evaluate each procedure, the data flow value of its own recursive invocation needs to be known first. This however cannot be determined until the whole procedure has been analysed. This paper describes a technique for resolving this difficulty and successfully completing data flow analysis on recursive procedures.
Four relational programs
Authors: MacLenna B. J.
Published: November 2005

In this report we demonstrate the relational programming language RPL by using it to develop four programs. These programs are: (1) computing a table of word frequencies from a text; (2) a simple data processing example involving updating an employee file; (3) Gaussian elimination; and (4) minimizing deterministic finite state automata. We do not present the RPL language systematically; rather it is described incrementally through the examples.
Simulating the object-oriented paradigm to Nial
Authors: Beaudet Philip J. , Jenkins Michael A.
Published: November 2005

Recently, the object-oriented paradigm has received much recent attention. Now programmers are attempting to simulate object-oriented programming using languages that do not directly support the paradigm. This paper describes our approach to simulating the object-oriented paradigm in Nial. Nial is a multiparadigm language, but it does not directly support the object-oriented paradigm.
Abstract data types with shared operations
Authors: Osterbye Kasper
Published: November 2005

It is argued that the concept of abstract datatypes can be extended in a way that allows for operations to be shared between two (or more datatypes), and that this will often give a better and more natural way of structuring programs. Shared operations can access the representation of more than one abstract datatype.
Are applicative languages inefficient?
Authors: Ponder Carl G. , McGeer Patrick , Ng Anthony P-C.
Published: November 2005

Side-effects are forbidden in applicative languages like Prolog [3], FP [2], pure Lisp [9], and SISAL [8]. Algorithms can often be reformulated applicatively with no loss of efficiency. It is not known whether this is always the case. Here are seven problems which have been resistant to efficient reformulation. The reader is invited to produce an efficient applicative program or lower-bound argument for any of these.
Tasking troubles and tips
Authors: Rising L.
Published: November 2005

All the problems associated with concurrency in any language are troublesome when using Ada: deadlock, critical access, race conditions, starvation, abnormal termination and timing errors. Programmers in Ada, however, must face additional concerns presented by the Ada tasking model. The following summarizes some difficulties encountered in an industrial project and others described in the literature.
The linked list class of Modula-3
Authors: Levy E.
Published: November 2005

The desirability of providing built-in linked list support for the next generation of system programming languages is discussed. A Modula-2 pseudo inheritance implementation is given that demonstrates a proposed set of primitives. A set of rules are specified that enhance reliability without adding significant restrictions. Benefits to concurrency control are described.
Resolving ambiguities in the parsing of translation grammars
Authors: Share M.
Published: November 2005

During the course of the Chameleon Research Project, situations arose in which ambiguities during LR parsing could not be solved by conventional deterministic means. The source of this problem and the implemented solution are presented.
Efficient compilation of lazy evaluation
Authors: Johnsson Thomas
Published: November 2005

This paper describes the principles underlying an efficient implementation of a lazy functional language, compiling to code for ordinary computers. It is based on combinator-like graph reduction: the user defined functions are used as rewrite rules in the graph. Each function is compiled into an instruction sequence for an abstract graph reduction machine, called the G-machine, the code reduces a function application graph to its value. The G-machine instructions are then translated into target code. Speed improvements by almost two orders of magnitude over previous lazy evaluators have been measured; we provide some performance figures.
Peep
Authors: Kessler Robert R.
Published: November 2005

Peep is an architectural description driven peephole optimizer, that is being adapted for use in the Portable Standard Lisp compiler. Tables of optimizable instructions are generated prior to the creation of the compiler from the architectural description of the target machine. Peep then performs global flow analysis on the target machine code and optimizes instructions as defined in the table. This global flow analysis allows optimization across basic blocks of instructions, and the use of tables created at compiler-generation time minimizes the overhead of discovering optimizable instructions.
Automatic loop interchange
Authors: Allen John R. , Kennedy Ken
Published: November 2005

Parallel and vector machines are becoming increasingly important to many computation intensive applications. Effectively utilizing such architectures, particularly from sequential languages such as Fortran, has demanded increasingly sophisticated compilers. In general, a compiler needs to significantly reorder a program in order to generate code optimal for a specific architecture.Because DO loops typically control the execution of a number of statements, the order in which loops are executed can dramatically affect the performance of a machine on a particular section of code. In particular,
loop interchange
can often be used to enhance the performance of code on parallel or vector machines.Determining when loops may be safely and profitably interchanged requires a study of the
data dependences
in the program. This work discusses specific applications of that theory to loop interchange. This theory is described as it has been implemented in PFC (Parallel Fortran Converter) -- a program which attempts to uncover operations in sequential Fortran code that may be safely rewritten as vector operations.
Sharing code among instances of Ada generics
Authors: Bray Gary
Published: November 2005

This paper describes the aspects of the Ada compiler for the Air Force Ada Integrated Environment (AIE) that are concerned with sharing code among generic instances. Sharing is achieved by forming equivalence classes of generic instances and sharing executable code among members of the class. This approach achieves the required efficiency for embedded applications while minimizing the storage consumed by the executable code of generic instances.
Type checking, separate compilation and reusability
Authors: Levy Michael R.
Published: November 2005

A strategy for performing type checking on programs built out of separately compiled parts is presented. This strategy is used in a programming environment that allows small components of a software system to be reconfigured in different ways. The strategy works by inferring type schemas for all of the undeclared functions used by a component and then unifying each schema with a program library when a configuration is built.
Static checking of interprocess communication in ECSP
Authors: Baiardi F. , Ricci L. , Vanneschi M.
Published: November 2005

The structure of a compiler for the ECSP language is described. ECSP is a concurrent language extending Hoare's CSP: it supports dynamic communication channels and nested processes. The compilation of ECPS programs is obtained by the composition of several tools of minimal functionalities.A set of static checks on interactions between concurrent processes is described. The checks verify the mutual consistency of the interfaces of processes: an interface is given by a set of input/output channels connecting a process to its partners. It is shown that the amount and the coverage of checks depend on the entities referred to in interprocess communication constructs and that both increase with the adoption of explicit naming.The checks on process interfaces are carried on in several tool of the compiler front-end to achieve machine independence. To support separate compilation, each tool can be applied to a subset of the processes of a program.
A core calculus for Java exceptions
Authors: Ancona D. , Lagorio G. , Zucca E.
Published: November 2005

In this paper we present a simple calculus (called CJE) in ourder to fully investigate the exception mechanism of Java, and in particular its interaction with inheritance, which turns out to be non trivial. Moreover, we show that the type system for the calculus directly dirven by the Java language specification (called FULL) uses too many types, in the sense that there are different types which rpovide exactly the same information. Hence, we obtain from FULL a simplified type system called MIN where equivalent types have been identified. We show that is useful both for type-checking optimization and for clarifying the static semantics of the language. The two type systems are proved to satisfy the subject reduction property
A parameterized type system for race-free Java programs
Authors: Boyapati Chandrasekhar , Rinard Martin
Published: November 2005

This paper presents a new static type system for multithreaded programs; any well-typed program in our system is free of data races. Our type system is significantly more expressive than previous such type systems. In particular, our system lets programmers write generic code to implement a class, then create different objects of the same class that have different objects of the same class that have different protection mechanisms. This flexibility enables programmers to reduce the number of unnecessary synchronizationoperations in a program without risking data races. We also support default types which reduce the burden of writing extra type annotations. Our experience indicates that our system provides a promising approach to make multithreaded programs more reliable and efficient
Object race detection
Authors: von Praun Christoph , Gross Thomas R.
Published: November 2005

We present an on-the-fly mechanism that detects access conflicts in executions of multi-threaded Java programs. Access conflicts are a conservative approximation of data races. The checker tracks access information at the level of objects (
object races
) rather than at the level of individual variables. This viewpoint allows the checker to exploit specific properties of object-oriented programs for optimization by restricting dynamic checks to those objects that are identified by escape analysis as potentially shared. The checker has been implemented in collaboration with an "ahead-of-time"Java compiler. The combination fo static program analysis (escape-analysis) and inline instrumentation during code generation allows us to reduce the runtime overhead of detecting access conflicts. This overhead amounts to about 16-129% in time and less than 25% in space for typical benchmark applications and compares favorably to previously published on-the-fly mechanism that incurred an overhead of about a factor of 2-80 in time and up to a factor of 2 in space.
A study of exception handling and its dynamic optimization in Java
Authors: Ogasawara Takeshi , Komatsu Hideaki , Nakatani Toshio
Published: November 2005

Optimizing exception handling is critical for programs that frequently throw exceptions. We observed that there are many such exception-intensive programs iin various categories of Java programs. There are two commonly used exception handling techniques, stack unwinding optimizes the normal path, while stack cutting optimizes the exception handling path. However, there has been no single exception handling technique to optimize both paths.
Portable resource control in Java
Authors: Binder Walter , Hulaas Jane G. , Villazón Alex
Published: November 2005

Preventing abusive resource consumption is indispensable for all kinds of systems that execute untrusted mobile coee, such as mobile object sytems, extensible web servers, and web browsers. To implement the required defense mechanisms, some support for resource control must be available: accounting and limiting the usage of physical resources like CPU and memory, and of logical resources like threads. Java is the predominant implementation language for the kind of systems envisaged here, even though resource control is a missing feature on standard Java platforms. This paper describes the model and implementation mechanisms underlying the new resource-aware version of the J-SEAL2 mobile object kernel. Our fundamental objective is to achieve complete portability, and our approach is therefore based on Java bytecode transformations. Whereas resource control may be targeted towards the provision of quality of service or of usage-based billing, the focus of this paper is on security, and more specificlly on prevention of denial-of-service attacks orginating from hostile or poorly implemented mobile code.
A dynamic optimization framework for a Java just-in-time compiler
Authors: Suganuma Toshio , Yasue Toshiaki , Kawahito Motohiro , Komatsu Hideaki , Nakatani Toshio
Published: November 2005

The high performance implementation of Java Virtual Machines (JVM) and just-in-time (JIT) compilers is directed toward adaptive compilation optimizations on the basis of online runtime profile information. This paper describes the design and implementation of a dynamic optimization framework in a production-level Java JIT compiler. Our approach is to employ a mixed mode interpreter and a three level optimizing compiler, supporting quick, full, and special optimization, each of which has a different set of tradeoffs between compilation overhead and execution speed. a lightweight sampling profiler operates continuously during the entire program's exectuion. When necessary, detailed information on runtime behavior is collected by dynmiacally generating instrumentation code which can be installed to and uninstalled from the specified recompilation target code. Value profiling with this instrumentation mechanism allows fully automatic code specialization to be performed on the basis of specific parameter values or global data at the highest optimization level. The experimental results show that our approach offers high performance and a low code expansion ratio in both program startup and steady state measurements in comparison to the compile-only approach, and that the code specialization can also contribute modest performance improvement
Visitor combination and traversal control
Authors: Visser Joost
Published: November 2005

The
Visitor
design pattern allows the encapsulation of polymorphic behavior outside the class hierarchy on which it operates. A common application of
Visitor
is the encapsulation of tree traversals. A clean separation can be made between the generic parts of the combinator set and the parts that are specific to a particular class hierarchy. The generic parts form a reusable framework. The generic parts form a reusable framework. The specific parts can be generated from a (tree) grammar. Due to this separation, programming with visitor combinators becomes a form of
generic programming
with significant reuse of (visitor) code.
A categorization of classes based on the visualization of their internal structure
Authors: Lanza Michele , Ducasse Stéphane
Published: November 2005

The reengineering and reverse engineering of software systems is gaining importance in software industry, because the accelerated turnover in software industry, because the accelerated turnover in software companies creates legacy systems in a shorter period of time. Especially understanding classes is a key activity in object-oriented programming, since classes represent the primary abstractions from which applications are built. The main problem of this task is to quickly grasp the purpose of a class and its inner structure. To help the reverse engineers in their first contact with a foreign system, we propose a categorization of classes based on the visualization of their internal structure. The contributions of this paper are a novel categorization of classes and a visualization of the which we call the
class blueprint
. We have validated the categorization on several case studies, two of which we present here.
An on-the-fly reference counting garbage collector for Java
Authors: Levanoni Yossi , Petrank Erez
Published: November 2005

Reference counting is not naturally suitable for running on multiprocessors. The update of pointers and reference counts requires atomic and synchronized operations. We present a novel reference counting algorithm suitable for a multiprocessor that does not require any synchronized operation in its write barrier (not even a compare-and-swap type of synchronization). The algorithm is efficient and may complete with any tracing algorithm.
Generic unification via two-level types and parameterized modules
Authors: Sheard Tim
Published: November 2005

As a functional pearl, we describe an efficient, modularized
implementation of unification using the state of mutable reference
cells to encode substitutions. We abstract our algorithms along two
dimensions, first abstracting away from the structure of the terms
to be unified, and second over the monad in which the mutable state
is encapsulated. We choose this example to illustrate two important
techniques that we believe many functional programmers would find
useful. The first of these is the definition of recursive data
types using two levels: a structure defining level, and a recursive
knot-tying level. The second is the use of rank-2 polymorphism
inside Haskell's record types to implement a form of type
parameterized modules.
A dependently typed assembly language
Authors: Xi Hongwei , Harper Robert
Published: November 2005

We present a dependently typed assembly language (DTAL) in which the type system supports the use of a restricted form of dependent types, reaping some benefits of dependent types at the assembly level. DTAL improves upon TAL , enabling certain important compiler optimizations such as run-time array bound check elimination and tag check elimination. Also, DTAL formally addresses the issue of representing sum types at assembly level, making it suitable for handling not only datatypes in ML but also dependent datatypes in Dependent ML (DML).
Functional array fusion
Authors: Chakravarty Manuel M. T. , Keller Gabriele
Published: November 2005

This paper introduces a new approach to optimizing array algorithms in functional languages. We are specifically aiming at an efficient implementation of irregular array algorithms that are hard to implement in conventional array languages such as Fortran. We optimize the storage layout of arrays containing complex data structures and reduce the running time of functions operating on these arrays by means of equational program transformations. In particular, this paper discusses a novel form of combinator loop fusion, which by removing intermediate structures optimizes the use of the memory hierarchy. We identify a combinator named loop P that provides a general scheme for iterating over an array and that in conjunction with an array constructor replicate P is sufficient to express a wide range of array algorithms. On this basis, we define equational transformation rules that combine traversals of loop P and replicate P as well as sequences of applications of loop P into a single loop P traversal. Our approach naturally generalizes to a parallel implementation and includes facilities for optimizing load balancing and communication. A prototype implementation based on the rewrite rule pragma of the Glasgow Haskell Compiler is significantly faster than standard Haskell arrays and approaches the speed of hand coded C for simple examples.
Mixed-initiative interaction = mixed computation
Authors: Ramakrishnan Naren , Capra Robert G. , Pérez-Quiñones Manuel A.
Published: November 2005

We show that partial evaluation can be usefully viewed as a programming model for realizing mixed-initiative functionality in interactive applications. Mixed-initiative interaction between two participants is one where the parties can take turns at any time to change and steer the flow of interaction. We concentrate on the facet of mixed-initiative referred to as 'unsolicited reporting' and demonstrate how out-of-turn interactions by users can be modeled by 'jumping ahead' to nested dialogs (via partial evaluation). Our approach permits the view of dialog management systems in terms of their support for staging and simplifying inter-actions; we characterize three different voice-based interaction technologies using this viewpoint. In particular, we show that the built-in form interpretation algorithm (FIA) in the VoiceXML dialog management architecture is actually a (well disguised) combination of an interpreter and a partial evaluator.
A modest proposal for curing the public field phobia
Authors: Spinellis Diomidis
Published: November 2005

Field accessor methods have become a ubiquitous feature of object-oriented programming. The definition and use of such methods promote code bloat and an unnatural expression style. We propose a simple addition to the C++ language that can move the burden of providing abstraction support for fields from the programmer to the compiler.
The HSSM macro-architecture, Virtual Machine and H languages
Authors: Wells Paul Damian
Published: November 2005

This paper is an introduction to the Hierarchical Simultaneous Set Membership (HSSM) macro-architecture project, the associated HSSM Virtual Machine (HVM) and "H" languages. The ultimate goal of this project is the automated synthesis and verification of large multithreaded software applications.
Programming languages should NOT have comment statements
Authors: Kaelbling M. J.
Published: November 2005

The purpose of this paper is to open discussion on the adequacy and design of commenting techniques in programming (and, indeed, all computer processing) languages. The argument is made that the common notion of comment statements is too simplistics, and that a powerful alternative exists. A distinction is made between simple comment statements and scoped comments. Two types of scoped comments are mentioned, and their weaknesses are considered. The paper ends with a call for language designers to address this issue.
Fast copy coalescing and live-range identification
Authors: Budimlic Zoran , Cooper Keith D. , Harvey Timothy J. , Kennedy Ken , Oberg Timothy S. , Reeves Steven W.
Published: November 2005

This paper presents a fast new algorithm for modeling and reasoning about interferences for variables in a program without constructing an interference graph. It then describes how to use this information to minimize copy insertion for ϕ-node instantiation during the conversion of the static single assignment (SSA) form into the control-flow graph (CFG), effectively yielding a new, very fast copy coalescing and live-range identification algorithm.This paper proves some properties of the SSA form that enable construction of data structures to compute interference information for variables that are considered for folding. The asymptotic complexity of our SSA-to-CFG conversion algorithm is where-is the number of instructions in the program.Performing copy folding during the SSA-to-CFG conversion eliminates the need for a separate coalescing phase while simplifying the intermediate code. This may make graph-coloring register allocation more practical in just in time (JIT) and other time-critical compilers For example, Sun's Hotspot Server Compiler already employs a graph-coloring register allocator[10].This paper also presents an improvement to the classical interference-graph based coalescing optimization that shows adecrease in memory usage of up to three orders of magnitude and a decrease of a factor of two in compilation time, while providing the exact same results.We present experimental results that demonstrate that our algorithm is almost as precise (within one percent on average) as the improved interference-graph-based coalescing algorithm, while requiring three times less compilation time.
Dynamic hot data stream prefetching for general-purpose programs
Authors: Chilimbi Trishul M. , Hirzel Martin
Published: November 2005

Prefetching data ahead of use has the potential to tolerate the grow ing processor-memory performance gap by overlapping long latency memory accesses with useful computation. While sophisti cated prefetching techniques have been automated for limited domains, such as scientific codes that access dense arrays in loop nests, a similar level of success has eluded general-purpose pro grams, especially pointer-chasing codes written in languages such as C and C++. We address this problem by describing, implementing and evaluating a dynamic prefetching scheme. Our technique runs on stock hardware, is completely automatic, and works for general-purpose programs, including pointer-chasing codes written in weakly-typed languages, such as C and C++. It operates in three phases. First, the profiling phase gathers a temporal data reference profile from a running program with low-overhead. Next, the profiling is turned off and a fast analysis algorithm extracts hot data streams, which are data reference sequences that frequently repeat in the same order, from the temporal profile. Then, the system dynamically injects code at appropriate program points to detect and prefetch these hot data streams. Finally, the process enters the hibernation phase where no profiling or analysis is performed, and the program continues to execute with the added prefetch instructions. At the end of the hibernation phase, the program is de-optimized to remove the inserted checks and prefetch instructions, and control returns to the profiling phase. For long-running programs, this profile, analyze and optimize, hibernate, cycle will repeat multiple times. Our initial results from applying dynamic prefetching are promising, indicating overall execution time improvements of 5.19% for several memory-performance-limited SPECint2000 benchmarks running their largest (ref) inputs.
Efficient and precise datarace detection for multithreaded object-oriented programs
Authors: Choi Jong-Deok , Lee Keunwoo , Loginov Alexey , O'Callahan Robert , Sarkar Vivek , Sridharan Manu
Published: November 2005

We present a novel approach to dynamic datarace detection for multithreaded object-oriented programs. Past techniques for on-the-fly datarace detection either sacrificed precision for performance, leading to many false positive datarace reports, or maintained precision but incurred significant overheads in the range of 3
x
to 30
x
. In contrast, our approach results in very few false positives and runtime overhead in the 13% to 42% range, making it both efficient
and
precise. This performance improvement is the result of a unique combination of complementary static and dynamic optimization techniques.
A type system for certified binaries
Authors: Shao Zhong , Saha Bratin , Trifonov Valery , Papaspyrou Nikolaos
Published: November 2005

A
certified binary
is a value together with a proof that the value satisfies a given specification. Existing compilers that generate certified code have focused on simple memory and control-flow safety rather than more advanced properties. In this paper, we present a general framework for explicitly representing complex propositions and proofs in typed intermediate and assembly languages. The new framework allows us to reason about certified programs that involve effects while still maintaining decidable typechecking. We show how to integrate an entire proof system (the calculus of inductive constructions) into a compiler intermediate language and how the intermediate language can undergo complex transformations (CPS and closure conversion) while preserving proofs represented in the type system. Our work provides a foundation for the process of automatically generating certified binaries in a typetheoretic framework.
Exploiting prolific types for memory management and optimizations
Authors: Shuf Yefim , Gupta Manish , Bordawekar Rajesh , Singh Jaswinder Pal
Published: November 2005

In this paper, we introduce the notion of
prolific
and
non-prolific
types, based on the number of instantiated objects of those types. We demonstrate that distinguishing between these types enables a new class of techniques for memory management and data locality, and facilitates the deployment of known techniques. Specifically, we first present a new
type-based
approach to garbage collection that has similar attributes but lower cost than generational collection. Then we describe the
short type pointer
technique for reducing memory requirements of objects (data) used by the program. We also discuss techniques to facilitate the recycling of prolific objects and to simplify object co-allocation decisions.We evaluate the first two techniques on a standard set of Java benchmarks (SPECjvm98 and SPECjbb2000). An implementation of the type-based collector in the Jalapeño VM shows improved pause times, elimination of unnecessary write barriers, and reduction in garbage collection time (compared to the analogous generational collector) by up to 15%. A study to evaluate the benefits of the short-type pointer technique shows a potential reduction in the heap space requirements of programs by up to 16%.