waashk/acm huggingface dataset:
experiences with process programming  our research has investigated the feasibility and ramifications of process programming. we claim that it is highly advantageous to treat software processes, such as development and maintenance, as actual software which can be specified, designed, coded, executed, tested, and maintained. if software processes are to be coded and executed, it is necessary for them to be coded in a language which can then be compiled, loaded, and executed. likewise, if software processes are to specified and designed it is necessary to have process specification and design formalisms. we claim that process specification, design, and coding languages and formalisms will strongly resemble languages and formalisms currently used to specify software products, but that there will also be significant differences. we also claim that a properly conceived and developed software support environment can support the development of both product software and process software. we have engaged in considerable research to evaluate these claims.  our progress has been hampered by "research deadlock." languages and formalisms are required to effectively represent such objects as process designs and process code. that suggests that such languages and formalisms should be developed first. on the other hand, the creation of new programming languages, design formalisms, and specification technologies should begin only after significant experience in creating these software objects. that suggests that significant process software development should come first.  we broke this "research deadlock" by developing a variety of prototypes \---e. g. prototype process programs, prototype process coding languages, and a prototype process modelling formalism---and by evaluating each in the context of the others. this work has led to significant insights into the nature of process programming, the nature of various specific software processes, the difference between process programming and process modelling, the requirements for an effective process coding language, and the requirements for an effective process interpretation support system.  leon j. osterweil
a notation for manipulating arrays of operations  much has been written on the-possibility of incorporating arrays of functions and arrays of operators into apl. various methods have been proposed for creating and restructuring such arrays. this paper proposes the introduction of arrays of operations in general into apl2. vector notation is extended, as suggested by brown and benkard, to allow easy creation of vectors of operations. a new object, called an elevator, is introduced in order to create operations for manipulating arrays of operations. the semantics of the jot is extended, as per benkard, to provide a means of extracting structural information from operation arrays.  an analysis of the meaning behind the new notation is undertaken. definitions are given which not only satisfy the notational requirements but also provide insights into the nature of structural operations on function arrays. the information retained in an empty function array is explained, and the relationship between the primitive enclose function and the each operator becomes clear.  david j. landaeta
probabilistic data flow system with two-edge profiling  traditionally optimization is done statistically independent of actual execution environments. for generating highly optimized code, however, runtime information can be used to adapt a program to different environments. in probabilistic data flow systems runtime information on representative input data is exploited to compute the probability with what data flow facts may hold. probabilistic data flow analysis can guide sophisticated optimizing transformations resulting in better performance. in comparison classical data flow analysis does not take runtime information into account. all paths are equally weighted irrespectively whether they are never, heavily, or rarely executed.  in this paper we present the best solution what we can theoretically obtain for probabilistic data flow problems and compare it with the state-of-the-art one-edge approach. we show that the differences can be considerable and improvements are crucial. however, the theoretically best solution is too expensive in general and feasible approaches are required. in the sequel we develop an efficient approach which employs two-edge profiling and classical data flow analysis. we show that the results of the two-edge approach are significantly better than the state-of-the-art one-edge approach.  eduard mehofer bernhard scholz
memory occupancy patterns in garbage collection systems  some programming languages and computer systems use dynamic memory allocation with garbage collection. it would be useful to understand how the utilization of memory depends on the stochastic parameters describing the size and life distributions of the cells. we consider a class of dynamic storage allocation systems which use a first-fit strategy to allocate cells and perform noncompacting garbage collections to recover free memory space when memory becomes fully occupied. a formula is derived for the expected number of holes (available cells) in memory immediately following a garbage collection which specializes to an analogue of knuth's 'fifty percent' rule for nongarbage- collection systems. simulations confirm the rule for exponentially distributed cell lifetimes. other lifetime distributions are discussed. the memory-size requirements for noncompacting garbage collection are also analyzed.  d. julia. m. davies
automated test data generation for programs with procedures test data generation in program testing is the process of identifying a set of test data that satisfies a selected testing criterion, such as, statement coverage or branch coverage. the existing methods of test data generation are limited to unit testing and may not efficiently generate test data for programs with procedures. in this paper we present an approach for automated test data generation for programs with procedures. this approach builds on the current theory of execution-oriented test data generation. in this approach, test data are derived based on the actual execution of the program under test. for many programs, the execution of the selected statement may require prior execution of some other statements that may be part of some procedures. the existing methods use only control flow information of a program during the search process and may not efficiently generate test data for these types of programs because they are not able to identify statements that affect execution of the selected statement. our approach uses data dependence analysis to guide the process of test data generation. data dependence analysis automatically identifies statements (or procedures) that affect the execution of the selected statement and this information is used to guide the search process. the initial experiments have shown that this approach may improve the chances of finding test data. bogdan korel
fortran 90 pointers vs. "cray" pointers  the fortran 77 standard does not contain pointer facilities, but because of heavy user demand, many fortran 77 compilers have been extended with "cray" pointers. the demand for pointers in fortran was heard by the standards committee, x3j3, and a pointer facility was added to the follow-on fortran standard, fortran 90. x3j3, for reasons that may soon become apparent, chose not to follow existing practice and specify "cray" pointers, but to standardize a somewhat different pointer facility. fortran 90 pointers complement the fortran 90 language; they fit well with the new fortran 90 array processing and data facilities. the popularity of "cray" pointers indicates that they fit well with fortran 77, and since fortran 90 contains all of fortran 77, kit would be possible to extend fortran 90 processors to accept "cray" pointers as well. this would make it easier for existing codes that use pointers to migrate to new fortran 90 processors. but is it a good idea for a processor to provide two pointer facilities? how difficult is it to convert from "cray" pointers to fortran 90 pointers? this paper provides some information that may be helpful in answering these questions.  jeanne martin
comparison checking: an approach to avoid debugging of optimized code  we present a novel approach to avoid the debugging of optimized code through comparison checking. in the technique presented, both the unoptimized and optimized versions of an application program are executed, and computed values are compared to ensure the behaviors of the two versions are the same under the given input. if the values are different, the comparison checker displays where in the application program the differences occurred and what optimizations were involved. the user can utilize this information and a conventional debugger to determine if an error is in the unoptimized code. if the error is in the optimized code, the user can turn off those offending optimizations and leave the other optimizations in place. we implemented our comparison checking scheme, which executes the unoptimized and optimized versions of c programs, and ran experiments that demonstrate the approach is effective and practical.  clara jaramillo rajiv gupta mary lou soffa
debugging heterogeneous distributed systems using event-based models of behavior  event based behavioral abstraction (ebba) is a high-level debugging approach which treats debugging as a process of creating models of actual behavior from the activity of the system and comparing these to models of expected system behavior. the differences between the actual and expected models are used to characterize erroneous system behavior and direct further investigation.  a set of ebba-based tools has been implemented that users can employ to construct libraries of behavior models and investigate the behavior of an errorful system through these models. ebba evolves naturally as a cooperative distributed program that can take better advantage of computational power available in a network computer system to enhance debugging tool transparency, reduce latency and uncertainty for fundamental debugging activities and accommodate diverse, heterogeneous architectures.  peter bates
operator strength reduction operator strength reduction is a technique that improves compiler-generated code by reformulating certain costly computations in terms of less expensive ones. a common case arises in array addressing expressions used in loops. the compiler can replace the sequence of multiplies generated by a direct translation of the address expression with an equivalent sequence of additions. when combined with linear function test replacement, strength reduction can speed up the execution of loops containing array references. the improvement comes from two sources: a reduction in the number of operations needed to implement the loop and the use of less costly operations.this paper presents a new algorithm for operator strength reduction, called osr. osr improves upon an earlier algorithm of allen, cocke, and kennedy [allen et al. 1981]. osr operates on the static single assignment (ssa) form of a procedure [cytron et al. 1991]. by taking advantage of the properties of ssa form, we have derived an algorithm that is simple to understand, quick to implement, and, in practice, fast to run. its asymptotic complexity is, in the worst case, the same as the allen, cocke,and kennedy algorithm (ack). osr achieves optimization results that are equivalent to those obtained with the ack algorithm. osr has been implemented in several research and production compilers. keith d. cooper l. taylor simpson christopher a. vick
a file system supporting cooperation between programs  file systems coordinate simultaneous access of files by concurrent client processes. although several processes may read a file simultaneously, the file system must grant exclusive access to one process wanting to write the file. most file systems consider processes to be antagonistic: they prevent one process from taking actions on a file that have any chance to harm to another process already using the file. if several processes need to cooperate in a more sophisticated manner in their use of a file, they must communicate explicitly among themselves.  the next three sections describe the file system procedures used by clients for using and sharing files. section two discusses how a client gains access to a file and how a client can respond if the file system asks it to give up a file it is using. section three discusses the mechanism by which a client might ask to be notified that a file is available for some access. section four discusses a controlled type of file access that lets clients read and write the same file at the same time.  section five comprises three examples of the cooperative features of the file system taken from the xerox development environment. section six discusses the subtleties of writing the call-back procedures that clients provide to the file system to implement interprocess cooperation. section seven discusses the implementation of this file system.  loretta guarino reid philip l. karlton
l-one-two-three (l1:..l2:..l3:) considered harmful it is said by non-apl- programmers that apl code is hard to read and that it is unstructured. here we argue that apl-programmers may refute this assertion by pointing out some misunderstandings, but admittedly a final analysis will show a deeper truth in these criticisms. we will show that apl gives ample opportunity for unstructured code. two proposals are presented to address this problem.the first rejects the developed convention for labelling and suggests the adoption of a proper style of programming enforced by a new standard of labelling. this standard will abolish unstructured code. both negative and positive aspects of this proposal are discussed.the second proposal revives an old idea of introducing one single proper control structure into the language. this would make the current jump ( ) superfluous and enforce structured code. f. h. d. van batenburg
atom: a system for building customized program analysis tools  atom (analysis tools with om) is a single framework for building a wide range of customized program analysis tools. it provides the common infrastructure present in all code-instrumenting tools; this is the difficult and time- consuming part. the user simply defines the tool-specific details in instrumentation and analysis routines. building a basic block counting tool like pixie with atom requires only a page of code.  atom, using om link-time technology, organizes the final executable such that the application program and user's analysis routines run in the same address space. information is directly passed from the application program to the analysis routines through simple procedure calls instead of inter-process communication or files on disk. atom takes care that analysis routines do not interfere with the program's execution, and precise information about the program is presented to the analysis routines at all times. atom uses no simulation or interpretation.  atom has been implemented on the alpha axp under osf/1. it is efficient and has been used to build a diverse set of tools for basic block counting, profiling, dynamic memory recording, instruction and data cache simulation, pipeline simulation, evaluating branch prediction, and instruction scheduling.  amitabh srivastava alan eustace
storage management in a prolog compiler  with the current intense interest in new computing paradigms based on logic, the efficient implementation of prolog has become an issue of prime importance. compiling prolog involves some unique and difficult problems relating to storage management: in particular, the somewhat conflicting requirements of backtracking, and cut and tail recursion processing. the usual solution is to use garbage collection, an expensive process in small computers with limited storage. we describe a prolog compiler which maintains the heap as lists of free records, to which records are released at the time they are deallocated, thus avoiding garbage collection. in this compiler, variable bindings are recorded in such a way that the speed of unification does not depend on the length of chains of bound variables. also, tail recursion optimisation is more thorough than in other implementations.  y-l. chang p. t. cox
debugging of heterogeneous parallel systems  the agora system supports the development of heterogeneous parallel programs, e.g. programs written in multiple languages and running on heterogeneous machines. agora has been used since september 1986 in a large distributed system [1]: two versions of the application have been demonstrated in one year, contrary to the expectation of two years per one version. the simplicity in debugging is one of the reasons of the productivity speedup gained. this simplicity is due both to the deeper understanding that the debugger has of parallel systems, and to a novel feature: the ability to replay the execution of parallel systems built with agora. a user is able to exactly repeat for any number of times and at a slower pace an execution that failed. this makes it easy to identify time-dependent errors, which are peculiar to parallel and distributed systems. the debugger can also be customized to support user defined synchronization primitives, which are built on top of the system provided ones. the agora debugger tackles three set of problems that no parallel debugger in the past has simultaneously addressed: dealing with programming-in-the-large, multiple processes in different languages, and multiple machine architectures.  alessandro forin
improving the cache locality of memory allocation  the allocation and disposal of memory is a ubiquitous operation in most programs. rarely do programmers concern themselves with details of memory allocators; most assume that memory allocators provided by the system perform well. this paper presents a performance evaluation of the reference locality of dynamic storage allocation algorithms based on trace-driven simualtion of five large allocation-intensive c programs. in this paper, we show how the design of a memory allocator can significantly affect the reference locality for various applications. our measurements show that poor locality in sequential-fit allocation algorithms reduces program performance, both by increasing paging and cache miss rates. while increased paging can be debilitating on any architecture, cache misses rates are also important for modern computer architectures. we show that algorithms attempting to be space- efficient by coalescing adjacent free objects show poor reference locality, possibly negating the benefits of space efficiency. at the other extreme, algorithms can expend considerable effort to increase reference locality yet gain little in total execution performance. our measurements suggest an allocator design that is both very fast and has good locality of reference.  dirk grunwald benjamin zorn robert henderson
creating efficient systems for object-oriented languages  increasingly computer science research has been done using workstations with high- resolution bitmap display systems. smalltalk-80 is a very attractive programming language for such computation environments, since it has very sophisticated graphical systems and programming environments. unfortunately there are still very few computer systems on which smalltalk-80 can run with satisfactory speed, and furthermore they are quite expensive. in order to make smalltalk-80 accessible to a large group of people at low cost,. we have developed compiler techniques useful to generate efficient code for standard register machines such as mc68000. we have also extended smalltalk-80 to include type expressions, which allow compilers to generate efficient code  norihisa suzuki minoru terada
on executable models for rule-based prototyping  this paper proposes a particular style of executable specifications as a method for rapid prototyping. using a general state-transition framework, system behavior is specified by pattern-oriented rules containing pre- and post-conditions for each transition. the specification method is introduced by two small examples in which a finite-state machine and database are modeled. the main example is an executable model of a backtracking prolog interpreter, which is specified using five transition rules adapted from the formal- semantic literature. all models in the paper are executable and written in prolog; minimal familiarity with prolog is assumed.  stanley lee
the nyu ada translator and interpreter  the nyu-ada project is engaged in the design and implementation of a translator-interpreter for the ada language. the objectives of this project are twofold: a) to provide an executable semantic model for the full ada language, that can be used for teaching, and serve as a starting point for the design of an efficient ada compiler; b) to serve as a testing ground for the software methodology that has emerged from our experience with the very-high level language setl. in accordance with these objectives, the nyu-ada system is written in a particularly high-level, abstract setl style that emphasizes clarity of design and user interface over speed and efficiency. a number of unusual design features of the translator and interpreter follow from this emphasis. some of these features are described below. we also discuss the question of semantic specification of programming languages, and the general methodology of "software prototyping" of which the nyu-ada system is a sizeable example.  robert b. k. dewar gerald a. fisher edmond schonberg robert froehlich stephen bryant clinton f. goss michael burke
controlling garbage collection and heap growth to reduce the execution time of java applications in systems that support garbage collection, a tension exists between collecting garbage too frequently and not collecting garbage frequently enough. garbage collection that occurs too frequently may introduce unnecessary overheads at the rist of not collecting much garbage during each cycle. on the other hand, collecting garbage too infrequently can result in applications that execute with a large amount of virtual memory (i.e., with a large footprint) and suffer from increased execution times die to paging. in this paper, we use a large colleciton of java applications and the highly tuned and widely used boehm-demers-weiser (bdw) conservative mark-and-sweep garbage collector to experimentally examine the extent to which the frequency of garbage collectio impacts an application's execution time, footprint, and pause times. we use these results to devise some guidelines for controlling garbage and heap growth in a conservative garbage collection in order to minimize application execution times. then we describe new strategies for controlling in order to minimize application execution times. tim brecht eshrat arjomandi chang li hang pham
precise executable interprocedural slices  the notion of a program slice, originally introduced by mark weiser, is useful in program debugging, automatic parallelization, program integration, and software maintenance. a slice of a program is taken with respect to a program point p and a variable x; the slice consists of all statements of the program that might affect the value of x at point p. an interprocedural slice is a slice of an entire program, where the slice crosses the boundaries of procedure calls.  weiser's original interprocedural-slicing algorithm produces imprecise slices that are executable programs. a recent algorithm developed by horwitz, reps, and binkley produces more precise (smaller) slices by more accurately identifying those statements that might affect the values of x at point p. these slices, however, are not executable. an extension to their algorithm that produces more precise executable interprocedural slices is described together with a proof of correctness for the new algorithm.  david binkley