waashk/acm huggingface dataset:
a greedy concurrent approach to incremental code generation  the psep system represents a novel approach to incremental compilation for block structured languages. psep implements a very fine grain, "greedy" approach as a highly concurrent system of two processes: an editor and a code generator. the design allows the two processes to execute without locking their shared data objects, utilizing semantic information about the concurrent system to guarantee the consistency of the shared objects. this design is compared with the more common "demand" approach to incremental compilation.  ray ford duangkaew sawamiphakdi
estimating the number of test cases required to satisfy the all-du-paths testing criterion  the all-du-paths software testing criterion is the most discriminating of the data flow testing criteria of rapps and weyuker. unfortunately, in the worst case, the criterion requires an exponential number of test cases. to investigate the practicality of the criterion, we develop tools to count the number of complete program paths necessary to satisfy the criterion. this count is an estimate of the number of test cases required. in a case study of an industrial software system, we find that in eighty percent of the subroutines the all-du-paths criterion is satisfied by testing ten or fewer complete paths. only one subroutine out of 143 requires an exponential number of test cases.  j. bieman j. schultz
using scheduler information to achieve optimal barrier synchronization performance  parallel programs frequently use barriers to synchronize successive steps in an algorithm. in the presence of multiprogramming the choice of spinning versus blocking barriers can have a significant impact on performance. we demonstrate how competitive spinning techniques previously designed for locks can be extended to barriers, and we evaluate their performance. we design an additional competitive spinning technique that adapts more quickly in a dynamic environment. we then propose and evaluate a new method that obtains better peformance than previous techniques by using scheduler information to decide between spinning and blocking. the scheduler information technique makes optimal choices incurring little overhead.  leonidas kontothanassis robert w. wisniewski
automatic verification of requirements implementation  requirements of event-based systems can be automatically analyzed to determine if certain safety properties hold. however, we lack comparable methods to verify that implementations maintain the properties guaranteed by the requirements. we have built a tool that compares implementations written in c with their requirements. requirements describe events which cause state transitions. implementations are annotated to describe changes in the values of their requirement's variables, and dataflow analysis techniques are used to determine the set of events which cause particular state changes. to show that an implementation is consistent with its requirements, we show that each event causing a change of state in the implementation appears in the requirements, and that all the events specified to cause state changes in the requirements appear in the implementation. the annotation language encourages programmers to describe local program behaviors. these behaviors are collected into system-level behaviors, which are compared to those in the requirements. since our analysis is not based on program code, annotations can describe behaviors at any level of granularity. we illustrate the use of our tool with several different annotations of a temperature-control system.  marsha chechik john gannon
a survey of structured and object-oriented software specification methods and techniques  this article surveys techniques used in structured and object-oriented software specification methods. the techniques are classified as techniques for the specification of external interaction and internal decomposition. the external specification techniques are further subdivided into techniques for the specification of functions, behavior, and communication. after surveying the techniques, we summarize the way they are used in structured and object- oriented methods and indicate ways in which they can be combined. this article ends with a plea for simplicity in diagram techniques and for the use of formal semantics to define these techniques. the appendices show how the reviewed techniques are used in 6 structured and 19 object-oriented specification methods.  roel wieringa
less complex elementary functions  the textbook definitions of complex elementary functions---e.g., sin(z)---are usually given in terms of formulae which involve complex operations. in this paper, we give formulae for complex elementary functions in which the real and imaginary parts can be computed separately using only real operations. many of these formulae are obvious, but some---e.g., asin(z), acos(z), atan(z), asinh(z), acosh(z), atanh(z)---are not obvious and/or not well-known.  henry g. baker
a checkable interface language for pointer-based structures  we present a technique for analyzing structural constraints on data aggregates in high-level languages. our technique includes a formal constraint language and a dataflow algorithm for automatically checking equality constraints. the constraint language is used to augment the type information on program interfaces. for example, one can specify that a procedure must return aggregates a and b where each element in aggregate a points to some element in aggregate b, and that parameter c will have the properties of a rooted tree both on input and output. our dataflow algorithm tracks the constraints which must apply at each statement in order for the procedure to satisfy its interface, and detects invalid programs which fail to satisfy the constraints on their interfaces. we apply our technique to several examples.  our work is motivated by the requirements for expressive interface definition languages for distributed systems, and by the desire to mechanically check program modules against their interfaces. our analysis techniques also yield information which may enable compilers and stub generators to produce better implementations.  james r. russell robert e. strom daniel m. yellin
extending apl: what more can a programmer ask for?  this paper explores certain underdeveloped parts of apl which ought to grow if apl is to qualify as implementation language for large and maintainable software systems. following specific problems are discussed:  * integrating apl with other parts of information processing environment.  • operating systems.  • programs written in other languages.  • data bases.  * using independently developed functions and subsystems.  • problems with names.  • problems with space.  * execution control of object attributes.  * communications among functions.  • passing parameters.  • returning values.  • transferring control.  * information hiding modules.  • packaging related functions.  • packaging data with functions.  • local functions.  dragan bozinovic
program optimization and parallelization using idioms  programs in languages such as fortran, pascal, and c were designed and written for a sequential machine model. during the last decade, several methods to vectorize such programs and recover other forms of parallelism that apply to more advanced machine architectures have been developed (particularly for fortran, due to its pointer-free semantics). we propose and demonstrate a more powerful translation technique for making such programs run efficiently on parallel machines which support facilities such as parallel prefix operations as well as parallel and vector capabilities. this technique, which is global in nature and involves a modification of the traditional definition of the program dependence graph (pdg), is based on the extraction of parallelizable program structures ("idioms") from the given (sequential) program. the benefits of our technique extend beyond the above-mentioned architectures and can be viewed as a general program optimization method, applicable in many other situations. we show a few examples in which our method indeed outperforms existing analysis techniques.  shlomit s. pinter ron y. pinter
theoretical comparison of testing methods  comparison of software testing methods is meaningful only if sound theory relates the properties compared to actual software quality. existing comparisons typically use anecdotal foundations with no necessary relationship to quality, comparing methods on the basis of technical terms the methods themselves define. in the most seriously flawed work, one method whose efficacy is unknown is used as a standard for judging other methods! random testing, as a method that can be related to quality (in both the conventional sense of statistical reliability, and the more stringent sense of software assurance), offers the opportunity for valid comparison.  r. hamlet
phone-based cscw: tools and trials  telephones are the most ubiquitous, best-networked, and simplest computer terminals available today. they have been used for voice mail but largely overlooked as a platform for asynchronous cooperative-work applications such as event calendars, issue discussions, and question-and-answer gathering. hypervoice is a software toolkit for constructing such applications. its building blocks are high-level presentation formats for collections of structured voice messages. the presentation formats can themselves be presented and manipulated, enabling significant customization of applications by phone. results of two field trials suggest social-context factors that will influence the success or failure of phone-based cooperative work applications in particular settings.  paul resnick
an experimental testbed for embedded real time ada 95 the modifications made to ada during the 9x process have resulted in a language that is ideally suited to programming real-time systems. in this paper we investigate the difficulties in realising this potential. in particular, we consider the issues raised when porting the public gnat system on to a bare processor and producing a predictable and effective run-time system. as we were also concerned with issues of distribution via a can broadcast bus, support for the can protocol was included in the run-time system. in addition to investigating the performance of real-time ada 95 applications we were also interested in more general issues associated with embedded kernel support for ada 95. to facilitate these investigations and obtain the required level of performance, the thread package via which gnat implement various aspects of the ada language has been re-implemented. we discuss the architecture selected for this embedded kernel implementation and its relation to the architecture of the gnat compiler. w. m. walker p. t. woolley a. burns
code reusability in the large versus code reusability in the small  as a general rule, the goals of software engineering involve the devel opment of techniques for improving software development productivity. it is no surprise, then, that a lot of attention has been focused on facilitating the reuse of program code. however, most of this attention has been directed with only shortsighted and self-supporting goals, and has thus condemned code reuse techniques to limited areas of success. this paper brings to light some of the issues involving code reusability, which include technical, social, economic, and psychological considerations. code reusability "in the large" is contrasted with code reusability "in the small," ; and methods for improving code reusability are examined.  mitchell d. lubars
developing domain knowledge through the reuse of project experiences  software development is no longer a homogenous field. software is being developed for an increasingly diverse set of applications and user populations, each with different characteristics and development constraints. as a consequence, researchers and practitioners have begun to realize the importance of identifying and understanding the characteristics and special development needs of application domains. this paper presents a method for developing and refining knowledge about application domains by creating a repository of project experiences. subsequent projects can then benefit from these experiences by locating similar projects and reusing the knowledge accumulated in the repository. we develop a framework for a system to capture relationships between development projects and resources for developing software, including process models, methods, technologies, and tools. we then show how this information can be reused to improve the productivity and quality of software development efforts.  scott henninger
static slicing in the presence of goto statements  a static program slice is an extract of a program which can help our understanding of the behavior of the program; it has been proposed for use in debugging, optimization, parallelization, and integration of programs. this article considers two types of static slices: executable and nonexecutable. efficient and well-founded methods have been developed to construct executable slices for programs without goto statements; it would be tempting to assume these methods would apply as well in programs with arbitrary goto statements. we show why previous methods do not work in this more general setting, and describe our solutions that correctly and efficiently compute executable slices for programs even with arbitrary goto statements. our conclusion is that goto statements can be accommodated in generating executable static slices.  jong-deok choi jeanne ferrante
integrating configuration management into a generic environment  the software development process consists of a number of complex activities for work coordination, organization, communication, and disciplines that are essential for achieving quality software, maintaining system integrity, and keeping the software process manageable. software engineering environments can be helpful instruments in pursuing these goals when they are integrated, open to extension, and capable of adapting to real processes as they occur in software development projects.  adaptability and the ability to perform adaptations rapidly are crucial features of sees. in this paper we are presenting an approach to rapid environment extension that provides the means to capture characteristics of software development processes and realize environment support for these processes by using existing tools. an object oriented environment infrastructure is the basis for achieving these goals while providing and maintaining an integrated behavior of the environment. the presented approach is demonstrated by defining a set of classes for version control and configuration management that model the behavior of an existing configuration management toolkit.  axel mahler andreas lampen
tsiopak - a proposal for a new sharp apl file system  communication between os files is often necessary when information that is manipulated and stored in sharp apl files is required to be used by non-apl routines. for example, one may use apl for number crunching and have the output processed by sas or fortran to plot the data.  the arising demand for procedures that would make data accessible from apl to other systems motivated the author to take action.  tsiopak was developed with the intention to provide a standard interface between sharp apl and the mvs operating system facilitating the accessibility of data created through apl and other languages. in addition, the reader will find that starting from the section titled the tsiopak file system, the format for each section looks very much like the sharp apl reference manual. this is not a coincidence, what the author has tried to achieve with this work is to have a file system functionally identical to sharp's using os files. the author's efforts have gone as far as trying to replicate the format of sharp's manual.  in addition, parts of the sharp apl file system have not been implemented in tsiopak due to the lack of time and resources. hence, this paper is a proposal for a new file system which would make apl-generated data generally available.  carlos g. leon
interface language for supporting programming styles  we suggest a novel application of a formal specification language: we use it to support some programming conventions and encourage certain styles of programming. the larch/c interface language (lcl) is a language for documenting the interfaces of ansi c programs. it is designed to support a style of c programming where a program is organized around a set of software modules. even though c does not support abstract data types, lcl supports the specifications of abstract data types, and provides guidelines on how abstract types can be implemented in c. a lint-like program checks for some conformance of c code to its lcl specification.  yang meng tan
gfsr pseudorandom number generation using apl this paper demonstrates the effectiveness of apl for implementing the generalized feedback shift register (gfsr) approach to producing a random number stream. various approaches to generating streams of pseudorandom numbers computationally have been devised, dating at least as far back as norbert wiener. these are normally discussed in the context of a course in modeling and simulation, since there may be practical implications to consider when building simulation models in apl or any other high level language. this is particularly the case for those circumstances when a (pseudo) random number sequence needs to be repeated, or when multiple streams are needed. in such cases a pseudorandom number generator other than that supplied in the programming language command set needs to be implemented. the linear congruential method for pseudorandom number generation is still commonly used, and is easily implemented in apl or any other high level language; however, it is known to have undesirable n-space uniformity characteristics. moreover, the period length of its random number stream is limited by the underlying machine's word size. this is a serious issue, since at present day computer speeds, a simulation run could exhaust such a random number stream in a few hours. very long period (vlp) pseudorandom number generators remedy this deficiency.one class of these, generalized feedback shift register (gfsr) pseudorandom number generators, is based on algebraic manipulation of irreducible trinomials of high order. the manner in which this is accomplished particularly lends itself to elegant apl implementation. charles winton
analyzing exotic instructions for a retargetable code generator  exotic instructions are complex instructions, such as block move, string search, and string edit, which are found on most conventional computers. recent retargetable code generator and instruction set analysis systems have not dealt with exotic instructions. a method to analyze exotic instructions is presented which provides the information needed by a retargetable code generator. the analysis uses source-to-source transformations to prove the equivalence of high-level language operators to exotic instructions. examples are presented which illustrate the analysis process.  thomas m. morgan lawrence a. rowe
layering and multiple views of data abstraction in ada: techniques and experiences  this paper describes the results of a study to investigate alternative techniques for using private types and packages to limit visibility of declarative items in ada. shortfalls of the conventional technique of applying private types, with regard to issues of recompilation, source code integrity, limiting visibility, performance, support of debugging, and interrelating abstractions, are identified. possibly other developers of large ada systems have encountered these issues; an analysis of over two million lines of ada software developed for the army, navy, and air force shows that private types are rarely used. this paper describes a series of unconventional techniques for using private types and packages to layer more abstract packages on top of less abstract packages, and to develop multiple views of abstract data types applicable to different classes of users. the promising techniques were applied on an actual software engineering problem, the development of a tree- builder component of an ada-to-diana translator. a description of experiences, in which the techniques realized benefits for changing and debugging the software and for improving reliability, is provided.  s. keller j. perkins k. o'leary
leases: an efficient fault-tolerant mechanism for distributed file cache consistency  caching introduces the overhead and complexity of ensuring consistency, reducing some of its performance benefits. in a distributed system, caching must deal with the additional complications of communication and host failures.  leases are proposed as a time-based mechanism that provides efficient consistent access to cached data in distributed systems. non-byzantine failures affect performance, not correctness, with their effect minimized by short leases. an analytic model and an evaluation for file access in the v system show that leases of short duration provide good performance. the impact of leases on performance grows more significant in systems of larger scale and higher processor performance.  c. gray d. cheriton
building partitioned architectures based on the ravenscar profile the requirement to support software partitioning is a recurring theme within high integrity and safety critical systems. the partition concept is used to implement differing access protection levels for applications of varying criticality levels executing on the same processor. partitions can also be used in fault tolerant systems that require high availability, redundancy or dynamic re-configuration.the _ravenscar profile_ was a major output of the 8th international real-time ada workshop. the profile defines a subset of the ada95 tasking constructs that matches the requirements of safety critical, high integrity and hard real-time systems by eliminating constructs with high overhead or non-deterministic behavior (semantically or temporally) whilst retaining those elements that form the basic building blocks for constructing analyzable and deterministic real-time software.this paper describes how a cots ada95 compilation system that implements the ravenscar profile can be used in the implementation of a partitioned architecture in an integrated modular avionics context based on the arinc 653 application executive (apex) standard. brian dobbing
experience with cst: programming and implementation  cst is a programming language based on smalltalk-802 that supports concurrency using locks, asynchronous messages, and distributed objects. in this paper, we describe cst: the language and its implementation. example programs and initial programming experience with cst are described. our implementation of cst generates native code for the j-machine, a fine- grained concurrent computer. some compiler optimizations developed in conjunction with that implementation are also described.  w. horwat a. a. chien w. j. dally
prettyprinting in an interactive programming environment  prettyprint algorithms designed for printing programs on paper are not appropriate in an interactive environment where the interface to the user is a crt screen. we describe a data representation and an algorithm that allow the efficient generation of program displays from a parsed internal representation of a program. the displays show the structure of the program by consistent and automatic indentation. they show the program in varying levels of detail by replacing unimportant parts with ellipsis marks. the relative importance of program parts is determined jointly by the structure of the program and by the current focus of attention of the programmer.  martin mikelsons