waashk/acm huggingface dataset:
static checking of interrupt-driven software  resource-constrained devices are becoming ubiquitous. examples include cell phones, palm pilots, and digital thermostats. it can be difficult to fit required functionality into such a device without sacrificing the simplicity and clarity of the software. increasingly complex embedded systems require extensive brute-force testing, making development and maintenance costly. this is particularly true for system components that are written in assembly language. static checking has the potential of alleviating these problems, but until now there has been little tool support for programming at the assembly level.  in this paper we present the design and implementation of a static checker for interrupt-driven z86-based software with hard real-time requirements. for six commercial microcontrollers, our checker has produced upper bounds on interrupt latencies and stack sizes, as well as verified fundamental safety and liveness properties. our approach is based on a known algorithm for model checking of pushdown systems, and produces a control-flow graph annotated with information about time, space, safety, and liveness. each benchmark is approximately 1000 lines of code, and the checking is done in a few seconds on a standard pc. our tool is one of the first to give an efficient and useful static analysis of assembly code. it enables increased confidence in correctness, significantly reduced testing requirements, and support for maintenance throughout the system life- cycle.  dennis brylow niels damgaard jens palsberg
futures: a mechanism for concurrency among objects  a future provides the basic primitive through which a user in an object- oriented distributed system can achieve concurrency. it is based on the notion of being able to translate what appears to be a remote procedure call into a request for computation to be scheduled by the system. the mechanism required to make this translation is discussed. refinements to the future mechanism allow futures to be passed as arguments to other procedure calls. this provides the user with the added flexibility of implementing synchronization schemes suited to specific needs. further, it simplifies the process of migrating an object which has outstanding futures at the time of migration.  a. chatterjee
characterization of object behaviour in standard ml of new jersey  we describe a method of measuring lifetime characteristics of heap objects, and discuss ways in which such quantitative object behaviour measurements can help improve language implementations, especially garbage collection performance. for standard ml of new jersey, we find that certain primary aspects of object behaviour are qualitatively the same across benchmark programs, in particular the rapid object decay. we show that the heap-only allocation implementation model is the cause of this similarity. we confirm the weak generational hypothesis for sml/nj and discuss garbage collector configuration tuning. our approach is to obtain object statistics directly from program execution, rather than simulation, for reasons of simplicity and speed. towards this end, we exploit the flexibility of the garbage collector toolkit as a measurement tool. careful numerical analysis of the acquired data is necessary to arrive at relevant object lifetime measures. this study fills a gap in quantitative knowledge of the workings of heap-based compilers and their run-time systems, and should be useful to functional language implementors.  darko stefanovic j. eliot b. moss
an array operation synthesis scheme to optimize fortran 90 programs  an increasing number of programming languages, such as fortran 90 and apl, are providing a rich set of intrinsic array functions and array expressions. these constructs which constitute an important part of data parallel languages provide excellent opportunities for compiler optimizations. in this paper, we present a new approach to combine consecutive data access patterns of array constructs into a composite access function to the source arrays. our scheme is based on the composition of access functions, which is similar to a composition of mathematic functions. our new scheme can handle not only data movements of arrays of different numbers of dimensions and segmented array operations but also masked array expressions and multiple sources array operations. as a result, our proposed scheme is the first synthesis scheme which can synthesize fortran 90 reshape, eoshift, merge, and where constructs together. experimental results show speedups from 1.21 to 2.95 for code fragments from real applications on a sequent multiprocessor machine by incorporating the proposed optimizations.  gwan-hwan hwang jenq kuen lee dz-ching ju
nesting in ada programs is for the birds  given a data abstraction construct like the ada package and in light of current thoughts on programming methodology, we feel that nesting is an anachronism. in this paper we propose a nest-free program style for ada that eschews nested program units and declarations within blocks and instead heavily utilizes packages and context specifications as mechanisms for controlling visibility. we view this proposal as a first step toward the development of programming methods that exploit the novel language features available in ada. consideration of this proposal's ramifications for data flow, control flow, and overall program structure substantiates our contention that a tree structure is seldom a natural representation of a program and that nesting therefore generally interferes with program development and readability.  lori a. clarke jack c. wileden alexander l. wolf
reflections on the verification of the security of an operating system kernel  this paper discusses the formal verification of the design of an operating system kernel's conformance to the multilevel security property. the kernel implements multiple protection structures to support both discretionary and nondiscretionary security policies. the design of the kernel was formally specified. mechanical techniques were used to check that the design conformed to the multilevel security property. all discovered security flaws were then either closed or minimized. this paper considers the multilevel security model, the verification methodology, and the verification tools used. this work is significant for two reasons. first, it is for a complete implementation of a commercially available secure computer system. second, the verification used off-the-shelf tools and was not done by the verification environment researchers.  jonathan m. silverman
ada as a software transition tool  our agency plans to use the ada programming language as a vehicle to transport a locally written inquiry system from burroughs' equipment to another vendor's hardware. this is being done in the following manner. a bootstrap ada translator has been written in pascal to generate burroughs' algol. the ada translator will be recoded into ada. the inquiry system will be rewritten into ada from algol and executed on the current burroughs' machine. when the new hardware is selected, the ada translator will be retargeted to generate an efficient language on that machine, thereby transporting the inquiry system. the ada translator will be discarded for an ada compiler on the new system.  gary l. filipski donald r. moore john e. newton
practicing judo: java under dynamic optimizations  a high-performance implementation of a java virtual machine (jvm) consists of efficient implementation of just-in-time (jit) compilation, exception handling, synchronization mechanism, and garbage collection (gc). these components are tightly coupled to achieve high performance. in this paper, we present some static anddynamic techniques implemented in the jit compilation and exception handling of the microprocessor research lab virtual machine (mrl vm), i.e., lazy exceptions, lazy gc mapping, dynamic patching, and bounds checking elimination. our experiments used ia-32 as the hardware platform, but the optimizations can be generalized to other architectures.  michal cierniak guei-yuan lueh james m. stichnoth
resourceful systems for fault tolerance, reliability, and safety  above all, it is vital to recognize that completely guaranteed behavior is impossible and that there are inherent risks in relying on computer systems in critical environments. the unforeseen consequences are often the most disastrous [neumann 1986].  section 1 of this survey reviews the current state of the art of system reliability, safety, and fault tolerance. the emphasis is on the contribution of software to these areas. section 2 reviews current approaches to software fault tolerance. it discusses why some of the assumptions underlying hardware fault tolerance do not hold for software. it argues that the current software fault tolerance techniques are more accurately thought of as delayed debugging than as fault tolerance. it goes on to show that in providing both backtracking and executable specifications, logic programming offers most of the tools currently used in software fault tolerance. section 3 presents a generalization of the recovery block approach to software fault tolerance, called _resourceful systems_. systems are resourceful if they are able to determine whether they have achieved their goals or, if not, to develop and carry out alternate plans. section 3 develops an approach to designing resourceful systems based upon a functionally rich architecture and an explicit goal orientation.  russell j. abbott
automatic alignment of array data and processes to reduce communication time on dmpps  this paper investigates the problem of aligning array data and processes in a distributed-memory implementation. we present complete algorithms for compile- time analysis, the necessary program restructuring, and subsequent code- generation, and discuss their complexity. we finally evaluate the practical usefulness by quantitative experiments.  the technique presented analyzes complete programs, including branches, loops, and nested parallelism. alignment is determined with respect to offset, stride, and general axis relations. placement of both data and processes are computed in a unifying framework based on an extended preference graph and its analysis. dynamic redistributions are derived.  the experimental results are very encouraging. the optimization algorithms implemented in our modula-2* compiler improved the execution times of the programs by an average over 40% on a maspar mp-1 with 16384 processors.  michael philippsen
structured tools and conditional logic: an empirical investigation  prior research has identified two psychological processes that appear to be used by programmers when they perform design and coding tasks: (a) taxonomizing---identifying the conditions that evoke particular actions; and (b) sequencing---converting the taxa into a linear sequence of program code. three structured tools---structured english, decision tables, and decision trees---were investigated in a laboratory experiment to determine how they facilitated these two processes. when taxonomizing had to be undertaken, structured english outperformed decision tables, and decision trees outperformed structured english. when sequencing had to be undertaken, decision trees and structured english outperformed decision tables, but decision trees and structured english evoked the same level of performance.  iris vessey ron weber
unreachable procedures in object-oriented programming  unreachable procedures are procedures that can never be invoked. their existence may adversely affect the performance of a program. unfortunately, their detection requires the entire program to be present. using a long-time code modification system, we analyze large, linked, program modules of c++, c, and fortran. we find that c++ programs using object-oriented programming style contain a large fraction of unreachable procedure code. in contrast, c and fortran programs have a low and essentially constant fraction of unreachable code. in this article, we present our analysis of c++, c, and fortran programs, and we discuss how object-oriented programming style generates unreachable procedures.  amitabh srivastava
the cip method: component- and model-based construction of embedded systems  cip is a model-based software development method for embedded systems. the problem of constructing an embedded system is decomposed into a functional and a connection problem. the functional problem is solved by constructing a formal reactive behavioural model. a cip model consists of concurrent clusters of synchronously cooperating extended state machines. the state machines of a cluster interact by multi-cast events. state machines of different clusters can communicate through asynchronous channels. the construction of cip models is supported by the cip tool, a graphical modelling framework with code generators that transform cip models into concurrently executable cip components. the connection problem consists of connecting generated cip components to the real environment. this problem is solved by means of techniques and tools adapted to the technology of the interface devices. construction of a cip model starts from the behaviour of the processes of the real environment, leading to an operational specification of the system behaviour in constructive steps. this approach allows stable interfaces of cip components to be specified at an early stage, thus supporting concurrent development of their connection to the environment.  hugo fierz
comparing frameworks and layered refinement  object-oriented frameworks are a popular mechanism for building and evolving large applications and software product lines. this paper describes an alternative approach to software construction, java layers (jl), and evaluates jl and frameworks in terms of flexibility, ease of use, and support for evolution. our experiment compares schmidt's ace framework against a set of ace design patterns that have been implemented in jl. we show how problems of framework evolution and overfeaturing can be avoided using jl's component model, and we demonstrate that jl scales better than frameworks as the number of possible application features increases. finally, we describe how constrained parametric polymorphism and a small number of language features can support jl's model of loosely coupled components and stepwise program refinement.  richard cardone calvin lin
a distributed architecture for programming environments  programming environments are typically based on concepts, such as syntax and semantics, and they provide functionalities, such as parsing, editing, type- checking, and compiling. most existing programming environments are designed in a fully integrated manner, where parsers, editors, and semantic tools are tightly coupled. this leads to systems that are the sum of all their components, with obvious implications in terms of size, reusability, and maintainability. in this paper, we present a proposal for a distributed architecture for programming environments.  dominique clement
introducing ada  the ada programming language was finalized in july 1980 with the publication of the proposed standard ada language reference manual [a1]. that standard document is being reviewed for clarity and internal consistency under american national standards institute (ansi) canvas procedures in preparation for the issuance of an ansi standard for ada. ada is also on the agenda of the international standards organization (iso).  the united states department of defense (dod) has sponsored the development of ada to provide a standard machine independent high order language (hol) for software which is embedded in or procured as part of major defense systems. examples of the intended applications include communications, avionics, air traffic control, missile guidance, and battlefield or shipboard decision support. computers are usually dedicated to these applications. frequently, they must operate in unfriendly environments, and are specially hardened to withstand shocks, vibrations, temperature fluctuations and other environmental stresses. dod's annual investment for software to run on these embedded computers far exceeds that for data processing applications such as payroll, inventory and financial management [c3].  william e. carlson larry e. druffel david a. fisher william a. whitaker
common ada bindings to compartmented mode workstations  this paper describes a project to build a common set of ada bindings to the compartmented mode workstation (cmw) operating system. the paper discusses various design alternatives for creating these bindings. an object-oriented cmw model is described together with an object-oriented common ada-cmw interface specification. a two-layered design solution is presented and its merits and demerits are discussed. issues relating to the development of these bindings including testing, ada 83 vs. ada 9x issues, and portability are described and some of the ways to handle these issues are discussed.  c. armstrong r. venkatraman
attribute propagation by message passing  the goal of our work is to use the paradigms of syntax-directed editing to perform very sophisticated semantic checking, for example, to check flow- sensitive properties such as whether a variable is necessarily defined before it is used. semantic checking of this power is much more important than syntax checking because it relieves the programmer of the need to keep track of numerous details as the program grows in complexity.  there has been a great deal of recent work on syntax-directed editing. this work primarily serves the needs of novice programmers: making the task of entering and editing programs easier and less error prone. most syntax- directed editors guarantee that the program fragment under construction is syntactically correct at all times. many of them also detect simple semantic errors such as undeclared variables or type errors. few, however, attempt to perform more semantic analysis than a typical (non-optimizing) compiler.  alan demers anne rogers frank kenneth zadeck
aplelegance - the art of staying within one's depth  a barrier to the successful use of apl2 is the need to control the changes of depth which arise from using the operator each with functions such as enclose and disclose. the "spilt pepper" effect following a deluge of "each"'s can be just as damaging as the chains of left- brackets, and of quotes with their accompanying @@@@'s which are the sign of an iso apl programmer losing his or her mental grip. the temptations of a fast interactive system as a substitute for thought are considerable, and should be resisted. to this end there are places in which informal perceptions of how apl2 functions and operators work can be more valuable than the formal descriptions given in the manuals, and this paper focuses on some points where such pedagogical issues arise. it consists of 4 sections, each with rules or precepts for the disciplined and controlled use of nestedness.  norman thomson
tutorial on programming language research  rowe: i am going to talk a little about data abstraction from a programming language viewpoint. i suspect that what i will say in some places will be every bit as controversial amongst programming language folks, as what dennis said was amongst database folks.  historically, programming languages evolve continually, from very low-level representations or descriptions of computations to higher-level descriptions. the idea is to express computations in a way that makes them easier to write, faster to debug, and make them survive change. all these marvelous buzzwords!
reconciling responsiveness with performance in pure object-oriented languages  dynamically dispatched calls often limit the performance of object- oriented programs, since opject-oriented programming encourages factoring code into small, reusable units, thereby increasing the frequency of these expensive operations. frequent calls not only slow down execution with the dispatch overhead per se, but more importantly they hinder optimization by limiting the range and effectiveness of standard global optimizations. in particular, dynamically dispatched calles prevent standard interprocedual optimizations that depend on the availability of a static call graph. the self implementation described here offers tow novel approaches to optimization. type feedback speculatively inlines dynamically dispatched calls based on profile information that predicts likely receiver classes. adaptive optimization reconciles optimizing compilation with interactive performance by incrementally optimizing only the frequently executed parts of a program. when combined, these two techniques result in a system that can execute programs significantly faster than previous systems while retaining much of the interactiveness of an interpreted system.  urs hölzle david ungar
software unit test coverage and adequacy  objective measurement of test quality is one of the key issues in software testing. it has been a major research focus for the last two decades. many test criteria have been proposed and studied for this purpose. various kinds of rationales have been presented in support of one criterion or another. we survey the research work in this area. the notion of adequacy criteria is examined together with its role in software dynamic testing. a review of criteria classification is followed by a summary of the methods for comparison and assessment of criteria.  hong zhu patrick a. v. hall john h. r. may
encapsulation and inheritance in object-oriented programming languages  object-oriented programming is a practical and useful programming methodology that encourages modular design and software reuse. most object- oriented programming languages support data abstraction by preventing an object from being manipulated except via its defined external operations. in most languages, however, the introduction of inheritance severely compromises the benefits of this encapsulation. furthermore, the use of inheritance itself is globally visible in most languages, so that changes to the inheritance hierarchy cannot be made safely. this paper examines the relationship between inheritance and encapsulation and develops requirements for full support of encapsulation with inheritance.  alan snyder
automatic synthesis of deadlock free connectors for com/dcom applications many software projects are based on the integration of independently designed software components that are acquired on the market rather than developed within the project itself. sometimes interoperability and composition mechanisms provided by component based integration frameworks cannot solve the problem of binary component integration in an automatic way. notably, in the context of component based concurrent systems, the binary component integration may cause deadlocks within the system. in this paper we present a technique to allow connectors synthesis for deadlock-free component based architectures [2] in a real scale context, namely in the context of com/dcom applications. this technique is based on an architectural, connector-based approach which consists of synthesizing a com/dcom connector as a com/dcom server that can route requests of the clients through a deadlock free policy. this work also provides guide lines to implement an automatic tool that derives the implementation of routing dead-lock-free policy within the connector from the dynamic behavior specification of the com components. it is then possible to avoid the deadlock by using com composition mechanisms to insert the synthesized connector within the system while letting the system com servers unimodified. we present a sucessful application of this technique on the (com version of the) problem known as _"the dining philosophers"._ depending on the type of deadlock we have a strategy that automatically operates on the connector part of the system architecture in order to obtain a suitably equivalent version of the system which is deadlock-free. paola inverardi massimo tivoli