waashk/acm huggingface dataset:
steps to an advanced ada programming environment  conceptual simplicity, tight coupling of tools, and effective support of host- target software development will characterize advanced ada programming support environments. several important principles have been demonstrated in the arcturus system, including template-assisted ada editing, command completion using ada as a command language, and combining the advantages of interpretation and compilation. other principles, relating to analysis, testing, and debugging of concurrent ada programs, have appeared in other contexts. this paper discusses several of these topics, considers how they can be integrated, and argues for their inclusion in an environment appropriate for software development in the late 1980's.  richard n. taylor thomas a. standish
exploiting virtual synchrony in distributed systems  we describe applications of a virtually synchronous environment for distributed programming, which underlies a collection of distributed programming tools in the isis2 system. a virtually synchronous environment allows processes to be structured into process groups, and makes events like broadcasts to the group as an entity, group membership changes, and even migration of an activity from one place to another appear to occur instantaneously --- in other words, synchronously. a major advantage to this approach is that many aspects of a distributed application can be treated independently without compromising correctness. moreover, user code that is designed as if the system were synchronous can often be executed concurrently. we argue that this approach to building distributed and fault-tolerant software is more straightforward, more flexible, and more likely to yield correct solutions than alternative approaches.  k. birman t. joseph
an optimizing compiler for lexically scoped lisp  we are developing an optimizing compiler for a dialect of the lisp language. the current target architecture is the s-i, a multiprocessing supercomputer designed at lawrence livermore national laboratory. while lisp is usually thought of as a language primarily for symbolic processing and list manipulation, this compiler is also intended to compete with the s-1 pascal and fortran compilers for quality of compiled numerical code. the s-1 is designed for extremely high-speed signal processing as well as for symbolic computation; it provides primitive operations on vectors of floating-point and complex numbers. the lisp compiler is designed to exploit the architecture heavily.  the compiler is structurally and conceptually similar to the bliss-11 compiler and the compilers produced by pqcc. in particular, the tnbind technique has been borrowed and extended.  rodney a. brooks richard p. gabriel guy l. steele
improving balanced scheduling with compiler optimizations that increase instruction-level parallelism  traditional list schedulers order instructions based on an optimistic estimate of the load latency imposed by the hardware and therefore cannot respond to variations in memory latency caused by cache hits and misses on non-blocking architectures. in contrast, balanced scheduling schedules instructions based on an estimate of the amount of instruction-level parallelism in the program. by scheduling independent instructions behind loads based on what the program can provide, rather than what the implementation stipulates in the best case (i.e., a cache hit), balanced scheduling can hide variations in memory latencies more effectively.  since its success depends on the amount of instruction-level parallelism in the code, balanced scheduling should perform even better when more parallelism is available. in this study, we combine balanced scheduling with three compiler optimizations that increase instruction-level parallelism: loop unrolling, trace scheduling and cache locality analysis. using code generated for the dec alpha by the multiflow compiler, we simulated a non-blocking processor architecture that closely models the alpha 21164. our results show that balanced scheduling benefits from all three optimizations, producing average speedups that range from 1.15 to 1.40, across the optimizations. more importantly, because of its ability to tolerate variations in load interlocks, it improves its advantage over traditional scheduling. without the optimizations, balanced scheduled code is, on average, 1.05 times faster than that generated by a traditional scheduler; with them, its lead increases to 1.18.  jack l. lo susan j. eggers
a nested mutual authentication protocol this paper describes an authentication protocol that is suited to modern, object-based, client-server systems. each object in a chain, whether acting in a client or server role, handles authentication with its neighbours, without any need to be aware of the resultant global behaviour. session keys are returned by an authentication server which services a client-server chain as a whole: nested requests are built along the forward chain; the final server presents the whole package to the authentication server; and sessions keys are delivered back down the chain. the protocol, as described, avoids entanglement with the politics of cryptography by using one-way-hash-functions throughout. the authentication chain might traverse different legal jurisdictions, but adjacent applications can use returned session keys for any legitimate purpose, including message sealing or encryption. john a. bull david j. otway
parallel skeletons for structured composition  in this paper, we propose a straightforward solution to the problems of compositional parallel programming by using skeletons as the uniform mechanism for structured composition. in our approach parallel programs are constructed by composing procedures in a conventional base language using a set of high- level, pre- defined, functional, parallel computational forms known as skeletons. the ability to compose skeletons provides us with the essential tools for building further and more complex application-oriented skeletons specifying important aspects of parallel computation. compared with the process network based composition approach, such as pcn, the skeleton approach abstracts away the fine details of connecting communication ports to the higher level mechanism of making data distributions conform, thus avoiding the complexity of using lower level ports as the means of interaction. thus, the framework provides a natural integration of the compositional programming approach with the data parallel programming paradigm.  john darlington yi-ke guo hing wing to jin yang
on the scope of static checking in definitional languages  the paper concerns the use in software development of a class of very high level languages characterized as definitional, where a specification of a program consists of assertions expressed as conditional equations. as compared to logic programming, where assertion are expressed in the form of horn clauses, definitional languages are more amenable to efficient compilation. also, use of equations is a natural way of expressing mathematical models in science, engineering and economics, where computer simulation of such models is often required. finally, definitional languages are well suited for programming dataflow machines, another important building block in a fifth generation project. thus, in many applications definitional languages are preferred choice for programming new generation computers.  in using definitional languages to develop programs, a user relies heavily on static analysis during the compilation stage of development, as compared to the traditional practice of relying much more extensively on dynamic analysis performed by execution of the program with test data. as this seems to be the common trend in development of all software tools for fifth generation computers, the limits of static checking are investigated for definitional languages in this paper.  a comprehensive approach to selecting and implementing automatic checks in the compiler is proposed. the checking methodology consists of representing the specification of a program by a directed graph and propagating various attributes throughout the entire graph. the choice of attributes and checks depends greatly on the types of errors that users are prone to make. this approach is described in the context of the model language and compiler. the paper reports also on an experiment to evaluate the effectiveness of various checking methods incorporated in the compiler and on reliance of static vs dynamic methods of checking. the types of checking constructed were: syntax analysis, ambiguity in naming, completeness of definitions, data type consistency, dimensionality (corresponds to nesting of loops), ranges of dimensions (corresponds to loop terminations) and circular logic.  b. szymanski n. prywes e. lock a. pnueli
co-array fortran for parallel programming co-array fortran, formerly known as f\\--, is a small extension of fortran 95 for parallel processing. a co-array fortran program is interpreted as if it were replicated a number of times and all copies were executed asynchronously. each copy has its own set of data objects and is termed an image. the array syntax of fortran 95 is extended with additional trailing subscripts in square brackets to give a clear and straightforward representation of any access to data that is spread across images.references without square brackets are to local data, so code that can run independently is uncluttered. only where there are square brackets, or where there is a procedure call and the procedure contains square brackets, is communication between images involved.there are intrinsic procedures to synchronize images, return the number of images, and return the index of the current image.we introduce the extension; give examples to illustrate how clear, powerful, and flexible it can be; and provide a technical definition. robert w. numrich john reid
problems in comprehending recursion and suggested solutions  recursion is a very powerful and useful problem solving strategy. but, along with pointers and dynamic data structures, many beginning programmers consider recursion to be a difficult concept to master. this paper report on a study of upper-division undergraduate students on their difficulty in comprehending the ideas behind recursion. three issues emerged as the points of difficulty for the students: (1) insufficient exposure to declarative thinking in a programming context (2) inadequate appreciation of the concept of functional abstraction (3) lack of a proper methodology to express a recursive solution. the paper concludes with a discussion of our approach to teaching recursion, which addresses these issues. classroom experience indicates this approach effectively aids students' comprehension of recursion.  raja sooriamurthi
optimizing array bound checks using flow analysis  bound checks are introduced in programs for the run-time detection of array bound violations. compile-time optimizations are employed to reduce the execution-time overhead due to bound checks. the optimizations reduce the program execution time through elimination of checks and propagation of checks out of loops. an execution of the optimized program terminates with an array bound violation if and only if the same outcome would have resulted during the execution of the program containing all array bound checks. however, the point at which the array bound violation occurs may not be the same. experimental results indicate that the number of bound checks performed during the execution of a program is greatly reduced using these techniques.  rajiv gupta
cocomo evaluation and tailoring  this paper gives the results of our efforts to evaluate and tailor a software cost estimation model called cocomo.1 the precise data for the analysis was collected from the records of 33 completed projects. we evaluate the original cocomo model, which overestimates the efforts required to develop software in our environment. then we tailor the model according to the cocomo tailoring methodology. to increase the precision and stability of the tailored model, we delete some unnecessary cost drivers in a heuristic manner with the aid of nonparametric statistical method. as a result, we can greatly improve the model. finally we suggest a method to tailor the cocomo effort multipliers. we believe we maintain the same direction as the originator's philosophy, and that our efforts can contribute to the progress of the cocomo tailoring methodology.  yukio miyazaki kuniaki mori
efficient instruction scheduling for delayed-load architectures  a fast, optimal code-scheduling algorithm for processors with a delayed load of one instruction cycle is described. the algorithm minimizes both execution time and register use and runs in time proportional to the size of the expression-tree. an extension that spills registers when too few registers are available is also presented. the algorithm also performs very well for delayed loads of greater than one instruction cycle. a heuristic that schedules dags and is based on our optimal expression-tree-scheduling algorithm is presented and compared with goodman and hsu's algorithm integrated prepass scheduling (ips). both schedulers perform well on benchmarks with small basic blocks, but on large basic blocks our scheduler outperforms ips and is significantly faster.  steven m. kurlander todd a. proebsting charles n. fischer
demand-driven register allocation  a new global register allocation technique, demand-driven register allocation, is described. demand-driven register allocation quantifies the costs and benefits of allocating variables to registers over live ranges so that high- quality allocations can be made. local allocation is done first, and then global allocation is done iteratively beginning in the most deeply nested loops. because local allocation precedes global allocation, demand-driven allocation does not interfere with the use of well-known, high-quality local register allocation and instruction-scheduling techniques.  todd a. proebsting charles n. fischer
workstation/apse productivity study results  this paper reports the outcome of a study conducted over the past three years to quantify the productivity and quality benefits resulting from the use of engineering workstations and software engineering environments on ada projects. improvement data from twenty firms was acquired, normalized and analyzed in an attempt to evaluate the business case aspects of these major investment decisions. these data, and the experience they encompass, are used to develop the findings, conclusions and recommendations offered relative to the acquisition of tools and workstations in the future.  d. reifer
information-flow and data-flow analysis of while-programs  until recently, information-flow analysis has been used primarily to verify that information transmission between program variables cannot violate security requirements. here, the notion of information flow is explored as an aid to program development and validation.  information-flow relations are presented for while-programs, which identify those program statements whose execution may cause information to be transmitted from or to particular input, internal, or output values. it is shown with examples how these flow relations can be helpful in writing, testing, and updating programs; they also usefully extend the class of errors which can be detected automatically in the "static analysis" of a program.  jean-francois bergeretti bernard a. carre
operational specification languages  the "operational approach" to software development is based on separation of problem- oriented and implementation-oriented concerns, and features executable specifications and transformational implementation. "operational specification languages" are executable specification languages designed to fit the goals, assumptions, and strategies of the operational approach. this paper defines the operational approach and surveys the existing operational specification languages, viz., the graphic notation of the jackson system development method, paisley, gist, and modern applicative languages.  pamela zave
structured assembly language in vax-11 macro  for several years, the introductory assembly language course at indiana-purdue at fort wayne has used "structured" assembly language on an ibm system 370. a later course makes use of vax-11 macro assembly language on a vax 11/780. this paper shows how the major constructs for structured programming may be implemented in vax-11 macro. the scheme involves assembly language templates for each of the constructs, a standard labeling scheme, and a commenting method which reflects the structure of the program.  robert r. leeper karl o. rehmer
the impact of time on the session problem  the session problem is an abstraction of synchronization problems in distributed systems. it has been used as a test- case to demonstrate the differences in the time needed to solve problems in various timing models, for both shared memory (sm) systems [2] and message- passing (mp) systems [4]. in this paper, the session problem continues to be used to compare timing models quantitatively. the session problem is studied in two new timing models, the periodic and sporadic. both sm and mp systems are considered. in the periodic model, each process takes steps at a constant unknown rate; different processes can have different rates. in the sporadic model, there exists a lower bound but no upper bound one step time, and message delay is bounded. we show upper and lower bounds on the time complexity of the session problem for these models. in addition, upper and lower bounds on running time are presented for the semi-synchronous sm model, closing an open problem from [4]. our results suggest a hierarchy of various timing models in terms of time complexity for the session problem.  injong rhee jennifer l. welch
experiments determining best paths for testing computer program predicates  zeil has developed a vector space measure which indicates those paths which best detect errors in a selected program predicate. this measure has to be applied to a set of paths post hoc, and so the problem is to heuristically characterize those paths which will provide maximal test information about the selected predicate; the problem of selecting the optimal set of paths is np- hard. experiments have been conducted which utilize the vector space criterion to indicate those characteristics of paths which can best be used to test a given predicate. these characteristics will then provide a selection mechanism for an appropriate set of paths. other questions involve the selection of those paths which sufficiently test all the program predicates, and to experimentally identify those program properties which lead to an irreducible error space for a predicate.  lee j. white prabhat n. sahay
vp: a new operation for semaphores a semaphore is a non-negative integer variable on which only operations p and v are allowed. the semaphore construct (with various extensions) is supported by many operating systems and is often used to implement other synchronization constructs. since the semaphore construct is low-level, a semaphore-based program may contain synchronization errors that are very difficult to detect. in this paper, we propose a new operation vp (s1,s2), where s1 and s2 are distinct or identical semaphores. an execution of vp(s1,s2) by a process t is equivalent to that of "v (s1); p(s2)" except that when t starts the v (s1) operation, t is guaranteed to be the next process to access s2 (i.e., t will execute the p(s2) operation before another process executes a p(s2) or v(s2) operation.) section 2 shows several examples to illustrate the advantages of the vp operation. section 3 concludes this paper. in this paper, we assume that the queue for a semaphore is first-in- first-out and that the order of processes blocked in a semaphore queue is the same order in which they executed p operations on the semaphore. we also assume that the scheduling of processes in a concurrent program is _fair,_ i.e., each process ready for execution will eventually be selected as the running process. programs in this paper use ada- like syntax. k. c. tai richard h. carver
resource partitioning in general purpose operating systems: experimental results in windows nt the principal role of the operating system is that of resource management. its task is to present a set of appropriate services to the applications and users it supports. traditionally, general-purpose operating systems, including windows nt, federate resource sharing in a fair manner, with the predominant goal of efficient resource utilisation. as a result the chosen scheduling algorithms are not suited to applications that have stringent quality-of-service (qos) and resource management requirements, such as continuous media streaming applications. several approaches to resource management that are able to meet these requirements, including the use of deterministic schedulers, are well established. operating systems already exist that provide services for fine-grained resource partitioning and qos based allocations. nevertheless, the question arises: can we introduce suitable management mechanisms into general-purpose operating systems that will provide adequate support for the majority of resource sensitive applications, particularly multimedia? or are there inherent problems in general-purpose operating system architectures that demand significant re- engineering?we attempt to answer this question by proposing the protected virtual machine (pvm) architecture. this introduces mechanisms into windows nt that enable partitioning of resources and protection from resource interference. the functionality of the pvm architecture is two-fold. first it introduces the necessary scheduling mechanisms and atomic resource abstractions into the operating system, and second it provides a higher level reservation and admission service directly to applications. the resulting system is able to provide both a best-effort service for applications with less stringent needs and a guaranteed service for multimedia and other resource critical processing in a shared environment, by enhancing the existing operating system, legacy applications can still be supported, thus avoiding a prominent obstacle in existing real-time and multimedia operating systems. d. g. waddington d. hutchison
debugging optimized code without being misled  correct optimization can change the behavior of an incorrect program; therefore at times it is necessary to debug optimized code. however, optimizing compilers produce code that impedes source-level debugging.  optimization can cause an inconsistency between where the user expects a breakpoint to be located and the breakpoint's actual location. this article describes a mapping between statements and breakpoint locations that ameliorates this problem. the mapping enables debugger behavior on optimized code that approximates debugger behavior on unoptimized code sufficiently closely for the user to use traditional debugging strategies.  optimization can also cause the value of a variable to be noncurrent\\---to differ from the value that would be predicted by a close reading of the source code. this article presents a method of determining when this has occurred, and shows how a debugger can describe the relevant effects of optimization. the determination method is more general than previously published methods; it handles global optimization and many flow graph transformations, and it is not tightly coupled to optimizations performed by a particular compiler. necessary compiler support is also described.  max copperman