waashk/acm huggingface dataset:
soft documentation - challenges and techniques for handling mixed-media documents (panel)  a pragmatic forum where practitioner panelists deliver short papers concerning the impact of the "distributed interactive environment" on the integration of disparate documentation (by different authors, on different media, in different locations) into a coherent document for transferring information to meet a given, yet variable, need-to-know of the reader/viewer(s).  interactive design, development, and programming provide the opportunities for both technical and end-user personnel to create on-line documentation. the panelists will address new challenges and techniques involved in providing cohesive communication within the areas of: -terminology, writing/editing styles, management, quality control, access, retrieval, publication, distribution, update, and audit controls.  interactive audience participation in an open discussion is encouraged.  frank melanson
scheduler-conscious synchronization  efficient synchronization is important for achieving good performance in parallel programs, especially on large-scale multiprocessors. most synchronization algorithms have been designed to run on a dedicated machine, with one application process per processor, and can suffer serious performance degradation in the presence of multiprogramming. problems arise when running processes block or, worse, busy- wait for action on the part of a process that the scheduler has chosen not to run. we show that these problems are particularly severe for scalable synchronization algorithms based on distributed data structures. we then describe and evaluate a set of algorithms that perform well in the presence of multiprogramming while maintaining good performance on dedicated machines. we consider both large and small machines, with a particular focus on scalability, and examine mutual-exclusion locks, reader-writer locks, and barriers. our algorithms vary in the degree of support required from the kernel scheduler. we find that while it is possible to avoid pathological performance problems using previously proposed kernel mechanisms, a modest additional widening of the kernel/user interface can make scheduler-conscious synchronization algorithms significantly simpler and faster, with performance on dedicated machines comparable to that of scheduler-oblivious algorithms.  leonidas i. kontothanassis robert w. wisniewski michael l. scott
a notation for problematic architecture interactions the progression of component-based software engineering (cbse) is essential to the rapid, cost- effective development of complex software systems. given the choice of well- tested components, cbse affords reusability and increases reliability. however, applications developed according to this practice can often suffer from difficult maintenance and control, problems that stem from improper or inadequate integrate solutions. avoiding such unfortunate results requires knowledge of what causes the interoperability problems in the first place. the time for this assessment is during application design. in this paper, we define _problematic architecture interactions_ using a simple notation with extendable properties. furthermore, we delineate a multi-phase process for pre-integration analysis that relies on this notation. through this effort, potential problematic architecture interactions can be illuminated and used to form the initial requirements of an integration architecture. l. davis r. gamble j. payton g. jonsdottir d. underwood
apl syntax and semantics  this paper presents a working model of apl syntax and semantics that incorporates explicit representations of functions, operators, and syntax, thus providing a basis for the clear and explicit statement of extended facilities in the language, as well as a tool for experimentation upon them. use of the model is illustrated in the treatment of the syntax of operators, and in the discussion of a number of new or recently- proposed facilities including indirect assignment, the operators axis, derivative, inverse, and til, and the functions link, and from. the entire model is included in an appendix.  kenneth e. iverson
measurement of processor occupancy in a cyclic non-preemptive real-time control system  an algorithm which is used to measure occupancy in stromberg-carlson's digital central office (dco) call processors is presented. the method is self- calibrating, making it independent of differences in processor speed, type, and other variables which affect processor performance. required is an external event generator which can generate an event to the processor at fixed time intervals. calibration needs one time interval with no events to occur before valid occupancy measurements may be made. no clock internal to the processor is required. the method is highly accurate even at high occupancies and incurs very little processor overhead to perform its measurements. processor occupancy can be displayed at the end of any user- specified time period.  richard w. moulton
minimizing system modification in an incremental design approach  _in this paper we present an approach to mapping and scheduling of distributed embedded systems for hard real-time applications, aiming at minimizing system modification cost. we consider an incremental design process that starts from an already existing system running a set of applications. we are interested to implement new functionality so that the already running applications are disturbed as little as possible and there is a good chance that, later, new functionality can easily be added to the resulted system. the mapping and scheduling problem are considered in the context of a realistic communication model based on a tdma protocol._  paul pop petru eles traian pop zebo peng
operators for program control  structured programming constructs such as if-then-else and do-while have traditionally been used to give a natural flow to programs written in one of the algol-like languages. languages with a functional basis, such as apl and lisp, provide (and are characterized by) alternative means of controlling the flow of expression. these include function modularity, the application of functions across data structures, the use of data structures to control program flow, and the mapping of operations across data and across other operations.  in apl2, the use of these methods has been enhanced by the generalization of apl data structures, the addition of the primitive operator each(″), and the ability to define operators. this paper will examine ways in which these features may be used to give a non-procedural look to apl2 functions.  edward v. eusebi
object oriented operating systems: an emerging design methodology  object oriented design of operating systems has evolved from pure protection considerations to a more general methodology of design as exemplified in intel's iapx-432 machine. this paper compares and contrasts, from an architectural point of view, eight major object oriented operating systems. five different architectural aspects have been chosen as a basis for this analysis. these aspects include: uniformity of the object approach, object type extensibility, the process concept, the domain concept, and object implementation techniques.  ariel pashtan
design and code reuse based on fuzzy classification of components a bottleneck in software reuse is the classification schema and retrieval method of components. particularly when large repositories of components are available, classification and retrieval for reuse should be flexible to allow the selection also of components which, although not perfectly matching requirements, are adaptable with a limited effort. this paper presents a fuzzy classification model for a repository storing descriptors of components. these descriptors include fuzzy-weighted keyword pairs describing components functionalities extracted from code and its design documentation. a mechanism for semi-automatic extraction of keywords, and for automatic assignement of fuzzy weights to keyword pairs based on text retrieval algorithms is provided. e. damiani m. g. fugini
25 years of quantum cryptography the fates of _sigact news_ and quantum cryptography are inseparably entangled. the exact date of stephen wiesner's invention of "conjugate coding" is unknown but it cannot be far from april 1969, when the premier issue of _sigact news_\\---or rather _sicact news_ as it was known at the time---came out. much later, it was in _sigact news_ that wiesner's paper finally appeared [74] in the wake of the first author's early collaboration with charles h. bennett [7]. it was also in _sigact news_ that the original experimental demonstration for quantum key distribution was announced for the first time [6] and that a thorough bibliography was published [19]. finally, it was in _sigact news_ that doug wiedemann chose to publish his discovery when he reinvented quantum key distribution in 1987, unaware of all previous work but wiesner's [73, 5].most of the first decade of the history of quantum cryptography consisted of this lone unpublished paper by wiesner. fortunately, bennett was among the few initiates who knew of wiesner's ideas directly from the horse's mouth. his meeting with the first author of this column in 1979 was the beginning of a most fruitful lifelong collaboration. it took us five more years to invent quantum key distribution [4], which is still today the best-known application of quantum mechanics to cryptography. the second author joined in slightly later, followed by a few others. but until the early 1990's, no more than a handful of people were involved in quantum cryptographic research. since then, the field has taken off with a vengeance, starting with artur k. ekert's proposal to use quantum nonlocality for cryptographic purposes [33].the golden age started in earnest when ekert organized the first international workshop on quantum cryptography in broadway, england, in 1993. since then, many conferences have been devoted at least partly to quantum cryptography, which has become a major international topic. the purpose of the aforementioned 1993 bibliography in _sigact news_ was to cite as much as possible _all_ papers ever written on the subject, including unpublished manuscripts: there were 57 entries in total. today, such an undertaking would be nearly impossible owing to the explosion of new research in the field.the purpose of this column is to give an overview of the current research in quantum cryptography. it is not our intention to be exhaustive and we apologize in advance to any researcher whose work we may have omitted. note that we do not necessarily agree with the claims in every paper mentioned here: this column should not be construed as a seal of approval! gilles brassard claude crepeau
an efficient approach to data flow analysis in a multiple pass global optimizer  data flow analysis is a time-consuming part of the optimization process. as transformations are made in a multiple pass global optimizer, the data flow information must be updated to reflect these changes. various approaches have been used, including complete recalculation as well as partial recalculation over the affected area. the approach presented here has been designed for maximum efficiency. data flow information is completely calculated only once, using an interval analysis method which is slightly faster than a purely iterative approach, and which allows partial recomputation when appropriate. a minimal set of data flow information is computed, keeping the computation and update cost low. following each set of transformations, the data flow information is updated based on knowledge of the effect of each change. this approach saves considerable time over complete recalculation, and proper ordering of the various optimizations minimizes the amount of update required.  s. jain c. thompson
an applicative compiler for a parallel machine  a compiler for the applicative language hope is described. the compiler is itself written in hope and generates a machine independent compiler target language, suitable for execution on the parallel reduction machine alice. the advantages of writing a compiler in a very high level applicative language are discussed, and the use of program transformation and other techniques to turn the initial 'runnable specification' into a more efficient (if less clear) program are outlined. extensions to the hope language and the compiler which can exploit the parallelism and various execution modes of alice are described.  ian w. moor
a software development environment for law-governed systems  this paper describes a software development environment based on a new approach for managing large-scale evolving systems. under this approach, the conventional notion of a system is augmented with a new component called the law of the system, which is an explicit and strictly enforced set of rules about the operation of the system, about its evolution, and about the evolution of the law itself. the resulting combination is called a law- governed system.  naftaly h. minsky david rozenshtein
safely creating correct subclasses without seeing superclass code  a major problem for object-oriented frameworks and class libraries is how to provide enough information about an extensible superclass so that programmers can safely create new subclasses without studying superclass code. the goal of my work is to determine what information is needed so library providers do not have to give away the code of library superclasses. a closely related goal is to provide guidelines that simplify reasoning about classes that inherit from such frameworks and class libraries. the long-term goal of my research is to develop tool support to automatically generate some of the necessary documentation and to assist programmers in reasoning about how to create correct subclasses.  clyde d. ruby
concurrent replicating garbage collection  we have implemented a concurrent copying garbage collector that uses replicating garbage collection. in our design, the client can continuously access the heap during garbage collection. no low-level synchronization between the client and the garbage collector is required on individual object operations. the garbage collector replicates live heap objects and periodically synchronizes with the client to obtain the client's current root set and mutation log. an experimental implementation using the standard ml of new jersey system on a shared-memory multiprocessor demonstrates excellent pause time performance and moderate execution time speedups.  james o'toole scott nettles
analysis of timing hazards in ada programs  safety-critical ada programs often contain asynchronous tasks and are, therefore, prone to timing hazards. neither rigorous testing nor rigorous formal verification is currently feasible for timing hazard detection. we propose an inexpensive static analysis that can assist in the identification of timing hazards. only a few ada constructs can generate results that depend on the asynchronous timing of tasks within a program. using the techniques of data dependency analysis, these timing dependencies can be traced through the program. if an output is timing dependent, manual inspection is required to determine whether the timing dependency is deliberate or is an unintended timing hazard.  louise e. moser p. m. melliar-smith
relational programs the objective of this research is to produce useful, low- cost methods for developing correct concurrent programs from formal specifications. in particular, we address the design and verification of the synchronization and communication portions of such programs. often, this portion can be implemented using a fixed, finite amount of synchronization related data, i.e., it is "finite-state." nevertheless, even when each program component contains only one bit of synchronization related data, the number of possible global synchronization states for _k_ components is about 2_k_, in general. because of this "state-explosion" phenomenon, the manual verification of large concurrent programs typically requires lengthy, and therefore error- prone, proofs. using a theorem prover increases reliability, but requires extensive formal labor to axiomatize and solve verification problems. automatic verification methods (such as reachability analysis and temporal logic model checking) use state- space exploration to decide if a program satisfies its specification, and are therefore also subject to state- explosion. to date, proposed techniques for ameliorating state-explosion either require significant manual labor, or work well only when the program is highly symmetric and regular (e.g., many functionally similar components connected in similar ways).to overcome these drawbacks, we advocate the _synthesis of programs from specifications._ this approach performs the refinement from specifications to programs automatically. thus, the amount of formal labor is reduced to writing a formal specification and applying the appropriate synthesis step at each stage of the derivation. while nontrivial, writing a formal specification is necessary in any methodology that guarantees correctness. farokh b. bastani
integration of complexity metrics with the use of decision trees we would like to present the use of the decision tree approach in the integration of various complexity metrics on the example of distinguishing between random and ordinary programs. following our proposition that randomness indicates meaningless we can state that with the approach we are able to measure the "meaning" of computer programs. the main contributions stated in the paper is that the new way of metrics integration enabling one to combine metrics with various measurement units. peter kokol janez brest milan zorman vili podgorelec
comparing data synchronization in ada 9x and orca protected object types are one of three major extensions to ada 83 proposed by ada 9x. this language feature is intended for light-weight data synchronization between tasks. the orca parallel programming language has a very similar construct, the shared data-object, with which we have over five years of experience, both in usage and implementation. this paper compares protected objects and shared data- objects, with regard to design, usage, and implementation. henri e. bal
dominators, super blocks, and program coverage  in this paper we present techniques to find subsets of nodes of a flowgraph that satisfy the following property: a test set that exercises all nodes in a subset exercises all nodes in the flowgraph. analogous techniques to find subsets of edges are also proposed. these techniques may be used to significantly reduce the cost of coverage testing of programs. a notion of a super block consisting of one or more basic blocks in that super block must be exercised by the same input. dominator relationships among super blocks are used to identify a subset of the super blocks whose coverage implies that of all super blocks and, in turn, that of all basic blocks. experiments with eight systems in the range of 1-75k lines of code show that, on the average, test cases targeted to cover just 29% of the basic blocks and 32% of the branches ensure 100% block and branch coverage, respectively.  hiralal agrawal
a concurrent copying garbage collector for languages that distinguish (im)mutable data  this paper describes the design and implementation of a concurrent compacting garbage collector for languages that distinguish mutable data from immutable data (e.g., ml) as well for languages that manipulate only immutable data (e.g., pure functional languages such as haskell). the collector runs on shared-memory parallel computers and requires minimal mutator/collector synchronization. no special hardware or operating system support is required.  our concurrent collector derives from sequential semi-space copying collectors. the collector requires that a heap object includes forwarding pointer in addition to its data fields. an access to an immutable object can be satisfied either by the original or the forwarded copy of the object. a mutable object is always accessed through the forwarded copy, if one exists.  measurements of this collector in a standard ml compiler on a shared-memory computer indicate that it eliminates perceptible garbage-collection pauses by reclaiming storage in parallel with the computation proper. all observed pause times are less than 20 milliseconds. we describe extensions for the concurrent collection of multiple mutator threads and refinements to our design that can improve its efficiency.  lorenz huelsbergen james r. larus
functions and data can dance as equal partners it is difficult today to think of machines of the early fifties. a vaguely recollected machine, which probably combines features of more than one real machine, had as memory a rotating drum. the instruction format included an operation code and four addresses. the first three addresses were not unusual: the locations of two operands and the result of the operation. the fourth address was the location of the next instruction. a programmer had to pick a spot on the drum that will be under the read head when the instruction finishes. it required a bit of ingenuity and lots of experimentation to get the most out machines from that era. the job was not made any easier by the fact the machines typically had about a thousand words of storage.it was not long before assemblers and compilers took over the job of managing machine operations. programs were divided into two major sections: procedures and data. the small storage capacity raised a problem: to store all numbers with the same number of bits required a choice. if the word size was small, precision was limited; if large, relatively few numbers could be stored. a compromise was reached by storing numbers in several different formats that used more storage when greater precision was required. data-types had arrived.it was to be a several years before the term _polymorphism_ was applied in the computer field. an early use of the word is cited in the oed: "the various portraits of her majesty astonish by their perplexing polymorphism…" [**1839** _fraser's_ mag. xx. 699].compilers in the fifties required a set of declarations that preceded the executable code. the names of variables were classified into groups that specified the storage formats of their respective members. different instruction sequences were needed to perform arithmetic on differently formatted numbers.nonnumeric data was a category by itself. before long nonnumeric subcategories, i. e., data-types, were recognized. some of them formed nested sequences, just as the early numeric types --- bits, small integers, large integers, and floating point --- formed a natural sequence. the domain of a function was the set of data-types on which it could operate.a typical oops requires declaration of the data-types and functions that apply to them in a different way. instead of considering functions and the data- types that they can accept, it considers data-types and the sets of functions that can use them. as in the case of fortran, declarations must be complete before programming begins. the sets of functions could be thought of as _function-types,_ although the term has been little used, if at all.no matter just how the information on data and function types were stored in the early computer and compiler days, and no matter whether they were stored with the cpu or on disk or drum, not many thought then about arrays of functions. the michigan algorithm decoder (mad), a compiler of the late fifties, is the only place i know of which supported indexed function name variables. j. philip benkard