bluuebunny/crossref_metadata_2025 huggingface dataset:
A stream compiler for communication-exposed architectures
Authors: Gordon Michael I. , Thies William , Karczmarek Michal , Lin Jasper , Meli Ali S. , Lamb Andrew A. , Leger Chris , Wong Jeremy , Hoffmann Henry , Maze David , Amarasinghe Saman
Published: November 2005

With the increasing miniaturization of transistors, wire delays are becoming a dominant factor in microprocessor performance. To address this issue, a number of emerging architectures contain replicated processing units with software-exposed communication between one unit and another (e.g., Raw, SmartMemories, TRIPS). However, for their use to be widespread, it will be necessary to develop compiler technology that enables a portable, high-level language to execute efficiently across a range of wire-exposed architectures.In this paper, we describe our compiler for StreamIt: a high-level, architecture-independent language for streaming applications. We focus on our backend for the Raw processor. Though StreamIt exposes the parallelism and communication patterns of stream programs, some analysis is needed to adapt a stream program to a software-exposed processor. We describe a partitioning algorithm that employs fission and fusion transformations to adjust the granularity of a stream graph, a layout algorithm that maps a stream graph to a given network topology, and a scheduling strategy that generates a fine-grained static communication pattern for each computational element.We have implemented a fully functional compiler that parallelizes StreamIt applications for Raw, including several load-balancing transformations. Using the cycle-accurate Raw simulator, we demonstrate that the StreamIt compiler can automatically map a high-level stream abstraction to Raw without losing performance. We consider this work to be a first step towards a portable programming model for communication-exposed architectures.
Mondrian memory protection
Authors: Witchel Emmett , Cates Josh , Asanović Krste
Published: November 2005

Mondrian memory protection (MMP) is a fine-grained protection scheme that allows multiple protection domains to flexibly share memory and export protected services. In contrast to earlier page-based systems, MMP allows arbitrary permissions control at the granularity of individual words. We use a compressed permissions table to reduce space overheads and employ two levels of permissions caching to reduce run-time overheads. The protection tables in our implementation add less than 9% overhead to the memory space used by the application. Accessing the protection tables adds than 8% additional memory references to the accesses made by the application. Although it can be layered on top of demand-paged virtual memory, MMP is also well-suited to embedded systems with a single physical address space. We extend MMP to support segment translation which allows a memory segment to appear at another location in the address space. We use this translation to implement zero-copy networking underneath the standard read system call interface, where packet payload fragments are connected together by the translation system to avoid data copying. This saves 52% of the memory references used by a traditional copying network stack.
Bidirectional data flow analysis
Authors: Khedker Uday P. , Dhamdhere Dhananjay M.
Published: November 2005

Research in bidirectional data flow analysis seems to have come to a halt due to an impression that the case for bidirectional data flow analysis has been considerably weakened by a plethora of investigations based on decomposability of known bidirectional placement algorithms into a sequence of purely unidirectional components. This paper shows that the approach of decomposability is not general enough in that it derives its power from the simplifying graph transformation of edge-splitting and the favourable nature of flows in partial redundancy elimination (PRE). This follows from the fact that in the absence of edge-splitting, PRE cannot be performed using a sequence of cascaded unidirectional flows. Further, edge-splitting inherently converts data flows involved in PRE into unidirectional flows. In our opinion, this obviates the need of an alternative formulation. We also show that edge-splitting cannot convert data flows involved in "truly" bidirectional data flow problems into unidirectional flows. Thus not every bidirectional data flow problem can be converted into unidirectional flows. Besides, we argue that the premise that bidirectional analysis is more complex than unidirectional analysis, is invalid. We also mention some issues in bidirectional data flow analysis which need to be investigated.
Object-oriented symbol management in syntax-directed compiler systems
Authors: Naik Mayur , Kumar Rajeev
Published: November 2005

Each symbol in a source program has a series of attributes that govern the operations performed on it. In this paper, we explore object-oriented techniques for representing the attributes of symbols and translating the operations performed on them. This approach is shown superior in memory and run-time speed to the procedural style traditionally used for writing compilers. We demonstrate object-oriented symbol management in a compiler for an arithmetic subset of C. We have used C++ --- a single-dispatching language --- to implement the same, but we emphasize the need for multiple dispatching to develop programs in a heavily-object-oriented style.
Minimal deterministic left-to-right pattern-matching automata
Authors: Nedjah Nadia
Published: November 2005

We propose a practical technique to compile pattern-matching of prioritised overlapping patterns in equational languages to an minimal deterministic left-to-right matching automaton. First, we present a method to construct a tree matching automaton for such patterns. The automaton obtained allows pattern-matching to be performed without any backtracking. Although this automaton is efficient since it avoids symbol re-examination, it can only achieve this at the cost of increased space requirements. Such space requirements could be minimised by using a dag automaton that shares all the isomorphic subautomata which are duplicated in a tree automaton. We design an efficient method to identify such subautomata and avoid their construction while generating the dag automaton. This is achieved without constructing the tree automaton first.
SPLAW
Authors: Xiaocong Fan , Dianxiang Xu , Jianmin Hou , Guoliang Zheng
Published: November 2005

Agent oriented programming (AOP), which is a special kind of object-oriented programming, has recently been discussed from several viewpoints. It can be worked out best for open systems and has the potential to become a very attractive technique in the future. In this paper, we describe a specification and programming language --- SPLAW, for BDI agent. The syntax and operational semantics of SPLAW are presented, and by means of labeled transition system; the proof theory is also provided. SPLAW has two advantages. First, it is based on KQML, the standard inter-agent communication language, which makes it possible for agents written in SPLAW to interoperate with other agents obeying KQML. And second, it has the correspondent relationship between its operational semantics and proof theory. Owing to these, we hope that SPLAW will provide a feasible solution to bridge the gap between theory and practice.
A neural net compiler system for hierarchical organization
Authors: Kumar Rajeev
Published: November 2005

We present a language framework for handling arbitrarily complex neural computations. The software architecture - which we call an

A

rtificial

N

eural Network

C

ompiler for

H

ierarchical

OR

ganization (
ANCHOR
) - facilitates network hierarchy and simpler sub-mappings. We define a
N
et
D
efinition
L
anguage (NDL) which is implemented in object-oriented programming paradigm; a trained network is decompiled back into NDL.
ANCHOR
is configured around the concept of a
Superneuron
which is a generalized view of a neuron-processing element and designed using reuse of object-model. The indistinguishability between a superneuron and a neuron is employed in hierarchical nesting of superneurons, up to (theoretically) infinite depth within other superneurons as well as linear or tree-structured cascading. Hierarchical decomposition of simple boolean functions has been demonstrated as proof-of-concept.
A systematic generation of initial register-reuse chains for dependence minimization
Authors: Zhang Yukong , Kwon Young-Jun , Lee Hyuk Jae
Published: November 2005

A register-reuse chain is a set of nodes assigned to the same register. This paper proposes a systematic technique to generate register-reuse chains while aiming to reduce unnecessary dependencies. To avoid any dependency, the first phase of the proposed technique assigns two nodes to the same chain, only if the two nodes do not overlap their live ranges by any possible schedule. To reduce the number of chains, the second phase merges chains by assigning a node and one of its dependent nodes to the same chain. Evaluation shows that the proposed technique reduces dependencies by an average of 20.9%.
ET++—an object oriented application framework in C++
Authors: Weinand Andre , Gamma Erich , Marty Rudolf
Published: November 2005

ET++ is an object-oriented application framework implemented in C++ for a UNIX† environment and a conventional window system. The architecture of ET++ is based on MacApp and integrates a rich collection of user interface building blocks as well as basic data structures to form a homogeneous and extensible system. The paper describes the graphic model and its underlying abstract window system interface, shows composite objects as a substrate for declarative layout specification of complex dialogs, and presents a model for editable text allowing the integration of arbitrary interaction objects.
A smalltalk window system based on constraints
Authors: Epstein Danny , LaLonde Wilf R.
Published: November 2005

We describe the design of a constraint-based window system for Smalltalk. This window system uses constraints to specify attributes of windows and relationships between them. Three classes of constraints are supported, one of which is implicit and not available for general use. The system extends the current Smalltalk system, providing support for both fixed-size and fixed-scale windows. It also provides the capability to dynamically reorganize the layout of a window. A goal of the design is to produce a system with real-time response that is fast enough to be substituted for the existing system. A prototype with response times of approximately 1/4 second has been implemented to demonstrate the feasibility of the design as well as to point out several important optimizations.
A overview of modular smalltalk
Authors: Wirfs-Brock Allen , Wilkerson Brian
Published: November 2005

This paper introduces the programming language Modular Smalltalk, a descendant of the Smalltalk-80 programming language. Modular Smalltalk was designed to support teams of software engineers developing production application programs that can run independently of the environment in which they are developed. We first discuss our motivation for designing Modular Smalltalk. Specifically, we examine the properties of Smalltalk-80 that make it inappropriate for our purposes. We then present an overview of the design of Modular Smalltalk, with an emphasis on how it overcomes these weaknesses.
Integrating an object-oriented programming system with a database system
Authors: Kim Won , Ballou Nat , Banerjee Jay , Chou Hong-Tai , Garza Jorge G. , Woelk Darrell
Published: November 2005

There are two major issues to address to achieve integration of an object-oriented programming system with a database system. One is the language issue: an object-oriented programming language must be augmented with semantic data modeling concepts to provide a robust set of data modeling concepts to allow modeling of entities for important real-world applications. Another is the computational-model issue: application programmers should be able to access and manipulate objects as though the objects are in an infinite virtual memory; in other words, they should not have to be aware of the existence of a database system in their computations with the data structures the programming language allows. This paper discusses these issues and presents the solutions which we have incorporated into the ORION object-oriented database system at MCC.
Controlling propagation of operations using attributes on relations
Authors: Rumbaugh James
Published: November 2005

Controlling the propagation of operations through a collection of objects connected by various relationships has been a problem both for the object-oriented and the data base communities. Operations such as copy, destroy, print, and save must propagate to some, but not all, of the objects in a collection. Such operations can be implemented using ad hoc methods on objects, at the cost of extra work and loss of clarity. The use of propagation attributes on the relationships between objects permits a concise, intuitive specification of the manner in which operations should propagate from one object to another. These concepts have been implemented in the object-oriented language DSM and have been used to write applications.
How to invent distributed implementation schemes of an object-based concurrent language: a transformational approach
Authors: Shibayama Etsuya
Published: November 2005

A design and verification technique for implementation schemes of distributed software is presented. In this technique, first, the specification is modelled by a concurrent object system, that is, one which is constituted of computational agents with capability of concurrent execution and message passing. Then, such a concurrent object system is transformed into another concurrent object system, which models a sophisticated implementation scheme.

Our transformation technique is mainly based on fusing and splitting concurrent objects. The correctness of transformation rules can be proven formally.
Reflection in an object-oriented concurrent language
Authors: Watanabe Takuo , Yonezawa Akinori
Published: November 2005

Our work is along the line of the work of B. Smith and P. Maes. We first discuss our notion of
reflection
in object-oriented
concurrent
computation and then present a reflective object-oriented concurrent language ABCL/R. We give several illustrative examples of reflective programming such as (1) dynamic concurrent acquisition of “methods” from other objects, (2) monitoring the behavior of concurrently running objects, and (3) augmentation of the time warp mechanism to a concurrent system. Also the definition of a meta-circular interpreter of this language is given as the definition of a meta-object. The language ABCL/R has been implemented. All the examples given in this paper are running on our ABCL/R system.
An execution model for distributed object-oriented computation
Authors: Bensley Edward H. , Brando Thomas J. , Prelle Myra Jean
Published: November 2005

This paper describes an execution model being developed for distributed object-oriented in a message-passing multiple-instruction/multiple-data-stream (MIMD) environment. The objective is to execute an object-oriented program as concurrently as possible. Some opportunities for concurrency can be identified explicitly by the programmer. Others can be identified at compile time. There are some opportunities for concurrency, however, that can only be discovered at runtime because they are data-dependent. The model of execution we describe attempts to discover and exploit the data-dependent concurrency that exists in a given program execution.
Non-intrusive and interactive profiling in parasight
Authors: Aral Ziya , Gertner Ilya
Published: November 2005

Debugging the performance of parallel applications is crucial for fully utilizing the potential of multiprocessor hardware. This paper describes profiling tools in Parasight, a programming environment that is geared towards non-intrusive performance analysis and high-level debugging. In Parasight, profilers execute as observer programs which run concurrently with the target program and monitor its behavior. This design grew out of our experience in debugging and monitoring the performance of real parallel programs.

Parasight is used to implement an interactive profiler based on gprof, a standard UNIX profiling tool. The new profiler is an interactive tool that is dynamically controlled by the programmer and can run concurrently with the target program. It is also less intrusive than the original. This was achieved in part by off-loading the profile gathering computations to an adjacent processor and in part by allowing selective profiling.

In conjunction with the new profiler, Parasight is used to implement high-level custom profiling routines that may be inserted at arbitrary locations in a target program to measure user-defined abstractions. One outcome has been to develop the beginnings of a profiling methodology in which high-level performance problems are detected through a function profiler and detailed performance bottlenecks are analyzed with custom profiling routines.

Parasight, the new profiler and their associated tools have been implemented on the Encore Multimax, a shared-memory multiprocessor running UNIX. They have been used to profile both parallel and sequential programs.
Program development for a systolic array
Authors: Bruegge Bernd
Published: November 2005

The primary objective of the Warp programming environment (WPE) is to simplify the use of Warp, a high-performance programmable linear systolic array connected to a general-purpose workstation host. WPE permits the development of distributed applications that access Warp either locally from the host or remotely from a large number of workstations connected to a local area network. Its audience includes the user who calls routines from a library, the programmer who develops new algorithms for Warp, as well as the implementor who writes support software. Since the linear arrangement of the cells in the array restricts direct input and output with the host to the boundary cells, a source language debugger is important for program development on Warp. This paper presents the Warp debugger and its relation to the other components of the Warp programming environment.
Efficient interprocedural analysis for program parallelization and restructuring
Authors: Li Zhiyuan , Yew Pen-Chung
Published: November 2005

An approach to efficient interprocedural analysis for program parallelization and restructuring is presented. Such analysis is needed for parallelizing loops which contain procedure calls. Our approach captures call effect on data dependencies by propagating the precise information of array subscripts from the called procedure. This allows the optimizing compiler to choose an efficient yet precise data dependence test scheme depending on the complexity of array reference patterns. The other existing methods do not provide such flexibility, hence may suffer from either imprecision or inefficiency. The paper also discusses usage of classical summary information in several important transformations for program parallelization. Experimental results are reported.
Qlisp: experience and new directions
Authors: Goldman Ron , Gabriel Richard P.
Published: November 2005

Qlisp, a dialect of Common Lisp, has been proposed as a multiprocessing programming language which is suitable for studying the styles of parallel programming at the medium-grain level. An initial version of Qlisp has been implemented on a multiprocessor and a number of experiments with it conducted. This paper describes the implementation, reports on some of the experiments, and presents some new constructs that are suggested from programming experience with Qlisp.
The parallel decomposition and implementation of an integrated circuit global router
Authors: Rose Jonathan
Published: November 2005

Better quality automatic layout of integrated circuits can be obtained by combining the placement and routing phases so that routing is used as the
cost function
for placement optimization. Conventional routers are too slow to make this feasible, and so this paper presents a parallel decomposition and implementation of an integrated circuit global router. The
LocusRoute
router is divided into three orthogonal “axes” of parallelism: routing several wires at once, routing segments of a wire in parallel, and dividing up the potential routes of a segment among different processors to be evaluated. The implementation of two of these approaches achieve significant speedup - wire-by-wire parallelism attains speedups from 6.9 to 13.6 using sixteen processors, and route-by-route achieves up to 4.6 using eight processors. When combined, these approaches can potentially provide speedups of as much as 55 times.
Soar/PSM-E: investigating match parallelism in a learning production sytsem
Authors: Tambe Milind , Kalp Dirk , Gupta Anoop , Forgy Charles , Milnes Brian , Newell Allen
Published: November 2005

Soar is an attempt to realize a set of hypotheses on the nature of general intelligence within a single system. Soar uses a production system (rule based system) to encode its knowledge base. Its learning mechanism, chunking, adds productions continuously to the production system. The process of searching for relevant knowledge, matching, is known to be a performance bottleneck in production systems. PSM-E is a
C
-based implementation of the OPS5 production system on the Encore Multimax that has achieved significant speedups in matching. In this paper we describe our implementation, Soar/PSM-E, of Soar on the Encore Multimax that is built on top of PSM-E. We first describe the extensions and modifications required to PSM-E in order to support Soar, especially the capability of adding productions at run time as required by chunking. We present the speedups obtained on Soar/PSM-E and discuss some effects of chunking on parallelism. We also analyze the performance of the system and identify the bottlenecks limiting parallelism. Finally, we discuss the work in progress to deal with some of them.
Applications experience with Linda
Authors: Carriero Nicholas , Gelernter David
Published: November 2005

We describe three experiments using C-Linda to write parallel codes. The first involves assessing the similarity of DNA sequences. The results demonstrate Linda's flexibility—Linda solutions are presented that work well at two quite different levels of granularity. The second uses a prime finder to illustrate a class of algorithms that do not (easily) submit to automatic parallelizers, but can be parallelized in straight-forward fashion using C-Linda. The final experiment describes the process lattice model, an “inherently” parallel application that is naturally conceived as multiple interacting processes. Taken together, the experience described here bolsters our claim that Linda can bridge the gap between the growing collection of parallel hardware and users eager to exploit parallelism.

This work is supported by the NSF under grants DCR-8601920 and DCR-8657615 and by the ONR under grant N00014-86-K-0310. We are grateful to Argonne National Labs for providing access to a Sequent Symmetry.
Exploiting variable grain parallelism at runtime
Authors: Gupta Anoop , Tucker Andrew
Published: November 2005

Currently, almost all parallel implementations of programs fix the granularity at which parallelism is exploited at design time. Depending on the application structure and the parallel hardware structure, the programmer decides to exploit parallelism at a fine granularity or coarse granularity or some intermediate granularity, but this granularity is not changed at runtime. In this paper we argue that for many applications fixing the granularity in advance is not a good strategy. Instead it is advantageous to decide the granularity at which parallelism is exploited at runtime, as a function of the available hardware resources and as a function of the overheads associated with going to a finer granularity. We present experimental results from a parallel implementation of a geometric constraint satisfaction system to support our thesis. Our results show a significant advantage in using adaptive parallelism.
Communication-sensitive heuristics and algorithms for mapping compilers
Authors: Stramm Bernd , Berman Francine
Published: November 2005

The mapping problem arises when parallel algorithms are implemented on parallel machines. When the number of processes exceeds the number of available processing elements, the mapping problem includes the contraction problem. In this paper, we identify communication-sensitive heuristics which promote good contractions for graph-based parallel algorithms on non-shared memory multiprocessors. We present algorithms which utilize these heuristics and discuss their performance on a group of diverse benchmarks.
An embedded language approach to teaching hardware compilation
Authors: Claessen Koen , Pace Gordon J.
Published: November 2005

This paper describes a course in hardware description and synthesis (hardware compilation), taught as an introductory graduate course at Chalmers University of Technology, and as an advanced undergraduate course at the University of Malta. The functional programming language Haskell was used both to describe circuits and circuit synthesis schemes.
Computer assisted manipulation of algebraic process specifications
Authors: Groote Jan Friso , Lisser Bert
Published: November 2005

Specifications of system behaviour tend to become large. Analysis of such specifications requires automated tools. Most attention hitherto has been invested in fully automatic tools. We however believe that in many cases human intervention is required and we therefore propose a number of computer tools to transform process specifications. The concrete manipulation tools that we describe can eliminate constants, redundant sum variables and parameters, and allow to split variables ranging over complex datatypes. These tools can transform specifications with large finite state spaces to variants with state spaces being a fraction of their original size, and transform specifications with infinite state spaces to those with finite state spaces.
Environment classifiers
Authors: Taha Walid , Nielsen Michael Florentin
Published: November 2005

This paper proposes and develops the basic theory for a new approach to typing multi-stage languages based a notion of
environment classifiers
. This approach involves explicit but lightweight tracking -- at type-checking time -- of the origination environment for future-stage computations. Classification is less restrictive than the previously proposed notions of closedness, and allows for both a more expressive typing of the "run" construct and for a unifying account of typed multi-stage programmin.The proposed approach to typing requires making cross-stage persistence (CSP) explicit in the language. At the same time, it offers concrete new insights into the notion of levels and in turn into CSP itself. Type safety is established in the simply-typed setting. As a first step toward introducing classifiers to the Hindley-Milner setting, we propose an approach to integrating the two, and prove type preservation in this setting.
Bitwidth aware global register allocation
Authors: Tallam Sriraman , Gupta Rajiv
Published: November 2005

Multimedia and network processing applications make extensive use of subword data. Since registers are capable of holding a full data word, when a subword variable is assigned a register, only part of the register is used. New embedded processors have started supporting instruction sets that allow direct referencing of bit sections within registers and therefore multiple subword variables can be made to simultaneously reside in the same register without hindering accesses to these variables. However, a new register allocation algorithm is needed that is aware of the bitwidths of program variables and is capable of packing multiple subword variables into a single register. This paper presents one such algorithm.The algorithm we propose has two key steps. First, a combination of forward and backward data flow analyses are developed to determine the bitwidths of program variables throughout the program. This analysis is required because the declared bitwidths of variables are often larger than their true bitwidths and moreover the minimal bitwidths of a program variable can vary from one program point to another. Second, a novel interference graph representation is designed to enable support for a fast and highly accurate algorithm for packing of subword variables into a single register. Packing is carried out by a node coalescing phase that precedes the conventional graph coloring phase of register allocation. In contrast to traditional node coalescing, packing coalesces a set of interfering nodes. Our experiments show that our bitwidth aware register allocation algorithm reduces the register requirements by 10\% to 50% over a traditional register allocation algorithm that assigns separate registers to simultaneously live subword variables.
Folklore confirmed
Authors: Carter Larry , Ferrante Jeanne , Thomborson Clark
Published: November 2005

Many program analysis techniques used by compilers are applicable only to programs whose control flow graphs are
reducible
. Node-splitting is a technique that can be used to convert any control flow graph to a reducible one. However, as has been observed for various node-splitting algorithms, there can be an exponential blowup in the size of the graph.We prove that exponential blowup is unavoidable. In particular, we show that any reducible graph that is equivalent to the complete graph on
n
nodes (or to related bounded-degree control flow graphs) must have at least 2

n-1

nodes. While this result is not a surprise, it may be relevant to the quest for finding methods of obfuscation for software protection.
Coercive subtyping for the calculus of constructions
Authors: Chen Gang
Published: November 2005

We present a coercive subtyping system for the calculus of constructions. The proposed system λ
C

CO

over≤ is obtained essentially by adding coercions and η-conversion to λ
C

≤

[10], which is a subtyping extension to the calculus of constructions without coercions. Following [17, 18], the coercive subtyping
c
:
A
η
B
is understood as a special case of typing in arrow type
c
:
A
→
B
such that the term
c
behaves like an identity function. We prove that, with respect to this semantic interpretation, the proposed coercive subtyping system is sound and complete, and that this completeness leads to transitivity elimination (transitivity rule is admissible). In addition, we establish the equivalence between λ
C

CO

over≤ and
CC

ßη

, this fact implies that λ
C

CO

over≤ has confluence, subject reduction and strong normalization. We propose a formalization of coercion inference problem and present a sound and complete coercion inference algorithm.
Destructors, finalizers, and synchronization
Authors: Boehm Hans-J.
Published: November 2005

We compare two different facilities for running cleanup actions for objects that are about to reach the end of their life.Destructors, such as we find in C++, are invoked synchronously when an object goes out of scope. They make it easier to implement cleanup actions for objects of well-known lifetime, especially in the presence of exceptions.Languages like Java[8], Modula-3[12], and C\#[6] provide a different kind of "finalization" facility: Cleanup methods may be run when the garbage collector discovers a heap object to be otherwise inaccessible. Unlike C++ destructors, such methods run in a separate thread at some much less well-defined time.Languages like Java[8], Modula-3[12], and C\#[6] provide a different kind of "finalization" facility: Cleanup methods may be run when the garbage collector discovers a heap object to be otherwise inaccessible. Unlike C++ destructors, such methods run in a separate thread at some much less well-defined time.We argue that these are fundamentally different, and potentially complementary, language facilities. We also try to resolve some common misunderstandings about finalization in the process. In particular:

The asynchronous nature of finalizers is not just an accident of implementation or a shortcoming of tracing collectors; it is necessary for correctness of client code, fundamentally affects how finalizers must be written, and how finalization facilities should be presented to the user.

An object may legitimately be finalized while one of its methods are still running. This should and can be addressed by the language specification amd client code.
A real-time garbage collector with low overhead and consistent utilization
Authors: Bacon David F. , Cheng Perry , Rajan V. T.
Published: November 2005

Now that the use of garbage collection in languages like Java is becoming widely accepted due to the safety and software engineering benefits it provides, there is significant interest in applying garbage collection to hard real-time systems. Past approaches have generally suffered from one of two major flaws: either they were not provably real-time, or they imposed large space overheads to meet the real-time bounds. We present a mostly non-moving, dynamically defragmenting collector that overcomes both of these limitations: by avoiding copying in most cases, space requirements are kept low; and by fully incrementalizing the collector we are able to meet real-time bounds. We implemented our algorithm in the Jikes RVM and show that at real-time resolution we are able to obtain mutator utilization rates of 45% with only 1.6--2.5 times the actual space required by the application, a factor of 4 improvement in utilization over the best previously published results. Defragmentation causes no more than 4% of the traced data to be copied.
Ownership types for object encapsulation
Authors: Boyapati Chandrasekhar , Liskov Barbara , Shrira Liuba
Published: November 2005

Ownership types provide a statically enforceable way of specifying object encapsulation and enable local reasoning about program correctness in object-oriented languages. However, a type system that enforces strict object encapsulation is too constraining: it does not allow efficient implementation of important constructs like iterators. This paper argues that the right way to solve the problem is to allow objects of classes defined in the same module to have privileged access to each other's representations; we show how to do this for inner classes. This approach allows programmers to express constructs like iterators and yet supports local reasoning about the correctness of the classes, because a class and its inner classes together can be reasoned about as a module. The paper also sketches how we use our variant of ownership types to enable efficient software upgrades in persistent object stores.
Types for atomicity
Authors: Flanagan Cormac , Qadeer Shaz
Published: November 2005

Ensuring the correctness of multithreaded programs is difficult, due to the potential for unexpected and nondeterministic interactions, between threads. Previous work addressed this problem by devising tools for detecting
race conditions
, a situation where two threads simultaneously access the same data variable, and at least one of the accesses is a write. Unfortunately, verifying the absence of such simultaneous-access race conditions is neither necessary nor sufficient to ensure the absence of errors due to unexpected thread interactions.We propose that a stronger non-interference property is required, namely the
atomicity
of code blocks, and we present a type system for specifying and verifying such atomicity properties. The type system allows statement blocks and functions to be annotated with the keyword atomic. If the program type checks, then the type system guarantees that for any arbitrarily-interleaved program execution, there is a corresponding execution with equivalent behavior in which the instructions of each atomic block executed by a thread are not interleaved with instructions from other threads. This property allows programmers to reason about the behavior of well-typed programs at a higher level of granularity, where each atomic block is executed "in one step", thus signi .cantly simplifying both formal and informal reasoning.Our type system is sufficient to verify a number of interesting examples. For example,it can prove that many methods of java.util. Vector are atomic, even though some methods have benign race conditions, and would be rejected by earlier type systems for race detection.
The logical approach to stack typing
Authors: Ahmed Amal , Walker David
Published: November 2005

We develop a logic for reasoning about
adjacency
and
separation
of memory blocks, as well as
aliasing
of pointers. We provide a memory model for our logic and present a sound set of natural deduction-style inference rules. We deploy the logic in a simple type system for a stack-based assembly language. The connectives for the logic provide a flexible yet concise mechanism for controlling allocation, deallocation and access to both heap-allocated and stack-allocated data.
Typed compilation of recursive datatypes
Authors: Vanderwaart Joseph C. , Dreyer Derek , Petersen Leaf , Crary Karl , Harper Robert , Cheng Perry
Published: November 2005

Standard ML employs an opaque (or generative) semantics of datatypes, in which every datatype declaration produces a new type that is different from any other type, including other identically defined datatypes. A natural way of accounting for this is to consider datatypes to be abstract. When this interpretation is applied to type-preserving compilation, however, it has the unfortunate consequence that datatype constructors cannot be inlined, substantially increasing the run-time cost of constructor invocation compared to a traditional compiler. In this paper we examine two approaches to eliminating function call overhead from datatype constructors. First, we consider a transparent interpretation of datatypes that does away with generativity, altering the semantics of SML; and second, we propose an interpretation of datatype constructors as coercions, which have no run-time effect or cost and faithfully implement SML semantics.
Centaur: the system
Authors: Borras P. , Clement D. , Despeyroux Th. , Incerpi J. , Kahn G. , Lang B. , Pascual V.
Published: November 2005

This paper describes the organization of the CENTAUR system and its main components. The system is a generic interactive environment. When given the formal specification of a particular programming language-including syntax and semantics — it produces a language specific environment. This resulting environment includes a structure editor, an interpreter/debugger and other tools, all of which have graphic interfaces. CENTAUR is made of three parts: a database component, that provides standardized representation and access to formal objects and their persistent storage; a logical engine that is used to execute formal specifications; an object-oriented man-machine interface that gives easy access to the system's functions. CENTAUR is essentially written in Lisp (Le_Lisp). The logical engine is Prolog (Mu-Prolog). The man-machine interface is built on top of the virtual graphics facility of Le_Lisp, itself primarily implemented on top of X-Windows.
The ergo support system: an integrated set of tools for prototyping integrated environments
Authors: Lee Peter , Pfenning Frank , Rollins Gene , Scherlis William
Published: November 2005

The Ergo Support System (ESS) is an engineering framework for experimentation and prototyping to support the application of formal methods to program development, ranging from program analysis and derivation to proof-theoretic approaches. The ESS is a growing suite of tools that are linked together by means of a set of abstract interfaces. The principal engineering challenge is the design of abstract interfaces that are semantically rich and yet flexible enough to permit experimentation with a wide variety of formally-based program and proof development paradigms and associated languages. As part of the design of ESS, several abstract interface designs have been developed that provide for more effective component integration while preserving flexibility and the potential for scaling. A benefit of the open architecture approach of ESS is the ability to mix formal and informal approaches in the same environment architecture. The ESS has already been applied in a number of formal methods experiments.
Graph attribution as a specification paradigm
Authors: Alpern Bowen , Carle Alan , Rosen Barry , Sweeney Peter , Zadeck Kenneth
Published: November 2005

An interactive software development environment can be viewed as a structure-based editor, provided that
structure
is broadly interpreted. The user sees and manipulates complex objects at various levels of detail. Many of the implications of changes are analyzed and made available to the user as frequently as the user wishes, without a mode change from editing to compiling or linking. To help provide these services in a uniform way that can readily respond to changes in the programming language(s) supported or in the preferences of individual users, some programming environments use attribute grammars.

The
attributed graph specifications (AGS's)
defined here are inspired by attribute grammars but are free of their restriction to structures expressible by parse trees generated by context-free grammars. An AGS deals with whatever structure is appropriate in a given application. The graph concept here is not tied to any decision about pictorial representation. Indeed, we do not care whether the user sees pictures or text or a combination of the two. The AGS formalism is a uniform paradigm for specifying the desired relations among many and varied chunks of information, some of which are changed by the user. The benefits of the original attribute grammar formalism were confined to parse trees and severely restricted manipulations of parse trees. The AGS paradigm extends those benefits to software development on a larger scale.
User interface support for the integration of software tools: an iconic model of interaction
Authors: Beaudouin-Lafon Michel
Published: November 2005

This paper presents a model of interaction based on an iconic representation of objects. An application of the model to an iconic shell for Unix™ is described. Finally a client server architecture for the implementation of the model is introduced. We show that a software development environment can take advantage of such a model and architecture in order to provide a consistent, adaptable and extensible user interface.
A graph transform model for configuration management environments
Authors: Heimbigner Dennis , Krane Steven
Published: November 2005

A model for software configuration management that subsumes several existing systems is described. It is patterned after compiler models in which programs are transformed by multiple phases ending in an executable program. We model configuration management as transforming a high-level specification of a software product to be produced into a complete specification capable of being executed to construct the product. This transformational approach is used to model four existing systems and to compare and contrast their operation.
Object management issues for software engineering environments workshop report
Authors: Penedo Maria H. , Ploedereder Erhard , Thomas Ian
Published: November 2005

During recent years, several research efforts in the area of software development environments have focused on the provision of uniform Object Management Systems (OMS) as a framework for tool integration and communication. This paper summarizes discussions of an OMS Workshop on the issues that arise in defining an appropriate data model for an OMS.
Portable IPC on Vanilla Unix
Authors: Rain M.
Published: November 2005

The paper describes an efficient, portable implementation of interprocess communication which does not require modifications to the operating system. The ipc facility described supports communication between arbitrary processes even on systems, such as vanilla Unix V, which normally restrict communication to parent/child or sibling process pairs. Interprocess channels are dynamically allocated, and no system configuration or other static specification is required. The implementation embeds a server registry facility to help clients find the ipc channels for servers. A library of C functions supports the creation, allocation, deallocation and maintenance of ipc channels, the registering, unregistering and searching for servers, and a general packet communication protocol for use between processes using ipc. While described in the context of Unix, the mechanism generalizes to any operating system which supports the 'pipe' or 'core file' concept.
SLD: a folk acronym?
Authors: Ringwood G. A.
Published: November 2005

Delving into the archives for the meaning of SLD reveals that the name is ill chosen. Furthermore, empiric evidence shows that the significance of the letters is entering the realms folklore. As clear logical thinking about a subject is impeded if the vocabulary is misleading or confused this note is intended to bring this matter to light before many more generations of logic programmers proliferate misconceptions. Clear logical thinking is of even greater import for a subject that purports to be about logic.
On prolog and the occur check problem
Authors: Marriott K. , Sondergaard H.
Published: November 2005

It is well-known that omission of the occur check in unification leads to unsound Prolog systems. Nevertheless, most Prolog systems omit the occur check because this makes unification much faster and unsoundness allegedly seldom manifests itself. We revisit the occur check problem and point to two aspects that have previously received no attention. Firstly, "unification without the occur check" is ambiguous, and in practice, Prolog systems vary markedly in their reaction to programs having occur check problems. Secondly, even very simple program transformations are unsafe for pure Prolog when the occur check is omitted. We conclude that the occur check problem is important, and in particular, that the current efforts to standardize Prolog should address it.
A translator from small euclid to pascal
Authors: Pintelas P. E. , Ventouris K. P. , Papassimakopoulou M. D.
Published: November 2005

This paper describes the design and implementation of a translator from Small Euclid, an extended subset of the system programming language Euclid, to Pascal. The translator is built with the help of the tools LEX and YACC and consists of three different passes each of which performs some transformations to the input program. During the translation of an input program no intermediate code is generated but the translation to Pascal is direct. The translator performs lexical and syntactic checks and a restricted number of semantic checks before producing an equivalent program in Pascal. The differences between Small Euclid and Pascal are identified and translation proposals are discussed while details of the translator's internal structures and its perfonance are given.
Formulations and benefits of the law of demeter
Authors: Lienberherr K. J.
Published: November 2005

Our initial ideas on preventive maintenance of object-oriented systems were presented in [LHR88] which describes a set of guidelines called the "Law of Demeter". As a result of this publication we have received much feedback, as well as a detailed critique from [Sak89]. In this paper we expand on the initial ideas and present a new perspective with which to view the Law. This perspective is based on client/supplier relationships between methods and classes and allows a cleaner description of the benefits of the Law. This paper is also a reply to [Sak89] which was pointing out that the formulation of the Law for C++ needs additional work.At first sight, the idea of any rules or principles being superimposed on the creative mind seems more likely to hinder than to help, but this is really quite untrue in practice. Disciplined thinking focusses inspiration rather than blinkers it.