bluuebunny/crossref_metadata_2025 huggingface dataset:
Genericity versus inheritance
Authors: Meyer Bertrand
Published: November 2005

Genericity, as in Ada or ML, and inheritance, as in object-oriented languages, are two alternative techniques for ensuring better extendibility, reusability and compatibility of software components. This article is a comparative analysis of these two methods. It studies their similarities and differences and assesses to what extent each may be simulated in a language offering only the other. It shows what features are needed to successfully combine the two approaches in a statically typed language and presents the main features of the programming language Eiffel, whose design, resulting in part from this study, includes multiple inheritance and limited form of genericity under full static typing.
Object identity
Authors: Khoshafian Setrag N. , Copeland George P.
Published: November 2005

Identity is that property of an object which distinguishes each object from all others. Identity has been investigated almost independently in general-purpose programming languages and database languages. Its importance is growing as these two environments evolve and merge.

We describe a continuum between weak and strong support of identity, and argue for the incorporation of the strong notion of identity at the conceptual level in languages for general purpose programming, database systems and their hybrids. We define a data model that can directly describe complex objects, and show that identity can easily be incorporated in it. Finally, we compare different implementation schemes for identity and argue that a surrogate-based implementation scheme is needed to support the strong notion of identity.
An alternative to subclassing
Authors: Sandberg David
Published: November 2005

Smalltalk-80 obtains some of its expressive power from arranging classes in a hierarchy. Inheritance is an important aspect of this hierarchy. An alternative organization of classes is proposed that emphasizes description instead of inheritance. This alternative can be used with compile-time type checking and retains the important characteristics of Smalltalk's hierarchy.
Design of a distributed object manager for the Smalltalk-80 system
Authors: Decouchant Dominique
Published: November 2005

This paper describes the design of a distributed object manager which allows several Smalltalk-80 systems to share objects over a local-area network. This object manager is based on the following principles: location transparency and uniform object naming, unique object representation and use of symbolic links for remote access, possibility of object migration and distributed garbage collection. A version of the object manager has been implemented and is currently being integrated on a two nodes configuration.
TOOLS: a unifying approach to object-oriented language interpretation
Authors: Koskimies K. , Paakki J.
Published: November 2005

The object-oriented paradigm is applied to the interpreting of programming languages. An intermediate representation of a program is created as a collection of objects representing various entities in the conceptual world of the source language. These objects cover both the static and the dynamic aspects of a program. As a major advantage of this approach, issues that are traditionally handled by very different techniques (like symbol table management and the generation and execution of intermediate code) can be treated in a unified manner. The specification language of an interpreter generator based on these principles is described.
GL—a denotational testbed with continuations and partial continuations as first-class objects
Authors: Johnson G. F.
Published: November 2005

In this paper we describe GL, a language designed to support interactive experimentation with denotational semantics of programming languages, and the novel features of its interpreter. GL is an expressional language that might best be described as an implementation of lambda calculus augmented with several useful basic data types including 1-values.A unique aspect of the GL environment is that it presents a visible, user-accessible implementation of the continuation semantics of GL. The user is expected to understand a denotational definition of GL, and to interact with the system in terms of that definition. In particular, if a computation is temporarily halted the expression continuation extant at that point can be interactively captured and later applied to other values and stores. The implementation of this feature is via a pair of routines called
setjmpup
and
longjmpup
that provide what might be called a partial continuation facility. A partial continuation is a function over stores or store/value pairs that represents execution of a partially executed program from its current state to some later state possibly before its half state. The semantics of partial continuations is interesting, and an extension of GL is presented that contains continuations and partial continuations as first-class objects.The GL environment is fairly complete; it has an experimental polymorphic type inference mechanism that supports self-application and report likely sources of user error in a robust manner, and it has a flexible breakpoint and trace facility that permits program execution to be observed and controlled at a variety of levels of granularity. Moreover, it has been used successfully to teach a graduate course in Theory of Programming Languages.
Interpreting ABF—a language for document construction
Authors: Harr H. , Evens M. W. , Sprowl J.
Published: November 2005

This paper describes an interpreter for ABF, a language for constructing legal documents. The ABF language defines both commands to develop documents and commands to manipulate those documents. The language has typical programming constructs for sequence, selection, and repetition but also allows the user other capabilities to aid in document construction; the user can modify the program while it is running (change the document while it is being processed), type the variables during the initial processing of a document, and then change the type during later processing, enter commands that require a change of context during the processing of a document, output a document with variables still undefined. A document is constructed using conditional and repeat statements and incorporation of other documents by reference. Data types include documents, strings, numbers, dollar amounts and logical values. Arrays can be formed for all types except documents. There are three forms of subprograms: documents can be incorporated by reference in other documents at any point at which a variable name is permitted; rules (subprocedures) for computing values can be attached to any variable; and alternate questions can be attached to variables in a similar manner. The ABF system queries the user for any values needed to complete a document; questions are generated from variable names.
Constructive real interpretation of numerical programs
Authors: Boehm H. J.
Published: November 2005

We explore the feasibility of providing exact real arithmetic for use in conventional numerical programs. We have built a prototype interpreter which replaces floating point operations with operations on constructive real numbers in the execution of conventional Fortran programs. Such a facility makes it unnecessary to concern oneself with issues of numerical stability in the solution of small problems. It also provides a useful tool for the development of larger numerical programs.We discuss the computability and algorithmic issues involved in the design of the interpreter, as well as some preliminary experiences and performance measurements.
Distributed garbage collection
Authors: Eckart J. D. , LeBlanc R. J.
Published: November 2005

There are two basic approachs to the problem of storage reclamation, process- and processor-based, named for the view point used to recognize when a particular piece of storage can be reclaimed. Examples of the processor approach include mark/sweep and copying algorithms and their variants, while reference counting schemes use a process view of the collection. It is argued that the process approach is better suited for distributed computation where links between dynamically allocated objects may cross processor boundaries. In addition, the process approach allows the heap to be more conveniently shared with other processes in those cases when different processes might not have their own virtual address spaces. A new algorithm using the process approach is given. Its space requirement per object is better than that for reference counting. In addition, a restricted form of pointer replacement is supported which allows circular structures so constructed to be properly collected.
An efficient approach to data flow analysis in a multiple pass global optimizer
Authors: Jain S. , Thompson C.
Published: November 2005

Data flow analysis is a time-consuming part of the optimization process. As transformations are made in a multiple pass global optimizer, the data flow information must be updated to reflect these changes. Various approaches have been used, including complete recalculation as well as partial recalculation over the affected area. The approach presented here has been designed for maximum efficiency. Data flow information is completely calculated only once, using an interval analysis method which is slightly faster than a purely iterative approach, and which allows partial recomputation when appropriate. A minimal set of data flow information is computed, keeping the computation and update cost low. Following each set of transformations, the data flow information is updated based on knowledge of the effect of each change. This approach saves considerable time over complete recalculation, and proper ordering of the various optimizations minimizes the amount of update required.
Control flow analysis in scheme
Authors: Shivers O.
Published: November 2005

Traditional flow analysis techniques, such as the ones typically employed by optimizing Fortran compilers, do not work for Scheme-like languages. This paper presents a flow analysis technique —
control flow analysis
— which is applicable to Scheme-like languages. As a demonstration application, the information gathered by control flow analysis is used to perform a traditional flow analysis problem, induction variable elimination. Extensions and limitations are discussed.

The techniques presented in this paper are backed up by working code. They are applicable not only to Scheme, but also to related languages, such as Common Lisp and ML.
Promises: linguistic support for efficient asynchronous procedure calls in distributed systems
Authors: Liskov B. , Shrira L.
Published: November 2005

This paper deals with the integration of an efficient asynchronous remote procedure call mechanism into a programming language. It describes a new data type called a
promise
that was designed to support asynchronous calls. Promises allow a caller to run in parallel with a call and to pick up the results of the call, including any exceptions it raises, in a convenient and type-safe manner. The paper also discusses efficient composition of sequences of asynchronous calls to different locations in a network.
Unfold/fold transformations and loop optimization of logic programs
Authors: Debray S. K.
Published: November 2005

Programs typically spend much of their execution time in loops. This makes the generation of efficient code for loops essential for good performance. Loop optimization of logic programming languages is complicated by the fact that such languages lack the iterative constructs of traditional languages, and instead use recursion to express loops. In this paper, we examine the application of unfold/fold transformations to three kinds of loop optimization for logic programming languages: recursion removal, loop fusion and code motion out of loops. We describe simple unfold/fold transformation sequences for these optimizations that can be automated relatively easily. In the process, we show that the properties of unification and logical variables can sometimes be used to generalize, from traditional languages, the conditions under which these optimizations may be carried out. Our experience suggests that such source-level transformations may be used as an effective tool for the optimization of logic programs.
ACM SIGPLAN history of programming languages conference ALGOL 60 language summary
Authors: Gries David
Published: November 2005

The term ALGOL is reported to have sprung from “ALGOrithmic Language”. Many forget, however, that ALGOL is the second brightest star in the constellation Perseus and part of an eclipsing binary. ALGOL exhibits a variation in light, which is caused by the fact that once every 69-odd hours it is partially eclipsed by a dark body, its partner star, for about 10 hours. But note that ALGOL always manages to regain its brilliance. ALGOL and its eclipsing companion (could it be FORTRAN?) are miles and miles apart (about 6,000,000).

ALGOL 60 and FORTRAN are both algebraic languages designed primarily for writing programs to solve numerical problems. Both have simple variables and arrays, declarations, assignment statements, conditional and iterative statements, and procedures (subroutines).
Origins of the APT language for automatically programmed tools
Authors: Ross Douglas T.
Published: November 2005

The Air Force announced today that it has a machine that can receive instruction sin English, figure out how to make whatever is wanted, and teach other machines how to make it.

An Air Force general said it will enable the United States to “build a war machine that nobody would want to tackle.”
The early history of COBOL
Authors: Sammet Jean E.
Published: November 2005

This paper discusses the early history of COBOL, starting with the May 1959 meeting in the Pentagon which established the Short Range Committee which defined the initial version of COBOL, and continuing through the creation of COBOL 61. The paper gives a detailed description of the committee activities leading to the publication of the first official version, namely COBOL 60. The major inputs to COBOL are discussed, and there is also a description of how and why some of the technical decisions in COBOL were made. Finally, there is a brief “after the fact” evaluation, and some indication of the implication of COBOL on current and future languages.
The FORTRAN Language
Authors: Galler Bernard A.
Published: November 2005

The FORTRAN language was intended to be a vehicle for expressing scientific and mathematical computation, while allowing efficient object code to be produced. Since there was an emphasis on scientific computation in FORTRAN and FORTRAN II, little provision was made for heterogeneous data structures. Only arrays of up to three dimensions were possible, and they had to be declared explicitly:

DIMENSION ALPHA (10,15), BETA (12)

Input and output statements allowed a little more flexibility, in that provision was made for controlling the format of information read from or written to the outside world (as opposed to reading or writing binary information on disk or tape):

WRITE (5,200) MTH, BETA, Y

200FORMAT (6H MONTH, 13, 8H; QUOTAS, 12F4.0, 10H; FORECAST, F 6.2 )
The development of the General Purpose Simulation System (GPSS)
Authors: Gordon Geoffrey
Published: November 2005

The General Purpose Simulation System (GPSS) is a programming system designed for the simulation of discrete systems. These are systems that can be modeled as a series of state changes that occur instantaneously, usually over a period of time. Complexities in their analysis arise because there are many elements in the system, and there is competition for limited system resources. The simulation technique uses numerical computation methods to follow the system elements through their changes of state, and predicts properties of the system from measurements on the model.

GPSS came into existence rapidly, with virtually no planning, and surprisingly little effort. It came rapidly because it filled an urgent need that left little time for exploring alternatives. The lack of planning came from a happy coincidence of a solution meeting its problem at the right time. The economy of effort was based on a background of experience in the type of application for which the language was designed, both on the part of the designer and the early users.
The development of the SIMULA languages
Authors: Nygaard Kristen , Dahl Ole-Johan
Published: November 2005

The organizers of this conference have told us that we should write at least 25 pages of manuscript, but that we may produce as many pages more as we wanted. Perhaps they did not envisage the possible consequences, but we have taken their words at face value.

This paper has implied a vast amount of work and archeological activities. We are grateful to SIGPLAN for defining a task to which resources had to be allocated by our institutions and which forced us to write down an account of our work from 1961 to 1971. While we are writing this preface, those years are very much alive to us. We realize that we lived through this period in a state of semimadness, a combination of very hard work, frustration, and euphoria.
Afterword
Authors: Wexelblat R. L.
Published: November 2005

The formal proceedings of the ACM SIGPLAN History of Programming Languages Conference are to be published in a volume containing not only the papers, but edited transcriptions of the keynote speech, the discussions following each paper, and other relevant material.

In this way, the organizers of the conference hope to provide a permanent archive of information on the early stages of the development of those languages which have proven their value through long and continued use.
Architectural support for the efficient generation of code for horizontal architectures
Authors: Rau B. R. , Glaeser C. D. , Greenawalt E. M.
Published: November 2005

Horizontal architectures, such as the CDC Advanced Flexible Processor [I] and the FPS APi20-B [2}, consist of a number of resources that can operate in parallel, each of which is controlled by a field in the wide instruction word. Such architectures have been developed to perform high speed scientific computations at a modest cost: Figure 1 displays those characteristics of horizontal architectures that are germane to the issues discussed in this paper. The simultaneous requirements of high performance and low cost lead to an architecture consisting of multiple pipelined processing elements (PEs) such as adders and multipliers, a memory (which for scheduling purposes may be viewed as yet another PE with two operations: a READ and a WRITE), and an interconnect which ties them all together. The interconnect allows the result of one operation to be directly routed to another PE as one of the inputs for an operation that is to be performed there. The required memory bandwidth is reduced since temporary values need not be written to and read from the memory. The final aspect of horizontal processors that is of interest is that their program memories emit wide instructions which synchronously specify the actions of the multiple and possibly dissimilar PEs. The program memory is sequenced by a conventional sequencer that assumes sequential flow of control unless a branch is explicitly specified.

As a consequence of the simplicity of such an architecture, it is inexpensive relative to the potential performance of the multiple pipelined PEs. However, if this potential performance is to be realized, the multiple resources of a horizontal processor must be scheduled effectively. The scheduling task for conventional horizontal processors is quite complex and the construction of highly optimizing compilers for them is a difficult and expensiw3 project. The polycyclic architecture [3- 6] is a horizontal architecture with architectural support for the scheduling task. The cause of the complexity involved in scheduling conventional horizontal processors and the manner in which the polycyclic architecture addresses this issue are outlined in this paper.
Guidelines for creating a debuggable processor
Authors: McLear R. E. , Scheibelhut D. M. , Tammaru E.
Published: November 2005

Hardware without software is of little use. Systems that ease the task of debugging software reduce cost and speed development. This paper presents guidelines for designing processors that ease debugging for real-time computer systems. Special hardware can aid the debugging process by tracing execution and accesses to memory. Such hardware requires access to signals that may not be readily available. Other, less exotic hardware provides an interface to the programmer and other processors. The hardware and software of the debugging system should not alter the real-time characteristics of the system under test and should be able to operate on a field-grade processor. It is undesirable to require special versions of processor hardware and software for the debugging system.
Heart
Authors: Kamibayashi N. , Ogawana H. , Nagayama K. , Aiso H.
Published: November 2005

This paper discusses the role of microprogramming in operating system design and shows several things: (1) advantages of the efficiency which may be gained from microcoded operating system primitives, (2) selecting the most appropriste primitives for implementation, and (3) an analysis of the tradeoffs among software, firmware, and hardware. The authors propose a practical approach of enhancing computer architecture level, from a view point of functional hierarchy of operating systems. In order to prove the advantages of this approach, we have designed and implemented an experimental abstract machine for an operating system nucleus. This research is an experimental design, and evaluation on its operating system nucleus machine,called HEART. HEART is a set of primitive and universal functions, and works as a nucleus of a multiprogrammed operating system. The research results of our approach are the followings: First, to clarify the properties of operating system nucleus, taking functional hierarchy of operating system into consideration. Second, to show the design of operating system nucleus based on novel concepts. Third, to confirm the possibility of implimenting operating system nucleus machine. Finally, we give a performance evaluation on microcoded HEART and the effectiveness of enhancing computer architecture level based on the properties of operating systems.
Data abstraction for designing database-intensive applications
Authors: Brodie Michael L.
Published: November 2005

There is a growing exchange of ideas amongst Artificial Intelligence (AI), Database (DB) and Programming Language (PL) researchers concerning conceptual modelling of complex, object-oriented applications. The complexity of these applications arises from complicated structural and behavioral properties which change through time; concurrent, interactive access by users with different processing needs over a shared database; information locality (i.e., DB views, PL data abstractions, AI perspectives); and primarily update-oriented transactions. Two main problems raised by these applications are:

managing the intellectual complexity of their design, development and evolution, and

defining and ensuring semantic integrity.
Default reasoning and inheritance mechanisms on type hierarchies
Authors: Carbonell Jaime G.
Published: November 2005

Type hierarchies abound in Artificial Intelligence, Data Bases and Programming Languages. Although their size, use and complexity differs, all share a central inference mechanism:
Inheritance of information
, their
raison d'etre
. This paper discusses various types of type hierarchies and inheritance mechanisms, concluding with a proposed
generalized inheritance mapping
approach to resolve issues of lateral and upward inheritance (to augment the traditional downward approach), as well as default reasoning and limited non-monotonic inference.
Data models in database management
Authors: Codd E. F.
Published: November 2005

It is a combination of three components: 1) a collection of data structure types (the building blocks of any database that conforms to the model);

2) a collection of operators or inferencing rules, which can be applied to any valid instances of the data types listed in (1), to retrieve or derive data from any parts of those structures in any combinations desired;

3) a collection of general integrity rules, which implicitly or explicitly define the set of consistent database states or changes of state or both—these rules may sometimes be expressed as insert-update-delete rules.
On the specification of behavioural constraints
Authors: Cristian Flaviu
Published: November 2005

When designing information processing systems, the key problem is to find what symbols and constructs (available in some given language) should be used so as to be able to answer the questions that the users want to ask and to perform the state transitions that the users have to perform in order to keep in step with some reality that is being modelled. If the language that is being used cannot be interpreted directly by the software of a computer (e.g. set theory, algebra, semantic networks), the resulting model is called an abstract model (e.g. a specification, a data base schema). If all of the symbols and constructs used to express the model can be interpreted by a computer, the model is a concrete implementation (e.g. a data base system). Both the abstract and concrete models capture some aspects of the reality that is modelled. They differ with respect to the languages in which they are expressed.

The choice of the languages which are appropriate for writing such models is a subject of intensive debate. The recent workshop on Data Abstraction, Data Bases and Conceptual Modelling has shown that this debate is not likely to diminish in the near future. In the context of this debate, however, a common opinion was expressed several times by data base participants: the data models used to specify data base schemas are lacking to support the specification of operations tailored to particular application environments. It is therefore expected that in the context of data base modelling, the integration of operations (behaviour) with data (structure) will be one of the most fertile research areas for the next few years.
Constraints
Authors: Deutsch L. Peter
Published: November 2005

Most programming systems reflect a model of computation which sharply distinguishes between “passive” data objects and “active” program objects (procedures). Furthermore, procedures describe not only a set of computations but the precise flow of control between them. In contrast, a group at MIT is investigating a new paradigm called
constraints
in which a single kind of object models both data and procedures, and in which the description of procedures minimizes commitment to the order in which computational steps will be executed.

A (primitive) constraint is an object with some
parts
, which correspond to fields of a data structure or input/output parameters of a procedure, and a
body
which describes how to compute the values of some parts from other parts. The body consists of
rules
written in an implementation language (Lisp in the MIT systems). Constraints with no body behave like ordinary data structures; constraints with substantial bodies behave more like procedures. However, unlike procedures, which always compute the same set of outputs from the same set of inputs, a constraint may compute in different directions depending on the available data.
Make more of data types
Authors: Mayr Heinrich C.
Published: November 2005

This position paper refers to some observations I made at the 'High Level Abstraction Workshop', and it exhibits a way to attack abstraction and specification problems in the database field. Because of the fixed page limit this will be done in a more or less cursory collection of remarks.
A three-level approach to the description of data structures, and notational framework
Authors: Meyer Bertrand
Published: November 2005

When talking about data structures, whether local to a program or persistent over time, three different viewpoints are equally important. The first one is that of the user, who is interested in the external properties of a certain structure, more precisely, its noticeable behavior in response to outside effects (queries, requests for modifications, etc.). The second viewpoint is that of the language designer, who is in search of a small number of basic objects and building mechanisms which will allow for the description of complex objects in terms of simpler ones. The last view is that of the implementor, who must find efficient representations for the constructs thus described.

Based on this remark, a three-level description of data structures has been used by the author in previous work [6, 7, 8]. The three levels may be called:
Issues in the design of database programming languages
Authors: Rowe Lawrence A.
Published: November 2005

This paper discusses two issues in the design of database constructs for programming languages. The first issue is whether records in a database correspond to records in a programming language or to a distinct type such as
tuple
. The second issue is what facilities are provided to define the interface between an application program and a database.

The discussion below is based on our research on the RIGEL database programming language [Rowe 79, 80a]. RIGEL is a block-structured language with constructs for accessing relational databases, a
module
construct for data abstraction, and an exception-handling mechanism. The first implementation of the language has recently been completed and is being distributed.
Towards constructive axiomatic specifications
Authors: dos Santos C. S. , Furtado A. L. , de Castilho J. M.V. , de Carvalho S. E.R.
Published: November 2005

The main goal of our efforts is the specification of data bases whose structure and behaviour are restricted by semantic integrity constraints. Research proceeds along the following stages:

1. Choose a data model;

2. Establish a taxonomy of integrity constraints;

3. Specify the data model formally;

4. Develop a methodology for specifying conceptual schemas for different applications, based on the data model;

5. Provide a conceptual characterization of query and update operations.
Data abstraction tools
Authors: Schmidt Joachim W.
Published: November 2005

Current research in data modeling is motivated by the following dilemma:

- At the
application
level - being confronted with “slices of reality” - details are perceived that, in general, cannot be represented.

- At the
representation
level - being confronted with “levels of machines” - details are represented that, in general, cannot be perceived.

Abstraction methods cope with that problem by suppressing unnecessary details and by formalizing and structuring the relevant information.
Abstraction, data types, and models for software
Authors: Shaw Mary
Published: November 2005

In the area of software development and maintenance, a major issue is managing the complexity of the systems. Programming methodologies and languages to support them have grown in response to new ideas about how to cope with this complexity. A dominant theme in the growth of methodologies and languages is the development of tools dealing with abstractions. An
abstraction
is a simplified description, or
specification
, of a system that emphasizes some of its details or properties while suppressing others. A
good
abstraction is one in which information that is significant to the reader (i.e., the user) is emphasized while details that are immaterial, at least for the moment, are suppressed.

What we call “abstraction” in programming systems corresponds closely to what is called “modelling” in many other fields. It shares many of the same problems deciding which characteristics of the system are important, what variability (i.e., parameters) should be included, which descriptive formalism to use, how the model can be validated, and so on
Transforming interpreters into inverse interpreters by partial evaluation
Authors: Glück Robert , Kawada Youhei , Hashimoto Takuya
Published: November 2005

The experiments in this paper apply the idea of prototyping programming language tools from robust semantics: we used a partial evaluator (Similix) to turn interpreters into inverse interpreters. This way we generated inverse interpreters for several small languages including interpreters for Turing machines, an applied lambda calculus, a flowchart language, and a subset of Java bytecode. Limiting factors of online partial evaluation were the polyvariant specialization scheme with its lack of generalization;advantages were the availability of higher-order values to specialize a breadth-first tree traversal.This application of self-applicable partial evaluation is different from the classical Futamura projections that tell us how to translate a program by specialization of an interpreter.
Exploiting task-level concurrency in a programmable network interface
Authors: Kim Hyong-youb , Pai Vijay S. , Rixner Scott
Published: November 2005

Programmable network interfaces provide the potential to extend the functionality of network services but lead to instruction processing overheads when compared to application-specific network interfaces. This paper aims to offset those performance disadvantages by exploiting task-level concurrency in the workload to parallelize the network interface firmware for a programmable controller with two processors. By carefully partitioning the handler procedures that process various events related to the progress of a packet, the system can minimize sharing, achieve load balance, and efficiently utilize on-chip storage. Compared to the uniprocessor firmware released by the manufacturer, the parallelized network interface firmware increases throughput by 65% for bidirectional UDP traffic of maximum-sized packets, 157% for bidirectional UDP traffic of minimum-sized packets, and 32--107% for real network services. This parallelization results in performance within 10--20% of a modern ASIC-based network interface for real network services.
Impala
Authors: Liu Ting , Martonosi Margaret
Published: November 2005

Sensor networks are long-running computer systems with many sensing/compute nodes working to gather information about their environment, process and fuse that information, and in some cases, actuate control mechanisms in response. Like traditional parallel systems, communication between nodes is of fundamental importance, but is typically accomplished via wireless transceivers. One further key attribute of sensor networks is that they are almost always long running systems, intended to operate in situ, with minimal direct human intervention, for months or years. This requirement for long-running autonomy mandates careful design of the runtime system that manages applications on each node, to ensure reliability and ease of upgrades over the life of the system.This paper describes Impala, a middleware architecture that enables application modularity, adaptivity, and repair-ability in wireless sensor networks. Impala allows software updates to be received via the node's wireless transceiver and to be applied to the running system dynamically. In addition, Impala also provides an interface for on-the-fly application adaptation in order to improve the performance, energy-efficiency, and reliability of the software system. Impala has been designed to be a part of the ZebraNet mobile sensor network, but we are also prototyping it within HP/Compaq iPAQ Pocket PC handhelds. We present performance data for both real system measurements of the Pocket PC version as well as simulations of a full mobile sensor system deployment. Overall, Impala is a lightweight runtime system that can greatly improve system reliability, performance, and energy-efficiency. The ideas introduced here for sensor networks have applicability more broadly in other long-running autonomous parallel systems as well.
No name
Authors: Biddle Robert , Martin Angela , Noble James
Published: November 2005

In the beginning, so our myths and stories tell us, the programmer created the program from the eternal nothingness of the void. In this essay, we recognise that programs these days are like any other assemblage, and suggest that in fact programming has always been about reuse. We also explore the nature of reuse, and claim that Components themselves are not the most important consideration for reuse; it is the end product, the composition. The issues still involve value, investment, and return. But pervasive reuse promotes a change in the method of construction of the program, and in the program itself.
A compile-time optimization framework for Ada rendezvous
Authors: Lu Hongmin , Zhou Yuming , Lu Jiangtao , Xu Baowen
Published: November 2005

Rendezvous is the basic synchronous communication mechanism used by tasks, which causes tasks blocked under some circumstances. Holding the semantics of the rendezvous, this paper uses semaphores to transform the entry call and accept statement pairs and makes tasks execute some statements during the blocked time because of waiting for the beginning or end of a rendezvous. Therefore, the parallelism between the client and the server is improved.
What can we gain by unfolding loops?
Authors: Song Litong , Kavi Krishna
Published: November 2005

Loops in programs are the source of many optimizations for improving program performance, particularly on modern high-performance architectures as well as vector and multithreaded systems. Techniques such as loop invariant code motion, loop unrolling and loop peeling have demonstrated their utility in compiler optimizations. However, many of these techniques can only be used in very limited cases when the loops are "well-structured" and easy to analyze. For instance, loop invariant code motion works only when invariant code is inside loops; loop unrolling and loop peeling work effectively when the array references are either constants or affine functions of index variable. It is our contention that there are many opportunities overlooked by limiting the optimizations to "well structured" loops. In many cases, even "badly-structured" loops may be transformed into "well structured" loops. As a case in point, we show how some loop-dependent code can be transformed into loop-independent code by transforming the loops. Our technique described in this paper relies on unfolding the loop for several initial iterations such that more opportunities may be exposed for many other existing compiler optimization techniques such as loop invariant code motion, loop peeling, loop unrolling and so on.
An iterative-design model for reusable object-oriented software
Authors: Gossain Sanjiv , Anderson Bruce
Published: November 2005

We present an iterative-design approach for reusable object-oriented software that augments existing design methods by incorporating iteration into the design methodology and focuses on the set of problems within the domain, encouraging reuse of existing design information. The model has five separate stages which are described, before an example design is outlined using the model with sample code constructs in C++. Our results have shown a high degree of code reuse when using the model, directly attributable to two distinct design stages. An analysis of these results is also presented.
Garbage collection of actors
Authors: Kafura Dennis , Washabaugh Doug , Nelson Jeff
Published: November 2005

This paper considers the garbage collection of concurrent objects for which it is necessary to know not only “reachability,” the usual criterion for reclaiming data, but also the “state” (active or blocked) of the object. For the actor model, a more comprehensive definition than previously available is given for reclaimable actors. Two garbage collection algorithms, implementing a set of “coloring” rules, are presented and their computational complexity is analyzed. Extensions are briefly described to allow incremental, concurrent, distributed and real-time collection. It is argued that the techniques used for the actor model applies to other object-based concurrent models
.
PCLOS: stress testing CLOS experiencing the metaobject protocol
Authors: Paepcke Andreas
Published: November 2005

This paper demonstrates that the CLOS
metaobject protocol
approach to defining and implementing an object model is very powerful. CLOS is an object-oriented language that is based on Common Lisp and is in the process of being standardized. Implementations of CLOS are themselves object-oriented with all major building blocks of the language being instances of system classes. A metaobject protocol provides a framework for CLOS implementations by specifying the hierarchy of these classes and the order and contents of the communication among their instances. This design has made CLOS both flexible and portable, two design goals that traditionally conflict. In support of this suggestion we present a detailed account of how we added object persistence to CLOS without modifying any of the language's implementation code.
Issues in object database management
Authors: Stein Jacob , Andrews Tim , Kent Bill , Rotzell Kate , Weinreb Dan
Published: November 2005

While the availability of commercial systems from several vendors indicates maturity in object database management technology, there are numerous issues which remain. This panel will attempt to expose and discuss several of these issues.

Part of the performance advantage realized by object database management systems comes from linking application programs with the database management system, and the use of large virtual memory caches. This is acceptable in engineering applications where previously large amounts of data were read from the file system into an application program's data space. However, the potential impact on database integrity of giving application programs direct access to very large database management system caches will be of great concern in commercial applications. How can these concerns be addressed with minimal impact on the performance advantage of object database management?

There appear to be two distinct approaches to object query languages: extensions to SQL and programming language extensions. SQL extensions might provide a fast path to a standard, but would have the traditional impedance mismatch problems associated with embedded query languages. Language extensions are elegant in that they use the same syntax as the programming language and do not suffer from impedance mismatch problems. However, language extensions would probably make standards more difficult to arrive at as it would require the coordination of extensions to multiple languages. Which of the approaches is most appropriate? In which order should these two approaches be addressed by the object database vendors and standards bodies?

One might argue that a good deal of research in relational theory has had little or no impact on commercial relational systems (e.g., relational dependence theory). From a vendor's perspective, what are the hard, interesting research issues whose resolution would allow you to build better systems?
The performance of an object-oriented threads package
Authors: Faust John E. , Levy Henry M.
Published: November 2005

Presto is an object-oriented threads package for writing parallel programs on a shared-memory multiprocessor. The system adds thread objects and synchronization objects to C++ to allow programmers to create and control parallelism. Presto's object-oriented structure, along with its user-level thread implementation, simplifies customization of thread management primitives to meet application-specific needs.

The performance of thread primitives is crucial for parallel programs with fine-grained structure; therefore, the principal objective of this effort was to substantially improve Presto's performance under heavy loads without sacrificing the benefits of its object-oriented interface. We discuss design and implementation issues for shared-memory multiprocessors, and the performance impact of various designs is shown through measurements on a 20-processor Sequent Symmetry multiprocessor.
A survey of semantic description frameworks for programming languages
Authors: Zhang Yingzhou , Xu Baowen
Published: November 2005

Formal semantic description is significant for design, reasoning and standardization of programming languages, and it plays an important part in the optimization of the compiler. However, compared to the amount of effort that has been made to the research of various semantic frameworks over more than forty years, their actual applications are definitely frustrating. This survey reviews the history of developments on semantic description frame-works for programming languages. It also illustrates features and actual applications of the main frameworks (including operational, deno-tational, axiomatic and hybrid semantics). In some practical aspects, such as comprehensibility, extensibility and applicability, the qualitative comparisons of these frameworks are given distinctly. It suggests that a more popular formal semantic description should behave more elegantly in readability, modularity, abstractness, comparability, reasonability, applicability and tool-support.
Back-propagation of knowledge from syntax tree to C source code
Authors: Yavner Jonathan
Published: November 2005

To support source-code annotation, an analysis of a program must provide (
filename, line, column
) positioning tokens. The Myer parser computes such tokens for individual compilation units, then combines units to create unified annotations for files, even header files. Myer is implemented using patches to gcc, an approach that has pluses and minuses.
When and what to compile/optimize in a virtual machine?
Authors: Kumar K. V. Seshu
Published: November 2005

To speed up the computation of some of the object languages, virtual machines use dynamic compilation. But due to compilation taking place during user application runtime, one has to choose which methods to compile, so that the compile time has little impact on the total runtime of the actual application. In order to achieve this, we have to use an estimate to determine the process of compilation. Current virtual machines use run time information such as number of calls made to this method, size of the method and as well as number of times the back edges taken to determine the hotness of a method. They use this information against some threshold which does not have any relationship with the method that is being considered for compilation.Detecting the hot routines is very important from the perspective of performance since optimized methods run 10 times faster than the interpreted version. In this paper we propose a new technique called
relative estimation
for determining the hotness of the functions. For each method in the application, we estimate the cost/benefits for compilation or optimization by doing method analysis. We select the methods for compilation or optimization initially based on the above metrics using the proposed relative estimation technique. Later on we use the online profile information such as backedge counters and invocation counts to adjust the relative estimation process itself. We have performed experiments to validate the effectiveness of the proposed method on SPECjvm98 benchmark suite and found that up to 4% performance improvement in the application execution time occurs.
Incremental execution of transformation specifications
Authors: Sittampalam Ganesh , de Moor Oege , Larsen Ken Friis
Published: November 2005

We aim to specify program transformations in a declarative style, and then to generate executable
program transformers
from such specifications. Many transformations require non-trivial program analysis to check their applicability, and it is prohibitively expensive to re-run such analyses after each transformation. It is desirable, therefore, that the analysis information is incrementally updated.We achieve this by drawing on two pieces of previous work: first, Bernhard Steffen's proposal to use
model checking
for certain analysis problems, and second, John Conway's theory of
language factors
. The first allows the neat specification of transformations, while the second opens the way for an incremental implementation. The two ideas are linked by using regular patterns instead of Steffen's modal logic: these patterns can be viewed as queries on the set of program paths.