waashk/acm huggingface dataset:
garbage collection of actors  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.  dennis kafura doug washabaugh jeff nelson
optimization with dynamic functions many optimization methods are iterative in nature and require users to specify constraints and objectives. the normal way to handle this type of problem would be to create a loop with an execute statement inside the body of the loop. the loop is necessary because of the iterative nature of the algorithm and the execute statement is necessary because the objective function is user-defined."execute" can be costly inside a loop. while there are existing ways to remove "execute" from the loop, they are awkward. however, dynamic functions can be built ahead of time and called inside the loop. defined operators allow an arbitrary optimization function to be passed to the looping function.the method of simulated annealing can deal with large-scale optimization problems without getting trapped in local minima. constraints can be treated as objectives with a high penalty for violations. hence we can eliminate constraints and deal only with objectives. a series of objectives is combined into a single objective function. since the objectives are defined by the user, a dynamic function is created. the goal is to reduce the result of the dynamic function to zero (negative values are not permitted). the function is called iteratively until a specific tolerance is reached.this paper will use an example from the mortgage industry to demonstrate the use of dynamic functions in iterative optimization methods. stephen m. mansour
recplay: a fully integrated practical record/replay system  this article presents a practical solution for the cyclic debugging of nondeterministic parallel programs. the solution consists of a combination of record/replay with automatic on-the-fly data race detection. this combination enables us to limit the record phase to the more efficient recording of the synchronization operations, while deferring the time-consuming data race detection to the replay phase. as the record phase is highly efficient, there is no need to switch it off, hereby eliminating the possibility of heisenbugs because tracing can be left on all the time. this article describes an implementation of the tools needed to support recplay.  michiel ronsse koen de bosschere
a workbench for quality based software re-engineering (poster)  this research presents a re-engineering workbench and architecture that allows for legacy systems written in procedural languages to be migrated to new object oriented platforms. this methodology allows for specific design and quality requirements of the target migrant system to be considered during the re- engineering process through an iterative and incremental process. the migration process recovers an object model from the procedural code and incrementally refines it by taking into consideration the design requirements for the migrant system. a case study is presented as a proof of concept.  ladan tahvildari kostas kontogiannis
the implementation of procedurally reflective languages  in a procedurally reflective programming language, all programs are executed not through the agency of a primitive and inaccessible interpreter, but rather by the explicit running of a program that represents that interpreter. in the corresponding virtual machine, therefore, there are an infinite number of levels at which programs are processed, all simultaneously active. it is therefore a substantial question to show whether, and why, a reflective language is computationally tractable. we answer this question by showing how to produce an efficient implementation of a procedurally reflective language, based on the notion of a level-shifting processor. a series of general techniques, which should be applicable to reflective variants of any standard applicative or imperative programming languages, are illustrated in a complete implementation for a particular reflective lisp dialect called 3-lisp.  jim des rivières brian cantwell smith
mimimal threshold separators and memory requirements for synchronization (abstract only)  a graph g is threshold if each vertex has an integer label and a set of vertices induces no edges if the sum of its labels does not exceed a separator t. if each vertex of g is a process and edges connect processes that cannot run simultaneously, a single shared variable with range 0 to t will implement mutual exclusion using pv-chunk operators. here we obtain a strong converse: even using test-and-set operators, a single shared variable implementing mutual exclusion needs at least t+1 values. the proof depends on finding a closed form for the minimum possible t in terms of the (easily computed) number of cliques of given size of g.  edward t. ordman
support for change in rpde3  rpde3 is a framework for building environments. great emphasis has been placed on supporting changes of various kinds, such as extensions to existing environments and creation of new environments by adapting existing environments. we have a three-pronged approach to supporting change: (1) use of a central framework providing key services is a uniform fashion, (2) an extended object-oriented programming paradigm supporting fine-grained changes by addition of small code fragments, and (3) structured representation of program material facilitating sophisticated language-sensitive processing. rpde3 has been used on a daily basis for its own development for about three years now, and during that time has undergone extensive change. this experience has indicated strongly that our approach to supporting change is effective, and has identified extensions to it that should make it more effective still. this paper describes the approach and, primarily, our experience.  harold ossher william harrison
predicting the cost-effectiveness of regression testing strategies selective regression testing strategies aim at choosing an appropriate subset of test cases from among a previously run test suite for a software system, based on information about the changes made to the system to create new versions. although there has been a significant amount of research in recent years on the design of such strategies, there has been significantly less investigation of their cost-effectiveness. in this paper some computationally efficient predictors of the cost-effectiveness of the two main classes of selective regression testing approaches are presented. a case study is described in which these predictors are used to assess the appropriateness of using a particular regression testing strategy to test multiple versions of a widely- used software system. david s. rosenblum elaine j. weyuker
synergy between component-based and generative approaches  building software systems out of pre-fabricated components is a very attractive vision. distributed component platforms (dcp) and their visual development environments bring this vision closer to reality than ever. at the same time, some experiences with component libraries warn us about potential problems that arise in case of software system families or systems that evolve over many years of changes. indeed, implementation level components, when affected by many independent changes, tend to grow in both size and number, impeding reuse. in this paper, we analyze in detail this effect and propose a program construction environment, based on generative techniques, to help in customization and evolution of component-based systems. this solution allows us to reap benefits of dcps during runtime and, at the same time, keep components under control during system construction and evolution. in the paper, we describe such a construction environment for component-based systems that we built with a commercial generator and illustrate its features with examples from our domain engineering project. the main lesson learnt from our project is that generative techniques can extend the strengths of the component-based approach in two important ways: firstly, generative techniques automate routine component customization and composition tasks and allow developers work more productively, at a higher abstraction level. secondly, as custom components with required properties are generated on demand, we do not need to store and manage multiple versions of components, components do not overly grow in size, helping developers keep the complexity of an evolving system under control.  stan jarzabek peter knauber
a knowledge-based method for inferring semantic concepts from visual models of system behavior  software designers use visual models, such as data flow/control flow diagrams or object collaboration diagrams, to express system behavior in a form that can be understood easily by users and by pogrammers, and from which designers can generate a software architecture. the research described in this paper is motivated by a desire to provide an automated designer's assistant that can generate software architectures for concurrent systems directly from behavioral models expressed visually as flow diagrams. to achieve this goal, an automated designer's assistant must be capable of interpreting flow diagrams in semantic, rather than syntactic, terms. while semantic concepts can be attached manually to diagrams using labels, such as stereotypes in the unified model language (uml), this paper considers the possibility of providing autmated assistance to infer appropriate tags for symbols on a flow diagram. the approach relies upon constructing an underlying metamodel that defines semantic concepts based upon (1) syntactic relationships among visual symbols and (2) inheritance relationships among semantic concepts. given such a metamodel, a rule-based inference engine can, in many situations, infer the presence of semantic concepts on flow diagram, and can tag symbols accordingly. futher, an object-oriented query system can compare semantic tags on digram instances for conformance with their definition in the metamodel. to illustrate the approach, the paper describes a metamodel for data flow/control flow diagrams used in the context of a specific software modeling method, concurrent object-based real-time analysis (cobra). the metamodel is implemented using an expert-system shell, clips v6.0, which integrates an object-oriented language with a rule-based inference engine.  the paper applies the implemented metamodel to design software for an automobile cruise-control system and provides an evaluation of the approach based upon results from four case studies. for the case studies, the implemented metamodel recognized, automatically and correctly, the existence of 86% of all cobra semantic concepts within the flow diagrams. varying degrees of human assistance were used to correctly identify the remaining semantic concepts within the diagrams: in two percent of the cases the implemented metamodel reached tentative classifications that a designer was asked to confirm or override; in four percent of the cases a designer was asked to provide additional information before a concept was classified; in the remaining eight percent of the cases the designer was asked to identify the concept.  kevin l. mills hassan gomaa
a mechanism for efficient debugging of parallel programs  this paper addresses the design and implementation of an integrated debugging system for parallel programs running on shared memory multi-processors (smmp). we describe the use of flowback analysis to provide information on causal relationships between events in a program's execution without re-executing the program for debugging. we introduce a mechanism called incremental tracing that, by using semantic analyses of the debugged program, makes the flowback analysis practical with only a small amount of trace generated during execution. we extend flowback analysis to apply to parallel programs and describe a method to detect race conditions in the interactions of the co- operating processes.  b. p. miller jong-deok choi
type-checking smalltalk  although most attempts to speed-up smalltalk have focused on providing more efficient interpreters, code optimization is probably necessary for further increases in speed. a type-system for smalltalk is a prerequisite for building an optimizing compiler. unfortunately, none of the type-systems so far proposed for smalltalk are adequate; they either cause nearly all smalltalk programs to be type incorrect, allow run-time type errors, or do not provide enough information for optimization. this paper presents a type-system for smalltalk that is suitable for code optimization.  ralph e. johnson
requirements and design of designvision and object-oriented graphical interface to an intelligent software design assistant  key findings from empirical studies---early design is opportunistic; critical role of pictures in design conception; impact of various cognitive limitations ---have very effectively determined requirements and design for a set of tools to support early design. key design features of the tools include respectively: (1) the (simultaneous) display of any software modules at arbitrary levels of abstraction and from any subsystems. the unrestricted, smooth navigation between these software modules. (2) multiple design notations---pictorial and symbolic--- cross-referenced, editable, and maintained consistent across all views. integrated views of control flow, data flow, and functional decomposition. (3) automatic layout at arbitrary levels of nesting. visual display of execution paths in the solution. automatic completeness and consistency check. automatic visual indication and listing of modules with constraint violations.  raymonde guindon
a procedure for designing abstract interfaces for device interface modules  this paper describes the abstract interface principle and shows how it can be applied in the design of device interface modules. the purpose of this principle is to reduce maintenance costs for embedded real-time software by facilitating the adaptation of the software to altered hardware interfaces. this principle has been applied in the naval research laboratory's redesign of the flight software for the navy's a-7 aircraft. this paper discusses a design approach based on the abstract interface principle and presents solutions to interesting problems encountered in the a-7 re-design. the specification document for the a-7 device interface modules is available on request; it provides a fully worked out example of the design approach discussed in this paper.  kathryn heninger britton r. alan parker david l. parnas
software reusability issues in code and design the phenomenal growth in the costs of producing software over the last three decades has forced the computing industry to look for alternative strategies to that implied by the waterfall model of computer system development. one frequently observed solution is flint of reusing existing software artifacts in the construction of new ones; this technique is known as _software reuse._ in this paper, software reusability issues are studied both at the code and design level. hyoseob kim cornelia boldyreff
higher-order functors with transparent signatures  the programming language standard ml provides first-order functors, i.e. modules parameterized by modules. first-order functors in the language have a simple and elegant static semantics. the type structure of higher-order modules, i.e. modules parameterized by functors, is well understood. but it is only in the recent past that we have seen an implementation of higher-order functors with a formally defined static semantics in a dialect of standard ml, sml/nj. a study of this static semantics shows it to be much more complicated than the static semantics of first-order functors. this paper investigates whether we can trade some semantic features in the module language to obtain a simpler static semantics, closer in spirit to that of first-order functors. this work helps in a conceptual understanding of the semantics of higher-order modules.  sandip k. biswas
procs and locks: a portable multiprocessing platform for standard ml of new jersey  we have built a portable platform for running standard ml of new jersey programs on multiprocessors. it can be used to implement user-level thread packages for multiprocessors within the ml language with first-class continuations. the platform supports experimentation with different thread scheduling policies and synchronization constructs. it has been used to construct a modula-3 style thread package and a version of concurrent ml, and has been ported to three different multiprocessors running variants of unix. this paper describes the platform's design, implementation, and performance.  j. gregory morrisett andrew tolmach
an approach to support automatic generation of user interfaces  in traditional interactive programming environments, each application individually manages its interaction with the human user. the result is duplication of effort in implementing user interface code and nonuniform--- hence confusing---input conventions. this paper presents an approach to support automatic generation of user interfaces in environments based on algebraic languages.  the approach supports the editing model of interaction, which allows a user to view all applications as data that can be edited. an application interacts with a user by submitting variables (of arbitrary types) to a dialogue manager, which displays their presentations to the user and offers type- directed editing of these presentations. applications and dialogue managers communicate through a protocol that allows a presentation to be kept consistent with the variable it displays.  a particular implementation of the approach, called dost, has been constructed for the xerox development environment and the mesa programming language. dost is used as a concrete example to describe the editing model, the primitives to support it, and our preliminary experience with these primitives. the approach is compared with related work, its shortcomings are discussed, and suggestions for future work are made.  prasun dewan marvin solomon
a workbench for quality based software re-engineering (doctoral symposium)  this research presents a re-engineering workbench and architecture that allows for legacy system written in procedural languages to be migrated to new object oriented platforms. this methodology allows for specific design and quality requirements of the target migrant system to be considered during the re- engineering process through an iterative and incremental process. the migration process recovers an object model from the procedural code and incrementally refines it by taking into consideration the design requirements for the migrant system.  ladan tahvildari kostas kontogiannis
interrupts as threads most operating system implementations contain two fundamental forms of asynchrony; processes (or equivalently, internal threads) and interrupts. processes (or threads) synchronize using primitives such as mutexes and condition variables, while interrupts are synchronized by preventing their occurrence for a period of time. the latter technique not only is expensive, but it locks out interrupts on the possibility that an interrupt will occur and interfere with the particular critical section of code that was interrupted.in the solaris 2 implementation of unix [eykholt 92] [kleiman 92], these two forms are unified into a single model, threads. interrupts are converted into threads using a low overhead technique. this allows a single synchronization model to be used throughout the kernel. in addition, it lowers the number of times in which interrupts are locked out, it removes the overhead of masking interrupts, and allows modular code to be oblivious to the interrupt level it is called at. steve kleiman joe eykholt
ada requirements methodology (arm)  this paper describes and evaluates the ada requirements methodology (arm - a subset of ada integrated methodology) that was developed during a study sponsored by the united states department of defense to evaluate design support for embedded systems. arm combines some traditional structured analysis techniques with the ada language to develop system requirements. the use of the implementation language (in this case ada) during the requirements phase of system development is a departure from the concept that requirements and design methodologies should be independent of the implementation language. reasons for using ada as a requirements language are addressed in this paper. additionally, the results of the first application of arm and some ideas for further study and enhancements are provided.  phillip crews darrell ward jerry mungle
toward shared variable events implications of (@@@@)sve in apl2  apl2 has two extensions for shared variables, a system function, (@@@@)svs, which returns the access state of variables and a system variable, (@@@@)sve, which provides a rudimentary mechanism for detecting events associated with shared variables. implementation of these constructs raises questions about the signalling rules followed by shared variable processors. this paper discusses those questions and suggests that further research be done.  john a. gerth
evolution of program documentation through a long-term project  this paper is a case study with some recommendations. over the course of a four- year (twenty person-year) project, the method of documenting programs changed from using separate files containing input data for a documentation lister, to placing all of the program documentation in the source code and using an extraction program when separate documentation was needed. the history and reasons for this evolution are described. the project revealed the usefulness of documentation tools including program templates, a good cross- reference lister, in-line documentation, and the extraction program.  peter e schilling john t wizzard
scheduler activations: effective kernel support for the user-level management of parallelism  threads are the vehicle for concurrency in many approaches to parallel programming. threads can be supported either by the operating system kernel or by user-level library code in the application address space, but neither approach has been fully satisfactory.  this paper addresses this dilemma. first, we argue that the performance of kernel threads is inherently worse than that of user-level threads, rather than this being an artifact of existing implementations; managing parallelism at the user level is essential to high-performance parallel computing. next, we argue that the problems encountered in integrating user- level threads with other system services is a consequence of the lack of kernel support for user- level threads provided by contemporary multiprocessor operating systems; kernel threads are the wrong abstraction on which to support user-level management of parallelism. finally, we describe the design, implementation, and performance of a new kernel interface and user-level thread package that together provide the same functionality as kernel threads without compromising the performance and flexibility advantages of user-level management of parallelism.  thomas e. anderson brian n. bershad edward d. lazowska henry m. levy