bluuebunny/crossref_metadata_2025 huggingface dataset:
Concurrent garbage collection using hardware-assisted profiling
Authors: Heil Timothy H. , Smith James E.
Published: November 2005

In the presence of on-chip multithreading, a Virtual Machine (VM) implementation can readily take advantage of
service threads
for enhancing performance by performing tasks such as profile collection and analysis, dynamic optimization, and garbage collection concurrently with program execution. In this context, a hardware-assisted profiling mechanism is proposed. The
Relational Profiling Architecture
(RPA) is designed from the top down. RPA is based on a relational model similar to the relational database model. Instructions selected for profiling produce a record of information. A simple
query engine
examines these records for patterns, and performs simple actions on matching records.

The power and flexibility of RPA is demonstrated by developing a concurrent generational garbage collector for Java. Detailed execution driven simulations show that this collector has an average runtime overhead of approximately 0.6%. The short pauses in the application required for synchronization with the garbage collector are at most 54 microseconds, given a 1GHz clock frequency.
Implementing an on-the-fly garbage collector for Java
Authors: Domani Tamar , Kolodner Elliot K. , Lewis Ethan , Salant Eliot E. , Barabash Katherine , Lahan Itai , Levanoni Yossi , Petrank Erez , Yanorer Igor
Published: November 2005

Java uses garbage collection (GC) for the automatic reclamation of computer memory no longer required by a running application. GC implementations for Java Virtual Machines (JVM) are typically designed for single processor machines, and do not necessarily perform well for a server program with many threads running on a multiprocessor. We designed and implemented an on-the-fly GC, based on the algorithm of Doligez, Leroy and Gonthier [13, 12] (DLG), for Java in this environment. An
on-the-fly collector
, a collector that does not stop the program threads, allows all processors to be utilized during collection and provides uniform response times. We extended and adapted DLG for Java (e.g., adding support for weak references) and for modern multiprocessors without sequential consistency, and added performance improvements (e.g., to keep track of the objects remaining to be traced). We compared the performance of our implementation with stop-the-world mark-sweep GC. Our measurements show that the performance advantage for our collector increases as the number of threads increase and that it provides uniformly low response times.
Diffusion tree restructuring for indirect reference counting
Authors: Dickman Peter
Published: November 2005

A new variant algorithm for distributed acyclic garbage detection is presented for use in hybrid garbage collectors. The existing fault-tolerance of Piquer's Indirect Reference Counting (IRC) is qualitatively improved by this new approach. The key insight that underpins this work is the observation that the parent of a node in the IRC diffusion tree need not remain constant. The new variant exploits standard mechanisms for implementing diffusion trees and remote references, using four simple low-cost techniques to dynamically restructure the trees to reduce their depth. This variant reduces third-party dependencies, which make standard IRC vulnerable to process failure, while retaining tolerance of message reordering and without incurring substantial overheads. The paper carefully motivates the algorithm, presents the full technical basis for its development, provides a clear explanation of implementation details and includes an initial discussion of performance issues.
Improving the quality of compiler construction with object-oriented techniques
Authors: Gutiérrez David Basanta , Luengo Díez Cándida , Izquierdo Castanedo Raul , Labra Gayo Jose Emilio , Cueva Juan Manuel
Published: November 2005

Compiler construction tools have proven to be very useful for developers in the traditional task of compiler construction and language processors that are present in editors, word processors or XML. In contrast to their importance, traditional tools like YACC have failed to take advantage of object-oriented techniques. This is particularly unfortunate because compilers, being complex systems, would definitely benefit from the modularity and code reuse that object orientation allows.In this paper, O2C2, an object-oriented framework generator, is presented. The tool has the potential to improve the quality of compiler construction by introducing the concept of frameworks in the field of compilers and language processors.
Multiparadigm design of a simple relational database
Authors: Knutson Charles D. , Budd Timothy A. , Vidos Hugh
Published: November 2005

Multiparadigm programming languages (such as Leda) seek to merge elements of several programming paradigms into a single cohesive language that utilizes programming and conceptual aspects from various paradigms (including imperative, object-oriented, functional and logic). While there are relatively few fully multiparadigm languages, most popular languages increasingly incorporate aspects from multiple paradigms. Despite the fact that multiparadigm programming is an increasing reality, there are few methods for multiparadigm design. This paper uses Leda to explore multiparadigm program design via a simple database example. This paper is exploratory in nature, and exposes areas that should be researched further.
A generic type system for the Pi-calculus
Authors: Igarashi Atsushi , Kobayashi Naoki
Published: November 2005

We propose a general, powerful framework of type systems for the π-calculus, and show that we can obtain as its instances a variety of type systems guaranteeing non-trivial properties like deadlock-freedom and race-freedom. A key idea is to express types and type environments as abstract processes: We can check various properties of a process by checking the corresponding properties of its type environment. The framework clarifies the essence of recent complex type systems, and it also enables sharing of a large amount of work such as a proof of type preservation, making it easy to develop new type systems.
Modules, abstract types, and distributed versioning
Authors: Sewell Peter
Published: November 2005

In a wide-area distributed system it is often impractical to synchronise software updates, so one must deal with many coexisting versions. We study static typing support for modular wide-area programming, modelling separate compilation/linking and execution of programs that interact along typed channels. Interaction may involve communication of values of abstract types; we provide the developer with fine-grain versioning control of these types to support interoperation of old and new code. The system makes use of a second-class module system with singleton kinds; we give a novel operational semantics for separate compilation/linking and execution and prove soundness.
Type-indexed rows
Authors: Shields Mark , Meijer Erik
Published: November 2005

Record calculi use labels to distinguish between the elements of products and sums. This paper presents a novel variation,
type-indexed rows
, in which labels are discarded and elements are indexed by their type alone. The calculus, λ
TIR
, can express tuples, recursive datatypes, monomorphic records, polymorphic extensible records, and closed-world style type-based overloading. Our motivating application of λ
TIR
, however, is to encode the "choice" types of XML, and the "unordered tuple" types of SGML. Indeed, λ
TIR
is the kernel of the language XMλ, a lazy functional language with direct support for XML types ("DTDs") and terms ("documents").The system is built from rows, equality constraints, insertion constraints and constrained, or qualified, parametric polymorphism. The test for constraint satisfaction is complete, and for constraint entailment is only mildly incomplete. We present a type checking algorithm, and show how λ
TIR
may be implemented by a type-directed translation which replaces type-indexing by conventional natural-number indexing. Though not presented in this paper, we have also developed a constraint simplification algorithm and type inference system.
Subtyping arithmetical types
Authors: Gil Joseph (Yossi)
Published: November 2005

We consider the type system formed by a finite set of primitive types such as integer, character, real, etc., and three type construction operators: (i) Cartesian product, (ii) disjoint sum, and (iii) recursive type definitions. Type equivalence is defined to obey the arithmetical rules: commutativity and associativity of product and sum and distributivity of product over sum. We offer a compact representation of the types in this system as multivariate algebraic functions. This type system admits two natural notions of subtyping: "multiplicative", which roughly corresponds to the notion of object-oriented subtyping, and "additive", which seems to be more appropriate in our context. Both kinds of subtyping can be efficiently computed if no recursive definitions are allowed. Our main result is that additive subtyping is undecidable in the general case. Perhaps surprisingly, this undecidability result is by reduction from Hilbert's Tenth Problem (HIO): the solution of Diophantine equations.
Dynamic software updating
Authors: Hicks Michael , Moore Jonathan T. , Nettles Scott
Published: November 2005

Many important applications must run continuously and without interruption, yet must be changed to fix bugs or upgrade functionality. No prior general-purpose methodology for dynamic updating achieves a practical balance between flexibility, robustness, low overhead, and ease of use.

We present a new approach for C-like languages that provides type-safe dynamic updating of native code in an extremely flexible manner (code, data, and types may be updated, at programmer-determined times) and permits the use of automated tools to aid the programmer in the updating process. Our system is based on
dynamic patches
that both contain the updated code and the code needed to transition from the old version to the new. A novel aspect of our patches is that they consist of
verifiable native code
(
e.g.
Proof-Carrying Code [17] or Typed Assembly Language [16]), which is native code accompanied by annotations that allow on-line verification of the code's safety. We discuss how patches are generated mostly automatically, how they are applied using dynamic-linking technology, and how code is compiled to make it updateable.

To concretely illustrate our system, we have implemented a dynamically-updateable web server, FlashEd. We discuss our experience building and maintaining FlashEd. Performance experiments show that for FlashEd, the overhead due to updating is typically less than 1%.
Principled scavenging
Authors: Monnier Stefan , Saha Bratin , Shao Zhong
Published: November 2005

Proof-carrying code and typed assembly languages aim to minimize the trusted computing base by directly certifying the actual machine code. Unfortunately, these systems cannot get rid of the dependency on a trusted garbage collector. Indeed, constructing a provably type-safe garbage collector is one of the major open problems in the area of certifying compilation.

Building on an idea by Wang and Appel, we present a series of new techniques for writing type-safe stop-and-copy garbage collectors. We show how to use intensional type analysis to capture the contract between the mutator and the collector, and how the same method can be applied to support forwarding pointers and generations. Unlike Wang and Appel (which requires whole-program analysis), our new framework directly supports higher-order funtions and is compatible with separate compilation; our collectors are written in provably type-safe languages with rigorous semantics and fully formalized soundness proofs.
The pointer assertion logic engine
Authors: Møller Anders , Schwartzbach Michael I.
Published: November 2005

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

Programs are annotated with partial specifications expressed in Pointer Assertion Logic, a new notation for expressing properties of the program store. We work in the logical tradition by encoding the programs and partial specifications as formulas in monadic second-order logic. Validity of these formulas is checked by the MONA tool, which also can provide explicit counterexamples to invalid formulas.

To make verification decidable, the technique requires explicit loop and function call invariants. In return, the technique is highly modular: every statement of a given program is analyzed only once.

The main target applications are safety-critical data-type algorithms, where the cost of annotating a program with invariants is justified by the value of being able to automatically verify complex properties of the program.
A unified framework for schedule and storage optimization
Authors: Thies William , Vivien Frédéric , Sheldon Jeffrey , Amarasinghe Saman
Published: November 2005

We present a unified mathematical framework for analyzing the tradeoffs between parallelism and storage allocation within a parallelizing compiler. Using this framework, we show how to find a good storage mapping for a given schedule, a good schedule for a given storage mapping, and a good storage mapping that is valid for all legal schedules. We consider storage mappings that collapse one dimension of a multi-dimensional array, and programs that are in a single assignment form with a one-dimensional schedule. Our technique combines affine scheduling techniques with occupancy vector analysis and incorporates general affine dependences across statements and loop nests. We formulate the constraints imposed by the data dependences and storage mappings as a set of linear inequalities, and apply numerical programming techniques to efficiently solve for the shortest occupancy vector. We consider our method to be a first step towards automating a procedure that finds the optimal tradeoff between parallelism and storage space.
Exact analysis of the cache behavior of nested loops
Authors: Chatterjee Siddhartha , Parker Erin , Hanlon Philip J. , Lebeck Alvin R.
Published: November 2005

We develop from first principles an exact model of the behavior of loop nests executing in a memory hicrarchy, by using a nontraditional classification of misses that has the key property of composability. We use Presburger formulas to express various kinds of misses as well as the state of the cache at the end of the loop nest. We use existing tools to simplify these formulas and to count cache misses. The model is powerful enough to handle imperfect loop nests and various flavors of non-linear array layouts based on bit interleaving of array indices. We also indicate how to handle modest levels of associativity, and how to perform limited symbolic analysis of cache behavior. The complexity of the formulas relates to the static structure of the loop nest rather than to its dynamic trip count, allowing our model to gain efficiency in counting cache misses by exploiting repetitive patterns of cache behavior. Validation against cache simulation confirms the exactness of our formulation. Our method can serve as the basis for a static performance predictor to guide program and data transformations to improve performance.
SPL
Authors: Xiong Jianxin , Johnson Jeremy , Johnson Robert , Padua David
Published: November 2005

We discuss the design and implementation of a compiler that translates formulas representing signal processing transforms into efficient C or Fortran programs. The formulas are represented in a language that we call SPL, an acronym from Signal Processing Language. The compiler is a component of the SPIRAL system which makes use of formula transformations and intelligent search strategies to automatically generate optimized digital signal processing (DSP) libraries. After a discussion of the translation and optimization techniques implemented in the compiler, we use SPL formulations of the fast Fourier transform (FFT) to evaluate the compiler. Our results show that SPIRAL, which can be used to implement many classes of algorithms, produces programs that perform as well as “hard-wired” systems like FFTW.
Using regional conferences to mentor student development
Authors: Hind Michael , Pfeiffer Phil
Published: November 2005

The reasons for introducing students in computer science programs to the practice of research should be apparent to readers of
SIGPLAN Notices
. Any graduate program that teaches the mastery of new ideas should obviously feature research work in its curriculum. The reasons for exposing undergraduates to research, although less obvious, are equally compelling. These reasons include helping undergraduates to make informed choices about graduate school, and helping students to appreciate how research influences the practice of computer science.
Teaching object-oriented design with heuristics
Authors: Gibbon C. , Higgins C.
Published: November 2005

The transition from "programmer" to "class designer" is difficult. Pedagogic challenges involve imparting an indepth knowledge of the object-oriented (OO) paradigm; gaining a firm understanding of the software engineering principles at play and knowing when and where to apply them effectively.
Articulation reflections
Authors: Austing Richard H.
Published: November 2005

Articulation is a topic of interest to most two-year colleges. Although it is essentially a local issue between a two-year college and one or more area colleges offering four-year degree programs, there are many aspects of articulation that are common to all two-year colleges. A forum on the issues of articulation is appropriate so that problems and solutions can be shared.
Improved teaching of multi-cultural groups
Authors: Isely Douglas C.
Published: November 2005

While teaching a multi-cultural class with a combination of Navajo, Hispanic, and Anglo students in a community college, I had the opportunity to discover some of the intercultural aspects of the students. What follows is the classroom setting and the findings.
The payoff on the information technology investment
Authors: Jonas Stephen
Published: November 2005

Institutions of higher learning are discovering not all investments are created equal, or can be evaluated equally well. Investments in information technology have their own distinctive set of characteristics that set them apart from other investments made by colleges. Compounding this scenario are increasing pressures to maximize returns on investment and to place a lid on costs, as well as the puzzle of evaluating when to jump into various pools of rapidly evolving computer technologies.
An OOPs teaching tool
Authors: Badman Scott
Published: November 2005

For a programmer, Object-Oriented Programming (OOP) can be pure joy. Code is so easy to create. If a piece of code already exists, you just use it. If it is not exactly what you want, you inherit and modify it. Your new code links and runs effortlessly with your previous code. The more complex your project becomes, the more you appreciate object-oriented code.
Adding breadth and interaction to computing classes
Authors: Janik Carol
Published: November 2005

I teach an elective course in
C++ and Object-Oriented Programming
offered in the evenings at Tompkins Cortland Community College. Last semester I had a full class of adults, many with four-year degrees, who worked in the community in computer-related jobs. I wanted to include some material about how object-oriented systems were being used in the real world and what the current trends were. To that end, I tried, without success, to line up some outside speakers. I also wanted to have the students share some of their experiences and expertise with the class. I realized that many had not used the CD-Rom databases in our library, so I decided to combine a library update for the students with an assigned report which students had to share with the class.
Death of the mainframe
Authors: Christofferson Martin , Ross Robert
Published: November 2005

Tompkins Cortland Community College's approach to campus-wide computing has demonstrated that microcomputer networking can meet the needs of a wide variety of campus users.
Orthogonal type extensions and reductions
Authors: Paakki Jukka , Karhinen Anssi , Silander Tomi
Published: November 2005

In this paper we present a generalization of Oberon's record type extensions. Our extension mechanism is orthogonally applicable to all the conventional data types found in Pascal-like languages. In order to balance the type system, we present an inverse concept, type reductions, that also can be applied to all the programmer-defined data types. These concepts provide flexible and powerful means for expressing universal subtyping and supertyping in a statically-typed programming language, as well as many possibilities for reuse of data types via a sound mathematical characterization of assignment statements. The presented ideas are under implementation in Alberich, a programming language that can be considered as a natural descendant of Oberon.
Bagof/3 to ZF expression
Authors: Greenfield Peter
Published: November 2005

There is sometimes the requirement in logic programming applications to collect all the solutions of a non-deterministic program and associated goal. A manual technique is given for translating an example Prolog procedure, append/3, used by the predicate bagof/3, to a functionally equivalent program expressed in the functional programming language Miranda which uses a ZF (Zermelo Frankel) expression.
An elementary language construct for parallel programming
Authors: Axford Tom
Published: November 2005

Current programmig practice, whether in procedural, functional or other types of languages, is strongly orientated to producing programs which are essentially sequential in nature. Procedural programmers make frequent use of loop structures (e.g. FOR and WHILE statements), while functional programmers use raw recursion instead. Neither of these mechanisms can be easily compiled into parallel code. It is suggested that there may be considerable advantages in avoiding the use of loop structures in procedural languages and raw recursion in any type of language. Instead, programs could be written using a general divide-and-conquer construct which is typically just as easy to use, but allows easy parallel implementation. A number of simple examples are given to show how this could be done and to provide evidence that the idea is not quite as outrageous as it may seem at first sight.
High level input/output in Modula-2
Authors: Crawford Albert L.
Published: November 2005

In this article, a high level I/O system for Modula-2 is presented. This system is designed to be in addition to the current Modula I/O, rather than to replace existing I/O. Its main purpose would be to have an I/O system that would be simple to use in educational settings and in general purpose programming.
Implementing generic types in Modula-2
Authors: Czyzowicz Jurek , Iglewski Michal
Published: November 2005

In SIGPLAN Notices, vol. 20, #6., June 1985 R. S. Wiener and R. F. Sincovec presented "Two Approaches to Implementing Generic Data Structures in Modula-2". Our paper presents a third solution which attempts to avoid or at least diminish the effects of some shortcomings existing in Wiener and Sincovec's approaches.
A new solution to the N <= 8 queens problem
Authors: Clay C.
Published: November 2005

This paper proposes a new solution to the problem of how many queens cover one chessboard. For the purposes of this paper, a Staunton style chess queen is assumed, and not the ruler of any country. This algorithm is implemented in Pidgin Algol (1), which will be demonstrated to support concurrency.
Generic packages in C
Authors: Grune Dick
Published: November 2005

The structuring achieved by generic packages in Ada can be cheaply emulated in C by judicious use of the preprocessor. Two files are required for the generic package: the specification and the body. Two more files are used in the instantiation: one holding the instantiation parameters and one with auxiliary code. Instantiation results in normal C header and object files (*.h and *.o). Dependency control can be delegated to the
make
progam.
A technique for automatically porting dialects of pascal to each other
Authors: Sorens Michael J.
Published: November 2005

In the course of programming events, there have been those who have found it necessary to write Pascal code that could be ported between dialects of Pascal which differ from machine to machine. This task cannot be accomplished just by writing "vanilla" code to a maximal degree, as there are inevitably syntactical and semantic differences from one dialect to another. We have developed a technique which, in conjunction with vanilla code, allows translation from one dialect to another to be performed automatically. Since it is generally the case that when a file of program text needs to be translated to a new dialect it also needs to be transmitted to a physically separate computer, our translation utility exists in two forms: a stand-alone translation utility, and a combination translation/transmission utility.
small-X — a language and interpreter for building expert systems
Authors: Kaplan Randy M.
Published: November 2005

This paper describes a programming language and its interpreter that have been developed for the construction of expert systems on microcomputers. The language has been developed with attention to simplicity and functionality. Its interpreter, now running on MS-DOS machines executes expert system programs written in small-X and provides a simple environment for expert system development.
Predicting potential COBOL performance on low level machine architectures
Authors: Otto Jerome A.
Published: November 2005

As a COBOL host, a computer architecture should efficiently execute those language constructs that are most frequently used in actual programs. However, when the language's control and data structures are at a far higher level than the control and data structures of the underlying machine, the compiler designer is faced with a large number of potential choices for mapping these high level structures to the low level architecture. This is the case for implementing COBOL on a typical mini-computer architecture. Restricting the choices to an implementable set meeting a given performance criteria and predicting the resulting performance level requires a complex analysis. This paper gives an example of the methodology used in one such analysis -- the performance of COBOL on low level architectures. This area was chosen because of the difficulty of the problem caused by the lack of support for COBOL constructs and data types on low level architectures used in most mini-and micro-computers. The Motorola MC68000 and a RISC-type architecture were selected as representative architectures.
Designing and Optimizing a Scalable CORBA Notification Service
Authors: Gore Pradeep , Cytron Ron , Schmidt Douglas , O'Ryan Carlos
Published: November 2005

Many distributed applications require a scalable event-driven communication model that decouples suppliers from consumers and simultaneously supports advanced quality of service (QoS) properties and event filtering mechanisms. The CORBA Notification Service provides a publish/subscribe mechanism that is designed to support scalable event-driven communication by routing events efficiently between many suppliers and consumers, enforcing various QoS properties (such as reliability, priority, ordering, and timeliness), and filtering events at multiple points in a distributed system.This paper provides several contributions to research on scalable notification services. First, we present the CORBA Notification Service architecture and illustrate how it addresses limitations with the earlier CORBA Event Service. Second, we explain how we addressed key design challenges faced when implementing the Notification Service in TAO, which is our high-performance, real-time ORB. We discuss the optimizations used to improve the scalability of TAO's Notification Service. Finally, we present empirical results of the performance of our implementation.
Integration of QoS-Enabled Distributed Object Computing Middleware for Developing Next-Generation Distributed Application
Authors: Krishnamurthy Yamuna , Kachroo Vishal , Karr David A. , Rodrigues Craig , Schmidt Douglas C.
Published: November 2005

This paper describes the integration of QoS-enabled distributed object computing (DOC) middleware for developing next-generation distributed applications. QoS-enabled DOC middleware facilitates ease of development and deployment of applications that can leverage the underlying networking technology or end-system QoS architecture. This paper also describes the development of a demonstration application utilizing QoS-enabled middleware to control the dissemination of Unmanned Air Vehicle (UAV) data throughout a ship.
Language and Compiler Support for Adaptive Distributed Applications
Authors: Adve Vikram , Lam Vinh Vi , Ensink Brian
Published: November 2005

Many distributed applications have to meet their performance or quality-of-service goals in environments where available resources change contantly. Important classes of distributed applications (including distributed multimedia codes, applications for mobile devices, and computational grid codes) use
runtime adaptation
in order to achieve their goals. The adaptation behavior in these applications is usually programmed in
ad hoc
code that is directly incorporated into the base application, resulting in systems that are complex to develop, maintain, modify, and debug. Furthermore, it is virtually impossible to extract high-level information about adaptive behaviour using program analysis, even if there were compiler and runtime sytems that could exploit such information. The goal of our research is to develop compiler and programming language support to simplify the development and improve the performance of adaptive distribtued applications. We describe a simple set of language extensions for adaptive distributed applications, and discuss potential compiler techniqes to support such appliations. We also propose a task-graph-based framework that can be used to formalize the description of a wide range of adaptation operations.
Use of object-oriented programming in a time series analysis system
Authors: Kerr R. K. , Percival D. B.
Published: November 2005

We describe the use of object-oriented programming (OOP) in the design and implementation of TSA, a system for interactive time series and spectral analysis. We show how such features of OOP as inheritance, generic messages, and decomposition of the programming problem in terms of objects have contributed to our goal of providing an extensible data analysis system. We discuss the strengths and limitations of both OOP and the particular implementation we used (Flavors on a Symbolics Lisp Machine) for our particular problem
.
Delegation is inheritance
Authors: Stein Lynn Andrea
Published: November 2005

Inheritance and delegation are alternate methods for incremental definition and sharing. It has commonly been believed that delegation provides a more powerful model. This paper demonstrates that there is a “natural” model of inheritance which captures all of the properties of delegation. Independently, certain constraints on the ability of delegation to capture inheritance are demonstrated. Finally, a new framework which fully captures both delegation and inheritance is outlined, and some of the ramifications of this hybrid model are explored.
Metaclasses are first class: The ObjVlisp Model
Authors: Cointe Pierre
Published: November 2005

This paper shows how an attempt at a uniform and reflective definition resulted in an open-ended system supporting ObjVlisp, which we use to simulate object-oriented language extensions.

We propose to unify Smalltalk classes and their terminal instances. This unification allows us to treat a class as a “first class citizen”, to give a circular definition of the first metaclass, to access to the metaclass level and finally to control the instantiation link. Because each object is an instance of another one and because a metaclass is a real class inheriting from another one, the metaclass links can be created indefinitely.

This uniformity allows us to define the class variables at the metalevel thus suppressing the Smalltalk-80 ambiguity between class variables and instance variables: in our model the instance variables of a class are the class variables of its instances.
Object-oriented programming in Smalltalk and ADA
Authors: Seidewitz Ed
Published: November 2005

Though Ada and Modula-2 are not object-oriented languages, an object-oriented viewpoint is crucial for effective use of their module facilities. It is therefore instructive to compare the capabilities of a modular language such as Ada with an archetypal object-oriented language such as Smalltalk. The comparison in this paper is in terms of the basic properties of encapsulation, inheritance and binding, with examples given in both languages. This comparison highlights the strengths and weaknesses of both types of languages from an object-oriented perspective. It also provides a basis for the application of experience from Smalltalk and other object-oriented languages to increasingly widely used modular languages such as Ada and Modula-2.
Logical composition of object-oriented interfaces
Authors: Grossman Mark , Ege Raimund K.
Published: November 2005

This paper describes an approach to object-oriented interface design that goes beyond mere object decomposition. In our user interface management system we use logic and filters to declaratively specify and control a space of ways that objects may be composed to create interfaces. A filter is a package of constraints and associated typed objects that express the relationship of data and representation objects.

Conceptually our system is completely based on constraints. Filters provide the high bandwidth constraints to maintain the components of the direct-manipulation interface while the logic forms the low bandwidth constraints to combine and provide communication between these components. The use of Horn-clause logic to compose separate interface objects facilitates both the distribution of computation onto multiple processors and the generation of multiple views of data. Intelligent backtracking implemented in the logic allows for user- and system-initiated
undo
operations to correct errors and/or try alternative approaches to a problem. We illustrate the power and flexibility of this approach by describing a floor layout and design system.
Retrofitting objects
Authors: Filman Robert E.
Published: November 2005

I present the results of an experiment in retrofitting objects into an existing system. I describe a technology, based on automatic redefinition of existing functions, that allowed alternative implementations of the fundamental data types of the KEE™ knowledge-based system building tool. This technology is applicable in environments where the system's procedures can be subject to programmatic manipulation. It allows the retrofitting of objects into the implementations of other existing systems. The experience of retrofitting objects into KEE provides insight into the issues of the interaction of semantic classes and data representation and granularity in object-based systems.
1
Relations as semantic constructs in an object-oriented language
Authors: Rumbaugh James
Published: November 2005

The relation as a semantic construct in an object-oriented language clearly expresses associations and constraints among objects which would otherwise be buried in implementation code. The externalization of references between objects permits a symmetric, non-redundant conceptual model which merits its own special notation and predefined operations. The object-relation model, which combines the object-oriented model with the entity-relationship model from data base theory, is particularly useful for designing and partitioning systems of interrelated objects. Relations can be implemented efficiently using hash tables. The model proposed here has been fully implemented in an object-oriented language written by the author which has been used to implement several production applications.
ISDE
Authors: Chesi M. , Dameri E. , Franceschi M. P. , Gatti M. G. , Simonelli C.
Published: November 2005

In this paper we present ISDE, an experimental Interactive Software Development Environment. Briefly described is the design methodology for the derivation of an interactive software development environment from a set of general meta-tools and (syntactic and semantic) language definition. The internal program representation common to every environment tool is presented, along with the main features of each implemented or under development tool, emphasizing tools integration and composition capabilities.
Preliminary experience from the dice system a distributed incremantal compiling environment
Authors: Fritzson Peter
Published: November 2005

Abstracts The DICE system Is a highly Integrated programming environment which provides programmer support in the case where the programming environment resides in a host computer and the program Is running on a target computer that Is connected to the host. Such a system configuration is also suitable for remote debugging and maintenance of production versions of programs that has been installed in a user environment.

The system contains tools such as an screen-oriented structure editor, a statement-level incremental compiler, a screen-oriented debugger and a program database. The debugger uses the same facility for pointing and display as does the editor, and it uses the incremental compiler for insertion of breakpoints and statement evaluation. Most of these tools are automatically generated from compact descriptions.

This paper describes some aspects of a prototype version of the system and gives some preliminary data on the performance. Also, strategies for implementing portable programming environments are discussed and are exemplified by the DiCE system.
Implementing relational views of programs
Authors: Linton Mark A.
Published: November 2005

Configurations, versions, call graphs, and slices are all examples of
views
, or cross-sections, of programs. To provide a powerful mechanism for defining, retrieving, and updating these views, the OMEGA programming system uses a relational database system to manage all program information.

We have built a prototype implementation of the OMEGA-database system interface. This implementation includes the design of a relational schema for a Pascal-like language, a program for taking software stored as text and translating it into the database representation, and a simple, pointing-oriented user interface. Initial performance measurements indicate that response is too slow in our current environment, but that advances in database software technology and hardware should make response fast enough in the near future.
Generation Scavenging
Authors: Ungar David
Published: November 2005

Many interactive computing environments provide automatic storage reclamation and virtual memory to ease the burden of managing storage. Unfortunately, many storage reclamation algorithms impede interaction with distracting pauses.
Generation Scavenging
is a reclamation algorithm that has no noticeable pauses, eliminates page faults for transient objects, compacts objects without resorting to indirection, and reclaims circular structures, in one third the time of traditional approaches.

We have incorporated
Generation Scavenging
in Berkeley Smalltalk(BS), our Smalltalk-80 implementation, and instrumented it to obtain performance data. We are also designing a microprocessor with hardware support for
Generation Scavenging
.
Worlds: an organizing structure for object-bases
Authors: Wile David S , Allard Dennis G
Published: November 2005

Object-bases are certain to supplant today's file systems in future program development environments. Unfortunately, file systems implicitly provide several important environmental features that are difficult or impossible to obtain using existing object-bases, such as focus of attention, garbage detection and collection, and data sharing. These deficiencies arise from the absence of mechanisms for naming and maintaining aggregations of information in structures larger than single relations or single object classes. This paper proposes a model for information in programming environments, called worlds, which naturally describes clusters of information forming conceptual units in an object-base. Because the model arose from the need to represent well-formed grammatical structures, the concept unifies syntax-directed manipulation with object-base facilities. In addition, this clustering capability provides a foundation in object-bases for the features lost from file systems. We illustrate worlds through their use to maintain persistence in the object-base of our programming environment, the Common Lisp Framework.
A graphical, extensible integrated environment for software development
Authors: Wasserman Anthony I , Pircher Peter A
Published: November 2005

Analysis and design are the essential first phases in most software development projects, yet most automated support environments are aimed at the programming phase. This paper describes a workstation-based environment that provides an integrated ensemble of graphical tools for analysis and design coupled to a project database, along with mechanisms for producing declarations, code skeletons, and executable programs. The environment is built on an “open architecture,” in which interfaces to the tools and their associated files are visible and accessible. The open architecture supports customization and extensibility of the tool environment, so that it can be effectively linked with traditional programming tools.
An incremental algorithm for software analysis
Authors: Carroll Martin , Ryder Barbara G
Published: November 2005

In programming environments aimed at “industrial strength” software development, there is a need for software tools which facilitate both design and maintenance. These tools should encourage experimentation with different system configurations which enable designers toa prioriestimate the associated system complexity and judge the ease of accommodating enhancements. Maintainers should be able to check straightforwardly the ramifications of system changes due to enhancements or “bug fixes”. With interprocedural data flow information about the definition and use of global variables and parameters in a software system, tools can be built to perform these tasks.

For large, complex systems, efficient methods for interprocedural analysis are necessarily incremental, as a software system is a dynamically evolving entity.Incremental algorithmsupdate current information about a system in response to a change rather than re-calculating the information by re-analyzing the entire system. This paper reports our development of a general purpose incremental data flow analysis algorithm, which is applicable to both intraprocedural and interprocedural domains. It is based on interval analysis, a technique whose observed performance is linear for most programs; under reasonable assumptions about program flow graphs this linearity can be verified [20].
Design characteristics of the WATFOR compiler
Authors: Cowan D. D. , Graham J. W.
Published: November 2005

About 1960, it became fashionable to introduce computer techniques into many of the courses being taught at the university level. These courses tended to be technically oriented (Engineering, Science, Mathematics), and the language most often used was one of the versions of FORTRAN. Students were introduced to computing by a brief course in FORTRAN, and then were expected to apply their newly-discovered knowledge to the solution of numerous problems related to some discipline. Introducing large numbers of students to computing in this manner created an entirely new type of demand for computer services. These new demands for computer services had to satisfy the following needs.

(i) The programmers were not professionals; thus, the proportion of errors in a given number of written statements was higher than usual.

(ii) The programs themselves were often quite short, usually 30 to 50 statements in length.

(iii) The volume of submitted programs was very high, in the order of hundreds of thousands per day.

(iv) The debugged program tended to be run in production only once, and was set aside as a completed assignment.
Effectiveness of an optimizing compiler for arithmetic expressions
Authors: Painter James A.
Published: November 2005

This paper defines the notion of effectiveness of an optimizing compiler and presents a proof that a simple optimizing compiler is effective. An optimizing compiler typically consists of a basic compiler and a set of optimizations for special cases. The fundamental notion of effectiveness is that the basic compiler is correct, all of the optimization transformations preserve correctness, and produce essentially equivalent programs which have a smaller value relative to a specified weighting function.