waashk/acm huggingface dataset:
trellis: turning designs into programs  when designing an object- oriented program, there are several goals to achieve:  the program should accurately model the real-world objects to be represented. this leads to a program that is easier to understand and therefore simpler to maintain.  code that implements the model accurately must also be robust. inconsistent models should be detected at design time, not diagnosed as a run-time error at a customer's installation.  the programming environment must allow for convenient exploration of the application; it should foster a reuse of existing types of objects, thus reducing the scale of the design. it should also facilitate changes to the program as the application design is updated.  the trellis programming system is an integrated language and environment that provides many of the mechanisms needed to design and implement object-oriented programs. the remainder of this sidebar discusses how trellis helps attain the goals outlined above.  michael kilian
direct execution of lisp on a list_directed architecture  we have defined a direct-execution model dedicated to non- numerical processing which is based upon an internal representation of source programs derived from lisp. this model provides good support for both sophisticated editing (syntactical parsing, tree manipulation, pretty- printing, ...) of conventional languages and artificial intelligence languages. a high level microprogramming language (lem) was designed to write the interpreters and the editors. a hardware processor was built and a lisp interpreter, microprogrammed in lem, has been operational since september 1980.  first, the influence of lisp on the lem language and the architecture is discussed. at the lem level, we will see that lisp has prompted the control constructs and the access functions to the tree-structured internal form. as for the architecture, we present the hardware implementation of a special garbage collector based upon reference counters.  in turn, the machine has influenced the implementation of lisp. we present here the structure of our lisp interpreter and we give evaluation measures dealing with size, development effort, speed; they prove that programming in lem is easy, short to debug and very concise. moreover, the speed of our lisp interpreter confirms that the architecture is very efficient for symbolic processing.  j. p. sansonnet m. castan c. percebois d. botella j. perez
stable and fault-tolerant object allocation  support for efficient dynamic migration and replication of objects is essential for achieving adequate performance and scalability. traditional solutions to the problem focused on competitiveness. this means that the algorithm's complexity matches the offline adversary's complexity within an acceptable ratio. we define and study the allocation problem under two new measures: stability and fault tolerance. stability considers the performance of an object allocation algorithm when the object access patterns at the individual nodes of a distributed system stabilize. we present a new algorithm for uniform networks based on the idea of sliding windows. besides being optimally competitive, the algorithm also exhibits good stability. for fault- tolerance, we consider the performance of allocation algorithms when at least t copies need to be maintained. we derive a lower bound on the competitiveness of such algorithms. finally, we modify our earlier solution so that it is also optimally fault-tolerant.  gregory johnson ambuj k. singh
exploring the type inference approach to deforestation  designing programs around the natural decomposition of a problem into reusable components makes it easier for programmers to write and maintain programs. this principle is known as modularity. despite the benefits of modularity, it introduces inefficiency into programs, in part due to the creation of intermediate data structures such as lists and trees. deforestation is a program transformation that eliminates some of these structures, allowing programmers to write modular programs with reckless abandon and still enjoy the efficiency benefits of monolithic programming.  kirsten chevalier
simplifying failure-inducing input  given some test case, a program fails. which part of the test case is responsible for the particular failure? we show how our delta debugging algorithm generalizes and simplifies some failing input to a minimal test case that produces the failure.  in a case study, the mozilla web browser crashed after 95 user actions. our prototype implementation automatically simplified the input to 3 relevant user actions. likewise, it simplified 896~lines of html to the single line that caused the failure. the case study required 139 automated test runs, or 35 minutes on a 500 mhz pc.  ralf hildebrandt andreas zeller
accumulative versioning file system moraine and its application to metrics environment mame  it is essential to manage versions of software products created during software development. there are various versioning tools actually used in these days, although most of them require the developers to issue management commands for consistent versioning. in this paper, we present a novel versioning file system moraine, which accumulatively and automatically collects all files created or modified. those files are versioned and stored as compressed forms. the older versions are easily retrieved from moraine by the time-stamps or tags if required.  using moraine system, we have developed a metrics (measurement) environment called mame (moraine as a metrics environment). mame can collect various metrics data for on-going or past projects, since its basis, moraine, is able to retrieve all versions of all products (files).  both moraine and mame have been implemented. using these systems, we have evaluated the performance of moraine and mame with various test data and student project data. the result shows that disk space required by this approach is several times larger than ordinary approaches; however, it is acceptable at the current tendency of disk price decrease. by this approach, an ideal metrics environment has been easily established by developing simple data-collection tools for version files.  tetsuo yamamoto makoto matsushita katsuro inoue
toward formalizing structured analysis  real-time extensions to structured analysis (sa/rt) are popular in industrial practice. despite the large industrial experience and the attempts to formalize the various "dialects," sa/rt notations are still imprecise and ambiguous. this article tries to identify the semantic problems of the requirements definition notation defined by hatley and pirbhai, one of the popular sa/rt "dialects," and discusses possible solutions. as opposed to other articles that give their own interpretation, this article does not propose a specific semantics for the notation. this article identifies imprecisions, i.e., missing or partial information about features of the notation; it discusses ambiguities, i.e., elements of the definition that allow at least two different ("reasonable") interpretations of features of the notation; and it lists extensions, i.e., features not belonging to the notation, but required by many industrial users and often supported by case tools. this article contributes by clarifying whether specific interpretations can be given unique semantics or retain ambiguities of the original definition. the article allows for the evaluation of formal definitions by indicating alternatives and consequences of the specific choices.  luciano baresi mauro pezzè
a preliminary evaluation of verifiability in ada  in this paper we examine ada with regard to program verification and make certain suggestions towards writing potentially provable ada programs. we attempt to isolate and discuss those features of ada which are not susceptible to current verification techniques. from verifiability considerations, the most critical features in ada appear to be those which deal with data sharing under concurrent processing, direct referencing of non-local variables, access variables, "approximate" data-types, and generic program units. the independence of program units along with well defined interfaces for interactions is presented as desirable not only from software engineering aspects but also from the formal proof considerations. however, the possibility of having a large number of variables, potentially sharable among concurrent processes, is likely to make the proofs of ada programs unmanageable. it is asserted, however, that with a certain discipline on the programmer verifiable programs can be written in ada.  a. r. tripathi w. d. young d. i. good
dual: an interactive tool for developing documented programs by step-wise refinements.  programs are integrated hierarchical structures of formal texts - instructions - and informal texts - documentation. only if there is a mechanical connection between program design and program development there can be higher chances that the program documentation, originated at design time, will not, sooner or later, become obsolete with respect to the current state of the system. dual is an interactive, incremental, intelligent editor of program and documentation texts to be used for software implementations whose anticipated life cycle is significantly long to deserve much attention. the screen interface plays a unique role in dual since it allows a visitor ( designer or maintenance engineer) "to replay" as many times as desired the evolution of the system from design to implementation. the access to the hierarchically organized design information is made easy and natural by the dual video oriented user interface.  luigi petrone antonio di leva franco sirovich
message driven computing and its relationship to actors  we define message driven computation as a style of computing with two characteristics: 1) messages, not sequential processes, convey both control and data. indeed, there are no sequential processes unless they are programmed explicitly in terms of messages. 2) computation is invoked by the presence of a collection of messages at the same location. mdc may be viewed as a generalization of actors [agha86].  mdc - message driven computing  mdc is based on message passing to named locations at which both data storage and computation is performed.  messages are sent to labeled message queues called portals. a locus is a named collection of portals.  messages are not sent or received by processes; rather, a collection of messages at a locus that match a pattern will trigger the execution of a procedure. these pattern-invoked procedures are called behaviors. the execution of a behavior can send further messages.  there are two kinds of patterns currently provided for triggering behaviors. 1) a specified number of messages at each of several specified portals at the same locus can trigger a behavior. 2) a message arriving at a specified portal of a locus can trigger a behavior if that locus has no other messages at any of its portals. the contents of the messages are not examined in either pattern match.  a locus is named by an arbitrary tuple of information. the first component is required to be a symbol, an internally generated value used somewhat like a pointer. all loci whose names begin with the same symbol are typically considered to be components of the same distributed object. moreover, a garbage collector can collect all loci whose names cannot be generated again because no active computation has access to their initial symbol.  a locus will occupy one node of a multi-computer. the node number may be calculated from the locus name by a user specified formula or by hashing if no other method is specified. a locus is created when a message arrives at it and vanishes when no further messages are present or the garbage collector discovers it can no longer be active.  similarly, portals are created at loci when messages arrive at them. a portal name is constructed out of a locus name and a portal label.  t. w. christopher
afs and the web: competitors or collaborators? over the last few years, the world-wide web [2] has risen to dominance as a mechanism for wide-area information access. each day brings new reports of the growth of the web, and this trend shows no signs of abating any time soon. to many people, the web and the internet are synonymous. unfortunately, success has exposed many limitations of the web such as its tendency to overload the network and servers, its limited ability to control access to sensitive data, its lack of mechanisms for data consistency, and its susceptibility to network and server failures. it is now widely recognized that these problems must be solved for the continued growth of the web.with much less fanfare, another world-wide information system, afs, has also been operational on the internet. afs was originally designed to support the file sharing needs of a campus-sized community of five to seven thousand workstations [11, 15]. in current parlance, afs was conceived as an information sharing mechanism for the _intranet_ of an organization. since then, afs has been evolved to function effectively over the internet [17, 21]. many organizations have been part of a single distributed unix file name space supported by afs. as of 1994, this system spanned well over 100 organizations world-wide, with each organization typically containing many tens or hundreds of clients. measurements reported in a recent paper [20] confirm that afs does indeed function effectively at this scale.the goal of this paper is to critically compare these two mechanisms for world-wide information access. we begin by asking the following questions: what are the relative strengths and weaknesses of the two mechanisms? which of these differences are superficial, and which are deep? why is the web so much more visible and popular?in performing this comparison, it is important to keep in mind that the two mechanisms are not addressing precisely the same problem. while afs has the relatively narrow and well- defined goal of provided distributed unix file access, the goal of the web is broader and less explicit. further, afs is now stable and mature while many aspects of the web are still evolving. in spite of these caveats, we believe that a comparison of the two mechanisms will provide useful insights.our comparison shows that the web and afs are not really competing technologies. rather, they represent complementary technologies that may be used together for mutual advantage. we present real-life examples to confirm that this potential can indeed be realized in practice. m. satyanarayanan mirjana spasojevic
task dependence and termination in ada  this article analyzes the semantics of task dependence and termination in ada. we use a contour model of ada tasking in examining the implications of and possible motivation for the rules that determine when procedures and tasks terminate during execution of an ada program. the termination rules prevent the data that belong to run-time instances of scope units from being deallocated prematurely, but they are unnecessarily conservative in this regard. for task instances that are created by invoking a storage allocator, we show that the conservative termination policy allows heap storage to be managed more efficiently than a less conservative policy. the article also examines the manner in which the termination rules affect the synchronization of concurrent tasks. master-slave and client-server applications are considered. we show that the rules for distributed termination of concurrent tasks guarantee that a task terminates only if it can no longer affect the outcome of an execution. the article is meant to give programmers a better understanding of ada tasking and to help language designers assess the strengths and weaknesses of the termination model.  laura k. dillon
an experimental investigation of scheduling strategies for unix  the scheduler used in an operating system is an important factor in the performance of the system under heavy load. this paper describes the scheduling philosophy employed in the unix operating system and outlines the standard scheduling strategies. modified strategies which address deficiencies in the standard strategies are described. the effectiveness of these modified strategies is assessed by means of performance experiments.  darwyn r. peachey richard b. bunt carey l. williamson tim b. brecht
separating data and control transfer in distributed operating systems  advances in processor architecture and technology have resulted in workstations in the 100+ mips range. as well, newer local-area networks such as atm promise a ten- to hundred-fold increase in throughput, much reduced latency, greater scalability, and greatly increased reliability, when compared to current lans such as ethernet.  we believe that these new network and processor technologies will permit tighter coupling of distributed systems at the hardware level, and that distributed systems software should be designed to benefit from that tighter coupling. in this paper, we propose an alternative way of structuring distributed systems that takes advantage of a communication model based on remote network access (reads and writes) to protected memory segments.  a key feature of the new structure, directly supported by the communication model, is the separation of data transfer and control transfer. this is in contrast to the structure of traditional distributed systems, which are typically organized using message passing or remote procedure call (rpc). in rpc-style systems, data and control are inextricably linked---all rpcs must transfer both data and control, even if the control transfer is unnecessary.  we have implemented our model on decstation hardware connected by an atm network. we demonstrate how separating data transfer and control transfer can eliminate unnecessary control transfers and facilitate tighter coupling of the client and server. this has the potential to increase performance and reduce server load, which supports scaling in the face of an increasing number of clients. for example, for a small set of file server operations, our analysis shows a 50% decrease in server load when we switched from a communications mechanism requiring both control transfer and data transfer, to an alternative structure based on pure data transfer.  chandramohan a. thekkath henry m. levy edward d. lazowska
protecting privacy using the decentralized label model  stronger protection is needed for the confidentiality and integrity of data, because programs containing untrusted code are the rule rather than the exception. information flow control allows the enforcement of end-to-end security policies, but has been difficult to put into practice. this article describes the decentralized label model, a new label model for control of information flow in systems with mutual distrust and decentralized authority. the model improves on existing multilevel security models by allowing users to declassify information in a decentralized way, and by improving support for fine-grained data sharing. it supports static program analysis of information flow, so that programs can be certified to permit only acceptable information flows, while largely avoiding the overhead of run-time checking. the article introduces the language jif, an extension to java that provides static checking of information flow using the decentralized label model.  andrew c. myers barbara liskov
what future for the distributed systems annex? in this paper, we report our experience as implementors and users of the ada 95 distributed systems annex (annex e of the ada reference manual). we identify the principal strengths and weaknesses of the annex, and make some proposals to improve it either immediately or for the next revision of the language (ada0x). our goal is to get an annex that is more open and compatible with other distributed systems such as corba, without loosing the capability of developing pure ada rock solid distributed systems.we assume that the reader is familiar with ada. knowledge of the distributed systems annex is useful but not required to understand the main ideas exposed in this article. laurent pautet samuel tardieu
a fine-grained model for code mobility  in this paper we take the extreme view that every line of code is potentially mobile, i.e., may be duplicated and/or moved from one program context to another on the same host or across the network. our motivation is to gain a better understanding of the range of constructs and issues facing the designer of a mobile code system, in a setting that is abstract and unconstrained by compilation and performance considerations traditionally associated with programming language design. incidental to our study is an evaluation of the expressive power of mobile unity, a notation and proof logic for mobile computing.  cecilia mascolo gian pietro picco gruia-catalin roman
an application development platform  while apl was a highly productive system for personal computing and application development when it was introduced, it is lacking nowadays in the areas of programming-in-the-large and user interface construction.  the design and implementation of a new application development platform (adp) is described. the adp frees the programmer from user interface concerns, and frees the application from device specific code. the adp ensures consistent user interfaces based on state-of-the-art window techniques.  together with the underlying apl language, a software repository (logos) and a data handling facility (viewpoint®) the adp is part of a full application environment.  the paper describes the underlying principles of our adp. we also present a small worked out example comparing a traditional toolbox with the adp.  morten kromberg martin gfeller
interacting with object-oriented program slicing object-oriented program slicing was introduced by law and maguire [1,2]. on the basis of object- oriented program slicing, c++ object-oriented program slicer [c++_oops] was developed to assist programmers locate program faults. technical investigation of object-oriented program slicing and the design of c++_oops can be found in [1,2]. this paper provides a discussion and analysis of programmers' views towards using c++_oops. users generally agree that c++_oops assists high-level debugging, yet a more user-friendly c++_oops environment could definitely be more beneficial. rob law
unconstrained duals and their use in achieving all-uses coverage testing takes a considerable amount of the time and resources spent on producing software. it would therefore be useful to have ways 1) to reduce the cost of testing and 2) to estimate this cost. in particular, the _number of tests_ to be executed is an important and useful attribute of the entity "testing effort". _all-uses coverage_ is a data flow testing strategy widely researched in recent years. in this paper we present _spanning sets of duas_ for the all-uses coverage criterion. a spanning set of duas is a minimum set of duas (definition-use associations) such that a set of test paths covering them covers every dua in the program. we give a method to find a spanning set of duas using the relation of subsumption between duas. intuitively, there exists a natural ordering between the duas in a program: some duas are covered more easily than others, since coverage of the former is automatically guaranteed whenever the latter are covered. those duas that are the most difficult to be covered according to this ordering are called _unconstrained._ a spanning set of duas is composed of unconstrained duas. our results are useful for reducing the cost of testing, since the generation of test paths can be targeted to cover the smaller spanning set of duas, rather than all those in a program. on the other hand, assuming that a different path is taken to cover each dua in a spanning set, the cardinality of spanning sets can be used to estimate the cost of testing. other interesting uses of spanning sets of duas are also discussed. martina marre antonia bertolino