waashk/acm huggingface dataset:
a generic account of continuation-passing styles  we unify previous work on the continuation-passing style (cps) transformations in a generic framework based on moggi's computational meta-language. this framework is used to obtain cps transformations for a variety of evaluation strategies and to characterize the corresponding administrative reductions and inverse transformations. we establish generic formal connections between operational semantics and equational theories. formal properties of transformations for specific evaluation orders follow as corollaries.  essentially, we factor transformations through moggi's computational meta- language. mapping λ-terms into the meta- language captures computation properties (e.g., partiality, strictness) and evaluation order explicitly in both the term and the type structure of the meta-language. the cps transformation is then obtained by applying a generic transformation from terms and types in the meta-language to cps terms and types, based on a typed term representation of the continuation monad. we prove an adequacy property for the generic transformation and establish an equational correspondence between the meta-language and cps terms.  these generic results generalize plotkin's seminal theorems, subsume more recent results, and enable new uses of cps transformations and their inverses. we discuss how to aply these results to compilation.  john hatcliff olivier danvy
a practical and flexible flow analysis for higher-order languages  a flow analysis collects data-flow and control-flow information about programs. a compiler can use this information to enable optimizations. the analysis described in this article unifies and extends previous work on flow analysis for higher-order languages supporting assignment and control operators. the analysis is abstract interpretation based and is parameterized over two polyvariance operators and a projection operator. these operators are used to regulate the speed and accuracy of the analysis. an implementation of the analysis is incorporated into and used in a production scheme compiler. the analysis can process any legal scheme program without modification. others have demonstrated that a 0cfa analysis can enables the optimizations, but a 0cfa analysis is o(n )3). an o(n) instantiation of our analysis successfully enables the optimization of closure representations and procedure calls. experiments with the cheaper instantiation show that it is as effective as 0cfa for these optimizations.  j. michael ashley r. kent dybvig
experience with the automatic temporal analysis of multitasking ada designs  in this paper, we report on experience gained in the temporal analysis of multitasking ada designs. the analysis tool-set, developed as part of the caede project, includes an operational specification language, and deadlock, starvation and critical race analyzers. we identify design parameters that lead to costly analysis, and then describe analysis heuristics that can lead to less costly analysis. several design examples in which we apply our heuristics, are described. in one of the examples, a 50-fold reduction in analysis cost was obtained with the application of one of the heuristics. finally, we make recommendations for design environment features that would support the application of analysis heuristics.  gerald m. karam raymond j. a. buhr
research on synthesis of concurrent computing systems (extended abstract)  the object of our research is the codification of programming knowledge for the synthesis of concurrent programs. we present sample rules and techniques that we show can be used to derive two concurrent algorithms: dynamic programming (for the class of problems that run in polynomial time on sequential machines) and array multiplication. for both derived concurrent versions the code runs in linear time. the concurrent versions are significant and complex algorithms, though they are not new and already have been reported in the literature. the synthesis knowledge for these derivations is embodied in seven synthesis rules. we expect these rules to generalize to other classes of algorithms.  we have also discovered a pair of techniques called virtualization and aggregation. this pair of techniques (plus the seven rules) is shown to be powerful enough to synthesize kung's systolic array architecture [kung-76] from a specification of matrix multiplication.  richard m. king
the structure and performance of interpreters interpreted languages have become increasingly popular due to demands for rapid program development, ease of use, portability, and safety. beyond the general impression that they are "slow," however, little has been documented about the performance of interpreters as a class of applications.this paper examines interpreter performance by measuring and analyzing interpreters from both software and hardware perspectives. as examples, we measure the mipsi, java, perl, and tcl interpreters running an array of micro and macro benchmarks on a dec alpha platform. our measurements of these interpreters relate performance to the complexity of the interpreter's virtual machine and demonstrate that native runtime libraries can play a key role in providing good performance. from an architectural perspective, we show that interpreter performance is primarily a function of the interpreter itself and is relatively _independent_ of the application being interpreted. we also demonstrate that high-level interpreters' demands on processor resources are comparable to those of other complex compiled programs, such as gcc. we conclude that interpreters, as a class of applications, do not currently motivate special hardware support for increased performance. theodore h. romer dennis lee geoffrey m. voelker alec wolman wayne a. wong jean-loup baer brian n. bershad henry m. levy
phoenix: a low-power fault-tolerant real-time network-attached storage device  phoenix is a real-time network-attached storage device (nasd) that guarantees real-time data delivery to network clients even across single disk failure. the service interfaces that phoenix provides are best-effort/real- time reads/writes based on unique object identifiers and block offsets. data retrieval from phoenix can be serviced in server push or client pull modes. phoenix's real-time disk subsystem performance results from a standard cycle- based scan-order disk scheduling mechanism. however, the disk i/o cycle of phoenix is either completely active or completely idle. this on-off disk scheduling model effectively reduces the power consumption of the disk subsystem, without increasing the buffer size requirement. phoenix also exploits unused disk storage space and maintains additional redundancy beyond the generic raid5-style parity. this extra redundancy, typically in the form of block replication, reduces the time to reconstruct the data on the failed disk. this paper describes the design, implementation, and evaluation of phoenix, one of the first, if not the first, nasds that support fault- tolerant, real-time, and low-power network storage service.  anindya neogi ashish raniwala tzi-cker chiueh
application and experimental evaluation of state space reduction methods for deadlock analysis in ada  an emerging challenge for software engineering is the development of the methods and tools to aid design and analysis of concurrent and distributed software. over the past few years, a number of analysis methods that focus on ada tasking have been developed. many of these methods are based on some form of reachability analysis, which has the advantage of being conceptually simple, but the disadvantage of being computationally expensive. we explore the effectiveness of various petri net- based techniques for the automated deadlock analysis of ada programs. our experiments consider a variety of state space reduction methods both individually and in various combinations. the experiments are applied to a number of classical concurrent programs as well as a set of "real- world" programs. the results indicate that petri net reduction and reduced state space generation are mutually beneficial techniques, and that combined approaches based on petri net models are quite effective, compared to alternative analysis approaches.  s. duri u. buy r. devarapalli s. m. shatz
an object addressing mechanism for statically typed languages with multiple inheritance  in this paper we are concerned with addressing techniques for statically typed languages with multiple inheritance. the addressing techniques are responsible for the efficient implementation of record field selection. in object-oriented languages, this record selection is equivalent to the access of methods. thus, the efficiency of these techniques greatly affects the overall performance of an object-oriented language. we will demonstrate that addresses, in such systems, cannot always be calculated statically and show how symbol tables have been used as address maps at run time. the essence of the paper is a new addressing technique that can statically calculate either the address of a field or the address of the address of the field. this technique is powerful enough to support an efficient implementation of multiple inheritance with implicit subtyping as described by cardelli.  r. c. h. conner a. dearle r. morrison a. l. brown
efficient approximation for models of multiprogramming with shared domains  queueing network models of multiprogramming systems with memory constraints and multiple classes of jobs are important in representing large commercial computer systems. typically, an exact analytical solution of such models is unavailable, and, given the size of their state space, the solution of models of this type is approached through simulation and/or approximation techniques. recently, a computationally efficient iterative technique has been proposed by brandwajn, lazowska and zahorjan for models of systems in which each job is subject to a separate memory constraint, i.e., has its own memory domain. in some important applications, it is not unusual, however, to have several jobs of different classes share a single memory "domain" (e.g., ibm's information management system). we present a simple approximate solution to the shared domain problem. the approach is inspired by the recently proposed technique which is complemented by a few approximations to preserve the conceptual simplicity and computational efficiency of this technique. the accuracy of the results is generally in fair agreement with simulation.  alexandre brandwajn william m. mccormack
acorn: apl to c on real numbers  a prototype apl to c compiler (acorn: apl to c on real numbers) was produced while investigating improved tools for solving numerically intensive problems on supercomputers. acorn currently produces code which runs slower than hand- coded cray fortran, but we have identified the major performance bottlenecks, and believe we know how to remove them. although created in a short time on a limited budget, and intended only as a proof of the feasibility of compiling apl for numerically intensive environments, acorn has shown that straightforward compiled apl will be able to compete with hand-optimized fortran in many common supercomputer applications.  robert bernecky charles brenner stephen b. jaffe george p. moeckel
manageability, availability and performance in porcupine: a highly scalable, cluster-based mail service this paper describes the motivation, design, and performance of porcupine, a scalable mail server. the goal of porcupine is to provide a highly available and scalable electronic mail service using a large cluster of commodity pcs. we designed porcupine to be easy to manage by emphasizing dynamic load balancing, automatic configuration, and graceful degradation in the presence of failures. key to the system's manageability, availability, and performance is that sessions, data, and underlying services are distributed homogeneously and dynamically across nodes in a cluster. yasushi saito brian n. bershad henry m. levy
a module mechanism for constraints in smalltalk  thinglab ii, a rewrite of thinglab, provides two representations of objects: fully-exposed and interpreted things, or hidden and compiled modules. both representations provide the full power of the thinglab ii constraint hierarchy (an ordering of constraint preferences), and both can be manipulated by the graphical user- interface. this paper briefly describes modules and their environmental support in thinglab ii. it also describes the process by which the modulecompiler translates a collection of objects (a thinglab ii thing) into a single object with compiled and optimized smalltalk-80 methods (a module).  b. n. freeman-benson
integrating segmentation and paging protection for safe, efficient and transparent software extensions the trend towards extensible software architectures and component-based software development demands safe, efficient, and easy-to-use extension mechanisms to enforce protection boundaries among software modules residing in the same address space. this paper describes the design, implementation, and evaluation of a novel intra- address space protection mechanism called _palladium,_ which exploits the segmentation and paging hardware in the intel x86 architecture and efficiently supports safe kernel-level and user-level extensions in a way that is largely transparent to programmers and existing programming tools. based on the considerations on ease of extension programming and systems implementation complexity, _palladium_ uses different approaches to support user-level and kernel-level extension mechanisms. to demonstrate the effectiveness of the _palladium_ architecture, we built a web server that exploits the user-level extension mechanism to invoke cgi scripts as local function calls in a safe way, and we constructed a compiled network packet filter that exploits the kernel-level extension mechanism to run packet-filtering binaries safely inside the kernel at native speed. the current _palladium_ prototype implementation demonstrates that a protected procedure call and return costs 142 cpu cycles on a pentium 200mhz machine running linux. tzi-cker chiueh ganesh venkitachalam prashant pradhan
the solution of separable queueing network models using mean value analysis  because it is more intuitively understandable than the previously existing convolution algorithms, mean value analysis (mva) has gained great popularity as an exact solution technique for separable queueing networks. however, the derivations of mva presented to date apply only to closed queueing network models. additionally, the problem of the storage requirement of mva has not been dealt with satisfactorily. in this paper we address both these problems, presenting mva solutions for open and mixed load independent networks, and a storage maintenance technique that we postulate is the minimum possible of any "reasonable" mva technique.  john zahorjan eugene wong
managing apl public code for an in-house apl system (before and after logos)  this paper will present apl public library management concepts used in a large in-house apl system development environment and describe a number of tools developed for this purpose. public libraries, workspaces, functions and variables are discussed as well as documentation, reporting of changes, audit records, backup versions, and test versions. user tools discussed include functions for describing apl public files, libraries, workspaces, functions and variables, locating these objects, keyword searches, and a glossary of terms. other user facilities include a news system and an online system for submitting problem reports and requests for enhancements. further maintenance tools include automatic generation of wsdoc listings when changes are made and automatically generated reports providing a variety of information such as libraries or workspaces lacking descriptions, lists of apl public workspaces and files with their status, function source verification, and exception reporting of workspace changes.  a discussion of logos, a programming environment for apl offered by ip sharp associates, is also presented and how it enhances the capabilities previously described.  d. f. stoneburner
efficient call graph analysis  we present an efficient algorithm for computing the procedure call graph, the program representation underlying most interprocedural optimization techniques. the algorithm computes the possible bindings of procedure variables in languages where such variables only receive their values through parameter passing, such as fortran. we extend the algorithm to accommodate a limited form of assignments to procedure variables. the resulting algorithm can also be used in analysis of functional programs that have been converted to continuation-passing-style.  we discuss the algorithm in relationship to other call graph analysis approaches. many less efficient techniques produce essentially the same call graph. a few algorithms are more precise, but they may be prohibitively expensive depending on language features.  mary w. hall ken kennedy
deadlock control with ada95 the ada programming language is unique in its high-level concurrency facilities, supported by a secure and powerful set of programming constructs. ada 95 now has additional capabilities, specifically the protected type construct.although the ada rendezvous is prone to deadlock, a careful discipline can ensure that this type of dead state does not occur. restricting task communication assists in preventing deadlock, yet such restrictions may be too limiting and/or too inefficient for an application. indeed, several researchers have suggested that deadlock should not be prevented, but monitored and corrected during testing and/or run time.this paper takes the position that deadlock should be prevented by following specific guidelines in the use of the rendezvous. we define deadlock, show how it can occur with ada tasks, and outline mechanisms that are appropriate for its control. trudy levine
general strategies for dynamic reconfiguration in recent years there has been a great deal of attention in the software engineering community on the development of techniques and tools that provide support for _dynamic reconfiguration,_ the ability to make changes to a running application. the changes of interest include 1) adding/removing/moving components; 2) adding/removing bindings (communication channels); 3) changing the characteristics of the components or bindings. my work in this area has focused both on software support for dynamic reconfiguration of parallel applications and on frameworks and static software analysis techniques for determining the validity of component-level adaptations in the context of dynamic reconfiguration. elizabeth l. white
extensible file system (elfs): an object-oriented approach to high performance file i/o  scientific applications often manipulate very large sets of persistent data. over the past decade, advances in disk storage device performance have consistently been outpaced by advances in the performance of the rest of the computer system. as a result, many scientific applications have become i/o-bound, i.e. their run-times are dominated by the time spent performing i/o operations. consequently, the performance of i/o operations has become critical for high performance in these applications. the elfs approach is designed to address the issue of high performance i/o by treating files as typed objects. typed file objects can exploit knowledge about the file structure and type of data. typed file objects can selectively apply techniques such as prefetching, parallel asynchronous file access, and caching to improve performance. also, by typing objects, the interface to the user can be improved in two ways. first, the interface can be made easier to use by presenting file operations in a more natural manner to the user. second, the interface can allow the user to provide an "oracle" about access patterns, that can allow the file object to improve performance. by combining these concepts with the object-oriented paradigm, the goal of the elfs methodology is to create flexible, extensible file classes that are easy to use while achieving high performance. in this paper we present the elfs approach and our experiences with the design and implementation of two file classes: a two dimensional dense matrix file class and a multidimensional range searching file class.  john f. karpovich andrew s. grimshaw james c. french
documenting the software development process  the software engineering process group (sepg) at the data systems division of litton systems, inc., was given the task of documenting the software development process used within the division. this paper describes how the sepg at litton accomplished this task. it discusses the sources we used for guidance and describes the resulting documentation for defining the software development process and the methods and tools that support the process.  after reviewing the existing software process documentation at litton, the sepg concluded that three separate documents were required: a revised set of software policies and procedures (ppgs), a software engineering handbook, and a software management handbook. the sepg established working groups to develop these documents. the working group responsible for the software engineering handbook decided to develop it as a user manual for the software development process. following weiss' guidelines for developing a usable user manual, the working group developed storyboards for sections of the manual. a model initially developed at ibm and refined by sei and others was used to describe the software development process as a series of work tasks, each of which has entry criteria, exit criteria, objectives, and steps to perform.  several authors developed the storyboards and the corresponding modules of the handbook. the handbook was partitioned into short modules, each of which has a topic sentence and a figure (where applicable). the result is a modular software engineering handbook that is easy to read and maintain.  the use of working groups and the development of the software engineering handbook as a user manual proved to be efficient and effective methods for generating high quality software process documentation.  june s. hopkins jean m. jernow
operations for programming in the all  a primary goal of software engineering is to improve the process of software development. it is being recognised that recent integrated programming environments have made significant progress towards this aim. this paper describes new operations, suitable for such environments, which are applicable in a much wider scope of programming, termed here as programming in the all. development of software in this new scope is carried out incrementally in program fragments of various types, called fragtypes. fragtypes range from a simple expression type to a complete subsystem type, and therefore are suited to the development of non- trivial software. the proposed operations on fragtypes have been incorporated in the design of the programming environment mupe-2 for modula-2, which is currently under development at mcgill university.  nazim h. madhavji
an approach to software configuration control  the purpose of this paper is to discuss the process by which a system's life cycle and its associated life cycle products are managed to ensure the quality and integrity of the system. we call this process configuration control. although many of the ideas in this paper are applicable to systems in general, the focus of this paper is on configuration control of systems with software content.  it is becoming apparent to many, in both government and private industry, that the high cost of maintenance of existing computer systems may be attributed to poor configuration control early in the system's life cycle. for example, in an article entitled "a corporate road, map for systems development in the '80s, the following claim appears,  william bryan stanley siegel gary whiteleather