waashk/acm huggingface dataset:
interfaces, protocols, and the semi-automatic construction of software adaptors  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.  daniel m. yellin robert e. strom
a generalized iterative construct and its semantics  a new programming language construct, called doupon, subsumes dijkstra's selective (if) and iterative (do) constructs. doupon has a predicate transformer approximately equivalent in complexity to that for do. in addition, it simplifies a wide variety of algorithms, in form as well as in discovery and proof. several theorems are demonstrated that are useful for correctness proofs and for optimization and that are not applicable to do or if. the general usefulness of doupon derives from a separation of the concerns of invariance, through iteration, from those of termination.  ed anson
writing multi-user applications in apl2  this paper presents a general scheme for quickly implementing multi-user applications. several facilities of apl2 are discussed which make apl2 a particularly suitable solution for such problems. the resulting implementation is used to demonstrate how the advanced facilities of apl2 affect the writing of programs. the simplicity of the programs indicates how productive apl2 can be. the paper does not discuss the necessary user-friendly front end that any application should have because that is no different from a single user application.  james a. brown
building interpreters by composing monads  we exhibit a set of functions coded in haskell that can be used as building blocks to construct a variety of interpreters for lisp-like languages. the building blocks are joined merely through functional composition. each building block contributes code to support a specific feature, such as numbers, continuations, functions calls, or nondeterminism. the result of composing some number of building blocks is a parser, an interpreter, and a printer that support exactly the expression forms and data types needed for the combined set of features, and no more.  the data structures are organized as pseudomonads, a generalization of monads that allows composition. functional composition of the building blocks implies type composition of the relevant pseudomonads.  our intent was that the haskell type resolution system ought to be able to deduce the appropriate data types automatically. unfortunately there is a deficiency in current haskell implementations related to recursive data types: circularity must be reflected statically in the type definitions.  we circumvent this restriction by applying a purpose-built program simplifier that performs partial evaluation and a certain amount of program algebra. we construct a wide variety of interpreters in the style of wadler by starting with the building blocks and a page of boiler-plate code, writing three lines of code (one to specify the building blocks and two to (redundantly) specify type compositions), and then applying the simplifier. the resulting code is acceptable haskell code.  we have tested a dozen different interpreters with various combinations of features. in this paper we discuss the overall code structuring strategy, exhibit several building blocks, briefly describe the partial evaluator, and present a number of automatically generated interpreters.  guy l. steele
process locking: a protocol based on ordered shared locks for the execution of transactional processes  in this paper, we propose _process locking_, a dynamic scheduling protocol based on ideas of ordered shared locks, that allows for the correct concurrent and fault-tolerant execution of transactional processes. transactional processes are well defined, complex structured collections of transactional services. the process structure comprises flow of control between single process steps and also considers alternatives for failure handling purposes. moreover, the individual steps of a process may have different termination characteristics, i.e., they cannot be compensated once they have committed. all these constraints have to be taken into consideration when deciding how to interleave processes. however, due to the higher level semantics of processes, standard locking techniques based on shared and exclusive locks on data objects cannot be applied. yet, process locking addresses both atomicity and isolation simultaneously at the appropriate level, the scheduling of processes, and accounts for the various constraints imposed by processes. in addition, process locking aims at providing a high degree of concurrency while, at the same time, minimizing execution costs. this is done by allowing cascading aborts for rather simple processes white this is prevented for complex, long- running processes within the same framework.  heiko schuldt
cache performance of garbage-collected programs  as processor speeds continue to improve relative to main-memory access times, cache performance is becoming an increasingly important component of program performance. prior work on the cache performance of garbage-collected programs either argues or assumes that conventional garbage-collection methods will yield poor performance, and has therefore concentrated on new collection algorithms designed specifically to improve cache-level reference locality.  this paper argues to the contrary: many programs written in garbage-collected languages are naturally well-suited to the direct-mapped caches typically found in modern computer systems. garbage- collected programs written in a mostly-functional style should perform well when simple linear storage allocation and an infrequently-run generational compacting collector are employed; sophisticated collectors intended to improve cache performance are unlikely to be necessary. as locality becomes ever more important to program performance, programs of this kind may turn out to have a significant performance advantage over programs written in traditional languages.  mark b. reinhold
reducing maintenance costs through the application of modern software architecture principles large software programs are usually long lived and continually evolve. substantial maintenance effort is often extended by engineers trying to understand the software prior to making changes. to successfully evolve the software, a thorough understanding of the architect's intentions about software organization is required. software maintenance costs can be reduced significantly if the software architecture is well defined, clearly documented, and creates an environment that promotes design consistency through the use of guidelines and design patterns. building a maintainable system depends upon the consistent application of these architectural practices. this paper describes the application of modern software architecture methods to achieve a maintainable implementation of a large, distributed, real-time, embedded software system. christine hulse scott edgerton michael ubnoske louis vazquez
cool: kernel support for object-oriented environments  the chorus object-oriented layer (cool) is an extension of the facilities provided by the chorus distributed operating system with additional functionality for the support of object-oriented environments. this functionality is realized by a layer built on top of the chorus v3 nucleus, which extends the chorus interface with generic functions for object management: creation, deletion, storage, remote invocation and migration. one major goal of this approach was to explore the feasibility of general object management at the kernel level, with support of multiple object models at a higher level. we present the implementation of cool and a first evaluation of this approach with a c++ environment using the cool mechanisms.  sabine habert laurence mosseri
an object-oriented approach to automated generation of challenge examinations using ada 95 the primary objective of this paper is to analyze and evaluate the usefulness of object-oriented development and the ada 95 programming language as applied to a specific software development project. a secondary objective is to show that structured development is still useful while applying object-oriented development and that the two methods can be integrated. the project is to develop an automated tool for generation of challenge examinations to test the knowledge of students in a given subject. the concepts of object-oriented and structured development are discussed and compared as they pertain to this problem domain. the methods are then applied and evaluated as the project is taken from analysis of the problem, through requirements specification, design, and implementation. during the requirements analysis and design phases, comparisons are made between object composition and functional decomposition, and rationale is discussed for the best places to use each. during the implementation phase, object-oriented features of the ada 95 programming language are used as well as traditional structured programming techniques. conclusions are summarized regarding the usefulness of the object-oriented paradigm and ada 95 for this project, and the benefits of incorporating traditional structured development where it fits best. arthur irving littlefield
object-oriented concurrent programming in cst  cst is a programming language based on smalltalk-80 that supports concurrency using locks, asynchronous messages, and distributed objects. distributed objects have their state distributed across many nodes of a machine, but are referred to by a single name. distributed objects are capable of processing many messages simultaneously and can be used to efficiently connect together large collections of objects. they can be used to construct a number of useful abstractions for concurrency. this paper describes the cst language, gives examples of its use, and discusses an initial implementation.  w. j. dally a. a. chien
a methodology for implementing highly concurrent data objects  a concurrent object is a data structure shared by concurrent processes. conventional techniques for implementing concurrent objects typically rely on critical sections; ensuring that only one process at a time can operate on the object. nevertheless, critical sections are poorly suited for asynchronous systems: if one process is halted or delayed in a critical section, other, nonfaulty processes will be unable to progress. by contrast, a concurrent object implementation is lock free if it always guarantees that some process will complete an operation in a finite number of steps, and it is wait free if it guarantees that each process will complete an operation in a finite number of steps. this paper proposes a new methodology for constructing lock-free and wait-free implementations of concurrent objects. the object's representation and operations are written as stylized sequential programs, with no explicit synchronization. each sequential operation is atutomatically transformed into a lock-free or wait-free operation using novel synchronization and memory management algorithms. these algorithms are presented for a multiple instruction/multiple data (mimd) architecture in which n processes communicate by applying atomic read, write, load_linked, and store_conditional operations to a shared memory.  maurice herlihy
kaleidoscope: mixing objects, constraints, and imperative programming  kaleidoscope is an object-oriented language being designed to integrate the traditional imperative object- oriented paradigm with the less traditional declarative constraint paradigm. imperative state changes provide sequencing while declarative constraints provide object relations. a variables as streams semantics enables the declarative-imperative integration. a running example is used to illustrate the language concepts---a reimplementation of the macdraw ii dashed-lines dialog box. the example is in three parts: the input channel, using imperative code to sequence through modes; the output channel, using constraints to update the display; and the internal relations, using constraints to maintain the data objects' consistency requirements. the last sections of the paper discuss views as a natural result of combining objects with constraints, as well as related and future work.  bjorn n. freeman-benson
a fully capable bidirectional debugger the goal of this research project is to develop a bidirectional program debugger with which one can move as easily backwards as current debuggers move forward. we believe this will be a vastly more useful debugger. a programmer will be able to start at the manifestation of a bug and proceed backwards investigating how the program arrived at the incorrect state, rather than the current and often tedious practice of the user stepping and breakpointing monotonically forward and then being forced to start over from the beginning if they skip past a point of interest.our experimental debugger has been implemented to work with c and c++ programs on digital/compaq alpha based unix workstations. bob boothe
an event trace monitor for the vax 11/780  this paper describes an event trace monitor implemented on version 1.6 of the vms operating system at purdue university. some necessary vms terminology is covered first. the operation of the data gathering mechanism is then explained, and the events currently being gathered are listed. a second program, which reduces the data gathered by the monitor to usable form, is next examined, and some examples depicting its operation are given. the paper concludes with a brief discussion of some of the monitor's uses.  stephen tolopka
inline function expansion for compiling c programs  inline function expansion replaces a function call with the function body. with automatic inline function expansion, programs can be constructed with many small functions to handle complexity and then rely on the compilation to eliminate most of the function calls. therefore, inline expansion serves a tool for satisfying two conflicting goals: minizing the complexity of the program development and minimizing the function call overhead of program execution. a simple inline expansion procedure is presented which uses profile information to address three critical issues: code expansion, stack expansion, and unavailable function bodies. experiments show that a large percentage of function calls/returns (about 59%) can be eliminated with a modest code expansion cost (about 17%) for twelve unix* programs.  p. p. chang w.-w. hwu
setl-a very high level language oriented to software systems prototyping  setl, like apl, is a language which facilitates manipulation of large relatively abstract data objects, namely sets, vectors, and maps, whose elements may in turn be sets, vectors, or maps. this language has been used to develop executable prototypes of several large software packages, including a full compiler for the new dod ada language. this talk will describe the man semantic features of setl, and assess its use as a software prototying tool.  jack schwartz
new challenges for fortran in the next millennium this paper discusses the economics of program optimisation and some of the challenges facing the parallel fortran community. industry takes a much broader view of cost optimisation than just speeding up a fortran application code. two examples of industrial "fortran" projects undertaken by the parallel applications centre (pac) at southampton are used to illustrate these industrial concerns. the promenvir project demonstrated cost-effective use of a europe-wide metacomputer, composed of idle workstations and parallel systems connected by a wan, to explore the design space of an industrial application. by contrast, the toolshed project was concerned with integration of the design and grid generation phase with the simulation phase of the industrial design cycle. the paper concludes with a discussion of three important challenges for the continued health of parallel fortran community. these are: the multiplicity of versions of parallel fortran; competition from high-level scientific packages such as axiom, matlab and mathematica; and finally, the inexorable rise in popularity of java-based, network-centric computing. tony hey
how to write an apl utility function in today's business climate, reusable code is essential. but many programmers often don't use existing utility functions because they find them difficult to use or not general enough. also, they may not know that such functions exist. instead, programmers often clone lines of code from other functions. this results in sloppy, undocumented code which is full of errors. in order to avoid this, the author of a utility function must make an extra effort to ensure that his function is designed properly.apl is easy to learn because its primitives behave consistently, work on arrays as well as scalars, can handle edge conditions, often use default values and are totally encapsulated from the user. we can learn from this by designing utility functions in the same way, allowing them to become an extension of apl and its set of primitives. this paper will show some examples and design techniques. stephen m. mansour
a fast method dispatcher for compiled languages with multiple inheritance  this paper addresses the problem of an efficient dispatch mechanism in an object-oriented system with multiple inheritance. the solution suggested is a direct table indexed branch such as is used in c++. the table slot assignments are made using a coloring algorithm. the method is applicable to strongly typed languages such as c++ (with multiple inheritance added) and eiffel, and in a slightly slower form to less strongly typed languages like objective c.  r. dixon t. mckee m. vaughan p. schweizer
an efficient relevant slicing method for debugging  dynamic program slicing methods are widely used for debugging, because many statements can be ignored in the process of localizing a bug. a dynamic program slice with respect to a variable contains only those statements that actually had an influence on this variable. however, during debugging we also need to identify those statements that actually did not affect the variable but could have affected it had they been evaluated differently. a relevant slice includes these potentially affecting statements as well, therefore it is appropriate for debugging. in this paper a forward algorithm is introduced for the computation of relevant slices of programs. the space requirement of this method does not depend on the number of different dynamic slices nor on the size of the execution history, hence it can be applied for real size applications.  tibor gyimothy arpad beszedes istan forgacs
airdisks and airraid (expanded extract): modeling and scheduling periodic wireless data broadcast a new generation of low-cost, low-power, and portable personal computer systems is emerging; sometimes these are referred to as palmtops or personal digital assistants (pdas). one of their key features is that they utilize wireless communication media, thus freeing the user from the constraints of wired or tethered communication. in fact, the wireless medium becomes a critical component of the i/o subsystem, allowing communication with fixed servers and other users. in particular, the broadcast nature of the wireless medium can be exploited to efficiently transmit information required by a large number of pda users (e.g. stock quotes, sports updates, etc.), with software on the pda being used to filter the information and present only the information of interest to the pda user.we introduce a simple model, called the airdisk, for modeling the access of data transmitted periodically over wireless media as being analogous to the access of data from a standard magnetic disk. we consider several issues related to airdisks, such as their mean rotational latency under certain assumptions. the problem of scheduling the order in which data items are broadcast is analogous to that of determining how data should be laid out on the disk. two problems of laying out data so as to minimize read time, given information about which data items are of most interest to the clients, are defined; both are shown to be np- complete. we discuss ways in which the information about which items are of interest to clients can be obtained. finally we consider how to increase the performance and storage capacity of airdisks, using the magnetic disk analogy as a guide. we suggest using multiple-track airdisks or borrowing the idea of redundant arrays of inexpensive disks (raid) which is used for magnetic disks; for the wireless data broadcast environment we call the latter approach airraid. ravi jain john werth
using the logos programming environment - a case history  logos is a unique programming environment for the apl language. it provides a uniform framework within which apl systems can be created and maintained. this paper describes how logos is used to manage and maintain a large, sharp apl- based information management system, viewpoint.  a brief overview of both logos and viewpoint is presented, and the steps taken to retrofit viewpoint into the logos environment are traced. emphasis is placed on the practical considerations and consequences of the conversion, and how the facilities of logos are used in practice. examples are given to demonstrate the effect logos had in changing the way problems relating to the organization and management of viewpoint were approached and solved. finally, the paper describes areas in which logos provided techniques to solve problems that might not otherwise have been addressed.  steve chapman
data locality enhancement by memory reduction  in this paper, we propose _memory reduction_ as a new approach to data locality enhancement. under this approach, we use the compiler to reduce the size of the data repeatedly referenced in a collection of nested loops. between their reuses, the data will more likely remain in higher-speed memory devices, such as the cache. specifically, we present an optimal algorithm to combine loop shifting, loop fusion and array contraction to reduce the temporary array storage required to execute a collection of loops. when applied to 20 benchmark programs, our technique reduces the memory requirement, counting both the data and the code, by 51% on average. the transformed programs gain a speedup of 1.40 on average, due to the reduced footprint and, consequently, the improved data locality.  yonghong song rong xu cheng wang zhiyuan li
implementing software configuration control in the structured programming environment  the fundamental problems in the control of software are explored. the elements of control as they relate to communications is defined, and the implementation of these elements in solving the fundamental problems and achieving optimal control during a software development life cycle, is explained.  control is defined as a vehicle for communicating changes to established, agreed-upon baseline points, made up of documents and subsequent computer programs. by communicating change to those involved or affected, and obtaining agreement of the change, one achieves a degree of control that does not inhibit software engineering innovation or progress, but helps maintain the project's prime objectives to deliver maintainable, error-free software to the ultimate user.  h. ronald berlack