waashk/acm huggingface dataset:
from design to redesign  software engineering environments have to support design methodologies whose main activity is not the generation of new independent programs, but the maintenance, integration, modification and explanation of existing ones. especially for software systems in ill- structured problem domains where detailed specifications are not available (like artificial intelligence and human-computer communication), incremental, evolutionary redesign has to be efficiently supported.  to achieve this goal we have designed and constructed an object-oriented, knowledge-based user interface construction kit and a large number of associated tools and intelligent support systems to be able to exploit this kit effectively. answers to the "user interface design question" are given by providing appropriate building blocks that suggest the way user interfaces should be built. the object-oriented system architecture provides great flexibility, enhances the reusability of many building blocks, and supports redesign. because existing objects can be used either directly or with minor modifications, the designer can base a new user interface on standard and well-tested components.  g. fischer a. c. lemke c. rathke
batch vs. timesharing: closing the gap  this paper describes and analyzes the current state of ibm timesharing. the functionality of the timesharing system is described through the evolution of the remote job processing facility. the constraints to the replacement of batch by timesharing are discussed, acknowledging that these constraints are offset by the potential of timesharing to provide an enhanced computing environment via its man-machine interface. finally the actual implementations of common computing tasks are compared against the full potential inherent to timesharing.  bruce lakin
industrializing software production  software production is very complex, even if tool-aided, as tools are complex too. specialization is necessary to simplify the work. stating analogy between traditional industry and software production, and drawing lessons from observations of some actual experiences, we propose a systematical specialization approach, namely industrialized programming (ip).  ip is based on a two- dimension life cycle. every phase contains intelligence, formalization and checking. the formalization seems like "execution" in traditional industry. ip is composed of: 1-analysts for creative tasks in the intelligence step; 2-specialists for the formalization tasks, each of them is specialized in one part of formalization techniques for all analysts. when accurately managed, ip will allow anyone to work according to his own capacity, without negative human side-effects.  huang weiqiao
macro-by-example: deriving syntactic transformations from their specifications  this paper presents two new developments. first, it describes a "macro-by- example" specification language for syntactic abstractions in lisp and related languages. this specification language allows a more declarative specification of macros than conventional macro facilities do by giving a better treatment of iteration and mapping constructs. second, it gives a formal semantics for the language and a derivation of a compiler from the semantics. this derivation is a practical application of semantics- directed compiler development methodology.  e. e. kohlbecker m. wand
standard fixpoint iteration for java bytecode verification  java bytecode verification forms the basis for java-based internet security and needs a rigorous description. one important aspect of bytecode verification is to check if a java virtual machine (jvm) program is statically well-typed. so far, several formal specifications have been proposed to define what the static well-typedness means. this paper takes a step further and presents a chaotic fixpoint iteration, which represents a family of fixpoint computation strategies to compute a least type for each jvm program within a finite number of iteration steps. since a transfer function in the iteration is not monotone, we choose to follow the example of a nonstandard fixpoint theorem, which requires that all transfer functions are increasing, and monotone in case the bigger element is already a fixpoint. the resulting least type is the artificial top element if and only if he jvm program is not statically well- typed. the iteration is standard and close to sun's informal specification and most commercial bytecode verifiers.  zhenyu qian
decay-usage scheduling in multiprocessors  decay-usage scheduling is a priority-aging time-sharing scheduling policy capable of dealing with a workload of both interactive and batch jobs by decreasing the priority of a job when it acquires cpu time, and by increasing its priority when it does not use the (a) cpu. in this article we deal with a decay-usage scheduling policy in multiprocessors modeled after widely used systems. the priority of a job consists of a base priority and a time- dependent component based on processor usage. because t he priorities in our model are time dependent, a queuing- theoretic analysis---for instance, for the mean job response time---seems impossible. still, it turns out that as a consequence of the scheduling policy, the shares of the available cpu time obtained by jobs converge, and a deterministic analysis for these shares is feasible: we show how for a fixed set of jobs with large processing demands, the steady-state shares can be obtained given the base priorities, and conversely, how to set the base priorities given the required shares. in addition, we analyze the relation between the values of the scheduler parameters and the level of control it can exercise over the steady-state share ratios, and we deal with the rate of convergence. we validate the model by simulations and by measurements of actual systems.  d. h. j. epema
a distributed hypercube file system  for the hypercube, an autonomous physically interconnected file system is proposed. the resulting distributed file system consists of an i/o organization and a software interface. the system is loosely-coupled architecturally but from operating systems point of view a tightly-coupled system is formed in which interprocessor messages are handled differently from file accesses. a matrix multiplication algorithm is given to show how the distributed file system is utilized.  r. j. flynn h. hadimioglu
modeling software tools with icon  this paper describes a new software test automation tool, a powerful new programming language, and the software development process that resulted when these tools were combined. a small development team of software developers and potential customers devised the unconventional process to meet a short deadline. the process produced an operational prototype or model of the entire software system that customers were able to use during the time it was being developed.  the first model of the buster automated testing system was conceived, designed, and implemented ahead of schedule in less than six months, complete with many features and components. the buster system provides a test- information subsystem with facilities for multi-project test sharing, per- project test storage and planning, and test downloading for lab use. a separate test execution facility is also included that features test- result logging, a results database, and per-session i/o recording. the customer, at&amp;t; 3b4000 system test, reports that system soak tests that had taken three weeks now can be completed in one week, using buster.  the software modeling technique that was used to create the buster test system is a new idea that can be used to produce reliable low-cost software in many applications. unlike more conventional software engineering approaches, including rapid prototyping, the model can be used by customers as it is slowly evolved into a finished product. the model is used to embody and test designs and identify missing requirements before making large investments in production level code and documentation. in addition, software modeling makes it possible to develop comprehensive system test suites long before production level software is available. the process is composed of three major components: brainstorming and team building with customers, high-level language engineering, and automated software testing.  o. r. fonorow
efficient algorithms for bidirectional debugging  this paper discusses our research into algorithms for creating anefficient bidirectional debugger in which all traditional forward movement commands can be performed with equal ease in the reverse direction. we expect that adding these backwards movement capabilities to a debugger will greatly increase its efficacy as a programming tool.  the efficiency of our methods arises from our use of event countersthat are embedded into the program being debugged. these counters areused to precisely identify the desired target event on the fly as thetarget program executes. this is in contrast to traditional debuggers that may trap back to the debugger many times for some movements. for reverse movements we re-execute the program (possibly using two passes) to identify and stop at the desired earlier point. our counter based techniques are essential for these reverse movements because they allow us to efficiently execute through the millions of events encountered during re- execution.  two other important components of this debugger are its i/o logging and checkpointing. we log and later replay the results of system callsto ensure deterministic re-execution, and we use checkpointing to bound theamount of re- execution used for reverse movements. short movements generally appear instantaneous, and the time for longer movements is usually bounded within a small constant factor of the temporal distance moved back.  bob boothe
parsing and compiling using prolog  this paper presents the material needed for exposing the reader to the advantages of using prolog as a language for describing succinctly most of the algorithms needed in prototyping and implementing compilers or producing tools that facilitate this task. the available published material on the subject describes one particular approach in implementing compilers using prolog. it consists of coupling actions to recursive descent parsers to produce syntax- trees which are subsequently utilized in guiding the generation of assembly language code. although this remains a worthwhile approach, there is a host of possibilities for prolog usage in compiler construction. the primary aim of this paper is to demonstrate the use of prolog in parsing and compiling. a second, but equally important, goal of this paper is to show that prolog is a labor-saving tool in prototyping and implementing many non-numerical algorithms which arise in compiling, and whose description using prolog is not available in the literature. the paper discusses the use of unification and nondeterminism in compiler writing as well as means to bypass these (costly) features when they are deemed unnecessary. topics covered include bottom-up and top-down parsers, syntax-directed translation, grammar properties, parser generation, code generation, and optimizations. newly proposed features that are useful in compiler construction are also discussed. a knowledge of prolog is assumed.  jacques cohen timothy j. hickey
a conceptual programming environment  conceptual programming means having programmers work directly with their models of how their system is put together. it means providing them with the means for designing, coding and maintaining systems on a computer using the pictures and text they normally use on paper. an environment for conceptual programming requires flexibility to support a wide range of languages and graphics to support languages based on pictures. the garden system is a prototype conceptual programming environment that uses an object-oriented framework to meet these requirements.  s. p. reiss
a practical method of documenting and verifying ada programs with packages  we present a method of formal specification of ada programs containing packages. the method suggests concepts and guidelines useful for giving adequate informal documentation of packages by means of comments.  the method depends on (1) the standard inductive assertion technique for subprograms, (2) the use of history sequences in assertions specifying the declaration and use of packages, and (3) the addition of three categories of specifications to ada package declarations: (a) visible specifications, (b) boundary specifications, (c) internal specifications.  axioms and proof rules for the ada package constructs (declaration, instantiation, and function and procedure call) are given in terms of history sequences and package specifications. these enable us to construct formal proofs of the correctness of ada programs with packages. the axioms and proof rules are easy to implement in automated program checking systems. the use of history sequences in both informal documentation and formal specifications and proofs is illustrated by examples.  david c. luckham wolfgang polak
borrowed-virtual-time (bvt) scheduling: supporting latency-sensitive threads in a general-purpose scheduler systems need to run a larger and more diverse set of applications, from real-time to interactive to batch, on uniprocessor and multiprocessor platforms. however, most schedulers either do not address latency requirements or are specialized to complex real-time paradigms, limiting their applicability to general-purpose systems.in this paper, we present _borrowed-virtual-time (bvt) scheduling,_ showing that it provides low-latency for real-time and interactive applications yet weighted sharing of the cpu across applications according to system policy, even with thread failure at the real-time level, all with a low-overhead implementation on multiprocessors as well as uniprocessors. it makes minimal demands on application developers, and can be used with a reservation or admission control module for hard real-time applications. kenneth j. duda david r. cheriton
verifying security protocols with brutus  due to the rapid growth of the "internet" and the "world wide web" security has become a very important concern in the design and implementation of software systems. since security has become an important issue, the number of protocols in this domain has become very large. these protocols are very diverse in nature. if a software architect wants to deploy some of these protocols in a system, they have to be sure that the protocol has the right properties as dictated by the requirements of the system. in this article we present brutus, a tool for verifying properties of security protocols. this tool can be viewed as a special-purpose model checker for security protocols. we also present reduction techniques that make the tool efficient. experimental results are provided to demonstrate the efficiency of brutus.  e. m. clarke s. jha w. marrero
accelerating apl programs with sac the paper investigates, how sac, a purely functional language based on c syntax, relates to apl in terms of expressiveness and run-time behavior. to do so, three different excerpts of real world apl programs are examined. it is shown that after defining the required apl primitives in sac, the example programs can be re-written in sac with an almost one-to-one correspondence. run-time comparisons between interpreting apl programs and compiled sac programs show that speedups due to compilation vary between 2 and 500 for three representative benchmark programs. clemens grelck sven-bodo scholz
hybrid run-time power management technique for real-time embedded system with voltage scalable processor  this paper presents a new run-time power management technique for real-time embedded systems which consist of a voltage scalable processor and power controllable peripheral devices. we have observed that there exist significant trade-offs in terms of energy consumption between the dynamic power management (dpm) scheme and the dynamic voltage scaling (dvs) scheme over a wide range of system operating conditions. the proposed technique fully exploits workload- variation slack time by partitioning the task into several timeslots and shut down the unneeded peripheral device on timeslot-by-timeslot basis. through extensive simulations, the novelty and the usefulness of the proposed technique are demonstrated.  minyoung kim soonhoi ha
toward a non-atomic era: l-exclusion as a test case  most of the research in concurrency control has been based on the existence of strong synchronization primitives such as test and set. following lamport, recent research promoting the use of weaker primitives, "safe" rather than "atomic," has resulted in construction of atomic registers from safe ones, in the belief that they would be useful tools for process synchronization. we argue that the properties provided by atomic operations may be too powerful, masking core difficulties of problems and leading to inefficiency. we therefore advocate a different approach, to skip the intermediate step of achieving atomicity, and solve problems directly from safe registers. though it has been shown that "test and set" cannot be implemented from safe registers, we show how to achieve a fair solution to l-exclusion, a classical concurrency control problem previously solved assuming a very powerful form of atomic "test and set". we do so using safe registers alone and without introducing atomicity. the solution is based on the construction of a simple novel non-atomic synchronization primitive.  danny dolev eli gafni nir shavit
lambda, the ultimate label or a simple optimizing compiler for scheme  optimizing compilers for higher-order languages need not be terribly complex. the problems created by non-local, non-global variables can be eliminated by allocating all such variables in the heap. lambda lifting makes this practical by eliminating all non-local variables except for those that would have to be allocated in the heap anyway. the eliminated non-local variables become local variables that can be allocated in registers. since calls to known procedures are just gotos that pass arguments, lifted lambda expressions are just assembly language labels that have been augmented by a list of symbolic names for the registers that are live at that label.  william d. clinger lars thomas hansen
transparency and reflection in distributed systems the recursive composition of systems to form functionally equivalent transparently distributed systems is an important paradigm for constructing distributed systems. the extent to which such recursive transparency can be achieved depends crucially on the semantics and functionality offered by the underlying systems. it is therefore important that systems should be designed so that their functionality scales gracefully in a distributed environment.in order to build a transparent extension to a system, it is necessary to be able to intercept its basic operations and extend their meaning to a distributed environment. this requires the underlying system to have a clean structure with well-defined interfaces and the reflective capability necessary to intercept and extend operations crossing those interfaces. thus, both reflection and transparency are important aspects of the design of extensible distributed systems.it is possible to make transparent extensions to object-oriented systems built on top of micro-kernel architectures but the lack of reflective capabilities in the current generation of object-oriented programming languages can make this unnecessarily awkward. more research is required to develop languages whose computational model and implementation are a better match for the underlying platforms which support them. robert stroud
building a timeline editor from prefab parts: the architecture of an object- oriented application  this article describes interval, a software tool that allows authors to create dynamic timelines. it is one tool in intermedia, a framework developed at brown university's institute for research in information and scholarship (iris) that allows professors and students to create linked multimedia documents and encourages exploration, connectivity, and visualization of ideas. the system was written using an object-oriented extension to c, macapp, and a set of underlying building blocks, or functional groups of objects. this paper describes interval and discusses the architecture of the interval application, focusing on the design of the object-oriented architecture and on the use of appropriate building blocks. concluding sections evaluate object- oriented programming and outline future work.  l. nancy garrett karen e. smith
estimating the distribution of software complexity within a program  this paper proposes an approach to the characterization of complexity within computer software source texts. we estimate the information content of individual program tokens as the basis for a relative ordering of tokens by their 'uncertainty' or 'perculiarity' within the context of the program in which they reside. the analysis method used is in part an extension of software science methods. the information gained from the analysis highlights language usage anomalies and potential errors. this information may be useful in guiding software review activities.  more theoretical work and experimental validation will be necessary before the analysis technique may be used in a productive environment.  thomas g. moher
a practical approach to semantic configuration management  a configuration management (cm) tool is supposed to build a consistent software system following incremental changes to the system. the notion of consistency usually is purely syntactic, having to do with the sorts of properties analyzed by compilers. semantic consistency traditionally has been studied in the field of formal methods and has been considered an impractical goal for cm.  although the semantic cm problem is undecidable, it is possible to obtain a structural approximation of the semantic effects of a change in a finite number of steps. our approximation technique is formalized in logic and is based on information- theoretic properties of programs. the method in its present form applies to many but not all software systems, and it is programming-language independent. to the best of our knowledge, the semantic cm problem has not been formalized previously in nonsemantic terms, and we believe that our simplified formulation offers the potential for considerably more powerful debugging and configuration management tools.  m. moriconi
optimal testing policies for software systems  an important problem of practical concern is to determine how much testing should be done before a system is considered ready for release. this decision, of course, depends on the model for the software failure phenomenon and the criterion used for evaluating system readiness.  in this paper, we first develop a cost model based on the time dependent failure rate function of goel and okumoto. next, we derive policies that yeild the optimal values of the level of test effort (b*) and software release time (t*). the sensitivity of the optimal solution is also numerically evaluated.  amrit l. goel
the modular structure of complex systems  this paper discusses the organization of software that is inherently complex because there are very many arbitrary details that must be precisely right for the software to be correct. we show how the software design technique known as information hiding or abstraction can be supplemented by a hierarchically- structured document, which we call a module guide. the guide is intended to allow both designers and maintainers to identify easily the parts of the software that they must understand without reading irrelevant details about other parts of the software. the paper includes an extract from a software module guide to illustrate our proposals.  d. l. parnas p. c. clements d. m. weiss