waashk/acm huggingface dataset:
four dark corners of requirements engineering  research in requirements engineering has produced an extensive body of knowledge, but there are four areas in which the foundation of the discipline seems weak or obscure. this article shines some light in the "four dark corners," exposing problems and proposing solutions. we show that all descriptions involved in requirements engineering should be descriptions of the environment. we show that certain control information is necessary for sound requirements engineering, and we explain the close association between domain knowledge and refinement of requirements. together these conclusions explain the precise nature of requirements, specifications, and domain knowledge, as well as the precise nature of the relationships among them. they establish minimum standards for what information should be represented in a requirements language. they also make it possible to determine exactly what it means for requirements and engineering to be successfully completed.  pamela zave michael jackson
bounds on the shared memory requirements for long-lived & adaptive objects (extended abstract)  in this paper we prove: for any constant d there is a large enough n such that there is no long-lived adaptive implementation of collect or renaming in the read write model with n processes that uses d or less mwmr registers.  in other words, there is no implementation of a long-lived and adaptive renaming or collect object in the atomic read/write model that uses o(1) multi-writer- multi-reader registers and any number of single-writer-multi- reader registers. in 1980 burns and lynch [1] proved that at least n multi- writer-multi-reader (mwmr) registers are necessary in any mutual exclusion algorithm that uses only mwmr registers (i.e., atomic registers). it is also relatively easy to see that any adaptive non-trivial algorithm uses at least one multi-writer-multi-reader (mwmr) register even when there are n single- writer- multi-reader (swmr) registers. here we extend the techniques of burns and lynch and prove that adaptive algorithms that use both swmr and mwmr registers such as, collect and renaming, need in addition to the (n) swmr registers a non-constant, f(n) number of mwmr registers.  yehuda afek pazi boxer dan touitou
quality guidelines = designer metrics  in spite of the significant body of research on traditional source code metrics, there has been a general failure to produce conclusive evidence as to their effectiveness for measuring software quality. we describe and recommend a potentially much more powerful and sensitive quality assessment alternative, software quality guidelines. software quality guidelines are presented as "designer metrics", that is, user-defined rules or constraints relating to measurable features of a program's structure, semantics, and syntax that affect its quality. to provide a methodology for designing, applying, and validating software quality guidelines, we recommend and briefly summarize ieee standard 1061. this standard gives a process for constructing and implementing a software quality metrics framework that can be tailor-made to meet quality requirements for a particular project and/or organization. our paper then demonstrates how software quality guidelines fit within the ieee framework and gives an example illustrating how user-defined guidelines can be applied to evaluate or assess the quality of an ada source unit. this guideline-based assessment of quality is then compared with an analysis based on traditional mccabe and halstead metrics. finally, we introduce a tool being developed by saic, called adarevu, as an effective mechanism for implementing and applying user-defined quality guidelines for ada source code.  david a. workman richard crutchfield
future directions in ada - distributed execution and heterogeneous language interoperability toolsets while the ada community has seen and embraced the development of ada 95 [1], with its enhanced object oriented features and various annexes, much of the rest of the commercial world continues to ignore ada as a viable tool for software system building. efforts have been ongoing for some time to provide rationale showing the superiority of ada 95 over other choices such as c and c++, but with limited success in the commercial marketplace. in this paper, we put forward the idea that the ada community should focus on: 1) interoperability with components built in other languages, and 2) convenient, easy to use toolsets for composing distributed systems from heterogeneous language components. anthony gargaro gary smith ronald j. theriault richard a. volz raymond waldrop
eraser: a dynamic data race detector for multithreaded programs  multithreaded programming is difficult and error prone. it is easy to make a mistake in synchronization that produces a data race, yet it can be extremely hard to locate this mistake during debugging. this article describes a new tool, called eraser, for dynamically detecting data races in lock-based multithreaded programs. eraser uses binary rewriting techniques to monitor every shared-monory reference and verify that consistent locking behavior is observed. we present several case studies, including undergraduate coursework and a multithreaded web search engine, that demonstrate the effectiveness of this approach.  stefan savage michael burrows greg nelson patrick sobalvarro thomas anderson
correspondent computing  in the context of the preliminary study reported here, correspondent computing is loosely defined as the generation of effects (results or outcomes) which are correspondent to the effect of an operation in a computer program. the operation whose effect is the target of correspondent computing is called the primary operation. operations generate correspondent effects are called correspondent operations. the philosophy of correspondence is that if executing an operation can produce a significant effect, an equivalently significant effect may be generated by another semantically correspondent operation. in general, correspondent operations can be categorized as the following three types. 1) reciprocal type. the behaviour of a reciprocal operation is semantically the inverse of the primary operation. 2) duplicate type. the behaviour of a duplicate operation is semantically equivalent to the primary operation. 3) residual (or complementary) type. an operation that fulfills the definition of correspondent operations, but is neither a duplicate, nor a reciprocal is termed as residual operation. all these three types of correspondent operations can be easily derived from the primary operation on the basis of correspondence. we believe that correspondent computing has the potential of becoming a powerful tool and can be used in the areas such as fault tolerance, artificial intelligence, graphics, database systems, etc. in the following paragraphs, we discuss the use of correspondent computing for error detection.  from the viewpoint of software fault tolerance, the correct behavior of some operations are more critical than the others although every operation is a constituent part of the program. therefore, the effect generated by these operations must be examined, and hence they are the primary operations - the targets of correspondent computing. using correspondent computing, the effect of a primary operation can then be checked by comparing with the effects generated by its correspondent operations. the specification of the comparative test is base on the precise relationship between the primary and correspondent operations. if an error occurs, the relationship between the two effects would not match that of the two operations. the greatest advantage of this error detection scheme is the simple and concise specification for the comparative test. as an example, suppose the program sum will sum up an array of n integer numbers. two correspondent operations are implemented for the purpose of error detection. array pa contains the original data of n integer numbers.  pen-nan lee
a customizable substrate for concurrent languages  we describe an approach to implementing a wide-range of concurrency paradigms in high-level (symbolic) programming languages. the focus of our discussion is sting, a dialect of scheme, that supports lightweight threads of control and virtual processors as first-class objects. given the significant degree to which the behavior of these objects may be customized, we can easily express a variety of concurrency paradigms and linguistic structures within a common framework without loss of efficiency.  unlike parallel systems that rely on operating system services for managing concurrency, sting implements concurrency management entirely in terms of scheme objects and procedures. it, therefore, permits users to optimize the runtime behavior of their applications without requiring knowledge of the underlying runtime system.  this paper concentrates on (a) the implications of the design for building asynchronous concurrency structures, (b) organizing large-scale concurrent computations, and (c) implementing robust programming environments for symbolic computing.  suresh jagannathan jim philbin
the interactive performance of slim: a stateless, thin-client architecture taking the concept of thin clients to the limit, this paper proposes that desktop machines should just be simple, stateless i/o devices (display, keyboard, mouse, etc.) that access a shared pool of computational resources over a dedicated interconnection fabric --- much in the same way as a building's telephone services are accessed by a collection of handset devices. the stateless desktop design provides a useful mobility model in which users can transparently resume their work on any desktop console.this paper examines the fundamental premise in this system design that modern, off-the-shelf interconnection technology can support the quality-of-service required by today's graphical and multimedia applications. we devised a methodology for analyzing the interactive performance of modern systems, and we characterized the i/o properties of common, real-life applications (e.g. netscape, streaming video, and quake) executing in thin-client environments. we have conducted a series of experiments on the sun ray 1 implementation of this new system architecture, and our results indicate that it provides an effective means of delivering computational services to a workgroup.we have found that response times over a dedicated network are so low that interactive performance is indistinguishable from a dedicated workstation. a simple pixel encoding protocol requires only modest network resources (as little as a 1mbps home connection) and is quite competitive with the x protocol. tens of users running interactive applications can share a processor without any noticeable degradation, and many more can share the network. the simple protocol over a 100mbps interconnection fabric can support streaming video and quake at display rates and resolutions which provide a high-fidelity user experience. brian k. schmidt monica s. lam j. duane northcutt
ada exception handling: an axiomatic approach  a method of documenting exception propagation and handling in ada programs is proposed. exception propagation declarations are introduced as a new component of ada specifications, permitting documentation of those exceptions that can be propagated by a subprogram. exception handlers are documented by entry assertions. axioms and proof rules for ada exceptions given. these rules are simple extensions of previous rules for pascal and define an axiomatic semantics of ada exceptions. as a result, ada programs specified according to the method can be analyzed by formal proof techniques for consistency with their specifications, even if they employ exception propagation and handling to achieve required results (i.e., nonerror situations). example verifications are given.  david c. luckham w. polak
the semantics of lazy (and industrious) evaluation  since the publication of two influential papers on lazy evaluation in 1976 [henderson and morris, friedman and wise], the idea has gained widespread acceptance among language theoreticians---particularly among the advocates of "functional programming" [henderson80, backus78]. there are two basic reasons for the popularity of lazy evaluation. first, by making some of the data constructors in a functional language non-strict, it supports programs that manipulate "infinite objects" such as recursively enumerable sequences, which may make some applications easier to program. second, by delaying evaluation of arguments until they are actually needed, it may speed up computations involving ordinary finite objects.  first, there are several semantically distinct definitions of lazy evaluation that plausibly capture the intuitive notion.  second, non-trivial lazy spaces are similar in structure (under the approximation ordering) to universal domains (as defined by scott [scott81, scott76]) such as the p@@@@ model for the untyped lambda calculus.  third, we prove that neither initial algebra specifications [adj76,77] nor final algebra specifications [guttag78, kamin80] have the power to define lazy spaces.  fourth, although lazy spaces have the same "higher-order" structure as p@@@@, they nevertheless have an elegant, natural characterization within first order logic. in this paper, we develop a simple, yet comprehensive first order theory of lazy spaces relying on three axiom schemes asserting  (1) the principle of structural induction for finite objects;  (2) the existence of least upper bounds for directed sets; and  (3) the continuity of functions.  robert cartwright james donahue
on the use of regular expressions for searching text  the use of regular expressions for text search is widely known and well understood. it is then surprising that the standard techniques and tools prove to be of limited use for searching structured text formatted with sgml or similar markup languages. our experience with structured text search has caused us to reexamine the current practice. the generally accepted rule of "leftmost longest match" is an unfortunate choice and is at the root of the difficulties. we instead propose a rule which is semantically cleaner. this rule is generally applicable to a variety of text search applications, including source code analysis, and has interesting properties in its own right. we have written a publicly available search tool implementing the theory in the article, which has proved valuable in a variety of circumstances.  charles l. a. clarke gordon v. cormack
storage reclamation models for ada programs  given ada's semantics regarding dynamically allocated objects, do programmers believe that storage reclamation is impractical? at first glance, it would appear that given these semantics, one cannot derive workable models for reclaiming all unneeded objects. in reality, ada provides features that allow programmers to define storage reclamation models that operate at close to 100 percent capacity. this paper describes methods by which ada programs can reclaim objects. examples of ada storage reclamation models are presented along with their associated algorithms. a taxonomy of units that perform storage reclamation is also discussed.  geoffrey o. mendal
interprocedural may-alias analysis for pointers: beyond k-limiting  existing methods for alias analysis of recursive pointer data structures are based on two approximation techniques: k-limiting, and store- based (or equivalently location or region-based) approximations, which blur distinction between elements of recursive data structures. although notable progress in inter-procedural alias analysis has been recently accomplished, very little progress in the precision of analysis of recursive pointer data structures has been seen since the inception of these approximation techniques by jones and muchnick a decade ago. as a result, optimizing, verifying and parallelizing programs with pointers has remained difficult.  we present a new parametric framework for analyzing recursive pointer data structures which can express a new natural class of alias information not accessible to existing methods. the key idea is to represent alias information by pairs of symbolic access paths which are qualified by symbolic descriptions of the positions for which the alias pair holds.  based on this result, we present an algorithm for interprocedural may-alias analysis with pointers which on numerous examples that occur in practice is much more precise than recently published algorithms [cwz90, he90, lr92, cbc93].  alain deutsch
apl2 and the cms system: exploiting the apl2/rexx connection  apl2 and rexx are both powerful interpretive languages. apl2 generally isolates the user/programmer from the operating environment, whereas rexx includes integral hooks to directly access the environment. the second release of apl2 includes the ability to access rexx functions and some variables, using the external function call (associated processor) facility. apl2 programmers can use rexx and appropriately-designed rexx procedures and functions to, for example:  access host system function and services;  perform arithmetic with arbitrarily-large precision;  provide tailored access to applications packages (e.g., script dcf);  perform string and word manipulation;  tailor the apl2 environment;  carry-over variables between workspaces in a given apl2 session;  communicate with the host after leaving apl2.  rexx programmers can test rexx procedures from within apl2, and can access apl2 workspaces and operations, to bring the power of apl2 to manipulate rexx data objects.  the rexx/apl2 interface is decried and some applications are discussed. attention is spent on the proper design of rexx and apl2 code to take advantage of (or even to allow the use of) the existing interface.  d. m. weintraub
an object oriented extension to apl  this paper describes an object oriented extension of apl, which is currently being implemented in a new apl system. this extension is integrated in a rather conservative way to apl. however, all the paradigms of object oriented languages (message passing, instance variables, methods, classes and inheritance) are made available to the user, without losing any of the successful features of apl.  the paper first explains what are the interests of object oriented programming, and what is expected from this introduction in the language. it then discusses syntactic and semantic choices, and shows how the selected solutions fit the philosophy of apl.  an example of this new style of programming in apl is proposed, then the internals of the implementation are presented, showing that this new possibility is made available at the cost of a minimal system overhead. finally, the paper discusses about the results obtained so far.  jean jacques girardot sega sako
a fresh approach to representing syntax with static binders in functional programming tell category theorists about the concept of abstract syntax for a language and they may say "that's just the initial algebra for a sum-of- products functor on the category of sets". despite what you might think, they are trying to be helpful since the initiality property is the common denominator of both definitions by structural recursion and proofs by structural induction [5, sect. 4.4]. in recent years we have learned how to extend this initial algebra view of abstract syntax to encompass languages with statically scoped binders. in the presence of such binders one wants to abstract away from the specific names of bound variables, either by quotienting parse trees by a suitable notion of alpha-equivalence, or by replacing conventional trees with ones containing de bruijn indices [1]. by changing from the category of sets to other well-known, but still 'set-like' categories of sheaves or presheaves, one can regain an initial algebra view of this even more than normally abstract syntax---the pay-off being new and automatically generated forms of structural recursion and induction that respect alpha-equivalence [2, 3]. one good test of these new ideas is to see if they give rise to new forms of functional programming. in fact they do. the paper [6] sketches a functional programming language for representing and manipulating syntactical structure involving binders, based on the mathematical model of variable-binding in [3, 4]. in this ml-like language there are new forms of type for names and name-binding that come along with facilities for declaring fresh names, for binding names in abstractions and for pulling apart such name-abstractions via pattern-matching. the key idea is that properly abstract uses of names, i.e. ones that do not descend below the level of alpha-conversion, can be imposed on the user by a static type system that deduces information about the freshness of names. even though we appear to be giving users a 'gensym' facility, the type system restricts the way it can be used to the extent that we keep within effect-free functional programming, in the sense that the usual laws of pure functional programming remain valid (augmented with new laws for names and name-abstractions). in this talk i will introduce this new approach to representing languages static binders in functional programming and discuss some of the difficulties we have had verifying its semantic properties. andrew m. pitts
predicting potential cobol performance on low level machine architectures  as a cobol host, a computer architecture should efficiently execute those language constructs that are most frequently used in actual programs. however, when the language's control and data structures are at a far higher level than the control and data structures of the underlying machine, the compiler designer is faced with a large number of potential choices for mapping these high level structures to the low level architecture. this is the case for implementing cobol on a typical mini-computer architecture. restricting the choices to an implementable set meeting a given performance criteria and predicting the resulting performance level requires a complex analysis. this paper gives an example of the methodology used in one such analysis -- the performance of cobol on low level architectures. this area was chosen because of the difficulty of the problem caused by the lack of support of cobol constructs and data types on low level architectures used in most mini- and micro- computers. the motorola mc68000 and a risc-type architecture were selected as representative architectures.  jerome a. otto
internal representation and rule development in object-oriented design  this article proposes a cognitive framework describing the software development process in object-oriented design (ood) as building internal representations and developing rules. rule development (method construction) is performed in two problem spaces: a rule space and an instance space. rules are generated, refined, and evaluated in the rule space by using three main cognitive operations: infer, derive, and evoke. cognitive activities in the instance space are called mental simulations and are used in conjunction with the infer operation in the rule space. in an empirical study with college students, we induced different representations to the same problem by using problem isomorphs. initially, subjects built a representation based on the problem description. as rule development proceeded, the initial internal representation and designed objects were refined, or changed if necessary, to correspond to knowledge gained during rule development. differences in rule development processes among groups created final designs that are radically different in terms of their level of abstraction and potential reusability. the article concludes by discussing the implications of these results for object-oriented design.  jinwoo kim f. javier lerch herbert a. simon