bluuebunny/crossref_metadata_2025 huggingface dataset:
A distributed garbage collector for active objects
Authors: Puaut Isabelle
Published: November 2005

This paper presents an algorithm that performs garbage collection in distributed systems of active objects (i.e., objects having their own threads of control). Our proposition extends the basic marking algorithm proposed by Kafura in [1] to a distributed environment. The proposed garbage collector is made up of a set of local garbage collectors, one per site, loosely coupled to a (logically centralized) global garbage collector that maintains a global snapshot of the system state relevant to garbage collection. The specific features of the proposed garbage collector are that local garbage collectors need not be synchronized with each other for detecting garbage objects, and that faulty sites and communication channels are tolerated. The paper describes the proposed garbage collector, together with its implementation and performance for a concurrent object-oriented language running on a local area network of workstations.
Interfaces, protocols, and the semi-automatic construction of software adaptors
Authors: Yellin Daniel M. , Strom Robert E.
Published: November 2005

In this paper we show how to augment object-oriented application interfaces with enhanced specifications that include sequencing constraints called
protocols
. Protocols make explicit the relationship between messages (methods) supported by the application. These relationships are usually only given implicitly, either in the code or in textual comments. We define notions of interface compatibility based upon protocols and show how compatibility can be checked, discovering a class of errors that cannot be discovered via the type system alone. We then define
software adaptors
that can be used to bridge the difference between object-oriented applications that have functionally compatible but type incompatible interfaces. We discuss what it means for an adaptor to be
well-formed
. Leveraging the information provided by protocols, we show how adaptors can be automatically generated from a high-level description, called an
interface mapping
.
Fusing loops with backward inter loop data dependence
Authors: Ganesh Amit
Published: November 2005

Loop fusion has been a traditional transformation in optimizing and parallelizing compilers. There are various benefits in performing loop fusion. Most trivially, loop fusion reduces the overheads associated in implementing loops in computer hardware by a factor of 2. But, in addition, loop fusion also holds promise in reducing the paging traffic in the memory hierarchy [Kuck 84]. Moreover, loop fusion may also reduce register loads/stores and the overall memory requirements in certain cases [Wolfe 89].
SUIF
Authors: Wilson Robert P. , French Robert S. , Wilson Christopher S. , Amarasinghe Saman P. , Anderson Jennifer M. , Tjiang Steve W. K. , Liao Shih-Wei , Tseng Chau-Wen , Hall Mary W. , Lam Monica S. , Hennessy John L.
Published: November 2005

Compiler infrastructures that support experimental research are crucial to the advancement of high-performance computing. New compiler technology must be implemented and evaluated in the context of a complete compiler, but developing such an infrastructure requires a huge investment in time and resources. We have spent a number of years building the SUIF compiler into a powerful, flexible system, and we would now like to share the results of our efforts.SUIF consists of a small, clearly documented
kernel
and a
toolkit
of compiler passes built on top of the kernel. The kernel defines the intermediate representation, provides functions to access and manipulate the intermediate representation, and structures the interface between compiler passes. The toolkit currently includes C and Fortran front ends, a loop-level parallelism and locality optimizer, an optimizing MIPS back end, a set of compiler development tools, and support for instructional use.Although we do not expect SUIF to be suitable for everyone, we think it may be useful for many other researchers. We thus invite you to use SUIF and welcome your contributions to this infrastructure. Directions for obtaining the SUIF software are included at the end of this paper.
Covariant specification
Authors: Shang David L.
Published: November 2005

Covariant specification is the process in a subclass to narrow the varying scope of an instance variable, or the varying scope of the input or output interface of an operation which has already been specified in the superclass. Covariant specification has been considered problematic and many object-oriented languages have restrictions on it. Several proposals have been put forth in order to achieve a type safe convariant specification, but none can be said a complete solution. Problems arise from type intra-dependency: the component type depends on its enclosing type, which has not been fully recognized so far.The type system described in this paper can well reflect the type intra-dependency, and hence gain a type-safe convariant specification. The keynote of our approach is to generalize the concept of constrained parameterized class, which encapsulates detailed information that can give a natural description of type intra-dependency, and makes it possible to incorporate a static type check of the dependency into a compiler.
Considerations in choosing a concurrent/distributed object-oriented programming language
Authors: Nelson Michael L.
Published: November 2005

Object-oriented programming (OOP) shows great potential for use in concurrent and distributed systems. However, several issues must be considered before moving into the concurrent/distributed arena. This paper considers the following issues: sharing of variables; various communication models; communication costs; and distributed object management.
Using yacc and lex with C++
Authors: Hahne Bruce , Satō Hiroyuki
Published: November 2005

We consider one approach to using C++ to write a compiler in combination with the lexical analysis tool Lex and the parser generator tool YACC. This approach uses C++ classes and constructors to build a syntax tree during the parse. Synthesized and inherited attributes are easy to declare for individual terminals and nonterminals, and synthesized attributes can be computed during the parse as long as no inherited attributes are involved in the computation. We also consider the use of virtual functions for tree traversal. A complete example YACC specification is included which demonstrates these techniques. Results show that C++ offers several advantages over C for compiler design with YACC and Lex.
A technique for monitoring run-time dynamics of an operating system and a microprocessor executing user applications
Authors: Argade Pramod V. , Charles David K. , Taylor Craig
Published: November 2005

In this paper, we present a non-invasive and efficient technique for simulating applications complete with their operating system interaction. The technique involves booting and initiating an application on a hardware development system, capturing the entire state of the application and the microprocessor at a well defined point in execution and then simulating the application on microprocessor simulators. Extensive statistics generated from the simulators on run-time dynamics of the application, the operating system as well as the microprocessor enabled us to tune the operating system and the microprocessor architecture and implementation. The results also enabled us to optimize system level design choices by anticipating/predicting the performance of the target system. Lastly, the results were used to adjust and refocus the evolution of the architecture of both the operating system and the microprocessor.
AP1000+
Authors: Hayashi Kenichi , Doi Tsunehisa , Horie Takeshi , Koyanagi Yoichi , Shiraki Osamu , Imamura Nobutaka , Shimizu Toshiyuki , Ishihata Hiroaki , Shindo Tatsuya
Published: November 2005

The scalability of distributed-memory parallel computers makes them attractive candidates for solving large-scale problems. New languages, such as HPF, FortranD, and VPP Fortran, have been developed to enable existing software to be easily ported to such machines. Many distributed-memory parallel computers have been built, but none of them support the mechanisms required by such languages. We studied the mechanisms required by parallelizing compilers and proposed a new architecture to support them. Based on this proposed architecture, we developed a new distributed-memory parallel computer, the AP1000+, which is an enhanced version of the AP1000. Using scientific applications in VPP Fortran and C, such as NAS parallel benchmarks, we simulated the performance of the AP1000+.
Hardware support for fast capability-based addressing
Authors: Carter Nicholas P. , Keckler Stephen W. , Dally William J.
Published: November 2005

Traditional methods of providing protection in memory systems do so at the cost of increased context switch time and/or increased storage to record access permissions for processes. With the advent of computers that supported cycle-by-cycle multithreading, protection schemes that increase the time to perform a context switch are unacceptable, but protecting unrelated processes from each other is still necessary if such machines are to be used in non-trusting environments.

This paper examines
guarded pointers
, a hardware technique which uses tagged 64-bit pointer objects to implement capability-based addressing. Guarded pointers encode a segment descriptor into the upper bits of every pointer, eliminating the indirection and related performance penalties associated with traditional implementations of capabilities. All processes share a single 54-bit virtual address space, and access is limited to the data that can be referenced through the pointers that a process has been issued. Only one level of address translation is required to perform a memory reference. Sharing data between processes is efficient, and protection states are defined to allow fast protected subsystem calls and create unforgeable data keys.
Program transformation in constructive type theory
Authors: Zhu Ming-Yuan
Published: November 2005

Transformational programming is a method for program development. To formalize the transformational programming techniques, the key point is to formally represent transformation rules and to prove the correctness of these rules. In this paper, we describe a constructive type-theoretical approach for formalizing the concepts of program schema, transformation rules and strategies, and software development processes. Some examples for verification and derivation of semantically correct program transformation rules are presented.
Object oriented method for Axiom
Authors: Boulanger Jean-Louis
Published: November 2005

Axiom
1
is a very powerful computer algebra system which combines two languages paradigms (functional and OOP). Mathematical world is complex and mathematicien use abstraction to design it. This paper presents some aspects of the object oriented development in Axiom. The axiom programming is based on several new tools for object oriented development, it uses two levels of class and some operations such that
coerce, retract
or
convert
which permit the type evolution. These notions introduce the concept of inulti-view.
Strength reduction of multiplications by integer constants
Authors: Wu Youfeng
Published: November 2005

Replacing a multiplication of an integer constant by a sequence of simple instructions can be beneficial because it reduces the total number of cycles and also provides more opportunity for instruction level parallelism. In this paper we developed an algorithm that selectively replaces multiplications of integer constants with sequences of SUB, ADD, SHIFT, and LEA instructions. The algorithm runs fast and the generated instruction sequences are of high quality. The number of simple instructions generated for a multiplication of an integer constant is about 84.5% of the number of 1-bits in the binary representation of the constant. Also, for several popular processors, the simple instruction sequences significantly reduces the execution time to perform the multiplications.
Guarded methods vs. inheritance anomaly
Authors: Ferenczi Szabolcs
Published: November 2005

The term Inheritance Anomaly has been introduced into Object-Oriented Concurrent Programming (OOCP). It has also been shown how different kinds of synchronization mechanisms fall into one of the three anomalies. Guarded Methods are shown to be an inadequate tool to solve either History-only Sensitive Anomaly or Modification of Acceptable States. This paper argues that any of the anomalies can be solved by Guarded Methods when a suitable semantics is found for it. The main contribution of the paper is the exposition that the concept of Guarded Methods, provided Guarded Methods are interpreted as Conditional Critical Regions, is an adequate language tool for expressing synchronization constraints in OOCP. Guarded Method based solutions are given for the above mentioned two cases of anomalies.
Intelligent and multi agent object level computing
Authors: Nourani Cyrus F.
Published: November 2005

We present new OOP techniques called Multi Agent Object Level Programming, and new paradigms for OOP defining intelligent objects. New linguistics constructs are defined for object level programming with String and Splurge functions treating object visibility and messages. Treating objects as abstract data types and a two level programming approach to OOP allows us to define Pullup abstractions to treat incompatible objects. The techniques open new areas of research on object level programming to pursue, and put us at MJOOP, the Multiagent Junction For OOP.
Foundations of Object-Oriented Languages
Authors: Castagna Giuseppe , Leavens Gary T.
Published: November 2005

A report on the workshop
Foundations of Object-Oriented Languages
, Paris, July 1994.
How to evaluate object-oriented software development?
Authors: Stiglic Bruno , Heričko Marjan , Rozman Ivan
Published: November 2005

Adoption of object-oriented technology by the software industry is to a large extent interfered with a lack of appropriate evaluation criteria. Measures of object-oriented systems are necessary in order to realize and achieve expected benefits and advantages of object technology. This paper presents some evaluation criteria, measures and metrics, suitable for object-oriented software development. The implemented prototype of OOMetTool that provides an automatic support for metric data gathering is described and some initial findings are presented.
Implementing FORTRAN77 support in the GNU
gdb
debugger
Authors: Butt Farooq
Published: November 2005

Commercially available source-level debuggers in the Unix world often shortchange FORTRAN77 users. While C and C++ are usually well-supported languages, FORTRAN77 has not been given the attention it deserves. Given the current interest in performance-measurement via the popular SPEC benchmarks (many of which are coded in FORTRAN77) as well as the large installed-base of mathematical/scientific FORTRAN77 software, it is imperative for system software vendors to provide FORTRAN77 users with the same sort of fast, effective and powerful source-level debugging environment that C and C++ users enjoy. This paper details the addition of FORTRAN77 features to the GNU gdb[2] debugger in order to better support users of the highly-optimizing Motorola PowerPC
1
mf77 compiler. These FORTRAN77 features currently (as of version 4.10) only target the native PowerPC mf77 compiler distributed by Motorola.
User interface metrics
Authors: Kokol Peter , Rozman Ivan , Venuti Vlado
Published: November 2005

The most important part of the majority of recent computer software systems, according to the users view, is the user interface. In this paper authors present some new metrics devoted to the assessment of some user interface characteristics.
Polymorphic queries across sets, bags, and lists
Authors: Wong Limsoon
Published: November 2005

Bulk data types such as sets, bags, and lists are an important component of a modern query language. It is desirable that operations on one bulk data type (such as sets) that have analogous counterparts in other bulk data types (such as bags and list) be expressed using the
same
expression. This kind of uniformity is achieved only to a limited degree in object-oriented languages, as these languages have the type information loss problem. Languages based on parametric polymorphism achieve this uniformity in a much better way, but only upto "bracket-switching." That is, in these languages, a query over bags that is analogous to a query over sets, are identical upto interchanging the set and bag brackets. This paper presents a simple extension to a popular parametric polymorphic type system. We show that it is possible to construct a query language around this type system so that the
same
expression can be used to implement analogous queries across sets, bags, and lists. Furthermore, this uniformity is achieved without any loss in type information.
Fortran program specialization
Authors: Kleinrubatscher Paul , Kriegshaber Albert , Zöchling Robert , Glück Robert
Published: November 2005

We have developed and implemented a partial evaluator for a subset of Fortran 77. A partial evaluator is a tool for program transformation which takes as input a general program and a part of its input, and produces as output a specialized program. The goal is efficiency: a specialized program often runs an order of magnitude faster than the general program. The partial evaluator is based on the off-line approach and uses a binding-time analysis prior to the specialization phase. The source language includes multi-dimensional arrays, procedures and functions, as well as global storage. The system is presented and experimental results are given.
Proper packaging promotes parameter passing proficiency
Authors: Čigas John F.
Published: November 2005

There are three major areas of confusion when learning about parameter passing in procedural programming language: formal vs. actual parameters; scope rules, including global variables; and value vs. reference parameters. This paper discusses one simple method, the use of separate modules/packages, to ameliorate the first two of these problems.
GURRR
Authors: Berson David A. , Gupta Rajiv , Soffa Mary Lou
Published: November 2005

When compiling for instruction level parallelism (ILP), the integration of the optimization phases can lead to an improvement in the quality of code generated. However, since several different representations of a program are used in the various phases, only a partial integration has been achieved to date. We present a program representation that combines resource requirements and availability information with control and data dependence information. The representation enables the integration of several optimizing phases, including transformations, register allocation, and instruction scheduling. The basis of this integration is the simultaneous allocation of different types of resources. We define the representation and show how it is constructed. We then formulate several optimization phases to use the representation to achieve better integration.
A linear-time algorithm for computing the memory access sequence in data-parallel programs
Authors: Kennedy Ken , Nedeljkovic Nenad , Sethi Ajay
Published: November 2005

Data-parallel languages, such as High Performance Fortran, are widely regarded as a promising means for writing portable programs for distributed-memory machines. Novel features of these languages call for the development of new techniques in both compilers and run-time systems. In this paper, we present an improved algorithm for finding the local memory access sequence in computations involving regular sections of arrays with
cyclic(k)
distributions. After establishing the fact that regular section indices correspond to elements of an integer lattice, we show how to find a lattice basis that allows for simple and fast enumeration of memory accesses. The complexity of our algorithm is shown to be lower than that of the previous solution for the same problem. In addition, the experimental results demonstrate the efficiency of our method in practice.
An array operation synthesis scheme to optimize Fortran 90 programs
Authors: Hwang Gwan-Hwan , Lee Jenq Kuen , Ju Dz-Ching
Published: November 2005

An increasing number of programming languages, such as Fortran 90 and APL, are providing a rich set of intrinsic array functions and array expressions. These constructs which constitute an important part of data parallel languages provide excellent opportunities for compiler optimizations. In this paper, we present a new approach to combine consecutive data access patterns of array constructs into a composite access function to the source arrays. Our scheme is based on the composition of access functions, which is similar to a composition of mathematic functions. Our new scheme can handle not only data movements of arrays of different numbers of dimensions and segmented array operations but also masked array expressions and multiple sources array operations. As a result, our proposed scheme is the first synthesis scheme which can synthesize Fortran 90 RESHAPE, EOSHIFT, MERGE, and WHERE constructs together. Experimental results show speedups from 1.21 to 2.95 for code fragments from real applications on a Sequent multiprocessor machine by incorporating the proposed optimizations.
Parallel algorithms for image histogramming and connected components with an experimental study (extended abstract)
Authors: Bader David A. , JáJá Joseph
Published: November 2005

This paper presents efficient and portable implementations of two useful primitives in image processing algorithms, histogramming and connected components. Our general framework is a single-address space, distributed memory programming model. We use efficient techniques for distributing and coalescing data as well as efficient combinations of task and data parallelism. Our connected components algorithm uses a novel approach for parallel merging which performs drastically limited updating during iterative steps, and concludes with a total consistency update at the final step. The algorithms have been coded in
Split-C
and run on a variety of platforms. Our experimental results are consistent with the theoretical analysis and provide the best known execution times for these two primitives, even when compared with machine-specific implementations. More efficient implementations of
Split-C
will likely result in even faster execution times.
Cilk
Authors: Blumofe Robert D. , Joerg Christopher F. , Kuszmaul Bradley C. , Leiserson Charles E. , Randall Keith H. , Zhou Yuli
Published: November 2005

Cilk (pronounced “silk”) is a C-based runtime system for multi-threaded parallel programming. In this paper, we document the efficiency of the Cilk work-stealing scheduler, both empirically and analytically. We show that on real and synthetic applications, the “work” and “critical path” of a Cilk computation can be used to accurately model performance. Consequently, a Cilk programmer can focus on reducing the work and critical path of his computation, insulated from load balancing and other runtime scheduling issues. We also prove that for the class of “fully strict” (well-structured) programs, the Cilk scheduler achieves space, time and communication bounds all within a constant factor of optimal.

The Cilk runtime system currently runs on the Connection Machine CM5 MPP, the Intel Paragon MPP, the Silicon Graphics Power Challenge SMP, and the MIT Phish network of workstations. Applications written in Cilk include protein folding, graphic rendering, backtrack search, and the *Socrates chess program, which won third prize in the 1994 ACM International Computer Chess Championship.
Joint integration of the object-oriented paradigm at Amarillo College and Texas Tech University
Authors: Bagert Donald J. , Haiduk H. Paul
Published: November 2005

The current debate over whether and where to include the object-oriented paradigm in undergraduate computing science curricula is strikingly similar to another debate not yet finished. Anyone who has been involved in CS curricula for over ten years will recall that we are still sometimes debating where to first present concepts of procedural and functional abstraction, although hardly anyone debates that we should not do so at all. Thus, there is a real sense of deja vu with respect to the current debate over the Object-Oriented Paradigm (OOP). That is, virtually everyone feels that it should be included, but there is still a wide variety of opinions as to where and how it should be done. This paper discusses how the teaching of the object-oriented paradigm has evolved over the last several years in the two-year program at Amarillo College and at the four-year undergraduate program at Texas Tech University, which are 120 miles apart.
Computer skills in demand
Authors: Rupert Keith W.
Published: November 2005

A recently-completed class project shows that Florida employers seek employees with computer skills in software applications, WordPerfect, and Louts 1-2-3. It also shows a need for programmers in COBOL and C/C++, with a new niche for skills in Visual BASIC. Unix-based systems are shown to have a large foothold as well.
Worst-case execution time analysis on modern processors
Authors: Nilsen Kelvin D. , Rygg Bernt
Published: November 2005

Many of the trends that have dominated recent evolution and advancement within the computer architecture community have complicated the analysis of task execution times. Most of the difficulties result from two particular emphases: (1) Instruction-level parallelism, and (2) Optimization of average-case behavior rather than worst-case latencies. Both of these trends have resulted in increased nondeterminism in the time required to execute particular code sequences. And since the analysis required to determine worst-case task execution times on modern processors is so complicated, it is not practical for programmers to perform all of the necessary analyses by hand. Tools must aid them. This paper describes ongoing research on a collection of tools intended to automate the analyses that must be performed in order to build reliable real-time software for modern computing environments. Emphasis is given to the interplay between components of the development environment.
RTsynchronizer
Authors: Ren Shangping , Agha Gul A.
Published: November 2005

We argue that the specification of an object's functional behavior and the timing constraints imposed on it may be separated. Specifically, we describe RTsynchronizer, a high-level programming language construct for specifying real-time constraints between objects in a distributed concurrent system. During program execution, RTsynchronizers affect the scheduling of distributed objects to enforce real-time relations between events. Objects in our system are defined in terms of the actor model extended with timing assumptions. Separation of the functional behaviors of actors and the timing constraints on patterns of actor invocation provides at least three important advantages. First, it simplifies code development by separating design concerns. Second, multiple timing constraints can be independently specified and composed. And finally, a specification of timing constraints can be reused even if the representation of the functional behavior of actors has changed, and conversely.A number of examples are given to illustrate the use of RTsynchronizers. These examples illustrate how real-time constraints for periodic events, simultaneous events, exception handling, and producer-consumer may be specified.
Software synthesis for real-time information processing systems
Authors: Thoen Filip , Cornero Marco , Goossens Gert , De Man Hugo
Published: November 2005

Software synthesis is a new approach which focuses on the support of embedded systems without the use of operating-systems. Compared to traditional design practices, a better utilization of the available time and hardware resources can be achieved with software synthesis, because the static information provided by the system specification is fully exploited and a application specific solution is automatically generated.In this paper on-going research on a software synthesis approach for real-time information processing systems is presented which starts from a concurrent process system specification and tries to automate the mapping of this description to a single processor. An internal representation model which is well suited for the support of concurrency and liming constraints is proposed, together with flexible execution models for multi-tasking with real-time constraints. The method is illustrated on a personal terminal receiver demodulator for mobile satellite communication.
The ControlShell component-based real-time programming system, and its application to the Marsokhod Martian Rover
Authors: Schneider Stan , Chen Vincent , Steele Jay , Pardo-Castellote Gerardo
Published: November 2005

Real-time system software is notoriously hard to share and reuse. This paper walks through the methodology and application of ControlShell, a component-based programming system for real-time system software development. ControlShell combines graphical system-building tools, an execution-time configuration manager, a real-time matrix package, and an object name service into an integrated development environment. It targets complex systems that require on-line reconfiguration and strategic control.ControlShell takes advantage of functional object hierarchies to enable code sharing and reuse. It gains flexibility by supporting easy interconnectivity of these objects. It features a unique configuration control system for changing operating modes.The paper concludes by examining the application of this framework to a teleoperated rover under development as a joint effort by NASA, several Russian space research institutes, and US industry. The rover is able to function remotely under control of a virtual reality interface.
Extending the statechart formalism
Authors: Allen Arthur , de Champeaux Dennis
Published: November 2005

Statecharts are extended to deal with events when no applicable transition is available, and to resolve conflicts relative to event scheduling and response that can arise whenever multiple states can be active simultaneously. "Event closure" and event scheduling are achieved without having to clutter up a basic statechart. The extensions are effected by means of declarative event disposition rules. These rules, together with the statechart topology, determine the contents of one or more disposition matrices. These matrices are combined with the statechart state to determine the response of the event dispatcher to incoming events. The operation of the event dispatcher is also described. A detailed example illustrates these concepts, which are further characterized, for the benefit of working programmers, in the form of a behavioral design pattern. A tool called StateCraft embodies these notions.
Object-oriented state machines
Authors: Sane Aamod , Campbell Roy
Published: November 2005

Software specification and implementation techniques based on state machines simplify design, coding, and validation. However, large systems require complex state machines. Incremental construction techniques can control this complexity. In this paper, we present a construction technique that permits derivation of complex state machines from simpler state machines. The technique uses subclassing, composition, delegation, and genericity to incrementally modify and combine simpler machines.In addition, we present a novel implementation technique that uses exactly one table-lookup and one addition to dispatch events on derived state machines, no matter the depth of the derivation. As an example, we describe the derivation of a complicated distributed virtual memory scheme from a simple paging virtual memory scheme.
Annotating objects for transport to other worlds
Authors: Ungar David
Published: November 2005

In Self 4.0, people write programs by directly constructing webs of objects in a larger world of objects. But in order to save or share these programs, the objects must be moved to other worlds. However, a concrete, directly constructed program is incomplete, in particular missing five items of information: which module to use, whether to transport an actual value or a counterfactuaI initial value, whether to create a new object in the new world or to refer to an existing one, whether an object is immutable with respect to transportation, and whether an object should be created by a low-level, concrete expression or an abstract, type-specific expression. In Self 4.0, the programmer records this extra information in annotations and attributes. Any system that saves directly constructed programs will have to supply this missing information somehow.
Modular reasoning in the presence of subclassing
Authors: Stata Raymie , Guttag John V.
Published: November 2005

Considerable progress has been made in understanding how to use subtyping in a way that facilitates modular reasoning. However, using subclassing in a way that facilitates modular reasoning is not well understood. Often methods must be overriden as a group because of dependencies on instance variables, and the programmers of subclasses cannot tell which methods are grouped without looking at the code of superclasses. Also, the programmers of subclasses must look at the code of superclasses to tell what assumptions inherited methods make about the behavior of overriden methods.We present a systematic way to use subclassing that facilitates formal and informal modular reasoning. Separate specifications are given to programmers writing code that manipulates instances of a class and to programmers writing subclasses of the class. The specifications given to programmers of subclasses are divided, by
division of labor specifications
, into multiple parts. Subclasses may inherit or override entire parts, but not sub-parts. Reasoning about the implementation of each part is done independently of other parts.
SmartFiles
Authors: Haines Matthew , Mehrotra Piyush , Van Rosendale John
Published: November 2005

Data files for scientific and engineering codes typically consist of a series of raw data values whose description is buried in the programs that interact with these files. In this situation, making even minor changes in the file structure or sharing files between programs (interoperability) can only be done after careful examination of the data files and the I/O statements of the programs interacting with this file. In short, scientific data files lack self-description, and other self-describing data techniques are not always appropriate or useful for scientific data files. By applying an object-oriented methodology to data files, we can add the intelligence required to improve data interoperability and provide an elegant mechanism for supporting complex, evolving, or multidisciplinary applications, while still supporting legacy codes. As a result, scientists and engineers should be able to share datasets with far greater ease, simplifying multidisciplinary applications and greatly facilitating remote collaboration between scientists.
Extending SQL-92 for OODB access
Authors: Kiernan Jerry , Carey Michael J.
Published: November 2005

This paper describes the design and implementation of a query engine that provides extended SQL-based access to the data managed by an object-oriented database system. This query engine allows extended SQL queries to be embedded in C++ programs or issued interactively as from a command line interface. The language supported by the engine is the complete SQL-92 select statement plus object extensions for navigating along paths and embedded structures, querying nested sets, and invoking member functions. In addition, an object-oriented SQL view facility is provided. Using this view facility, one can define object-oriented views; one can also define views that flatten complex OODB schemas, allowing direct access by existing tools designed to provide remote access to relational databases. The view facility also supports the definition of views that include reference and set-valued columns based on other views, thus allowing entire "view schemas" to be created. This paper describes the SQL-92 query and view extensions and discusses a number of issues that arose on the way to the implementation that is currently running on top of the ObjectStore OODB system.
Computer language usage in CS1
Authors: Levy Suzahne Pawlan
Published: November 2005

The Reid Report[Reid 94] is a list of more than 400 schools throughout the world and the language they are using in their first computer science course (commonly referred to as ACM's CS1). It is a voluntary report updated regularly. Its list of schools is not exhaustive or complete. Based on this report, 139 colleges and universities within the United States who are not using Pascal were surveyed. The intent of the survey was threefold:• to find out why these schools are using their choice of language in CS1,• how the instructors at these schools feel about their current language as it compares to Pascal in the way it aids in the teaching of introductory programming skills, and• which language these instructors feel is the best one to use in a CS1 course.The results of this survey, conducted in February 1995, are summarized below.
Network-user policy
Authors: Krebeck Bret
Published: November 2005

As a network administrator in an educational setting, I have a host of special issues to consider! However, one issue must be addressed as soon as the first user logs on: Network resources must be used in an appropriate manner.
The reason God made Oklahoma?
Authors: Parker Anne M.
Published: November 2005

Hot. Dusty. Shimmering north Texas noontime. Waves of heat flowing over my car, now making its fourth trip from Sarasota, Florida to Edmond, Oklahoma in the baking summer sun. Trunk of the car loaded with mountains of computer equipment for the Institute. Me praying it's cool enough in there for laser printer, monitor, modem, system case and accessories to survive all the way to UCO -- the University of Central Oklahoma.
A rule-based and object-oriented AI programming language
Authors: Li Tao
Published: November 2005

This paper presents a new artificial intelligence programming language called ROOP which is machine independent and has the ability to deal with logical programming in general. ROOP is a multiple paradigm language which combines rule-based, procedure, logic and object-oriented programming techniques.
Register allocation using lazy saves, eager restores, and greedy shuffling
Authors: Burger Robert G. , Waddell Oscar , Dybvig R. Kent
Published: November 2005

This paper presents a fast and effective linear intraprocedural register allocation strategy that optimizes register usage across procedure calls. It capitalizes on our observation that while procedures that do not contain calls (
syntactic leaf routines
) account for under one third of all procedure activations, procedures that actually make no calls (
effective leaf routines
) account for over two thirds of all procedure activations. Well-suited for both caller-and calle-save registers, our strategy employs a “lazy” save mechanism that avoids saves for all effective leaf routines, an “eager” restore mechanism that reduces the effect of memory latency, and a “greedy” register shuffling algorithm that does a remarkbly good job of minimizing the need for temporaries in setting up procedure calls.
Storage assignment to decrease code size
Authors: Liao Stan , Devadas Srinivas , Keutzer Kurt , Tjiang Steve , Wang Albert
Published: November 2005

DSP architectures typically provide indirect addressing modes with auto-increment and decrement. In addition, indexing mode is not available, and there are usually few, if any, general-purpose registers. Hence, it is necessary to use address registers and perform address arithmetic to access automatic variables. Subsuming the address arithmetic into auto-increment and auto-decrement modes improves the size of the generated code.

In this paper we present a formulation of the problem of optimal storage assignment such that explicit instructions for address arithmetic are minimized. We prove that for the case of a single address register the decision problem is NP-complete. We then generalize the problem to multiple address registers. For both cases heuristic algorithms are given. Our experimental results indicate an improvement of 3.
Interprocedural partial redundancy elimination and its application to distributed memory compilation
Authors: Agrawal Gagan , Saltz Joel , Das Raja
Published: November 2005

Partial Redundancy Elimination (PRE) is a general scheme for suppressing partial redundancies which encompasses traditional optimizations like loop invariant code motion and redundant code elimination. In this paper we address the problem of performing this optimization interprocedurally. We use interprocedural partial redundancy elimination for placement of communication and communication preprocessing statements while compiling for distributed memory parallel machines.
A new sort algorithm
Authors: Wang Sunny Y.
Published: November 2005

This paper presents a new sort algorithm, self-indexed sort
(SIS)
, on an approach of non compare-based sorting. Results on time complexity
O
(
n
) and space complexity
O(n+m)
are achieved, where
n
is the size of data being sorted and
m
is the size of the sorting space.Two versions of
SIS
sort algorithm are implemented with one for the sort of structured records and the other for pure data file. The performance of
SIS
sort is tested and analysed under various conditions.
Static and dynamic partitioning of pointers as links and threads
Authors: Wise David S. , Walgenbach Joshua
Published: November 2005

Identifying some pointers as invisible threads, for the purposes of storage management, is a generalization from several widely used programming conventions, like threaded trees. The necessary invariant is that nodes that are accessible (without threads) emit threads only to other accessible nodes. Dynamic tagging or static typing of threads ameliorates storage recycling both in functional and imperative languages.We have seen the distinction between threads and links sharpen both hardware- and software-supported storage management in S
CHEME
, and also in C. Certainly, therefore, implementations of languages that already have abstract management and concrete typing, should detect and use this as a new static type.
Simplifying subtyping constraints
Authors: Pottier François
Published: November 2005

This paper studies type inference for a functional, ML-style language with subtyping, and focuses on the issue of simplifying inferred constraint sets. We propose a powerful notion of entailment between constraint sets, as well as an algorithm to check it, which we prove to be sound. The algorithm, although very powerful in practice, is not complete. We also introduce two new typing rules which allow simplifying constraint sets. These rules give very good practical results.
First-class synchronization barriers
Authors: Turbak Franklyn
Published: November 2005

Our purpose is to promote a second-class mechanism --- the synchronization barrier --- to a first-class value. We introduce the synchron, a novel synchronization mechanism that enables the coordination of a dynamically varying set of concurrent threads that share access to a first-class synchronization token. We demonstrate how synchrons can be used to modularly manage resources in cases where existing techniques are either inapplicable or non-modular. In particular,
synchronized lazy aggregates
enable the first space-efficient aggregate data decomposition of a wide range of algorithms. We also introduce
explicit-demand graph reduction
, a new semantic framework that we have developed to describe concurrency and explain the meaning of a synchron rendezvous.
A theory of weak bisimulation for core CML
Authors: Ferreira William , Hennessy Matthew , Jeffrey Alan
Published: November 2005

Concurrent ML (CML) is an extension of Standard ML of New Jersey with concurrent features similar to those of process algebra. In this papes we build upon John Reppy's reduction semantics for CML by constructing a compositional operational semantics for a fragment of CML, based on higher-order process algebra. We use this to build a semantic theory for CML, based on weak bisimulation equivalence. We give some small examples of proofs about CML expressions, and show that our semantics corresponds to Reppy's up to weak first-order bisimulation.
A popular new course
Authors: Badman Scott
Published: November 2005

The idea for our new Microcomputer Hardware and Systems course came from a student named Carmella who is majoring in Computer Information Systems (CIS) at Jamestown Community College. She showed one of the other computing faculty members a description of a course titled
Microcomputer Operations
offered at a small college about a hundred miles away. She wondered why no college in this area offered such a course. This course covered microcomputer setup and configuration, networks, DOS, Windows, software installation, and board replacement repairs. When a faculty member from the technology area heard about the course he said it would fit well into some proposed changes he was developing for the Computer Technology (CT) degree program. Collectively we realized we had the potential to serve three different constituencies: CIS majors, CT majors, and non-matriculated adults. Since the subject matter fit well with my earlier experience as an electronics technician, I volunteered to develop the course.
Perspectives on reuse (panel)
Authors: Cameron Lorette , Berman Charles , Henderson-Sellers Brian , Hill Laura , Smith Randall , Gossain Sanjiv
Published: November 2005

Reuse is about more than sharing code. As technology, standards and ideas evolve: so do the artifacts available for reuse. Our understanding of the non-technical issues associated with reuse also progresses. This panel will look at reuse from 5 different perspectives. We will look at the reuse of design patterns and of services in a service-based, distributed architecture as examples of artifacts relatively new to the corporate world. We will also focus on the psychological factors affecting the success of reuse programs along with organizational modifications and measurement techniques that will help make reuse work. Lastly, we will take a look at how certain kinds of reuse can affect the success of a project at the user level, and what this might imply for measuring the effectiveness of our reuse programs. The audience will leave with some concrete ideas about how to implement and measure reuse program as well as new thoughts on what artifacts may be reused.
The basic object system
Authors: Dutoit Allen , Levy Sean , Cunningham Douglas , Patrick Robert
Published: November 2005

BOS is a prototype-based, object-oriented toolkit aimed at better supporting evolutionary software development. BOS attempts to support a spectrum of activities in one environment---ranging from rapid prototyping to code hardening. Features enabling rapid prototyping include a prototype-based object model, an interpreted language, run-time argument constraints, position and keyword arguments, and a user interface toolkit. BOS also provides features for code hardening such as multi-methods, multiple inheritance, external code wrapping mechanisms, and interfaces to other packages such as database management systems. BOS thus enables the end-to-end programming of software in an integrated and unified environment. BOS has been used to develop several full-size applications which have been evaluated and delivered externally.