waashk/acm huggingface dataset:
specification and implementation of resilient, atomic data types  a major issue in many applications is how to preserve the consistency of data in the presence of concurrency and hardware failures. we suggest addressing this problem by implementing applications in terms of abstract data types with two properties: their objects are atomic (they provide serializability and recoverability for activities using them) and resilient (they survive hardware failures with acceptably high probability). we define what it means for abstract data types to be atomic and resilient. we also discuss issues that arise in implementing such types, and describe a particular linguistic mechanism provided in the argus programming language.  william weihl barbara liskov
data flow analysis for `intractable' system software  we describe, and give experience with, a new method of intraprocedural data flow analysis on reducible flow-graphs[9]. the method is advantageous in imbedded applications where the added value of improved performance justifies substantial optimization effort, but extremely powerful data flow analysis is required due to the code profile.  the method is unusual in that (1) various kinds of forward data flow analysis are done simultaneously, so that benefit is derived from informative interactions (e.g. between constant propagation[7] and alias analysis[8]) and (2) we abandon insistence on reaching a least fixed point, allowing us to handle extremely broad classes of information (e.g., inequality of array indices, which implies non-aliasing in array references).  we argue that the gain from using a very rich framework more than offsets the loss due to non-minimal fixed points, and justify this with a 'thought experiment' and practical results.  harold johnson
a middleware overview: goals, research issues, and coded examples (abstract)  in this tutorial, i will focus on the roles, types, and issues of middleware. i will give a short overview of the software problems that middleware addresses and (mostly) solves. i will do a survey of the different kinds of middleware and their applicability to diverse problem domains. i will spend somewhat longer discussing, with examples, corba, rmi, and jini, in particular pointing out relative strengths and weaknesses. finally, i will discuss some of the major and outstanding research issues, especially those that a podc audience might find stimulating, and suggest where and how solutions might be found.  michael ogg
the application of javacc to develop a c/c++ preprocessor the commonly available software metrics-extraction tools for c/c++ depend on commercial preprocessors to preprocess the source file before being input into the analyzers. the following paper introduces a java compiler generator called javacc and the application of the generator to develop a java-based preprocessor for c/c++. some technical features to the development of preprocessor are also mentioned, such as (1) handling of rescanning in preprocessing with ll(k) parsers, (2) managing conditional compiling with the state-based features of the lexical analyzer in javacc, and (3) resolving macro replacement and expansion with parsers. giancarlo succi raymond w. wong
a new approach to debugging optimized code  debugging optimized code is a desirable capability not provided by most current debuggers. users are forced to debug the unoptimized code when a bug occurs in the optimized version. current research offers partial solutions for a small class of optimizations, but not a unified approach that handles a wide range of optimizations, such as the sophisticated optimizations performed by supercomputer compilers.  the trend with current research is to make the effects of optimization transparent, i.e., provide the same behavior as that of the unoptimized program. we contend that this approach is neither totally feasible nor entirely desirable. instead, we propose a new approach based on the premise that one should be able to debug the optimized code. this implies mapping the current state of execution back to the original source, tracking the location of variables, and mapping compiler-synthesized variables back to user-defined induction variables. to aid the user in understanding program behavior, various visual means are provided, e.g., different forms of highlighting and annotating of the source/assembly code. while this unavoidably requires the user to have a basic understanding of the optimizations performed, it permits the user to see what is actually happening, infer the optimizations performed, and detect bugs. an example illustrates the effectiveness of visual feedback.  to support conventional debugger functionality for optimized code, the compiler must generate additional information. current compiler-debugger interfaces (cdis) were neither designed to handle this new information nor are they extensible in a straight forward manner. therefore, a new cdi was designed that supports providing visual feedback and the debugging of optimized code. this paper specifies the details of a new cdi and relates each feature back to the debugger functionality it supports.  gary brooks gilbert j. hansen steve simmons
apl-generated teaching and testing items to enhance a student's ability to discover functional relationships ideas and designs for programs to generate teaching examples are introduced. some of these ideas are tested and demonstrated by a prototype _apl_ program. descriptions of the internal structure and requirements of the example generators are presented. the examples produced by the program are designed to motivate students to discover rules or relationships capable of mapping the in-domain inputs to correct outputs. experimental examples used for demonstrating typical concepts and mathematical processes include the functions , , x, +, ÷, | and with their intrinsic _apl_ definitions. initially, the types of arguments for these examples will be kept simple at first to promote learning such mathematical functions by permitting only single scalar arguments. later, for discovery learning, the functions may be selected to permit or require arguments that are vector or array objects. an important component in the design of this system is parameter specification. parameters determine the number of examples and their perspicuity. a student using the system may request additional examples that are easy to comprehend before the function is discovered from the program generated examples provided. the example-generating program also facilitates checking that establishes that a student's response is operationally equivalent to a correct one. alvin j. surkan
the polylith software bus  we describe a system called polylith that helps programmers prepare and interconnect mixed-language software components for execution in heterogeneous environments. polylith's principal benefit is that programmers are free to implement functional requirements separately from their treatment of interfacing requirements; this means that once an application has been developed for use in one execution environment (such as a distributed network) it can be adapted for reuse in other environments (such as a shared-memory multiprocessor) by automatic techniques. this flexibility is provided without loss of performance. we accomplish this by creating a new run-time organization for software. an abstract decoupling agent, called the software bus, is introduced between the system components. heterogeneity in language and architecture is accommodated since program units are prepared to interface directly to the bus and not to other program units. programmers specify application structure in terms of a module interconnection language (mil); polylith uses this specification to guide packaging (static interfacing activities such as stub generation, source program adaptation, compilation, and linking). at run time, an implementation of the bus abstraction may assist in message delivery, name service, or system reconfiguration.  james m. purtilo
t: a dialect of lisp or lambda: the ultimate software tool  the t project is an experiment in language design and implementation. its purpose is to test the thesis developed by steele and sussman in their series of papers about the scheme language: that scheme may be used as the basis for a practical programming language of exceptional expressive power; and, that implementations of scheme could perform better than other lisp systems, and competitively with implementations of programming languages, such as c and bliss, which are usually considered to be inherently more efficient than lisp on conventional machine architectures. we are developing a portable implementation of t, currently targeted for the vax under the unix and vms operating systems and for the apollo, a mc68000-based workstation.  jonathan a. rees norman i. adams iv
data and activities: exploiting hierarchies of classes  we wish to briefly discuss recent work in conceptual modelling from a slightly different point of view in order to highlight the parallels between data and transactions, and then mention some benefits of this view.  a time-honoured way of describing a system (portion of the world) is by positing a domain of objects and then inter-relating them through function and predicate symbols. the resulting description is a set of axioms in a fopc. if the world is dynamic, one usually augments the description with the notion of time or state, in which case axioms can be divided naturally into "general laws" (heretofore constraints) holding in all states, and state-specific "facts". given states, one then also has the ability to describe state transitions (events) as predicates on pairs of states or, as shown below, as objects in their own right.  alexander t. borgida sol greenspan
the design of a language-directed editor for block-structured languages  a language-directed editor combines the text manipulation functions of a general-purpose editor with the syntax-checking functions of a compiler. it allows a user to create and modify a program in terms of its syntactic structure. the design of a user interface and an implementation for one such editor is described in language-independent terms. the design rationale is given. the implementation is outlined in terms of its major data structures.  joseph m. morris mayer d. schwartz
fabrik: a visual programming environment  fabrik is a visual programming environment - a kit of computational and user- interface components that can be "wired" together to build new components and useful applications. fabrik diagrams utilize bidirectional dataflow connections as a shorthand for multiple paths of flow. built on object- oriented foundations. fabrik components can compute arbitrary objects as outputs. music and animation can be programmed in this way and the user interface can even be extended by generating graphical structures that depend on other data. an interactive type system guards against meaningless connections. as with simple dataflow, each fabrik component can be compiled into an object with access methods corresponding to each of the possible paths of data propagation.  dan ingalls scott wallace yu-ying chow frank ludolph ken doyle
an automatic object inlining optimization and its evaluation  automatic object inlining [19, 20] transforms heapdata structures by fusing parent and child objects together. it canimprove runtime by reducing object allocation and pointer dereferencecosts. we report continuing work studying object inlining optimizations. in particular, we present a new semantic derivation of the correctness conditions for object inlining, and program analysis which extends our previous work. and we present an object inlining transformation, focusing on a new algorithm which optimizes class field layout to minimize code expansion. finally, we detail a fuller evaluation on eleven programs and libraries (including xpdf, the 25,000 line portable document format (pdf) file browser) that utilizes hardware measures of impact on the memory system.  we show that our analysis scales effectively to large programs,finding many inlinable fields (45 in xpdf) at acceptable cost, and weshow that, on some programs, it finds nearly all fields for which object inlining is correct, and averages 40% of such fields across our benchmarks. we implement our analyses in an advanced analysis infrastructure, and we show that, compared to traditional 1-cfa, that infrastructure provides better results and lower and more scalable cost. across all programs, analysis identified about 30% of objects as inlinable on average. our transformation increases code size by only 20% while inlining this 30% of fields. inlining these objects eliminated on average 28% of field reads, 58% of object creations, 12% of all loads. further, the optimized programs have significantly improved memory reference behavior, producing 25% fewer l1 data cache misses and 25% fewer read stalls. on average the runtime improved by 14%.  julian dolby andrew chien
new syntax for if- and case statements  we like to propose slightly different syntax for if- and case statements in english-like programming languages such as pascal, which is based on the following two principles: (i) programmers should be able to align coordinative expressions or statements, and (ii) syntax is correct according to the english grammar, if possible. the first principle is one of the most important points in program-writing because if coordinative expressions or statements are aligned then programmers can understand the structure of a program more easily and hence will make less mistakes. we will point out that in the case of a nested if-statement it is not possible to do so. the second principle is self- explanatory. unusual abbreviations and grammatically incorrect syntax may be justified only if they improve program-writing significantly; otherwise, we should not adapt them. a case-statement is such an example. moreover, even though it is a special case of more general if-statement, its syntax has no resemblance to that of the general case. our syntax for a case-statement is a straight abbreviation of a grammatically correct if-statement and not so restrictive as pascal-type case- statements.  masao kishore
caching in the sprite network file system  the sprite network operating system uses large main-memory disk block caches to achieve high performance in its file system. it provides non-write-through file caching on both client and server machines. a simple cache consistency mechanism permits files to be shared by multiple clients without danger of stale data. in order to allow the file cache to occupy as much memory as possible, the file system of each machine negotiates with the virtual memory system over physical memory usage and changes the size of the file cache dynamically. benchmark programs indicate that client caches allow diskless sprite workstations to perform within o-12 percent of workstations with disks. in addition, client caching reduces server loading by 50 percent and network traffic by 90 percent.  michael n. nelson brent b. welch john k. ousterhout
summary of software designer's associates project  a software designer's associates (sda) is, 1) a workstation-based, coherent, upgradable collection of tools, 2) capable of supporting the description, evaluation and comparison of software system architectural designs, and 3) molded to a specific user's habits, the tasks a designer is performing and the method a designer is using. each sda is a specific instance of a generic facility which supports a team member's design activities, cooperation among team members, and overall team management. it provides a framework for the integration of tools supporting the use of various notations within the context of a particular set of technical and managerial methods.  the sda project is a joint effort involving a consortium of researchers from academic and industrial organizations in both japan and the united states. currently, 19 organizations are participating the project. for past two years, the project is focused on the following major themes:  requirements definition for sdas,  models for integrating software environments,  alternative architectures for generic and specific sdas,  object, process and adaptation server concept definitions,  environment infrastructure, and  special tools.  prototyping is being performed in the following areas:  support for the use of formalisms (algebraic, attribute grammar),  demonstration of the ability to use relational/object-oriented technology, and  demonstration of the ability to provide a skeletal sda and generators to create specific sda's.  additional efforts are related to software process description. the approach to process description includes:  a non-procedural technique for general activity sequence modeling  extensions to existing formalism such as imperative, procedural language, algebraic specification languages, rule-based languages, attribute grammar based languages, and petri nets and state transition diagrams.  descrition of well-known methodologies have been written using some of the above approaches. also, an attempt has been made to describe design processes for actual software projects among participating organizations.  the process server is one of the key components for an sda. it is a logical component which supports conformance to the policies defined by the software process which is supported by the environment. it is knowledgeable about the process's artifacts, operations, constraints and criteria. it should also assist in recording, monitoring, guiding and enacting process related activities.  masatoshi matsuo
&amp;square; user: the user-definable system function in data general's aos/vs apl  this paper describes the implementation of an apl interface to user-provided subroutines written in a language other than apl. the user's subroutines are incorporated directly into the apl interpreter, yet the interface is implemented in a way which prevents such problems as unintentional corruption of the apl workspace. examples illustrate the use in apl. via the interface, of data general's gks (graphical kernel system) subroutine package, a flexible, powerful, standard-compliant library of graphics subroutines for compiled languages.  jan-willem neurdenburg phil s. schwarz
an asymmetric stream communication system  input and output are often viewed as complementary operations, and it is certainly true that the direction of data flow during input is the reverse of that during output. however, in a conventional operating system, the direction of control flow is the same for both input and output: the program plays the active role, while the operating system transput primitives are always passive. thus there are four primitive transput operations, not two: the corresponding pairs are passive input and active output, and active input and passive output. this paper explores the implications of this idea in the context of an object oriented operating system.  this work is supported in part by the national science foundation under grant no. mcs-8004111. computing equipment and technical support are provided in part under a cooperative research agreement with digital equipment corporation.  andrew p. black
an algebraic approach to file synchronization a _file synchronizer_ restores consistency after multiple replicas of a filesystem have been changed independently. we present an algebra for reasoning about operations on filesystems and show that it is sound and complete with respect to a simple model. the algebra enables us to specify a file-synchronization algorithm that can be combined with several different conflict-resolution policies. by contrast, previous work builds the conflict- resolution policy into the specification, or worse, does not specify the synchronizer's behavior precisely. we classify synchronizers by asking whether conflicts can be resolved at a single disconnected replica and whether all replicas are identical after synchronization. we also discuss timestamps and argue that there is no good way to propagate timestamps when there is severe clock skew between replicas. norman ramsey el
a hierarchical structuring method for functional software systems  a hierarchical structuring method for functional software systems is described. this method is greatly influenced by the authors experiences in developing the experimental hierarchical software processor (hisp) during the last four years. in this paper, however, the method is described in a general setting. this method appears to be applicable to a broad class of functional software systems.  we first describe the words "functional" and "hierarchical". then the hierarchical structuring method is presented. some applications of this method are also discussed. in particular, an example of transformational programming based on this structuring method is presented. the truncated syntax diagrams of the hisp language are also given as an appendix.  kokichi futatsugi koji okada
type extension through polymorphism  a record data type can be extended by addition of more fields. the extended type is a subtype of the original, in that any value of the extended type can be regarded as a value of the original type by ignoring the additional fields. this results in a type hierarchy.  milner [3] has proposed a polymorphic type system. with the milner approach, the type of a function may contain type variables. this also results in a type hierarchy.  in a language with a polymorphic type system, if it is anticipated that a record type will need to be extended, then the record type can be defined to have a dummy extension field. in the parent type, the extension field will have null contents of type void. the type of the extension field can differ with different subtypes.  the approach can be extended to allow a type to be subtype of two or more parent types.  to a limited extent, this approach can be used in ada and other languages with generic program units.  f. warren burton
ada-linda: a powerful paradigm for programming distributed ada applications  in spite of recent advances in hardware and computer technology, we still face a daunting task when programming parallel or distributed systems. the difficulties are linked to the expression and control of concurrent activities and to their communication and synchronization. in this context, our approach is to introduce software engineering features in a domain where these notions are not widely used. we have in mind a set of reusable software components which address various issues related to distributed system programming: control, communication and paradigms. in this paper, we present the linda model which offers an interesting paradigm for the distribution of ada applications.  yvon kermarrec laurent pautet
separate compilation in chipsy  this paper describes a practical implementation scheme for separate compilation of strongly typed high-level languages. the scheme provides full inter-module type checking, while limiting the problems of "big inhale" and most redundant recompilations by employing smart recompilation at reasonable cost. it also provides type-safe link-time substitution of module variants.  the scheme has been implemented for chill1 in chipsy®, and has been in use since 1983. the current host is vax/vms. targets include vax, intel 8086 and 80286, both stand-alone and under ms-dos. a sun-386i and vax/ultrix hosted version is under development. chipsy is marketed by kvatro a/s of trondheim, norway.  h. eidnes d. o. hallsteinsen d. h. wanvik